ALGORITMOS MINIMAX Y NEGAMAX
Algoritmo Minimax
El
algoritmo Minimax es un procedimiento recursivo llamado también como algoritmo
de decisión que permite minimizar la pérdida máxima aplicada especialmente en
juegos de adversarios; este algoritmo nos brinda información completa del
adversario en un juego y a la vez encontrar la mejor jugada posible.
Minimax
tiene un corte de recursión dado por las siguientes condiciones:
·
Gana un 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.
El algoritmo Minimax, el espacio de
búsqueda está definido por:
·
Estado inicial:
Es una configuración inicial del juego, es decir, un estado en el que se
encuentre el juego.
·
Operadores:
Corresponden a las jugadas legales que se pueden hacer en el juego.
·
Condición Terminal:
Determina cuando el juego se acabó.
·
Implementación Minimax:
Los pasos que sigue minimax pueden variar, pero lo importante es tener una idea
clara de cómo es su funcionamiento, los pasos a seguir son:
v Generación del
árbol de juego.
Se generarán todos
los nodos hasta
llegar a un estado terminal.
v Cálculo de
los valores de la función
de utilidad para cada nodo
terminal.
v Calcular
el valor de los nodos superiores a
partir del valor
de los inferiores.
Alternativamente se elegirán los valores mínimos y
máximos representando los
movimientos del jugador
y del oponente, de ahí el nombre de Minimax.
v Elegir la
jugada valorando los
valores que han llegado al nivel
superior
§ Generación del
árbol de juego.
Se generarán todos
los nodos hasta
llegar a un estado terminal.
§ Cálculo de
los valores de la función
de utilidad para cada nodo terminal.
§ Calcular
el valor de los nodos superiores a
partir del valor
de los inferiores. Alternativamente se elegirán los
valores mínimos y máximos
representando los movimientos del
jugador y del
oponente, de ahí el nombre de Minimax.
§ Elegir la
jugada valorando los
valores que han llegado al nivel
superior.
·
El
algoritmo explorará los
nodos del árbol
asignándoles un valor
numérico mediante una
función de utilidad,
empezando por los nodos terminales y subiendo hacia la raíz.
·
Colocar
0 ó 1
en los nodos
terminales dependiendo si gana
MIN o MAX
·
La función de utilidad definirá lo buena
que es
la posición para
un jugador cuando la alcanza.
·
Se
requiere de una
estrategia que garantice
llegar a estados
terminales ganadores independientemente de
lo que haga el oponente.
·
Un
valor positivo indica
la ventaja de
un jugador y
uno negativo la
ventaja del otro.
·
El jugador que espera valores positivos se
conoce como maximizador.
·
El
jugador que espera
valores negativos se
conoce como minimizador.
·
El
maximizador busca movimientos
que lo conduzcan
al mayor número
positivo.
·
El minimizador busca
movimientos que lo
conduzcan al menor
número negativo.
·
Desde
el punto de
vista del maximizador, el minimizador puede escoger 2
ó 1.
·
Los
resultados de un
nivel determinan la
acción y el
resultado del nivel
inmediato superior
Ejemplo:
Juego de Tres en Raya:
v Dos
jugadores MIN y MAX
v Los
jugadores colocan fichas en un tablero de 3 X 3
v MAX
usa las fichas X
v MIN
usa las fichas O
Reglas:
v Inicialmente
el tablero está vacío
v MAX
empieza y se alternan los movimientos.
v MAX
gana si obtiene una línea de 3 X’s
v MIN
gana si obtiene una línea de 3 O’s
v Existe
la posibilidad de empate.
Espacio de Estado para Tres en Raya:
Procedimiento:
v Se
desarrolla una búsqueda por niveles, generando los nodos del cada nivel.
v Se aplica
una función de
evaluación a cada nodo.
v La
función de evaluación
considera los siguientes factores:
o
Número de casillas restantes.
o
Posición de casillas vacías.
v La
función de evaluación
devolverá los siguientes valores:
o
Positivos altos: Si la
situación de uno de los jugadores es ventajosa.
o
Negativos altos: Si la
situación del otro jugador es ventajosa.
o
Cero:
Si ninguno de
los jugadores tiene ventaja.
Función de Evaluación para el Tres en
Raya:
v Si
s no
es ganadora para
cualquiera de los jugadores (MAX o MIN):
f(s)=No.
filas abiertas para MAX - No. Filas, columnas o diagonales abiertas para MIN
f(s)=
No. Líneas que no contiene una “O” – No. Líneas que no contienen una “X.
Esto
es:
v Si
S es ganadora para el jugador MAX.
f(s)=
∞ (mayor número positivo posible)
v Si
s es ganadora para el jugador MIN.
f(s)=
-∞ (mayor número negativo posible)
v MAX elegirá
los nodos de
mayor evaluación.
v MIN elegirá
los nodos de
menor evaluación f(s)= -∞
(mayor número negativo posible).
Caso
Práctico de función de Evaluación del Tres en Raya:
v Se
define la función de evaluación:
f(s)=NMAX(s)-NMIN(s)
donde:
v S:
Situación o distribución del tablero
v f(s): Función
de evaluación del
tablero (nodo del espacio de
estados)
v NMAX(s): No.
de filas, columnas
o diagonales abiertas
para MAX (donde
aún puede ganar)
v NMIN(s):
No. de filas, columnas o diagonales abiertas
para MIN (donde
aún puede ganar)
Espacio de Estados:
v Primera
Etapa:
v Segunda
Etapa:
v Tercera
Etapa:
Algoritmo Negamax
Es
un algoritmo basado en minimax, pero está es más compacta. Negamax es una
variante del algoritmo minimax donde cada nodo independientemente si fuese MIN
o MAX toma el valor máximo de sus hijos (como si todos los nodo fueran MAX),
solo que los valores de los nodos MAX se cambian de signo (de ahí su nombre, en
vez de tomar máximos y mínimos toma siempre máximos pero con valores
cambiados). De esta forma se logra el mismo efecto ya que tomar el mayor valor
pero cambiado de signo es en realidad tomar el menor así cuando el algoritmo
está en un nivel MIN cuando toma el mayor de sus hijos en realidad está tomando
al menor.
La
función Negamax podría recibir como parámetro un signo, de esta manera se
podría comenzar por niveles MIN o niveles MAX, pero no necesariamente ya se
puede establecer niveles estáticos, donde cada nivel está definido por un signo
distinto.
No
utiliza las funciones de Max y Min, en vez de estos utiliza la siguiente
función matemática que traduce en una búsqueda de la Máxima, permitiendo la
posibilidad de simplificar el código:
max(a,b) == – min(-a, -b)
Maneja
valores positivos para la máquina y negativos para las del adversario.
Evidentemente a esta
versión comprimida del MiniMax también puede aplicársele la poda alfa-beta
acortando el tiempo de ejecución.
Ejemplo:
Donde
estado_final() verifica si se llegó a un estado de corte de recursión,
evaluacion_heurística() devuelve el valor heurístico del nodo,
movimiento_posible() es un movimiento dentro del sub-árbol de todos los
movimientos posibles, mover() efectúa el movimiento para luego hacer un
Backtracking.
REFERENCIAS:
Comentarios
Publicar un comentario