ALGORITMO MINIMAX
Este
algoritmo de decisión se utiliza para minimizar la pérdida máxima aplicada en
juegos entre adversarios. La Información es completa ya que cada jugador conoce
el estado del otro, y puede elegir el mejor movimiento para cada jugador,
suponiendo que el contrincante escogerá el peor. Devuelve la acción
correspondiente al movimiento mejor posible, es decir, el movimiento que
conduce al resultado con la mejor utilidad, conforme al axioma que el oponente
juega para minimizar la utilidad. Las funciones Valor-Max y el Valor-Min pasan
por el árbol de juegos enteró, por todos los caminos hacia las hojas, para
determinar el valor que le llega a un estado.
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.
De forma
más detallada, la idea consiste en comenzar en la posición actual del juego y
usar el generador de movimientos legales para generar las posibles posiciones
sucesivas hasta un cierto límite de niveles (si es posible porque el juego lo
permita, se desarrolla el árbol completo de juego hasta las posiciones
finales). A continuación, se aplica una función de evaluación estática, que es
capaz de decir lo bueno o malo que es cada estado, a los últimos estados
obtenidos 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.
Habitualmente,
se suele trabajar con una función de evaluación que devuelve valores positivos
para indicar buenas situaciones para el jugador que hace uso del algoritmo, y
valores negativos para indicar buenas situaciones para el adversario. Así
planteado, el objetivo es maximizar el valor de esta función estática sobre las
posibles jugadas que se pueden hacer desde la posición actual del juego.
De este
mecanismo es de donde viene el nombre del algoritmo: dada la función evaluadora
estática, el jugador que hace uso del algoritmo intenta maximizar su valor,
mientras que el adversario intenta minimizarlo. En un árbol de juego donde los
valores de la función evaluadora se calculan en relación al jugador
maximizante, se maximiza y minimiza alternadamente de un nivel a otro hasta
llegar al nivel actual de juego.
Formalmente,
los pasos del algoritmo Minimax son:
- Generación del árbol de
juego: Se generan todos los nodos hasta llegar a un estado terminal (si no
podemos afrontar la generación del árbol completo, es posible aplicar los
pasos siguientes sobre una sección del mismo, aunque entonces no podremos
asegurar la optimalidad de los resultados).
- Se calculan los valores de
la función de evaluación para cada nodo terminal del árbol construido.
- Se evalúan los nodos
superiores a partir del valor de los inferiores. Según si estos nodos pertenecen
a un nivel MAX o un nivel MIN, se elegirán los valores mínimos y máximos
representando los movimientos del jugador y del oponente.
- Se repite el paso 3 hasta
llegar al nodo superior.
- Se selecciona la jugada-nodo
directamente accesible desde la jugada actual que optimiza el valor de la
evaluación.
PODA ALFA-BETA
La poda alfa beta es una técnica de búsqueda que reduce
el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se
trata de una técnica muy utilizada en programas de juegos entre adversarios
como el ajedrez, el tres en raya o el Go.
El problema de la búsqueda Minimax es que el número de
estados a explorar es exponencial al número de movimientos. Partiendo de este
hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol,
aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo
movimiento que devolvería este, gracias a que la poda de dichas ramas no
influye en la decisión final.
EJEMPLO
EJERCICIO
Algoritmo
MiniMax
posición inicial
PASOS DEL ALGORITMO MINIMAX
1. Generar el árbol de juego. Se generarán todos los
nodos hasta llegar a un estado terminal.
2. Calcular los valores de la función de utilidad para
cada nodo terminal.
3. 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.
4. Elegir la jugada valorando los valores que han llegado
al nivel superior.
Posición final
EJERCICIO MINIMAX
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
class Minimax{ //Clase Minimax
private:
const int MAX = 1000; //Valores para alfa y beta
const int MIN = -1000;
public:
Minimax();
int proceso(int, int, int, bool, int[], int, int);
~Minimax();
};
Minimax::Minimax()
{
cout<<"Construyendo Arbol"<<endl;
}
Minimax::~Minimax()
{
cout<<"Destruyendo Arbol"<<endl;
}
int Minimax::proceso(int niveles, int depth, int nodeIndex, bool maximizingPlayer, int values[], int alpha, int beta)
{
if (depth == niveles)
return values[nodeIndex];
if (maximizingPlayer) //Función que realiza el proceso del MINIMAX
{
int best = MIN;
for (int i = 0; i < 2; i++)
{
int val = proceso(niveles, depth + 1, nodeIndex * 2 + i, false, values, alpha, beta);
best = max(best, val);
alpha = max(alpha, best);
if (beta <= alpha)
break;
}
return best;
}
else
{
int best = MAX;
for (int i = 0; i < 2; i++)
{
int val = proceso(niveles, depth + 1, nodeIndex * 2 + i, true, values, alpha, beta);
best = min(best, val);
beta = min(beta, best);
if (beta <= alpha)
break;
}
return best;
}
}
int main()
{
Minimax x; //Objeto Minimax
int cant;
int MIN, MAX;
int par ;
do{
cout<<"Ingrese el numero de nodos del nivel final del arbol: ";
cin>>cant;
par = cant % 2;
if(par != 0){
cout<<"El numero de nodos debe ser par"<<endl;
}
}while(par != 0);
int prof= log2(cant);
int values[cant];
for(int i=0; i<cant; i++){
cout<<"Ingrese un valor para el "<<i+1<<" nodo: ";
cin>>values[i];
}
cout<<endl<<"El valor optimo para este arbol es: "<< x.proceso(prof, 0, 0, true, values, MIN, MAX);
cout<<endl;
return 0;
}
No hay comentarios:
Publicar un comentario