Publicação: BTT-Go: um agente jogador de Go com busca Monte-Carlo aprimorada com tabela de transposição e modelo Bradley-Terry
Carregando...
Arquivos
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
O jogo de Go é, atualmente, um dos grandes desaos para a área de Inteligência
Articial, pois este reúne uma série de características que impedem o sucesso de técnicas
que foram bem sucedidas em outros jogos. Entre as características desaadoras do jogo,
está o alto nível de complexidade que inviabiliza o uso de técnicas que necessitam explorar,
ao máximo, seu espaço de busca.
Diante deste desao, neste trabalho de Mestrado foi criado o agente jogador de Go
denominado BTT-Go. Este agente foi criado a partir de outro jogador, chamado Fuego,
que utiliza uma das poucas técnicas que proporcionam bons ganhos aos jogadores autom
áticos de Go: o algoritmo de busca Monte-Carlo. O Fuego possui uma aprendizagem
essencialmente supervisionada, uma vez que seu processo de busca pelo melhor movimento
baseado, exclusivamente, nas simulações Monte-Carlo, em avaliações heurísticas de tabuleiros
e em bases de dados de início de jogo (opening book). Assim sendo, o objetivo do
presente trabalho é produzir um agente inspirado no Fuego que se mantenha bastante
competitivo apesar de apresentar um nível de supervisão inferior ao do citado jogador
automático. Para atingir este objetivo, o BTT-Go foi desenvolvido em três versões: na
primeira delas, foi usada uma Tabela de Transposição, que serve como um repositório de
dados previamente processados. Desta maneira, é possível reduzir a supervisão da quantidade
de simulações efetuadas pelo algoritmo de busca Monte-Carlo, avaliação que permite
substituir, em alguns casos, a avaliação prior-knowledge herdada do Fuego. A segunda
versão do BTT-Go consiste na aplicação, durante a etapa nal da busca Monte-Carlo, de
uma técnica bayesiana inspirada no modelo Bradley-Terry. Esta técnica permite predizer
a melhor jogada através da avaliação do tabuleiro. Esta avaliação é feita em função de
alguns atributos, que servem para dizer o quanto uma jogada é boa. No Fuego esta etapa
tem os movimentos gerados, unicamente, por políticas. Na terceira versão é feita a associa
ção da primeira com a segunda versão para o funcionamento em conjunto das técnicas
aplicadas.
Uma vez concluídas as três versões do agente BTT-Go, testes foram realizados em
tabuleiros de tamanho 9x9, 13x13 e 19x19. Nestes testes observou-se que com a aplicação
da Tabela de Transposição reduziu-se a supervisão no agente. Contudo, ocorreu uma leve
queda no percentual de vitórias em tabuleiros maiores (13x13 e 19x19), quando comparado
ao jogador Fuego, mas mesmo assim o agente se manteve competitivo. Contudo, com a
aplicação da técnica inspirada no modelo Bradley-Terry observou-se um aumentou na
competitividade do jogador mesmo em tabuleiros maiores (13x13 e 19x19), chegando em
alguns casos ser melhor que o agente Fuego.
Portanto, a criação do jogador BTT-Go proporcionou a redução da supervisão, obtida
tanto pelo uso da Tabela de Transposição quanto pela técnica bayesiana inspirada no
modelo Bradley-Terry. Também proporcionou ao agente um aumento da acuidade na
geração de movimentos no processo de busca.
Abstract
The game of Go is, nowadays, one of the greatest challenge in the Articial Intelligence
area, since this game has a set of characteristics that prevents the success application of
techniques, which has been very successful in other games. In this set of characteristics
there is the high level of complexity, which prevents it from the use of techniques that
require the maximum exploration of its search state-space.
In this thesis is described the development of a player agent for the game of Go named
BTT-Go. This agent was created from another one named Fuego, which uses one of the
few techniques that had provided improvement to the automatic players of Go: the Monte-
Carlo Tree Search algorithm. The player Fuego uses a supervised learning, once its search
method is based, exclusively, on Monte-Carlo simulations, heuristics board evaluations and
database, which contains data about the game start (opening book).This way, the objective
of this thesis is to produce a competitive agent in spite of the supervision reduction, which
is much less then the supervision used by the agent Fuego. To achieve this objective, BTTGo
was developed in three versions: in the rst, the agent uses a Transposition Table,
which is a repository of data processed previously. This way, it is possible to reduce
the simulation supervision by its reduction, and in some situations, the agent uses the
data from the table instead of using the Fuego prior knowledge evaluation. The second
version of BTT-Go consists in the application, in the nal stage of the Monte-Carlo search
algorithm, of a bayesian technique inspired on Bradley-Terry model. This technique
predicts the best move by a board evaluation. This evaluation is done considering some
features that describes how good a move is. In this stage, the agent Fuego uses policies
to indicate which move should be played. The BTT-Go third version was created by the
combination of the rst and the second versions, in a way that the techniques used can
work together without any loss.
Once the development of the three version was completed, it was performed some
experiments in dierent board sizes (9x9, 13x13 and 19x19). In these experiments, it was
observed that the use of Transposition Table reduced the agent supervision. Although,
there was a little reduction in its winning rate in large boards (13x13 and 19x19), comparing
it to Fuego, nevertheless BTT-Go is still a competitive player. It was also observed
that the technique inspired on Bradley-Terry model increased the competitiveness of the
agent in large boards (13x13 and 19x19), and in some situation it was better than the
agent Fuego.
Therefore, the development of the player BTT-Go has provided a supervision reduction
by the use of Transposition Table and by the use of bayesian technique inspired on Bradley-
Terry model, and also a increase of the acuity in the moves generation during the search
process.
Palavras-chave
Go, Busca monte-carlo, Modelo bradley-terry, Simulações monte-carlo, Monte-carlo tree search, Bradley-terry model, Monte-carlo simulations, Jogos eletrônicos, Jogos por computador, Monte Carlo, Método de
Citação
VIEIRA JÚNIOR, Eldane. BTT-Go: um agente jogador de Go com busca Monte-Carlo aprimorada com tabela de transposição e modelo Bradley-Terry. 2014. 91 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2014. DOI https://doi.org/10.14393/ufu.di.2014.165