Othello en lisp algoritmo alfabeta

Solo disponible en BuenasTareas
  • Páginas: 26 (6306 palabras)
  • Descarga(s): 3
  • Publicado: 13 de julio de 2010
Leer documento completo
Vista previa del texto
Desarrollo del Algoritmo Minimax con Poda Alfa-Beta como Estrategia para el Juego Othello en Common Lisp
Luis Fernando Espino Barrios Instituto Tecnológico de Costa Rica luisespino@yahoo.com Noviembre 2009

Resumen: Este artículo trata acerca del desarrollo del algoritmo minimax junto con la extensión de poda alfa-beta como estrategia para lograr un adversario robusto en el juego de Othello enCommons Lisp. La finalidad es la puesta en práctica de algoritmos de inteligencia artificial y claramente la construcción de un adversario que busca la mejor jugada basada en futuras decisiones del juego a través de arboles utilizando el algoritmo de minimax. Además se utilizaron dos heurísticas, una que cuenta el número de fichas del jugador y del adversario, y otra que le da pesos a lasdiferentes posiciones en el tablero, especialmente premiando a las esquinas y castigando a las casillas antes de las esquinas. Palabras clave: Algoritmos de búsqueda, algoritmos en common lisp, algoritmo minimax, cortes alfa beta, poda alfa-beta, resolución de problemas, reversi.

1. Introducción La verificación de los algoritmos de inteligencia artificial converge en la prueba utilizando juegos,debido a una inexplicable fascinación. Un algoritmo importante es el del adversario, que plantea un problema donde intervienen dos o más jugadores, sean personas o máquinas, y el objetivo es adelantarse a posibles movimientos para seleccionar el movimiento propio. Hay muchas razones para la utilización de los juegos en inteligencia artificial, en [1] se presenta un enfoque en que mencionan dos razonespor las que los juegos aparecen para ser un buen dominio, en el cual se explora la inteligencia artificial:

-

-

Los juegos proveen tareas estructuradas en las cuales es muy fácil medir sucesos o fallos. Los juegos no requieren de mucho conocimiento, y se pensaba que la solución podría estar en búsquedas directas de un punto de partida a un punto final de éxito.

Sin embargo, la segundarazón no es tan cierta en juegos complicados, debido a la creación excesiva de nodos, el alto factor de ramificación y también por los muchos movimientos posibles. Y aquí es donde entran otros algoritmos como el minimax y sus extensiones que mejoran de una manera considerable la funcionalidad de algoritmos de búsqueda como los tratados en [2] y [3].

En el resto del artículo se hace unaintroducción al algoritmo minimax y sus extensiones, una breve descripción del juego Othello, la implementación del juego con el algoritmo estudiado y los resultados.

El primer paso por la disposición del árbol es minimizar las hojas, para el caso del nodo b minimizará 3 y 7, el resultado es 3 por ser el menor.

2. Algoritmo minimax 2.1. Descripción del algoritmo La idea principal del algoritmo [1]es iniciar en una posición y utilizar un generador de movimientos plausibles para generar un conjunto de posiciones de posible sucesores, se aplica una función de evaluación estática y se selecciona el mejor movimiento promoviendo el valor. Hay ciertas definiciones mencionadas en [4] que son importantes: La poda, nos permite ignorar partes de un árbol de búsqueda que no marcan diferencia paraobtener un movimiento óptimo. Las funciones de evaluación, son heurísticas que permiten aproximar la utilidad verdadera de estado sin hacer una búsqueda completa. Una estrategia óptima es una secuencia de movimientos que conducen a un estado objetivo, en el cual será ganador.
Figura 2: Minimización de valores del árbol ejemplo.

Figura 1: Árbol de juegos de ejemplo.

En el caso del nodo cminimizará 6 y 9, el resultado es 6, el resultado de ambas operaciones se promueve a los nodos padre, tal como se refleja en la Figura 2.

-

-

Por lo que, el algoritmo minimax calcula la decisión minimax del estado actual, utilizando el cálculo simple recurrente de los valores minimax de cada estado sucesor, directamente implementando ecuaciones de definición.

2.2. Ejemplo Se supone el árbol...
tracking img