Activa las notificaciones para estar al tanto de lo más nuevo en tecnología.

Programación lúdica: los juegos legales del gato

En este nuevo reto, al lector se le propone la tarea de escribir un programa que muestre todas las posiciones legales del juego del gato. ¿Le entra?

El juego del gato tiene muchas virtudes: por una parte es un juego entre dos personas que es elemental y que pronto se aprende cómo ganar o cómo no perder. Su complejidad no es ni remotamente como la de otros juegos de suma-cero e información perfecta, pero es un juego muy interesante para enseñar mucho en computación.

En este reto no estamos buscando que se escriba un programa que juegue al gato, sino que haga algo más trivial, dé todas las posiciones posibles de los juegos de gato legales. Por ejemplo, la siguiente figura muestra una posición del gato que no se puede alcanzar jugando (aunque se juegue mal) y por tanto no se considera una posición “legal”, para decirle de algún modo.

La pregunta es entonces: ¿Cuántas posiciones legales tiene el juego del gato? De acuerdo con este sitio, hay 9 formas diferentes de empezar un juego, y entonces, el rival tendrá 8 maneras diferentes de responder. Entonces de nuevo el primer jugador tendrá 7 casilleros donde poner su tirada y así sucesivamente, es decir: 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 9! = 362880. Pero este número parece demasiado grande. Supongamos que un juego termina en el sexto movimiento. Claramente habrán quedado casillas sin llenar, pero ya no se necesitan llenar. Si las llenamos entonces puede ser que cuente como más de un juego.

Se puede hacer un análisis más cuidadoso, por ejemplo: cuántos son los juegos que acaban en el quinto movimiento. Si tenemos 8 líneas de tres casilleros (vertical, horizontal y diagonal), y además, donde no importa en qué orden se llenan las casillas, estamos entonces viendo 8 * 3! * 6 * 5 = 1440 posibilidades de juegos que se ganen en 5 movimientos.

Por ejemplo, la tabla 1 muestra las posiciones posibles para un jugador en cada momento de una partida de gato. Así, cuando nadie ha hecho ninguna jugada, hay 1 posible posición y el jugador puede tirar en una de las 9 casillas, es decir, tiene 9 posibles alternativas. Pero el rival puede contestar a esto con 8 posibles respuestas. Eso da entonces 9 * 8 = 72. Con este mismo razonamiento, se puede entonces tener 252 posiciones, en donde hay 504 formas de llegar al mismo. Y así sucesivamente.

Considerando la simetría se puede armar entonces la siguiente tabla, en donde claramente en la primera jugada, quien participa tiene 3 lugares donde puede tirar, en una esquina, en una banda o en el centro. E; contrario podrá entonces hacer lo propio 4 veces, por lo que lo hará 12 veces en total, y así sucesivamente. De ahí sale el total de 765 posiciones.

Hay quien se ha encargado entonces de hacer estos cálculos. Por ejemplo, en el 2002 Steve Schaefer calculó el número de soluciones en donde además, tomó en cuenta la simetría (lo que reduce de alguna manera las posiciones legales, porque algunas son imágenes rotadas de otros juegos de gato). Y halló que hay 765 posibles soluciones.

Entonces el reto de la programación lúdica es hacer un programa que encuentre las 765 posiciones legales del gato y las entregue en un archivo de texto con un formato leíble, desde luego.

El reto tendrá como premio una taza de la Morsa. Si el ganador es de provincia, se le mandará un USB de 8 GB al menos, porque mandar una taza por mensajería es ridículamente costoso. Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. Si hay, por ejemplo, dos o más respuestas satisfactorias, ganará quien la haya mandado primero. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto.

Comentarios