Turing Test & Loebner Prize
On October 12 took place, at the University of Reading, the 18th edition of the Loebner Prize. In this competition, several ACEs (Artificial Conversational Entities) interact with humans through a chat-like interface. ACEs have to deceive their human interrogators, making them think that they are talking to another human, instead of a machine.
The competing ACEs have to face several five minute long rounds where human interrogators talk to ACEs without any constraints, so the ACE must be versatile enough to maintain a coherent generic conversation with a non predictable human. Interrogators doesn’t know whether they’re talking to a human or to a machine so, if the ACE is able to behave like a human the interrogator will be fooled.
The software that won this year edition was Elbot, created by Fred Roberts, who won the $3000 prize, sponsored by Hugh Loebner. Elbot was able to fool 25% of humans, which means that they’re geting closer to the 30% threshold set by Alan Turing in his original paper of 1950.
These kind of tests are the so called Turing Tests, and the formal definition given by Alan Turing in his paper “Computing, machinery & intelligence” is as follows: “If, during text-based conversation, a machine is indistinguishable from a human, then it could be said to be ‘thinking’ and, therefore, could be attributed with intelligence”.
It’s worth to have a look at the transcriptions of the conversations, one can found there even some kind of “feelings” and “humor” in the answers given by the AIs, without a doubt a good trick to fool the human judges. But, can this skill “to behave like” be called intelligence?
How about a nice game of chess? (revisited)
Lo que pongo a continuación es un comentario que ha dejado Juan Carlos Jimenez a mi post “How about a nice game of chess?” ampliando muchísimo la información sobre el duelo Kasparov-Deep Blue. Dada su extensión y tremendo interés, y con el permiso de Juan Carlos, lo publico como post en vez de como comentario para que pueda ser leido con más comodidad. Os recomiendo también que visitéis el blog personal de Juan Carlos, donde encontraréis información sobre sus viajes a Japón y, como no, sobre Ajedrez :)
Aunque comentas de pasada el tema del segundo encuentro entre Kasparov y Deep Blue, ya que el tema central del post es el Go, me gustaría aprovecharme de mi afición al ajedrez para matizar cosas que deberían saberse :P
Es justo que en un post como este aparezca toda la información…
Deep Blue y Kasparov se enfrentaron en “tres” ocasiones (en la primera como Deep Thought y las últimas dos como Deep Blue) a ritmo de juego lento o torneo que consiste en 2 horas para las primeras 40 jugadas y luego una hora más a finish (señalo esto porque a ritmo de juego rápido una máquina es bastante superior a un jugador de ajedrez y es en la modalidad lenta donde se juegan los torneos de ajedrez validos para calcular la puntuación ELO de los jugadores y donde estos expresan su mejor cualidad ajedrecística).
La primera fue en 1989 en un match de dos partidas que ganó Kasparov, la segunda y tercera contra Deep Blue en los años 1996 y 1997 en sendos match a 6 partidas que terminaron 4-2 para Kasparov el primero y 3′5-2′5 para Deep Blue el último.
Pero hubo muchas dudas y razones que hacen pensar que en el último enfrentamiento, la legalidad del match fue dudosa y es que éste nunca se planteó en situación de equidad.
En primer lugar, Deep Blue contaba en su base de datos con todas las partidas de Kasparov (aparte de varios millones más de partidas de otros Grandes Maestros) mientras que Kasparov nunca recibió de IBM ni una sola partida de Deep Blue pese a haberlas pedido repetidas veces para estudiar el juego de su adversario.
En la sala de juego acondicionada para las partidas se encontraba el Gran Maestro, el tablero y un operario con un terminal y un ratón a través de los cuales enviaba las jugadas y recibía las respuestas de Deep Blue. Kasparov pidió comprobar las comunicaciones de dicho terminal y/o poder ver que efectivamente la máquina y sólo la máquina estaba conectado al mismo pero se le negó. Esto resulta importante ya que a dicho terminal podían estar llegando las respuestas de Deep Blue o de cualquier otra cosa. Cualquiera pensaría que sería tonto no conectar a dicho terminal a la máquina más potente que existía para jugar al ajedrez, pero es que dicha máquina no es el mejor jugador de ajedrez del planeta… Un grupo de Grandes Maestros que estuvieran analizando la partida y jugándola desde otra habitación en pleno coloquio (como usualmente se reúnen los grupos de analistas y entrenadores de los grandes maestros) bastarían para derrotar al mejor jugador humano del mundo.
El grupo de analistas de Deep Blue estaba compuesto por varios Grandes Maestros de todo el mundo. Entre ellos se encontraba Miguel Illescas (en el momento campeón de España e ingeniero informático). La función de los analistas era dialogar con los programadores para afinar la función de evaluación que se calcula sobre cada variantes de los varios cientos de millones que calculaba DB por segundo.
¿Pero era ese el único cometido de dichos analistas? Durante el match, Deep Blue era afinado en tiempo real en cada jugada por dichos analistas y programadores en función de las respuestas que daba a cada movimiento el campeón del mundo (algo del todo ilógico ya que la máquina debería ser autónoma y proseguir su cálculo con total normalidad sin ser afectada en cada jugada por ajedrecistas humanos).
Hago un inciso aquí para explicar un detalle importante que la gente menos conocedora del ajedrez debe conocer para comprender lo que sigue a continuación. En ajedrez hay dos componentes: la táctica y la estrategia (o posición). Los valores tácticos resultan de la continuación de varias jugadas en adelante para conseguir una mínima ventaja (un peón de más, cambiar un caballo por un alfil, etc.). Los ordenadores hasta el momento sólo se limitaban a calcular posiciones en profundidad (con el algoritmo minimax de Shannon y el podado alfa-beta). A mayor potencia de cálculo mayor profundidad de jugadas calculadas (aunque si la función de evaluación de las posiciones no está bien afinada, de nada sirve ver 10 jugadas por delante si estas no son perfectas). Una componente hoy por hoy casi imposible de definir perfectamente en una máquina capaz de jugar al ajedrez es la componente posicional del juego (para la que sí está preparado un humano). La evaluación del programa, que se basa en hechos concretos y tiene dificultades para incorporar evaluaciones posicionales a más largo plazo, no tiene en cuenta este aspecto estratégico o posicional del juego (al menos como estaba programado DB en aquel momento).
Con tantas irregularidades como se habían cometido hasta el momento, Kasparov tendió una trampa a Deep Blue: en la última partida Kasparov perdió fulminantemente en muy pocas jugadas tras plantear deliberadamente (es imposible en el ajedrez de élite que dicha jugada se tratara de un lapsus o un error) una variante de apertura muy dudosa, y bastante conocida incluso entre aficionados. La explicación a aquella aplastante derrota es que Kasparov planteó esa línea con el convencimiento de que la máquina no realizaría un sacrificio de caballo muy fuerte, a cambio de dos peones, en las primeras jugadas de la partida. Entre humanos es conocido que ese sacrificio, que no obtiene ventaja inmediata sino una presión posicional continuada pero abstracta, es muy fuerte y plantea grandes dificultades al bando defensor. Kasparov confiaba en que la evaluación del programa, que se basa en hechos concretos y tiene dificultades para incorporar evaluaciones posicionales a más largo plazo, descartaría el sacrificio por una cuestión simplemente numérica, teniendo en cuenta el valor de las piezas intercambiadas y la compensación resultante. El caso es que Deep Blue sacrificó el caballo en la partida decisiva (el marcador señalaba un empate en ese momento) y Kasparov tuvo que rendirse en tan sólo 21 movimientos.
Como informático y jugador de ajedrez me queda muy claro que existió una mano humana tras aquel sacrificio y Kasparov así lo hizo saber en la rueda de prensa posterior al match.
Kasparov acusó a IBM de haber hecho trampas enumerando todas estas razones y argumentando muchas otras y ofreció la posibilidad de revancha el año siguiente con las normas adecuadas para que el match posterior se llevara a cabo en igualdad. IBM nunca aceptó el reto…
Si os interesa el tema y queréis más información al respecto os recomiendo encarecidamente el documental ‘Game Over: Kasparov and the machine’ (documental del que se ha sacado el vídeo que se incluye en este post) en el que durante una hora se explica, argumenta e intenta demostrar todo esto explicado aquí.
Si te parece que el comentario es muy largo (que lo es) y prefieres publicar todo el texto en un nuevo post de tu blog, hazlo con toda libertad.
How about a nice game of chess?
Muchos lo recordaréis, en el año 1.997 Gari Kasparov era “derrotado” por Deep Blue. Fue un suceso muy mediático, como suele ocurrir cada vez que parece que una máquina da un paso dentro de un área en el que el humano es lider indiscutible. Una máquina ganaba a un gran maestro de ajedrez, un paso más hacia la esclavitud del hombre por las máquinas :)
Es justo recordar que, a pesar de esta derrota contra Deep Blue, Kasparov no fue ni mucho menos “derrotado” en competiciones similares celebradas en el año 2.003 contra Deep Junior y X3D Fritz.
Pero este post no trata sobre ajedrez computacional, sino sobre Go computacional, ya que la noticia está en que la semana pasada el programa Mogo lograba vencer (aunque con 9 piedras de ventaja) a Myungwan Kim, jugador de Go profesional 8-dan, en un tablero de 19×19.
El Go se considera la “última frontera” a conquistar en términos relativos a Inteligencia Artificial y teoría de juegos, ya que comparado con el ajedrez el go presenta dificultades adicionales:
- Los tableros de 19×19 generan tal cantidad de posibles combinaciones que se convierte en un problema algorítmico de considerable dificultad.
- Las fichas del go gozan de mucha más libertad que las del ajedrez.
- A diferencia del ajedrez donde según avanza la partida se van eliminando piezas del tablero, en el go según avanza la partida se incrementan las posibilidades.
- Las técnicas computacionales desarrolladas para el ajedrez no son aplicables al go, se trata de un problema completamente diferente.
- A diferencia del ajedrez, es más complicado generar funciones de evaluación y no existen tablas de finales de juego.
Hasta ahora el éxito más importante en go computacional se remontaba al año 2.002 con la resolución de juegos en tableros de 5×5. El salto a tableros de 19×19 es un hito muy importante dentro de este área, si bien este logro no sale gratis. El programa MoGo se ejecutó sobre un supercomputador con 800 procesadores a 4.7GHz que ofrecía un total de 15 TeraFLOPS. Según el maestro Myungwan Kim, el programa tenía un nivel de entre 2-dan y 3-dan, aunque llegó a comportarse como un 5-dan.
Realmente, por tanto, la cuestión no es que el maestro 8-dan de Go ha sido derrotado por la maquina, sino más bien, ¿qué ha hecho falta para derrotarle?… un superordenador de 15 TeraFLOPS, un handicap de 9 piedras y 50 minutos de proceso de los 60 minutos que duraba la partida. También hay que tener en cuenta, que de acuerdo a los programadores de MoGo, hace 1 año el handicap era de 18 piedras, en 1 año lo han reducido a 9 piedras… ¿el año que viene vencerá sin necesidad de handicap? La humanidad puede seguir durmiendo tranquila… por el momento ;)
¿Y cómo hace Mogo?, ¿es fuerza bruta?… la respuesta es Monte Carlo. Si estáis interesados en el algoritmo usado por MoGo nada mejor que ver la conferencia dada por su creador Silvain Gelly.