Monday, September 14, 2009

El juego del mago


Uno de los primeros programas que se dejan a los alumnos en las carreras de computación, particularmente en lo que se refiere a estructuras de datos, es la del árbol binario. A través de este ejercicio el alumno tiene que construir una estructura arbórea, en donde de la raíz del árbol salen dos ramas, a su vez de éstas salen, en cada una dos ramas y así sucesivamente. Para ilustrar el asunto normalmente se usa el juego de las preguntas, el cual se basa en respuestas de sí y no, de manera que de acuerdo a las preguntas, si la respuesta es “”, se recorre uno a la rama de la izquierda y si se contesta “no”, entonces se recorre a la rama derecha. El sistema puede preguntar cosas de este estilo: “piensa en animal real” (digamos que nuestra elección es ‘elefante’). La primera pregunta podría ser: “¿pesa más de 300 kilogramos? Contestaremos “”. Siguiente pregunta: ¿es acaso el animal que pensaste un toro?. La respuesta será “no”. Entonces el sistema nos dirá: Dame una pregunta (de respuesta “sí” o “no”), que distinga a un elefante de un toro. Podríamos poner la siguiente pregunta: ‘el animal en el que estás pensando ¿tiene trompa?’. Si la respuesta es afirmativa, entonces estaríamos hablando de un elefante”.

Así, la siguiente vez que se entra a este programa éste preguntará empezando por “¿pesa más de 300 kilogramos?” Y seguirá las preguntas en el orden en que han sido programadas. De acuerdo a la base de datos arbórea, estaremos recorriendo las ramas hasta llegar a una rama terminal (la cual ya no tiene más ramas). Si es así, el sistema pondrá la respuesta que asume debe ser. Si acierta, el juego concluye. Si no acierta, entonces habrá que crear una rama extra, con la respuesta positiva a la izquierda y la negativa en el lado derecho.

Pues bien, en el sitio http://es.akinator.com/ hallé este juego. Me pedían que pensara en un personaje real o ficticio y el “mago” intentaría decirme en qué personaje estaba pensando. Se me ocurrió por razones que desconozco, pensar en Garry Kasparov, excampeón mundial de ajedrez y quizás el jugador más fuerte de toda la historia del tablero escaqueado. El mago inició sus preguntas, y me hizo muchas, en donde la mayoría eran si mi personaje era real o ficticio, si jugaba algún deporte, si utilizaba pelotas para el mismo, si era un deporte de combate, etc. Finalmente me dijo: “Piensas en Garry Kasparov”. ¡Había acertado!

Suena increíble si no se entiende el mecanismo de un árbol binario. ¿Cómo pudo saber, entre tantos personajes que hay en el planeta, el que estaba pensando haciéndome una serie de preguntas? La respuesta es fácil, teniendo una base de información en un árbol binario y recorriéndose por las ramas del mismo, guíadas por las respuestas. Pensemos, por ejemplo, ¿cuántos personajes puede contener este programa? La respuesta no es muy difícil. Si iniciamos el árbol ráiz con dos ramas, a la izquierda puede ir –digamos– Serena Williams (la tenista) y a la derecha Penélope Cruz (la actriz). Preguntamos entonces, como primera pregunta, si el personaje que pensamos es actriz. Si la respuesta es “”, entonces asumimos que hablamos de Penélope. Si la respuesta es “no” asumimos que hablamos de la tenista. Si contestamos que “”, pero no se trataba de Penélope entonces el sistema nos debe preguntar en qué actriz pensábamos y cómo la diferenciamos de la anterior. La pregunta podría ser: “¿es una actriz mexicana?”. Si la respuesta es “”, hablaríamos de Salma Hayek, si es la respuesta contraria, podríamos decir que es, no sé, Galilea Montijo. Obsérvese con este ejemplo que el árbol crecerá en potencias de dos: una raíz, dos ramas, cuatro subramas, ocho sub-subramas, dieciséis sub-sub ramas, treinta y dos sub sub sub ramas, etc. Así, a la pregunta 8 ya podremos decidir sobre un total de 256 personajes. Si tenemos 9 preguntas, hablaremos de 512 personajes ya en nuestra base de datos. 10 preguntas nos dan información sobre 1024 personas, 11 preguntas y tendremos 2048. 12 preguntas y estaremos con 4096. 13 preguntas serían 8192 personajes. 14 preguntas nos darían un resultado posible de 16384, etc. Es decir, esto aumenta en 2 a la potencia N, donde en cada N que aumenta en 1, se duplica la información que tenemos. Así entonces, por eso es que el sistema adivina el personaje de los miles que quizás puedan existir, sin considerar siquiera que habrá unos más famosos que otros por los medios y por la época que nos tocó vivir.

11 comments:

Yixus said...

Pero el caso del Akinator no es un árbol binario, ¿no?, porque admite varias respuestas

Yixus said...

Je, je,escogí a un personaje que no tienen. No sé si abusé, pero creo que un bicampeón mundial de scrabble debería de estar, jajajaja

Morsa said...

Pues si con un árbol binario es así, más mérito tiene este programa, que deb ser más complejo de crear.

saludos
Manuel

Brito said...

A mi me adivinó AMLO, pero le costó trabajo al genio que hasta rojo se puso jeje.

Ernesto said...

Yo había visto este:

http://www.20q.net/

Saludos,
Ernesto

Cyberprimo ® said...

jaja no me adivino y a que no saben en quien estaba pensando?? en Alexandra Kosteniuk se la puse dura XD creyo que era Gisele Bundchen, no lo culpo muy wapas las dos.

Cyberprimo ® said...

Joer me adivino a Lorena Herrera XD
es una pasada este genio se revindico como le hara?? jejeje

Saludos y felices fiestas patrias me dejo al genio por la fiesta XD

Luisillo said...

pues yo jugué 3 veces con Bobby Fischer y sólo adivinó la segunda, las preguntas no fueron las adecuadas como por ejemplo "es ciudadano de estados unidos?" después de haberme preguntado si había muerto jeje. respondí que no "es" ciudadano de estados unidos aunque no sé si debí haber puesto que sí.

Joel said...

Ya que mencionan a Fischer ¿No es considerado él el juagod más fuerte de la historia del "deporte ciencia"?

Saludos.

Morsa said...

Joel,

Cito lo que escribió Kasparov en el libro "Fischer: His Approach to Chess", de Elie Agur

Prólogo

Todavía recuerdo los días del campeonato mundial entre Spassky y Fischer en 1972. Yo era un niño de nueve años haciendo mis primeros pasos en la carrera ajedrecística, en la pacífica Bakú. Yo sabía, por supuesto, que Spassky, el campeón del mundo reinante era un muy fuerte jugador, pero yo tenía la idea de que Fischer, mi ídolo de ajedrez de ese entonces, era un jugador de otro calibre, alguien que estaba en otra clase, en su propia clase.

La escena del ajedrez ha cambiado mucho desde entonces y yo, he hecho algunos progresos en estos veinte años... Cuando comparo mi propia carrera con la de Fischer, debo admitir que yo gocé de cierta ventaja sobre él. El no tenía nadie a su lado como para alcanzar las alturas a las que llegó, en donde yo tuve el privilegio de tener un jugador de primera clase como Karpov, que me forzó a esforzarme más a mí mismo y avanzar todavía más arriba.

Si uno puede juzgar la fuerza de los jugadores comparándolos con sus contemporáneos, pareciera que los logros de Fischer son imposibles de sobrepasar. El espacio entre él y sus más cercanos rivales fue el más amplio que ha habido entre el campeón del mundo y los jugadores de más alto rating en su tiempo. Él estaba unos 10 a 15 años por encima de su tiempo, en preparación y entendimiento. Esto puede atribuirse en parte a su dedicación al juego, que fue jamás igualada por otros jugadores antes o en el tiempo de Fischer.

Yo le recuerdo como una combinación mitológica, un centauro si usted quiere, una síntesis entre hombre y ajedrez.

Y no es una partida en particular la cual me impresionó, aunque él jugó grandes partidas. Es su actitud profesional al juego, sus cualidades como luchador que me llamaban tanto la atención. Fischer fue el primer jugador profesional realmente y yo me considero su seguidor.

Estudiar los juegos de Fischer es importante, pienso, para cualquier jugador de cualquier fuerza ajedrecística. Pero sobre todas las cosas, esto le dará una idea de cómo enfocarse al juego, o ponerlo de otra manera, esto deberá cambiar su actitud al juego de manera que le permita mejor su propio nivel.

Garry Kasparov (1992)

Joel said...

Volviendo al tema, sólo jugué una vez con el mago y me adivinó a Roger Federer (que es muy conocido), me gustó mucho la página.

Y ya que hablo sobre Roger, puedo compararlo entonces con Kasparov según el prólogo que mencionas. Roger (ahora es considerado por muchos el mejor jugador de la historia) ha tenido que competir con Nadal que lo ha llevado al límite. Y aunque Sampras tuvo a Agassi y así con otros jugadores históricos como Borj, Lendl, etc tuvieron rivales fuertes Nadal ha resultado uno de los más fuerte de los segundos lugares de la historia. Me parece que es la misma idea que plantea Kasparov.

Saludos.