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. / 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. / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/urn:repox.ist.utl.pt:RI_UFU:oai:repositorio.ufu.br:123456789/12547 |
| Date | 04 November 2013 |
| Creators | Aguiar, Matheus Araújo |
| Contributors | Julia, Rita Maria da Silva, Lopes, Carlos Roberto, Chaimowicz, Luiz |
| Publisher | Universidade Federal de Uberlândia, Programa de Pós-graduação em Ciência da Computação, UFU, BR, Ciências Exatas e da Terra |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFU, instname:Universidade Federal de Uberlândia, instacron:UFU |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds