Juego con adversario

Juegos CON adversario
Algoritmo MINIMAX
En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento de búsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada. La idea consiste en comenzar en la posición actual y usar el generador de movimientos plausibles para generar las posibles posiciones sucesivas hasta un cierto límite de niveles. Acontinuación se aplica la función de evaluación estática a las posiciones obtenidas y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores. Se supone una función de evaluación estática que devuelve valores elevados para indicar buenas situaciones y valores negativos para indicar buenassituaciones para el oponente. Visto de esta manera, la meta es maximizar el valor de la función estática de la siguiente posición de tablero. El nombre del algoritmo deriva de considerar que, dada una función estática que devuelve valores en relación al jugador maximizante, éste procura maximizar su valor mientras que su oponente procura minimizarlo. En un árbol de juego donde los valores de la funciónestática están en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro. La figura 1 muestra un ejemplo donde la elección del siguiente movimiento según la búsqueda Minimax de tres niveles sería el nodo D. El algoritmo Minimax es un procedimiento recursivo, y el corte de la recursión está dado por alguna de las siguientes condiciones:
* Gana algún jugador* Se han explorado N capas, siendo N el límite establecido
* Se ha agotado el tiempo de exploración
* Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro
En el algoritmo MINIMAX detallado en breve la función de corte de recursión SUFICIENTE (posición, profundidad) sólo considera las dos primeras condiciones de corte

El algoritmo MINIMAX(posición, profundidad, jugador) usa dos funciones:
* GENMOV (posición, jugador): devuelve la lista de movimientos posibles para el jugador a partir de la posición
* ESTÁTICA (posición, jugador): devuelve un número que representa la bondad de la posición desde el punto de vista de jugador.
A diferencia de los valores mostrados en el ejemplo de la figura 1, la función ESTÁTICA devuelvevalores en relación al jugador actual en vez del jugador maximizante. Por esta razón, en lugar de realizar maximización y minimización alternativas, siempre se maximiza el valor que devuelve esta función.
El algoritmo MINIMAX no necesita tratar diferente a los niveles maximizante y minimizante dado que invierte los valores de un nivel a otro. La función Minimax devuelve una estructura con
*VALOR: valor propagado de la función estática
* CAMINO: camino para llegar a la solución desde la posición
La primera llamada a la función recursiva será:
MINIMAX (posiciónactual, 0, JUGADOR-UNO)
El algoritmo MINIMAX es el siguiente: MINIMAX( posición, profundidad, jugador)
comienzo
Si SUFICIENTE (posición, profundidad) entonces
resultado.VALOR := ESTATICA (posición, jugador);resultado.CAMINO := NULO;
return resultado;
sino
Sucesores := GENMOV (posición, jugador);
Si EstaVacia (Sucesores) entonces
resultado.VALOR := ESTATICA (posición, jugador);
resultado.CAMINO := NULO;
return resultado;
sino
resultadoMejor.VALOR := MININT;
por cada sucesor de Sucesores
resultadoSucesor := MINIMAX (sucesor, profundidad+1, CONTRARIO (jugador));
SiresultadoMejor.VALOR < - resultadoSucesor.VALOR entonces
resultadoMejor.VALOR := - resultadoSucesor.VALOR;
resultadoMejor.CAMINO := sucesor + resultadoSucesor.CAMINO;
fin si;
fin por;
return resultadoMejor;
fin sino;
fin sino;
fin MINIMAX;

Teorema Minimax
John von Neumann es el creador del teorema minimax, quien dio la siguiente noción de lo que era un juego:
"Un juego es una situación...