Principio Minimax

ANTECEDENTES EN LA FORMULACIÓN DEL PRINCIPIO MINIMAX Y DEL PRINCIPIO MAXIMIN:

Principio Minimax consiste en que un jugador A escoge sólo aquella estrategia que en caso de ser derrotada sólo le dará al oponente B una recompensa cuyo valor siempre es el mínimo que podría obtener frente a otras pérdidas aún mayores que podría sufrir el jugador A si hubiera usado otra estrategia distinta a su alcance.

FUNCIONAMIENTO DEL PRINCIPIO MINIMAX Y DEL PRINCIPIO MAXIMIN EN UN ÁRBOL DE NODOS:

Maximin y el Principio Minimax se pueden aplicar principalmente en los juegos estratégicos de tipo Combinatorio (la movida de cada jugador condiciona el abanico de las siguientes movidas a realizar), Secuenciales (los que se juegan por turnos entre oponentes), de Información Perfecta, de Suma Cero (un jugador sólo puede ganar un punto si el oponente pierde el mismo valor) y en los que no interviene el azar, como ocurre en el ajedrez, las damas (English Draughts o Checkerso Damas Internacionales), el NIm, el go, el ajedrez chino (Xiangqi), el ajedrez japonés (Shogi), el Juego del Molino (NineMen’sMorris), el Tres en Línea (Tic Tac Toe), el Reversi, el Conecta Cuatro, el konane, el chaturanga, el hex, etc.

Para aplicar el Principio Maximin y el Principio Minimax en juegos estratégicos como los antes mencionados cuando son representados de forma extensiva mediante un árbol de decisiones o nodos, se tienen en cuenta las siguientes reglas:

a−) Se construye el respectivo árbol de decisiones, incluyendo toda posible ramificación y nodo, desde el Nodo Raíz hasta llegar a todos los Nodos Terminales; b−) Se deben valorar los nodos terminales mediante una Función de Utilidad, la cual le asigna un valor positivo a los nodos que representan el camino hacia una victoria o recompensa para el jugador que aplica el Principio Maximin y le asigna un valor negativo a los nodos que representan el camino hacia una victoria o recompensa para el jugador que aplica el Principio Minimax. Si un nodo terminal representa un empate o un estado del juego en que ya no es posible realizar un movimiento legal, entonces el valor asignado es cero;

c−) Los valores positivos (Valor Maximin) o los valores negativos (Valor Minimax) asignados a los nodos terminales se propagan desde éstos por cada ramificación hacia los nodos de los niveles superiores hasta llegar al nodo raíz, para lo cual se sobreentiende que el jugador que tiene el primer turno siempre aplica el Principio Maximin (MAX) y por tanto un nodo de MAX siempre toma el valor del nodo sucesor o nodo terminal con el mayor valor, mientras que en contraste el jugador que tiene el segundo turno siempre aplica el Principio Minimax (MIN) y por tanto un nodo de MIN siempre toma el valor del nodo sucesor o nodo terminal con el menor valor; y,

d−) Para trazar la solución más óptima del juego entre las ramificaciones del árbol una vez le han sido asignados a todos los nodos los respectivos valores positivos o negativos, se sobreentiende que cada jugador siempre elige en su turno el movimiento que conduce al estado sucesor del actual con mejor valoración según le corresponda aplicar el Principio Maximin o el Principio Minimax.

Un ejemplo clarifica la aplicación de lo anterior. Supongamos un juego de Nim con una pila inicial conformada por 6 fichas. Cada jugador en su turno sólo puede retirar 1, 2 ó 3 fichas de la pila según su libre decisión, de tal forma que gana el juego el jugador que logre obligar a su oponente a retirar la última ficha que quede de la pila. El primer jugador A aplica la estrategia Maximin (MAX), por tanto en su turno siempre elige la movida de mayor valor, mientras que el jugador B aplica la estrategia Minimax (MIN) y por tanto en su turno siempre elige la movida de menor valor. El siguiente es el árbol de decisiones de este juego:

En la anterior gráfica los números dentro de los círculos rojos son nodos que indican la cantidad de fichas que quedan en la pila después de que cada jugador en su turno retiró 1, 2 ó 3 fichas según las ramificaciones que representan las posibles movidas que derivan de cada estado del juego. Los nodos terminales sombreados de color verde son estados del juego que equivalen a una victoria de A, mientras que los nodos terminales sombreados de color lila son estados del juego que equivalen a una victoria de B. Los nodos terminales que equivalen a una victoria de A tienen al lado de la ramificación un 1 que es el valor que les corresponde al aplicar la Función de Utilidad teniendo en cuenta el Principio Maximin, mientras que los nodos terminales que equivalen a una victoria de B tienen al lado de la ramificación un −1 que es el valor que les corresponde al aplicar la Función de Utilidad teniendo en cuenta el Principio Minimax. La propagación de estos valores hacia los nodos de los niveles superiores se realiza considerando que si A en su turno tiene varias ramificaciones que equivalen a posibles movidas que puede realizar, entonces bajo el Principio Maximin siempre elegirá la que conduce al nodo de mayor valor posible (1) y descartará las ramificaciones que conducen a nodos de menor valor (−1), mientras que si B en su turno tiene varias ramificaciones que equivalen a posibles movidas que puede realizar, entonces bajo el Principio Minimax siempre elegirá la que conduce al nodo de menor valor posible (−1) y descartará las ramificaciones que conducen a nodos de mayor valor (1).

Por supuesto, los jugadores A (MAX) y B (MIN) sólo pueden escoger entre un valor positivo y un valor negativo cuando en su respectivo turno disponen de alternativas que permiten hacer esa elección. Cuando en el turno de un jugador sólo existe una única ramificación que representa una movida, necesariamente el jugador debe realizar esa movida independientemente de su valor positivo o negativo, ya que se trata de una jugada forzada. Del mismo modo, cuando el juego está «Determinado», entonces llega un momento en que se hace realidad el Teorema de Zermelo, es decir, el Valor Maximin de la mejor movida elegida por A es igual al Valor Minimax de la mejor movida elegida en respuesta por B. En efecto, en la anterior gráfica se observa que este juego de Nim está determinado a favor del jugador A desde el primer movimiento que él realiza, ya que en su primer turno le corresponde el valor de −1 a la opción de retirar 3 fichas para reducir la pila a 3, también tiene el valor de −1la opción de retirar 2 fichas para reducir la pila a 4, y tiene el valor de 1 retirar una sola ficha para reducir la pila a 5, por tanto, al aplicar el Principio Maximin, su mejor jugada es la última que tiene un valor de 1 que es mayor al de las otras dos opciones. Dentro de esa ramificación cuando le corresponde el turno a B, éste encuentra que tiene tres alternativas de movimientos, pero todas

...