Minimax: construyendo el árbol
| < Minimax: la larga búsqueda | [Cheoss] [índice] | Alfabeta: el árbol podado > |
Repitiendo el proceso del minimax el número suficiente de veces en teoría es posible construir el árbol completo de variantes del juego del ajedrez y jugar la partida perfecta. En la práctica por supuesto esto no es posible debido al inimaginable número de posiciones que habría que calcular.
Observemos la representación gráfica del árbol de variantes. Empieza de un único punto de partida (la posición inicial marcada en el diagrama con ?).
En los primeros niveles hay pocas ramas, pero aumentan rápidamente con cada nivel. El esquema anterior está muy simplificado, en relidad en la posición inicial de una partida de ajedrez las blancas pueden elegir entre 20 posibles movimientos, no 3 como en el gráfico.
Puesto que existen 20 movimientos legales, al realizarlos sobre el tablero tendremos 20 posiciones en el segundo nivel. Supongamos que para cada una de estas posiciones resultantes del primer nivel también hay 20 movimientos posibles. Tras llamar al generador de movimientos y aplicar la lista de jugadas en el tablero obtenemos 20 x 20 = 400 posiciones en el tercer nivel.
En el tercer nivel ya partimos con 400 posiciones, si seguimos suponiendo que en cada una de ellas hay 20 jugadas para escoger tenemos por tanto 400 x 20 = 8000 posiciones en el siguiente paso.
Si seguimos realizando las operaciones suponiendo siempre 20 jugadas legales por cada posición nos encontramos con un árbol de 1.280 millones de posiciones en el nivel 6 y 25.600 millones en el nivel 7.
Es fácil comprobar que el crecimiento del árbol de variantes es explosivo.
En el ejemplo hemos llegado hasta el séptimo nivel, o lo que es lo mismo, 7 medias jugada o 3 jugadas completas y un movimiento. Para ver una linea de tres jugadas ya estamos obligados a calcular 25.600 millones de jugadas.
Y la realidad es peor todavía: hemos supuesto 20 jugadas posibles en cada posición, una cifra más realista sería entre 30 y 35 movimientos posibles para una posición de medio juego.
El hecho es que el conjunto de posiciones distintas que pueden darse en una partida de ajedrez es tan enorme que continúa siendo inabarcable para los ordenadores actuales.
Es por eso que el algoritmo minimax, que en teoría es capaz de encontrar la mejor jugada posible en los juegos llamados de información completa y suma cero, no funciona en la práctica con el ajedrez. La clave es el factor de ramificación.
La rapidez de crecimiento del árbol de jugadas en cualquier juego está relacionada con el "factor de ramificación" que podemos definir como el número medio de jugadas legales que tiene un jugador a su disposición.
Según esta definición un juego como el tres en raya tiene un factor de ramificación de 3. El ajedrez tiene un factor mucho más alto: alrededor de 35, esto lo convierte en un hueso muy duro de roer para el minimax.
Existen otros juegos, como el go, para los cuales el factor de ramificación es todavía más alto: un jugador de este juego puede elegir entre 100 jugadas legales por término medio en una posición determinada. Sin duda esto explica por qué todavía no se ha conseguido hacer un programa que juegue bien al go.
| < Minimax: la larga búsqueda | [Cheoss] [índice] | Alfabeta: el árbol podado > |
