Next: Alfabeta: Haciendo Minimax Factible
Up: Técnicas de Búsqueda
Previous: Técnicas de Búsqueda
  Índice General
Cuando el juego de ajedrez se inicia las blancas eligen uno entre
20 movimientos posibles. Siguiendo el movimiento de las blancas,
las negras tienen 20 opciones de respuesta cualquiera haya sido la
elección de las blancas.
De acuerdo a esto, 400 posiciones distintas pueden surgir sólo de
la primera jugada de una partida de ajedrez. Luego de 2 jugadas el
número de posiciones posibles crece sobre las 20.000, llegando a
una cifra astronómica luego de varias jugadas más. El "árbol de
ajedrez" posee más posiciones que la cantidad de átomos presentes
en la via láctea. De acuerdo al reglamento del juego una partida
es tablas (empate) si transcurren 50 jugadas sin que se haya
realizado algún movimiento de peón y sin que se haya producido
algún cambio de pieza, por lo cual según algunos cálculos una
partida de ajedrez puede durar como máximo 3150 jugadas
[6], por lo que el árbol de variantes puede tener una
cantidad de posiciones limitada a esta cantidad.
Si fuese posible examinar el árbol por completo, buscando todas
las líneas de juego y sus conclusiones sería posible determinar
cuál es el mejor movimiento inicial. Sin embargo, en la práctica
el árbol es demasiado extenso para considerar este mecanismo.
Incluso el determinar el mejor movimiento buscando en el árbol de
variantes a partir de una avanzada posición de medio juego resulta
imposible. Lo mejor que puede realizarse es buscar en un sector
limitado del árbol de variantes, esperando obtener suficiente
información con tal de decidir correctamente cual es el mejor
movimiento.
En los inicios de 1970 la búsqueda en árboles de variantes
alcanzaba la cantidad aproximada de 200 posiciones por segundo.
Hoy (año 2003), DEEP BLUE busca en 2.000.000 de posiciones por
segundo. Los mejores programas logran examinar todas las
secuencias de movimientos con una profundidad de 8 a 10 movidas en
el árbol (4 a 5 jugadas por bando).
Líneas de juego cruciales como jaques y capturas tienen una
profundidad de búsqueda aún mayor. En la jerga de programas de
ajedrez, una búsqueda de fuerza bruta de 6 movimientos
significa una búsqueda de todos los movimientos posibles para cada
bando hasta una profundidad de 6 niveles (3 jugadas por bando) y
con mayor profundidad en líneas altamente tácticas.
Para un árbol de variantes dado, el algoritmo minimax entrega una
regla para decidir qué movimiento realizar frente a una posición
dada. El algoritmo comienza calculando el valor numérico o puntaje
para la posición al final de cada variante. Estas posiciones son
denominadas Posiciones Terminales y su puntaje es
calculado por una Función de Evaluación. La función de
evaluación intenta medir cuan buena es la posición para el primer
jugador. Un puntaje positivo significa que la computadora tiene
ventaja, un puntaje negativo significa que su oponente tiene
ventaja.
El algoritmo entiende que el objetivo del primer jugador es llevar
al juego a una posición en la cual maximice su puntaje, mientras
que el objetivo del rival es el opuesto, lograr una posición que
sea mínima en puntaje. Esto es equivalente a plantear que en
niveles similares del árbol de variantes el algoritmo Minimax
asignará a cada posición no terminal un puntaje igual al máximo
puntaje de alguna de las posiciones sucesoras. En otras palabras,
la computadora tomará el movimiento que le reporta el mayor
beneficio para el movimiento siguiente. En los niveles impares
donde juega el oponente el algoritmo asignará a cada posición no
terminal un puntaje igual al mínimo de las posiciones sucesoras.
Dado que los puntajes de las posiciones sucesoras de una posición
no terminal deben ser conocidos con tal de dar un puntaje a esa
posición los puntajes de las posiciones terminales deben ser
determinados primero y luego los puntajes de las posiciones
restantes hasta llegar a la posición raíz.
En juegos de cálculo extenso como el ajedrez los programas pueden
examinar sólo una parte del árbol de variantes sin llegar hasta el
final del juego. En estos casos los programas buscan hasta un
cierto limite de nodos, estimando en ellos las posibilidades de
ganar de cada bando mediante la función de evaluación.
Figura:
Ejemplo de aplicación del algoritmo minimax.
|
Existen varios algoritmos que ayudan a mejorar la eficiencia del
Minimax. Uno de ellos es la poda Alfa-Beta, bajo la cual el
programa debe buscar sólo aproximadamente la raíz cuadrada del
numero de nodos que debería buscar sin esta implementación. Otras
implementaciones incluyen las tablas de transposición las cuales
guardan la información de posiciones ya examinadas. Ambas técnicas
son analizadas en puntos siguientes.
Desafortunadamente el algoritmo minimax es de un orden O(bn)
donde b (factor de anchura) es el número de movimientos legales
disponibles en promedio en cualquier momento y n(profundidad) es
el número de movimientos que se calculan, donde un movimiento es
una movida de un bando. Este número crece en forma exponencial a
medida que la profundidad aumenta, por lo cual una considerable
cantidad de trabajo ha sido hecha con tal de desarrollar
algoritmos que minimicen el esfuerzo realizado en buscar
movimientos a una determinada profundidad.
Next: Alfabeta: Haciendo Minimax Factible
Up: Técnicas de Búsqueda
Previous: Técnicas de Búsqueda
  Índice General
Santiago de Chile, Julio 2003