Post on 29-Nov-2015
“Año de la Integración Nacional y el Reconocimiento de Nuestra Diversidad”
Curso:
Inteligencia Artificial
Docente:
Ing. Saúl Pérez
Tema: Algoritmo Minimax.
Alumnos:
Aranda Palomino, Rosa Elizabeth.
Chávez Ganoza, Fiorella Stefany.
Chumbes Lizárraga, Bryan.
Contreras Taype, Milagros.
Marco Cárdenas, Jeyson.
Lima Este – 2012
Introducción
La inteligencia Artificial, es una campo de que ha tomado gran interés en
los últimos tiempos debido a su capacidad de poder resolver soluciones imitando
el razonamiento lógico de las personas y hasta el mecanismo de cómo ellas la
resuelven.
Un tema interesante a tratar a lo que concierne a la Inteligencia Artificial
son los juegos. Los juegos han sido estudiados a lo largo de la historia
formulándose incluso modelos matemáticos que permitiesen desarrollarlos.
En un principio, estos juegos fueron estudiados por una rama de la ciencia
denominada Investigación Operativa, la cual proporcionaba técnicas que solo
podrían ser aplicables si existía un procedimiento finito. Con el surgimiento de la
Inteligencia Artificial se crean nuevos algoritmos de búsquedas que permiten
desarrollar soluciones dentro de procedimientos no finitos.
Uno de estos algoritmos es el algoritmo Minimax, que es una técnica que
se centra en la resolución de problemas de búsquedas, basadas en la alternación
de dos entes o agentes a los cuales se les denominan Min y Max utilizando Poda
Alpha-Beta que es muy usado en la teoría de Juegos y que permite encontrar
soluciones dentro de un campo de búsquedas infinito.
Algoritmo MiniMax Utilizando Poda Alpha-Beta
Algoritmo Mini Max:La estrategia MiniMax es una estrategia de búsqueda exhaustiva mediante
un árbol de búsqueda. Este algoritmo considera el caso de 2 participantes a los
que se les denomina Max y Min.
El que inicia el juego es Max y existe una alternancia en la participación del
juego. Por lo tanto lo que tiene que hacer Max, es determinar la secuencia de
jugadas que conduzca a un estado Terminal ganador o favorecedor.
En teoría de juegos, Minimax es un método de decisión para minimizar la
pérdida máxima esperada en juegos con adversario y con información perfecta.
Este cálculo se hace de forma recursiva.
El funcionamiento de Minimax puede resumirse como elegir el mejor
movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para
ti.
Es un algoritmo inteligente, que tiene una base de conocimientos el cual
tiene como objetivo almacenar jugadas realizadas cada vez que inicia un juego o
de acuerdo a los movimientos y al historial que tiene con respecto a ellos.
Una vez que ya ha tenido recorrido juegos lo que empieza hacer este
algoritmo es aplicar la experiencia obtenida a nuevos juegos. Este algoritmo es
imparcial pues busca que el oponente realice jugadas que no beneficien tanto su
estrategia de juego.
Ventajas:
El algoritmo tiene la capacidad de aprender de acuerdo a una base de
datos histórica de movimientos realizado, es decir, aprende con la
experiencia
El algoritmo será infalible o un gran oponente a vencer entre más juegos y
movimientos tenga en su historial.
Aprende del oponente y al tiempo le da ventaja (para luego utilizar las
estrategias del oponente en otros juegos).
Desventajas:
El algoritmo tiene una complejidad muy elevada de implementación, pues
el hecho de estructurar una base de datos de experiencia requiere de
armar y estructurar un esquema de aprendizaje óptimo.
Es lento de aprendizaje, pues por cada jugada realizada y el conjunto de
las que tiene almacenadas lo obliga a implementar algoritmos de
comparación, búsqueda, inserción, etc.
Por cada nuevo oponente deberá implementar estructuras de aprendizaje,
pues no todos los oponentes juegan de la misma forma.
El algoritmo solo funciona para enfrentar un oponente a la vez
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.
Alfa-beta es un algoritmo BPP, rama y cota, que avanza por el árbol en un
orden ya fijado (de izquierda a derecha) y va usando la información de la
valuación de los nodos hoja para podar ramas dominadas que no sirven para
cambiar el valor MiniMax del nodo inicio (la jugada inminente).
Es una técnica mejorada del algoritmo MiniMax, que consiste en dividirlo en
la mitad. La jugada es que es posible calcular la decisión mínima correcta sin
mirar todos los nodos en el árbol de juegos. La poda Alfa-Beta puede aplicarse a
arboles de cualquier profundidad y también subárboles enteros.
Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel,
D.J Edwards y T.P. Hart, Alan Kotok, Alexander Brudno, Donald Knuth y Ronald
W. Moore4
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.
Desarrollo del algoritmo:
La búsqueda MiniMax es primero en profundidad, por ello en cualquier
momento sólo se deben considerar los nodos a lo largo de un camino en el árbol.
La poda alfa-beta toma dicho nombre de la utilización de dos parámetros
que describen los límites sobre los valores hacia atrás que aparecen a lo largo de
cada camino.
α es el valor de la mejor opción hasta el momento a lo largo del camino para
MAX, esto implicará por lo tanto la elección del valor más alto
β es el valor de la mejor opción hasta el momento a lo largo del camino para
MIN, esto implicará por lo tanto la elección del valor más bajo.
Esta búsqueda alfa-beta va actualizando el valor de los parámetros según
se recorre el árbol. El método realizará la poda de las ramas restantes cuando el
valor actual que se está examinando sea peor que el valor actual de α o β para
MAX o MIN, respectivamente.
Características:
Omitir la expansión de nodos que por sus valores no pueden se los
mejores (peores).
Interrumpe la búsqueda en algún nivel y aplica evaluaciones heurísticas a
las hojas (profundidad limitada).
Si el valor del nodo MAX (Alfa) es menor que el más alto hasta este
momento, entonces omite el nodo.
Si el valor del nodo MIN (Beta) es mayor que el nodo más bajo hasta este
momento, entonces omite el nodo.
Alfa-Beta permite la búsqueda dos veces más profunda.
Problema de la búsqueda MiniMax: el número de estados que tiene que
examinar es exponencial con el número de movimientos.
El exponente no se puede eliminar, pero se puede dividir en la mitad.
Es posible calcular la decisión MiniMax correcta sin mirar todos los nodos
en el árbol.
La poda alfa-beta permite eliminar partes grandes del árbol, sin influir en la
decisión final.
Eficacia de la poda alfa-beta:
La eficacia de la poda Alfa-Beta depende del orden en el que se examinan
los sucesores, es decir, el algoritmo se comportará de forma más eficiente si
examinamos primero los sucesores que probablemente serán los mejores.
Si esto pudiera hacerse, implicaría que Alfa-Beta sólo tendría que examinar
en lugar de los de Minimax. Esto implica que el factor de
ramificación eficaz será de en lugar de . En otras palabras, alfa-beta podría
mirar hacia delante aproximadamente dos veces más que Minimax en la misma
cantidad de tiempo.
Si se recurre a una ordenación aleatoria en lugar de primero el mejor en los
sucesores, el número aproximado de nodos examinados sería de para
un valor moderado de .
En ajedrez se puede realizar una función de ordenación sencilla teniendo
en cuenta primero capturas de fichas, después amenazas, movimientos hacia
delante y por último movimientos hacia detrás, esto conseguiría aproximadamente
un factor de dos del resultado del mejor caso. La inclusión de esquemas
dinámicos para ordenar movimientos, basados en experiencia podría acercarse al
límite teórico.
APLICACIONES
1. Aplicación Del Algoritmo Poda Alpha-Beta Para La Implementación Del Juego “Ajedrez”
El juego del ajedrez es un juego adecuado para tratarlo mediante
técnicas de IA debido a que tiene claramente definidos el objetivo que se quiere
alcanzar (meta) y los medios para llegar (movimientos permitidos) .
En este juego, el programa en todo momento debe conocer la
configuración del tablero para la maquina poder tomar la decisión adecuada
(jugada), que le permita ganar.
Para ello necesita de gran capacidad de almacenamiento de información,
utilizando estructuras que le permitan llegar a conclusiones coherentes.
2. Implementación del Algoritmo Poda Alfa - Beta en el Juego del Acorralado
3. Desarrollo del Algoritmo Minimax con Poda Alfa-Beta como Estrategia para el Juego Othello en Common Lisp
Se implementó el algoritmo MiniMax con poda alfa-beta como estrategia
para crear un adversario robusto en el juego de Othello en Common Lisp.
Las heurísticas utilizas fueron dos: la diferencia de fichas de los jugadores
para determinar quién va ganando, y la segunda es una heurística basada en
pesos según las posiciones que se consideran mejores que otras.
Con base a las pruebas realizadas la mejor heurística fue la heurística de
las esquinas que proporciona una visión adelantada más detallada del juego para
volver robusto al jugador artificial.
4. Tres en Raya en Prolog usando Algoritmo MINIMAX y Poda Alfa-Beta