Método de Monte-Carlo Tree Search (MCTS) para resolver problemas de alta complejidad: jugador virtual para el juego del Go

Nasarre Embid, Beatriz
Serón Arbeloa, Francisco José (dir.) ; González Bedia, Manuel (dir.)

Universidad de Zaragoza, EINA, 2012
Informática e Ingeniería de Sistemas department, CC. de la Computación e Inteligencia Artificial area

Ingeniero en Informática

Abstract: El Go es un juego de mesa estratégico para dos jugadores. Se originó en China y su historia se remonta hace más de 2500 años. A pesar de la simplicidad de sus reglas, el Go, supone aún un reto para la Inteligencia Artificial, incapaz de realizar mediante ordenador un jugador capaz de vencer a los humanos expertos en el juego. El método Monte-Carlo Tree Search (MCTS) estudiado, en contraste con los algoritmos clásicos, no necesita ninguna función heurística de evaluación de posición, ya que realiza una exploración aleatoria del espacio de búsqueda, construyendo gradualmente en memoria un árbol de juego a través de los resultados de exploraciones anteriores. Este algoritmo resulta interesante para una gran cantidad de dominios, ha conseguido muy buenos resultados en problemas de juegos de todo tipo, especialmente en el juego del Go. En este proyecto se ha realizado la implementación del juego del Go, un módulo que implementa el método Monte-Carlo Tree Search y una aplicación que permite al usuario enfrentarse en el juego del Go a un jugador virtual dotado de cierta inteligencia y que usa el método anterior.

Free keyword(s): inteligencia artificial ; monte-carlo tree search ; mcts ; monte carlo ; go ; juegos

Tipo de Trabajo Académico: Proyecto Fin de Carrera