UNIDAD4 PA3

 Ejemplo: jugando al tres en raya

Maxine y Minnie son verdaderas fanáticas de los juegos. Les encantan. Especialmente los juegos de información perfecta para dos personas, como es el caso del ajedrez o el tres en raya. Un día estaban jugando al tres en raya. Maxine, o Max, como la llaman sus amigos, iba con las X. Minnie, Min para los amigos, tenía los O. Min acababa de terminar su turno y el tablero estaba así:

Max miraba el tablero pensando su próximo movimiento, ya que era su turno, cuando de repente hundió la cabeza entre las manos desesperada, estampa que recordaba a Garri Kaspárov jugando contra Deep Blue en 1997.

Sí, Min estaba a punto de conseguir tres O en la fila superior, pero Max podía acabar fácilmente con su plan. ¿Por qué Max era tan pesimista?

Árboles de juego
Para resolver juegos utilizando la IA, introduciremos el concepto de «árbol de juego». Los distintos estados del juego se representan mediante nodos en el árbol de juego, de manera muy similar a los problemas de planificación vistos antes, aunque la idea es ligeramente diferente. En el árbol de juego, los nodos están dispuestos en niveles que se corresponden con los turnos de cada jugador, de forma que el nodo «raíz» del árbol (normalmente representado en la parte superior del diagrama) es la posición inicial en el juego. En el tres en raya, sería la cuadrícula vacía, sin X ni O. Debajo de la raíz, en el segundo nivel, se representan los estados que pueden derivarse de los primeros movimientos de los jugadores, ya sea X o O. Nos referimos a estos nodos como los «hijos» del nodo raíz.
A su vez, cada nodo del segundo nivel tendrá como nodos hijos los estados que pueden resultar de él en función de los movimientos del jugador contrincante. Esta situación prosigue, nivel a nivel, hasta alcanzar estados en los que el juego finaliza. En el tres en raya, esto significa que uno de los jugadores consigue colocar tres fichas en línea y gana, o que el tablero está completo y el juego termina en empate.
Valor minimizante y maximizante
Para desarrollar un método de IA que trate de ganar el juego, asignamos un valor numérico a cada resultado final posible. A las posiciones del tablero en las que hay tres X en raya de forma que Max gana les asignamos el valor +1, y, del mismo modo, a las posiciones en que Min gana con tres O en raya les asignamos el valor -1. Para las posiciones en que el tablero está lleno y ninguna de las jugadoras gana, utilizamos el valor neutral 0 (realmente no importa cuáles sean los valores mientras sigan este orden, de forma que Max intente maximizar el valor y Min, minimizarlo).
Un modelo de árbol de juego
Consideremos, por ejemplo, el siguiente árbol de juego, que no empieza en la raíz, sino a mitad de la partida (de lo contrario, el árbol sería demasiado grande para ilustrarlo). Fíjate en que no es igual que el juego de la ilustración al principio de esta sección. Hemos asignado a los nodos los números 1, 2,..., 14.
El árbol está formado por niveles que se alternan, en función de que sea el turno de Min de colocar un O o el de Max de colocar una X en cualquiera de las casillas vacías del tablero. En la parte izquierda se indica a qué jugadora le corresponde el turno.
El juego continúa a partir de la posición del tablero que se muestra en el nodo raíz (en la parte superior) con el número 1. Es el turno de Min de colocar un O en cualquiera de las tres casillas libres. Los nodos 2 a 4 muestran las posiciones del tablero con cada una de las tres posibilidades. En el siguiente paso, cada nodo permite dos elecciones para que Max coloque una X, de ahí las tres ramas del árbol.
Al partir de la posición inicial indicada, la partida siempre termina con tres en raya: en los nodos 7 y 9, la ganadora es Max, que juega con las X, y, en los nodos 11 a 14, la ganadora es Min, que juega con los O.
Verás que, como los turnos de las jugadoras se alternan, se puede hablar de «niveles de Min» y «niveles de Max», indicando a quién le corresponde el turno.
Aplicar una estrategia
Centrémonos en los nodos 5 a 10 del segundo nivel desde abajo. En los nodos 7 y 9 la partida termina y Max gana con tres X en raya. El valor de estas posiciones es +1. En los otros nodos, 5, 6, 8 y 10, la partida también está prácticamente acabada, puesto que Min solo necesita colocar su O en la única casilla libre para ganar. En otras palabras, en cada nodo del segundo nivel desde abajo sabemos cómo acabará la partida. Por consiguiente, podemos decidir que el valor de los nodos 5, 6, 8 y 10 sea también -1.
Ahora viene la parte interesante. Veamos los valores de los nodos situados un nivel por encima hacia la raíz: los nodos 2 a 4. Como hemos observado que los dos hijos del nodo 2, es decir, los nodos 5 y 6, conducen a la victoria de Min, podemos, sin lugar a dudas, asignar el valor -1 también al nodo 2. No obstante, en el caso del nodo 3, el hijo izquierdo 7 lleva a la victoria de Max, +1, mientras que el hijo derecho 8 conduce a la victoria de Min, -1. ¿Cuál es el valor del nodo 3? Reflexiona unos instantes, teniendo en cuenta a quién le toca elegir en el nodo 3.
Puesto que es el turno de Max, es obvio que elegirá el hijo izquierdo, el nodo 7. Así, siempre que lleguemos a la posición del tablero que se muestra en el nodo 3, Max tendrá la victoria asegurada, de modo que podemos asignarle el valor +1.
Lo mismo se aplica al nodo 4: de nuevo, como Max puede elegir dónde colocar su X, tiene la posibilidad de asegurarse la victoria, y, por tanto, asignamos el valor +1.
Determinar quién es el ganador
La lección más importante de esta sección es aplicar el anterior razonamiento repetidamente para determinar de antemano el resultado del juego desde cualquier posición del tablero.
Hasta ahora, hemos decidido que el valor del nodo 2 sea -1, lo que significa que, si llegamos a esa posición del tablero, Min podrá asegurarse la victoria, y que en el caso de los nodos 3 y 4, se dará la situación inversa, esto es, su valor será +1, lo que quiere decir que Max puede tener la certeza de ganar si juega con sensatez.
Por último, cabe deducir que, puesto que Min es una jugadora experimentada, puede llegar a la misma conclusión y, por tanto, solo cuenta con una opción real: colocar el O en el medio del tablero.
En el diagrama que figura a continuación, hemos incluido el valor de cada nodo, así como el desarrollo óptimo del juego a partir del turno de Min en el nodo raíz.
El valor del nodo raíz = quién gana
El valor del nodo raíz, que se considera el valor del juego, nos dice quién gana (y cuánto, si el resultado no es simplemente la victoria o la derrota): Si el valor del juego es +1, gana Max; si es -1, gana Min, y si es 0, se produce un empate. En otros juegos, el valor también puede tomar otros valores (por ejemplo, el valor monetario de las fichas en el póquer).

Todo esto se basa en la hipótesis de que ambos jugadores eligen lo que más les conviene, y lo que más conviene a uno es lo peor para el otro (lo que se denomina «juego de suma cero»).

El algoritmo minimax

Podemos aprovechar el concepto anterior del valor del juego para obtener un algoritmo denominado «algoritmo minimax». Este algoritmo garantiza un desarrollo óptimo del juego (teóricamente) en cualquier juego de suma cero que sea determinista, de dos jugadores y de información perfecta. A partir de un determinado estado del juego, el algoritmo sencillamente computa los valores de los hijos del valor dado y elige el que tenga el valor máximo si es el turno de Max y el que tenga el valor mínimo si es el turno de Min.

El algoritmo se puede aplicar usando unas pocas líneas de código. Pero bueno, basta con que captes la idea general. Si quieres echar un vistazo al algoritmo en sí (advertencia: hay que saber programación),