Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/12547
metadata.dc.type: Dissertação
metadata.dc.rights: Acesso Aberto
Title: Um agente jogador de GO com busca em árvore Monte-Carlo aprimorada por memória esparsamente distribuída
metadata.dc.creator: Aguiar, Matheus Araújo
metadata.dc.contributor.advisor1: Julia, Rita Maria da Silva
metadata.dc.contributor.referee1: Lopes, Carlos Roberto
metadata.dc.contributor.referee2: Chaimowicz, Luiz
metadata.dc.description.resumo: Com mais de 4000 anos de história, o jogo de Go é atualmente um dos mais populares jogos de tabuleiro e representa um grande desao para a Inteligência Articial. Apesar de suas regras simples, as técnicas que anteriormente obtiveram sucesso em outros jogos como xadrez e damas não conseguem lidar satisfatoriamente com os padrões e comportamentos complexos que emergem durante uma partida de Go. O presente trabalho implementa o SDM-Go, um agente jogador de Go competitivo que procura reduzir a utilização de supervisão no processo de busca pelo melhor movimento. O SDM-Go emprega o modelo de memória esparsamente distribuída como um recurso adicional à busca em árvore Monte- Carlo utilizada por muitos dos melhores agentes automáticos atuais. Baseado no jogador código-aberto Fuego o uso da memória esparsamente distribuída pelo SDM-Go tem como objetivo ser uma alternativa ao processo fortemente supervisionado utilizado por aquele agente. A busca em árvore Monte-Carlo executada pelo jogador Fuego utiliza um conjunto de heurísticas codicadas por prossionais humanos para guiar as simulações e também avaliar novos nós encontrados na árvore. De maneira distinta, o SDM-Go implementa uma abordagem não supervisionada e independente de domínio, onde o histórico dos valores dos estados de tabuleiros previamente visitados durante a busca são utilizados para avaliar novos estados de tabuleiro (nós da árvore de busca). Desta maneira, o SDM-Go reduz a supervisão do agente Fuego, substituindo as heurísticas deste pela memória esparsamente distribuída que funciona como repositório das informações do histórico de estados de tabuleiro visitados. Assim, as contribuições do SDM-Go consistem em: (1) a utilização de uma memória esparsamente distribuída para substituir a abordagem supervisionada do Fuego para avaliar previamente novos nós encontrados na árvore; (2) a implementação de uma representação de tabuleiro baseada em vetores de bits, para não comprometer o desempenho do sistema em função dos tabuleiros armazenados na memória; (3) a extensão da utilização dos resultados das simulações Monte-Carlo para atualizar os valores dos tabuleiros armazenados na memória. Diferentemente de muitos outros agentes atuais, o uso da memória esparsamente distribuída representa uma abordagem independente de domínio. Os resultados obtidos em torneios contra o conhecido agente código-aberto Fuego mostram que o SDM-Go consegue desempenhar com sucesso a tarefa de prover uma abordagem independente de domínio e não supervisionada para avaliar previamente novos nós encontrados na árvore de busca. Apesar do maior tempo de processamento requerido pela utilização da memória esparsamente distribuída, peça central para o desempenho do agente, o SDM-Go consegue manter um nível de jogo competitivo, principalmente no tabuleiro 9X9.
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.
Keywords: Jogos
Agente para go
Memória esparsamente distribuída
Busca em árvore monte-carlo
Simulações
Game
Agent for go
Sparse distributed memory
Monte-carlo tree search
Simulations
Inteligência artificial
Computação
Jogos eletrônicos
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
metadata.dc.language: por
metadata.dc.publisher.country: BR
Publisher: Universidade Federal de Uberlândia
metadata.dc.publisher.initials: UFU
metadata.dc.publisher.department: Ciências Exatas e da Terra
metadata.dc.publisher.program: Programa de Pós-graduação em Ciência da Computação
Citation: AGUIAR, Matheus Araújo. Um agente jogador de GO com busca em árvore Monte-Carlo aprimorada por memória esparsamente distribuída. 2013. 109 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2013.
URI: https://repositorio.ufu.br/handle/123456789/12547
Issue Date: 4-Nov-2013
Appears in Collections:PPGCC - Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
AgenteJogadorGo.pdf2.54 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.