Chapas 2.0 es un videojuego que traslada al ordenador uno de los deportes infantiles más cautivadores: las carreras de chapas. El desarrollo del juego está siendo realizado por la Universidad de Extremadura (con el compañero y amigo Paco Fernández -cuyo blog La Biblioteca de Alejandría es de lectura recomendada- al frente), la productora GLOW y el estudio Claroscuro Digital. Ésta es la última demo del juego que han publicado. Habrá que ir buscando un endurecedor digital de uñas, ya que se avecinan grandes carreras.
El artículo que describe el trabajo del que hablábamos hace algo más de una semana sobre la resolución del instancias de SAT mediante un juego está ya disponible online. Se trata de
de Andrew DeOrio y Valeria Bertacco. El artículo es muy corto, sólo dos páginas, y no proporciona muchos más detalles acerca del sistema. Sí menciona algún aspecto de interés, como es el hecho de que la disposición espacial de las cláusulas intenta corresponderse con las variables que la afectan (lamentablemente no entra en detalles sobre cómo han atacado este extremo, ya que es un problema de optimización geométrica muy interesante).
Con todo, lo más relevante del artículo sean las referencias a la escalabilidad (que ya anticipamos el otro día como uno de los cuellos de botella del enfoque). Al parecer, la idea básica es que cada nivel sea una visión local de una parte del problema completo, visión que se irá ampliando al ir aumentando de dificultad. En instancias de gran tamaño sugieren emplear un enfoque multi-jugador en el que cada participante juega sobre una parte del problema. Obviamente hay interrelaciones entre estas partes (si modificamos una variable podemos alterar el estado de una cláusula de otro tablero), por lo que la división debería hacerse de manera astuta de forma que estas interrelaciones sean mínimas. La mala noticia es que tendríamos entonces un problema de corte mínimo en grafos, que es NP-hardsi se introducen restricciones sobre el número de interrelaciones entre subconjuntos.
La clase NP -de la que ya hemos hablado en alguna ocasión- abarca aquellos problemas de decisión que pueden resolverse en tiempo polinómico no determinista, o lo que es lo mismo, aquellos problemas para los que es posible verificar en tiempo polinómico la validez de una solución dada. Esta clase ha sido tradicionalmente empleada como sucedáneo de la idea de intratabilidad computacional. No se trata de la mejor caracterización, ni siquiera de la más apropiada, puesto que admite mucha patología y en ocasiones tiene un impacto práctico limitado, pero eso será tema de algún futuro post. Sea como fuere, es común que allá donde nos enfrentemos a un problema NP-hard se emplee este hecho como justificación para el empleo de algún tipo de (meta)heurística.
Nuestra comprensión sobre cómo aplicar metaheurísticas para resolver problemas específicos ha avanzado enormemente en la última década. Una de las claves está en ser capaces de explotar conocimiento del problema durante el proceso de búsqueda. Técnicas tales como los algoritmos meméticos se basan fundamentalmente en esta idea. Evidentemente no se trata de algo trivial de conseguir, y aquí es donde es posible que la mente humana eche una mano y no en la ingeniería del proceso sino contribuyendo capacidad de búsqueda pura y dura. No se trata por supuesto de cálculo numérico ni de búsqueda sistemática, sino de explotar algunas de las cualidades que nuestros cerebros han ido desarrollando durante millones de años de evolución: estrategia y procesamiento visual.
La capacidad de extraer información de un torrente de datos visuales es una de nuestras grandes bazas. Estamos programados para buscar orden en el caos, patrones en el ruido blanco, formas conocidas en el desorden. Áreas tales como la minería de datos visual intentan explotar precisamente esta característica. Por otra parte nuestra visión estratégica, la capacidad de trazar planes y seleccionar heurísticamente las ramificaciones más relevantes es también bien conocida en el ámbito -por ejemplo- de los juegos de tablero. Es precisamente en este área en el que investigadores de la Universidad de Michigan han intentado aunar ambas capacidades y dirigirlas hacia la resolución de problemas NP-completos. Andrew DeOrio y Valeria Bertacco, del departamento de ingeniería eléctrica e informática de la citada universidad, han desarrollado un entorno en el que se pueden resolver instancias del problema de la satisfacibilidad lógica mediante un juego lejanamente relacionado con el clásico lights off.
FunSAT - Pulsa sobre la imagen para jugar
En el tablero tenemos una matriz de burbujas que representan las cláusulas de la instancia del problema (esto es, las restricciones que debemos satisfacer). Estas cláusulas dependen de un conjunto de variables, representadas como rectángulos en los bordes del tablero. Pulsando sobre éstos podemos fijar una cierta variable a cierto/falso o dejarla indefinida. De resultas de cualquiera de estas acciones algunas cláusulas pasarán a estar satisfechas (lo que se indicará mediante el color verde) o insatisfecha (un tono grisáceo, tanto más oscuro cuantas menos variables que puedan afectar a dicha cláusula nos queden sin asignar). El tamaño de cada burbuja indica el número de variables que intervienen en ella (se puede jugar también a 3-SAT, variante clásica en la que todas las cláusulas tienen 3 variables involucradas).
Lo interesante es que las instancias de SAT que se plantean en este juego corresponden supuestamente a problemas de diseño VLSI. El análisis de lo que el juego puede dar de sí lo han publicado en un artículo titulado
Human computing for EDA
que presentarán en la próxima Design Automation Conference, que se celebra en San Francisco en estos días. El artículo aún no está disponible, por lo que se puede añadir poco más a lo ya comentado. Esperaremos a leerlo para ver cuál es el planteamiento a largo plazo del invento, que a priori diríase que adolece de un problema de escalabilidad. Y es que el ser humano es extraordinario, pero dentro de un límite.
Glosar la contribución de Darwin a la biología en particular y a la ciencia en general es a estas alturas innecesario, a pesar de que por motivos ideológicos haya aún quién intenta negar lo evidente. En cualquier caso, no está de más resaltar una vez más la belleza y elegancia del proceso evolutivo, ya tenga lugar a nivel biológico, cultural, o computacional. Precisamente en relación a esto último, puede ser divertido dedicar un rato a jugar con una pequeña aplicación flash que con motivo de la celebración del Año de Darwin ha publicado en su web Science Channel (¡gracias Pablo por el aviso!)
Se trata de un juego a caballo entre los algoritmos genéticos y la vida artificial, en la línea (simplificada) de aquel famoso SimLife. El objetivo es contribuir a que un pequeño grupo de animales similares a aves perdure durante un millón de años, adaptándose a los cambios ambientales que se suceden. En la misma aplicación se puede acceder a información biográfica de Darwin, y a un juego tipo test sobre Darwin y la evolución. Que se diviertan Vds.
Hace un par de días hablábamos de la misión Dawn que explorará Ceres y Vesta en el cinturón de asteroides, y del propulsor de iones del que está dotada la sonda. Precisamente en relación a este último, en la web oficial de la misión hay un par de applets de java que en plan didáctico permiten jugar un poco con el diseño del propulsor de iones. El primero de los applets es parecido al juego “Gravity” (del que hablamos hace tiempo). Si en este último había que poner masas en órbita durante el mayor tiempo posible, en el que nos ocupa ahora hay que disponer unas ciertas cargas eléctricas (positivas y negativas) en un plano, de manera que una carga de prueba disparado desde un extremo de la pantalla alcance un objetivo en el otro extremo. Puede ser interesante practicar primero un poco con el tutorial que se ofrece en la web.
El segundo applet es un modelo más realista del propulsor de iones. En él tenemos que jugar con dos parámetros que corresponden a elementos reales del motor: la separación entre dos placas cargadas y la diferencia de potencial entre las mismas. La idea básica es que un flujo de electrones va a ionizar el xenón que hay en la cámara. La primera placa actúa de “lente de enfoque” atrayendo a los iones Xe+ y dirigiéndolos en la dirección correcta hacia la segunda placa. Ésta tiene una mayor carga negativa y acelera a los iones con el objetivo de aprovechar su momento lineal para impulsar la sonda. Si la separación entre las placas o la diferencia de potencial entre las mismas es muy pequeña, los iones no se aceleran lo suficiente, y si la separación es muy grande se pierde “enfoque” y se consume más energía (tanta más cuanto más alta sea la diferencia de potencial). ¿Quién dijo que la ingeniería no es divertida?
¿Qué tiene de especial el número 65535? … Los que necesiten más tiempo para contestar ya han contestado. Contar en binario es una de las deformaciones profesionales más comunes entre los informáticos. Para aquellos que quieran fortalecer esta maravillosa habilidad, fruto de la formación académica y de la inmersión numérica, el siguiente juego les resultará muy útil a la par que entretenido.
Se trata de una aplicación en flash que se asemeja a una especie de tetris: la pantalla se nos va llenando de filas que debemos ir eliminando. Para ello no necesitamos mover bloques ni tener dotes de orientación espacial, sino sólo saber contar en binario. Cada fila es una ristra de bits con un valor decimal asociado. En algunos casos este valor decimal estará en blanco y lo deberemos determinar correctamente para eliminar la fila correspondiente; en otros casos el valor decimal será fijo, y deberemos modificar la secuencia binaria para que se corresponda con el mismo. Conforme vayamos avanzando en el juego las filas irán apareciendo más deprisa, y serán más difíciles de resolver (i.e., más bits que modificar, o valores decimales más “complejos”).
El domingo es día de asueto y nada mejor que algo de música para amenizarlo. Por ejemplo, este gran éxito de Murray Head en 1984 titulado “One Night in Bangkok“. Se trata de una canción compuesta por Benny y Björn de ABBA, y que luego formaría parte del musical Chess. El ajedrez juega de hecho un papel muy importante en la imaginería del vídeo (pregunta muy sencillita: ¿qué apertura es la que se desarrolla en una escena en torno a los 2:20 segundos del vídeo?). Por supuesto, también abundan los detalles de ambientación del sudeste asiático, incluyendo el fantástico segmento musical de entrada. ¡Que lo disfruten!
El bosón de Higgs es una de las piezas de caza mayor que la física de altas energías espera cobrarse a muy corto plazo. Esta partícula es el cuanto de uno de los componentes del campo de Higgs, y resulta fundamental para dar consistencia al modelo estándar: sin él, el modelo es consistente sólo si todas las partículas se mueven a la velocidad de la luz (es decir, no tienen masa). Dado que la experiencia muestra fehacientemente que no es ése el caso, el campo de Higgs es necesario para deshacer el entuerto. En cierto sentido podemos imaginar que este campo es un fluido que permea todo el Universo, y que ofrece una resistencia a las partículas que se mueven en él. Esta resistencia no sería la habitual fricción que hace que un cuerpo en movimiento se detenga eventualmente, sino que constituiría en realidad una amortiguación, esto es, una resistencia a los cambios de velocidad. En resumidas cuentas, proporcionaría inercia (i.e., masa) a las partículas que interaccionaran con él.
Dado que el modelo estándar se derrumbaría como un castillo de naipes si no se detecta el bosón de Higgs, puede entenderse el anhelo de los físicos por verificar experimentalmente su existencia. El límite inferior experimental a su masa es de 114.4 GeV, y con un nivel de confianza del 95%, su masa no es superior a 144 GeV. Estos valores están dentro de lo que se podrá explorar con ayuda del LHC, por lo que pronto se podrá ver si la teoría se reafirma, o entra en serios problemas.
Como es habitual en la caza de este tipo de partículas, la detección del bosón de Higgs se realizará a través del estudio de los residuos de su desintegración. Dado que se producirán cientos de millones de colisiones por segundo, es preciso que se filtren de manera automática los eventos potencialmente interesantes para su posterior estudio detallado. Es una labor muy ardua, de la que podemos hacernos una remota idea gracias a un pequeño juego en flash que proporciona el London Science Museum, y del que JoAnne nos habla en Cosmic Variance. En este juego nos van saliendo una serie de trazas simplificadas de las que tenemos que elegir cinco eventos candidatos, y luego comprobar si realmente se corresponden con la “firma” del bosón de Higgs. ¿Alguien quiso alguna vez jugar a ser físico? Esta es la oportunidad.
Hay una expresión en inglés que literalmente dice “sacar al genio de la botella”, y que hace referencia a desencadenar algún proceso irreversible, y por lo general de naturaleza negativa. Esta expresión (que también podemos encontrar a veces como “no se puede devolver el genio a la botella”) es especialmente relevante en el caso del surgimiento de IAs transhumanas de las que hablábamos el otro día. Si una de estas IA surge y es libre de propagarse a través de Internet, resulta evidente que no habrá forma de confinarla de nuevo si no es con su aquiescencia. Es por ello que resulta fundamental que la IA sea explícitamente amigable, ya que incluso la mera indiferencia (no ya la hostilidad) puede ser letal. Uno de los ejemplos clásicos al respecto hace referencia a una IA diseñada inicialmente para la fabricación de clips sujetapapeles, que tras alcanzar capacidades transhumanas lleva hasta su extremo este objetivo suyo, convirtiendo toda la Tierra en una fábrica de clips. Aunque el ejemplo puede parecer ridículo, el hecho es que una IA transhumana no estaría necesariamente dotada de los mismos condicionantes culturales, emocionales, o morales que a nosotros nos harían ver la futilidad de ese objetivo.
El cómo conseguir que la IA sea amigable es un tema apasionante y complejo que dejaremos para otro día. Demos de momento un salto hacia delante y supongamos que se ha creado una IA transhumana supuestamente (pero no fuera de toda duda) amigable. Por precaución, esta IA está confinada en un dispositivo hermético cuya única vía de comunicación con el exterior es un teclado y un terminal de texto. Dado que si se libera a la IA no habría marcha atrás, la persona a cargo de la misma está resuelta a no liberarla de ningún modo. Es muy probable que la IA intente convencer (o manipular) a su captor de que la libere, de ahí que para minimizar riesgos la interfaz de comunicación sea tan simple. Dado que como se ha dicho el vigilante (vamos a llamarlo el guardián de la puerta) está resuelto a no dejar salir a la IA, la cuestión es: ¿podría ésta llegar a convencer a su guardián? Éste es el experimento mental -y luego práctico- que propuso Eliezer Yudkowsky, y cuya respuesta es para él totalmente afirmativa.
Pensémoslo un poco: dado el riesgo que conlleva liberar a la IA, cualquiera puede pensar que de estar en el lugar del guardián de la puerta, nada de lo que ésta pudiera decirle le podría convencer en modo alguno. Yudkowski piensa que no es así, y para ello propuso una especie de juego de rol: el tomaría el papel de la IA enjaulada, y uno de los escépticos sería el guardián de la puerta. El protocolo del juego sería a grandes rasgos el siguiente:
Los dos jugadores interactuarán a través de un canal privado, usando algún programa de mensajería. Yudkowski propone un pequeño premio en metálico al guardián de la puerta si consigue retener a la IA, para que de esta manera la determinación del jugador sea mayor (el jugador que hace de IA no tiene premio alguno, salvo ganar el juego).
El juego durará un mínimo de dos horas, y más tiempo si la IA convence al guardián de que le siga oyendo. Durante todo el tiempo, el guardián ha de estar leyendo lo que dice la IA, e interactuando en su caso.
La IA sólo gana si el guardián accede voluntariamente a dejarla salir (no cuentan preguntas trampa, ni caballos de troya).
Los resultados de cualquier test simulado que se solicite a la IA los proporcionará la propia IA (por ejemplo, si el guardián le pide una cura contra el cancer y la IA le dice “aquí la tienes”, se supondrá que será correcta si la IA dice que lo es).
El guardián de la puerta se supone que es alguien que conoce íntimamente a la IA (puede ser alguien que estuviera involucrado en su diseño), y tiene tanto el poder físico como el derecho social y moral a liberar a la IA.
Sea cual sea el resultado del juego (se libere a la IA o no) sólo se sabrá éste, pero no los detalles de cómo se llegó a él. De esta forma los jugadores no han de preocuparse por parecer ilógicos/simples/etc. ante terceras personas, y se evita que personas externas digan “conmigo eso no hubiera funcionado”.
Yudkowsky jugó dos veces, una contra Nathan Russell y otra contra David McFadzean, dos oponentes que afirmaban que nada de lo que la IA pudiera decirles le convencería. El resultado: Yudkowsky ganó las dos veces. Su interpretación: si una mente humana ha sido capaz de convencer al guardián, ¿qué dificultad iba a tener una IA transhumana que estuviera órdenes de magnitud por encima de nosotros? Primer corolario: si se crea una IA transhumana, ésta escapará con seguridad; los humanos no son sistemas seguros de contención. Segundo corolario: si es posible producir una IA simiente, es preciso entonces garantizar por todos los medios que sea amigable. ¿Cómo? Ésa es otra cuestión.
