Algoritmo MiniMax - Negamax
Algoritmo MiniMax:
El algoritmo mimimax consiste en elegir el mejor movimiento para la maquina, este algoritmo permite minimizar la pérdida máxima aplicada en juegos de adversarios.
Es recursivo y el corte de la recursión se da por las siguientes condiciones:
Gana algún jugador.
Se han explorado N capas, siendo N el límite establecido o 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.
Para el algoritmo MINIMAX tenemos los siguientes pasos:
- Generar el árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.
- Calcular 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.
Algoritmo Negamax:
Podemos definir al algoritmo Negamaz como una mejora del algoritmo minimax, ya que cambia los valores de los nodos Max de esta forma: Max (x, y) = -min (-x, -y), consiguiendo el mismo resultado que el Minimax, pero tomando el mayor, buscando obtener el resultado mas conveniente.
Las elecciones que el algoritmo toma están orientadas a la manera en la que la heurística está estructurada de forma que logre minimizar la pérdida máxima en un juego con adversario.
La ventaja del algoritmo Negamax es que al final satisface la resolución de problemas de búsquedas sencillos encontrando una solución óptima.
No es recomendable para problemas complejos, ya que este debe realizar un recorrido en todos los nodos sin embargo Negamax cuenta con una mejora que es Negascout.
Ocupa mucho espacio en memoria debido a que recorre todos los nodos que presenta un árbol.
A continuación se presenta el algoritmo Negamax:
ç
En la imagen se puede apreciar los metodos:
Estado_final(): se encarga de verificar si el recorrido llegó a un nodo hoja, o sin ramificación.
Evaluacion_heurística(): devuelve el valor heurístico del nodo.
Movimiento_posible(): se encarga verificar que el nodo tenga ramificaciones o nodos hijos no visitados para su posible movimiento dentro del sub-árbol.
Mover(): se encarga de moverse entre los nodos hijos.
REFERENCIAS:
Elegir la jugada valorando los valores que han llegado al nivel superior.
ç
Comentarios
Publicar un comentario