25 - 29 de Noviembre de 2002

Montevideo, Uruguay

Radisson Victoria Plaza Hotel

 
CL69
 
Resolución de Juegos de Información Perfecta empleando Algoritmos Genéticos y Redes Neuronales

Raul Fernando Bouroncle Cuba
Universidad Nacional de San Agustin
rbouroncle@yahoo.com
Waldo Cancino Ticona
Universidade de São Paulo
wcancino@icmc.sc.usp.br
Juan C. Gutierrez Caceres
Universidade de São Paulo
juan@icmc.sc.usp.br
 
Abstract

The problem with complex games is that there are many ways to play them. In other words the group of possible strategies is large. However, if we consider a strategy as a succession of pure strategies through generations in the game (as a game tree), we can solve the problem with a Genetic Algorithm (GA). Furthermore, fitness funcion, which evaluates the individuals, needs to know the state of the game, in order to apply the best stragey. Representing discreetly the state of the game (pattern) we can train a Backpropagation's Neural Network (BPN) to recognize it. This research work proposes a method to solve games with perfect information from Artificial Intelligence's perspective. The use of this method will be shown on the development of the hybrid system, which can play chess departures successfully. The adventage between this method and the extensive method is that the number of individuals in each generation is always the same (only the best strategy survive).

Keywords: Games with perfect information, Genetic Algorithm, Backpropagation

 
Resumen

El principal problema en juegos complejos es radica en la infinidad de alternativas para su solución. Sin embargo, considerando una de esas alternativas como una sucesión de estratégias puras, a través de generaciones de jugadas (como un árbol de juego) se puede resolver el problema como un Algorítmo Genérico. Por otro lado, la función de utilidad que evalua a los individuos, necesita saber el estado del juego, para aplicar la estratégia más adecuada. Representando discretamente el estado de juego, podemos entrenar una Red Neural Backpropagation para reconocerlo. Este trabajo de investigación propone una forma de resolver los juegos de información perfecta désde la perspectiva de la inteligencia artificial. Se mostrará el empleo de estas técnicas con la elaboración de un sistema híbrido que pueda sostener con éxito una partida de Ajedrez. La ventaja de esta propuesta frente al método extensivo es que las generaciones mantienen siempre el mismo número de individuos (sobreviven las mejores estratégias).

Palabras Clave: Juegos de Informacion Perfecta, Algoritmo Genetico, Backpropagation



Volver

infoUYclei 2002