Efectivamente, ya no tenemos limitaciones de memoria. Esto nos permite analizar muchos niveles de profundidad y, por tanto, que el C64 juegue mejor.

Sin embargo, es cierto que la vida es puñetera y ahora tenemos un nuevo límite: el tiempo. Lógicamente, se trata de no aburrir al personal y de no tirarse media hora en cada jugada. ¿Cuánto puede esperar un jugador al siguiente movimiento del C64? ¿Cinco minutos como máximo?

A modo de ejemplo se muestra la siguiente tabla de datos. Téngase en cuenta que cuando es el turno de los gatos hay un máximo de 8 movimientos (4 gatos x 2 movimientos) y cuando es el turno del ratón hay un máximo de 4 movimientos (1 ratón x 4 movimientos):

(*) Aunque 2 horas puede parecer mucho, y sin duda lo es para un jugador esperando el siguiente movimiento, hay que tener en cuenta que estamos hablando de 33,5 millones de tableros para un ordenador que funciona a 1 MHz.

En definitiva, es fantástico que el C64 juegue fuerte a 10 niveles de profundidad, y que sea imbatible o muy difícil ganarle a ese nivel, pero sería muy conveniente agilizar el proceso. Para ello hay varias estrategias:

Podar el árbol de juego:

Podar el árbol de juego consiste en eliminar aquellas ramas que no tiene sentido generar y evaluar.

Por ejemplo, si en un tablero del árbol de juego el ratón está a la espalda de los gatos, la partida ya está ganada para el ratón (salvo que el humano juegue a perder intencionadamente), por lo que no se hace necesario seguir desarrollando esa rama. Se puede podar.

En este sentido, el procedimiento minimax admite una mejora importante que se llama poda alfa – beta.

Poner un límite de tiempo a cada movimiento:

Si el C64 empieza a tener un juego fuerte a partir del nivel 10, pero en ese nivel decidir cada jugada lleva mucho tiempo, simplemente ha llegado el momento de asumir que no es posible generar y evaluar todos los movimientos. Por tanto, nos ponemos un límite de tiempo razonable (ej. X minutos por movimiento) y, cuando se haya agotado ese tiempo, optamos por el mejor movimiento descubierto hasta ese momento.

La forma habitual de implementar esto es mediante una técnica llamada “iterative deepening” o “profundización progresiva”. Es decir, aunque el usuario haya decidido jugar a profundidad 10, la máquina juega a profundidades 1, 2, 3, 4, 5, …, y así sucesivamente hasta que se agote el tiempo disponible. Una vez que se agota el tiempo, sea en el nivel que sea, por ejemplo 7, se elige la mejor jugada descubierta hasta ese momento.

Esta forma de funcionar parte de la base de que no vas a poder desarrollar el árbol completo hasta el nivel N, y que te vas a tener que conformar con lo mejor que encuentres en un tiempo limitado, por lo que se vuelve especialmente interesante ordenar los movimientos y desarrollar primero los que sean más prometedores.

Hasta ahora no hemos hecho esto. Hemos generado todos los movimientos y en un orden un tanto arbitrario. El orden de los movimientos ha venido fijado por las matrices que los generan:

Se podrían ordenar y desarrollar primero, por ejemplo, aquellos movimientos que mantienen la formación de los gatos, es decir, aquellos que no generan huecos. De este modo, la probabilidad de que el “deadline” nos pille habiendo generado y analizado jugadas malas se reduce.

Otras técnicas:

Hay más técnicas para acelerar el proceso de generar y evaluar el árbol de juego. Por ejemplo, si dos secuencias de jugadas distintas llevan al mismo tablero, no hay necesidad de desarrollar ese tablero dos veces. La segunda vez que se presente el mismo tablero en el árbol de juego, se puede detectar que es una repetición y copiar su evaluación previa o podarlo, sin necesidad de desarrollarlo más.

Para que dos tableros sean idénticos las piezas deben ocupar las mismas casillas y, además, el turno de juego debe ser el mismo.

Y como recorrerse todo el árbol generado previamente a la caza y captura de un tablero igual que el actual sería inviable, puesto que costaría más hacerlo que lo que se ahorraría, lo que se suele hacer es definir una especie de “función hash” que, dado un tablero, genera un número (ej. la suma de los offsets de los gatos menos el offset del ratón). Luego estos números se almacenan en una tabla ordenada y, si al generar un nuevo tablero su “hash” ya está en la tabla, asumimos que el tablero es repetido y actuamos en consecuencia.

Bueno, iremos viendo hasta dónde llegamos…