Método min-max

Un método estándar para que una computadora juegue un juego de 2 participantes, es hacer uso de un “árbol de juego”. En el mismo, cada nodo representa una posición posible en el juego, y los arcos representan una movida o jugada posible.

En este ejemplo se considerará un juego de damas en un tablero 4×4, para simplificar la explicación.

La siguiente imágen muestra el árbol de juego de nuestro tablero de damas. El primer nodo representa el punto inicial. Los nodos del segundo nivel representan las 3 posibles jugadas que realizamos “nosotros”, las fichas negras. Y los nodos del tercer nivel representan las posibles jugadas de las fichas rojas (en el gráfico, blancas).

arbolexpandido

Ahora supongamos que analizamos los hijos de cada nodo del tercer nivel para poder determinar qué pasa después. En el caso del hijo izquierdo del nodo que está a la izquierda, el negro está a punto de perder, por lo que le asignamos un -1. El del medio será un empate, por lo que le asignamos un 0. Y el derecho está a punto de ganar, por lo que le asignamos un 1. De la misma forma, asignamos números a cada nodo del tercer nivel.

A partir de estos numeros, podemos suponer que en el caso en que el negro mueva la ficha como el primer nodo del segundo nivel,  el rojo elegirá la opción que nos haga perder, es decir, el nodo con el valor -1. De esta forma asignamos el valor mínimo de los hijos a cada nodo del segundo nivel. Es decir, resultaría en una secuencia -1, 0, -1.

Por lo tanto, elegimos el nodo con el valor mayor, en este caso el del medio que tiene el valor 0. De esta forma en el peor de los casos empataríamos.

El procedimiento ilustrado es el conocido como método min-max. En 1962 Arthur Samuel escribió un programa que juega damas usando este método, y le pudo ganar a un campeón estatal.

Sin embargo, en juegos más complicados como el ajedrez, el método es ineficiente ya que el árbol crecería desmesuradamente. Para solucionar dicho problema, existen estrategias como el procedimiento alpha-beta, que permite reducir el numero de operaciones de forma significativa.

 

Fuente:

Dewdney, A. (2001). The (new) Turing omnibus : 66 excursions in computer science. New York: Henry Holt.