• Author / Uploaded
• Bryancito Chumbes Lizarraga

Citation preview

Universidad César Vallejo - Lima Este

“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

Universidad César Vallejo - Lima Este

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.

Universidad César Vallejo - Lima Este

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.

Universidad César Vallejo - Lima Este 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

Universidad César Vallejo - Lima Este

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.

Universidad César Vallejo - Lima Este 

α 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.

Universidad César Vallejo - Lima Este 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 ramificación eficaz será de

de Minimax. Esto implica que el factor 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 un valor moderado de

para

.

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.

Universidad César Vallejo - Lima Este 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.

Universidad César Vallejo - Lima Este 2. Implementación del Algoritmo Poda Alfa - Beta en el Juego del Acorralado

3. Desarrollo del Algoritmo Minimax con Poda AlfaBeta como Estrategia para el Juego Othello en Common Lisp

Universidad César Vallejo - Lima Este 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