Um agente jogador de GO com busca em árvore Monte-Carlo aprimorada por memória esparsamente distribuída

Abstract

The game of Go is very ancient, with more than 4000 years of history and it is still popular nowadays, representing a big challenge to the Articial Intelligence. Despite its simple rules, the techniques which obtained success in other games like chess and draughts cannot handle satisfactorily the complex patterns and behaviours that emerge during a match of Go. The present work implements the SDM-Go, a competitive agent for Go that seeks to reduce the usage of supervision in the search process for the best move. The SDMGo utilizes the sparse distributed memory model as an additional resource to the Monte- Carlo tree search, which is used by many of the best automatic Go players nowadays. Based upon the open-source player Fuego, the use of the sparse distributed by SDM-Go has the purpose of being an alternative to the strong supervised process used by Fuego. The Monte-Carlo tree search executed by agent Fuego uses a set of heuristics codied by human professionals to guide the simulations and also to evaluate new nodes found in the tree. In a dierent way, SDM-Go implements a non-supervised and domain independent approach, where the history of the values of board states previously visited during the search are used to evaluate new boards (nodes of the search tree). In this way, SDM-Go reduces the supervision of Fuego, substituting its heuristics by the sparse distributed memory, which works as a repository for the information from the history of visited board states. Thus, the contributions of SDM-Go consist of: (1) the utilization of a sparse distributed memory to substitute the supervised approach of Fuego to evaluate new nodes found in the search tree; (2) the implementation of a board state representation based on bit vectors, in order to not compromise the performance of the system due to the boards stored in the memory; (3) the extension of the usage of the Monte-Carlo simulation results to update the values of the board states stored in the memory. Distinctly from many other existing agents, the use of the sparse distributed memory represents an approach independent of domain. The results obtained in tournaments against the well known open-source agent Fuego show that SDM-Go can perform successfully the task of providing a non-supervised and independent of domain approach to evaluate new nodes found in the search tree. Despite the longer runtime required by the use of the sparse distributed memory, the core of the agent performance, SDM-Go can keep a competitive level of play, especially at the 9X9 board.