Tuesday, September 09, 2008

El juego del gato y sus aplicaciones

No me acuerdo desde cuando entendí que el juego del gato (tres en línea, tic-tac-toe), es uno de los pasatiempos más interesantes para programar por computadora. Por un lado, es lo suficientemente sencillo para que no requiera de demasiados recursos. Por otra parte, es relativamente complejo y por ende, tampoco resulta un ejercicio trivial. Soluciones del juego del gato y programas que lo juegan correctamente hay muchos. En mis cursos de Prolog (programación lógica, inteligencia artificial), es una tarea que se deja de rigor.

De hecho, Martin Gardner alguna vez contó que cuando era estudiante de secundaria estaba en una clase de matemáticas intentando hallar alguna fórmula para resolver el gato. Su maestro lo vio (de acuerdo a su criterio, jugando al gato el solo), y le reprendió. Le dijo que mejor estudiara matemáticas y dejara esos jueguitos tontos para su tiempo libre.

Pues bien, en la Universidad Iberoamericana, este semestre estoy dando un curso de Reconocimiento de Patrones. Aunque la parte teórica nunca me ha terminado de gustar (en mi opinión hay demasiadas matemáticas y creo que el enfoque debería ser más práctico, aunque comprendo perfectamente que de esta manera se le da el formalismo y rigor necesarios), pero en la parte práctica, de experimentación, hay N temas que pueden abordarse.

De esta manera, le dejé a mi alumno (¡sólo tengo un alumno en ese curso!), Daniel González, que escribiera un juego de gato pero que lo resolviera usando solamente patrones. La idea era generar los patrones necesarios para siempre ganar (empezando la computadora y tirando ésta siempre en el centro), y a cada jugada del adversario, el sistema debería buscar el patrón correspondiente, aplicarlo y generar la jugada correcta.

Daniel hizo su programa en Java y utilizó dos trucos: primero generó 42 patrones (incluyendo el del tablero vacío) y de ahí tuvo que ubicar posibles respuestas que se salieran de los patrones utilizando giros del juego del gato (90, 180, 270 grados). De esta manera, como el juego tiene simetría, pudo eliminar información redundante y logró un bonito programa que resuelve (simplemente buscando el patrón correcto), cada jugada que debe hacer la computadora para ganar o al menos, nunca perder. Y hago énfasis en esto: el programa no tiene un algoritmo para resolver el juego del gato o jugar bien. Simplemente es un sistema de búsquedas de patrones y las acciones a realizar cuando el patrón se encuentra. Cabe señalar que están todos los patrones posibles.

Quien quiera jugar contra el software de Daniel mándeme un mensaje a mi correo (morsa@la-morsa.com) y se lo envío. se necesita una versión de Java que sea 6.0 o superior.

3 comments:

Gonzalo said...

Muy Interesante. El tema de patrones es un tema muy extenso, se puede ver en muchisimas ciencias asi como en lenguages naturales y tambien vida diaria.

Actualmente estoy leyendo el libro: "The Timeless Way of Building" el cual tambien habla de muchisimos patrones. El capitulo que estoy leyendo es como hacer un ambiente de felicidad :) en la vida del ser humano por medio de lo que lo rodea muy interesante.

Ojala pudiera atender tu clase.

Morsa said...

Hola, Gonzalo,

gracias por tus comentarios.

saludos
Manuel

Gonzalo said...

Hace un tiempo atras estaba averiguando como dar una presentacion para cierto grupo, en mi busqueda encontre que hay una organizacion que ha sido creada con el proposito de compartir algunos Patrones efectivos para la ensenanza.

http://www.pedagogicalpatterns.org/