Desarrollo de una política de selección para general Game Playing basada en el problema del bandido multi-armado

Abstract

Durante la historia de la Inteligencia Artificial se han desarrollo diversos agentes inteligentes capaces de jugar juegos de tablero de entre los m´as destacados se tiene a DeepBlue para el ajedrez y AlphaGo para el juego de Go. Sin embargo, estos agentes solo est´an enfocados en un solo juego por lo cual el paso natural es desarrollar agentes capaces de jugar m´as de un juego, idea que persigue el ´area General Game Playing la cual se enfoca en desarrollar agentes completamente aut´onomos que puedan jugar cualquier juego de tablero sin intervenci´on humana y sin conocimiento previo. La mayor´ıa de los agentes est´an basados en el m´etodo de Arbol de B´usqueda Monte Carlo que usa ´ simulaciones Monte Carlo para estimar movimientos prometedores, este m´etodo consiste en cuatro pasos: Selecci´on, Expansi´on, Simulaci´on y Propagaci´on Hacia Atr´as. Los esfuerzos para incrementar el rendimiento del Arbol de B´usqueda Monte Carlo se enfocan en el paso de simulaci´on, sin embargo, ´ es tambi´en el paso de Selecci´on el que repercute en dicho rendimiento. El paso de selecci´on controla la forma en que se recorre el ´arbol asociado al juego de tablero, dicho recorrido es guiado por una Pol´ıtica de Selecci´on de la cual Upper Confidence Bound es la popularmente usada. En esta tesis de investigaci´on se presentan dos pol´ıticas de selecci´on UCBα1 y UCBα2, las cuales est´an basadas en Upper Confidence Bound pero est´an pensadas completamente para su aplicaci´on en General Game Playing. UCBα1 y UCBα2 a diferencia de Upper Confidence Bound aprovechan la estructura del ´arbol asociados a los juegos de tablero para determinar para un nodo padre, cu´anto se debe explorar los nodos hijos que representan los movimientos disponibles antes de decidirse por explotar un nodo hijo con un movimiento prometedor. Upper Confidence Bound controla la exploraci´on de nodos hijos por medio de una constante de exploraci´on, sin embargo, esta constante permanece fija en todo el ´arbol sin importar el n´umero de nodos hijos. UCBα1 y UCBα2 usan una funci´on que depende del 1