Publicação: D-VisionDraughts: uma rede neural jogadora de damas que aprende por reforço em um ambiente
de computação distribuída
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
Orientador
Coorientador
Resumo
O objetivo deste trabalho é propor um sistema de aprendizagem de damas, o DVisionDraughts
(Distributed VisionDraughts): um agente distribuído jogador de damas
baseado em redes neurais que aprende por reforço. O D-VisionDraughts é treinado em
um ambiente de processamento distribuído de modo a alcançar um alto nível de jogo sem
a análise de especialistas e com o mínimo de intervenção humana possível (diferentemente
do agente campeão do mundo de damas Chinook). O D-VisionDraughts corresponde a
uma versão distribuída do eciente jogador VisionDraughts, onde este último corresponde
à uma rede neural MLP (multilayer perceptron) que aprende pelo método das diferenças
temporais. O papel da rede neural é avaliar o quanto um estado de tabuleiro é favorável
ao agente (valor de predição). Este valor irá guiar o módulo de busca na procura pela
melhor ação (neste caso, o melhor movimento) correspondente ao estado de tabuleiro
corrente do jogo. Outro fator que é importante na eciência da busca, e que foi analisado
neste trabalho, é o grau de ordenação da árvore de jogo. Desta forma, as principais
contribuições deste trabalho consistem em: substituir o algoritmo serial utilizado para
a busca em árvore de jogos do VisionDraughts, o minimax com poda alpha-beta, pelo
algoritmo distribuído Young Brothers Wait Concept (YBWC); o uso de heurísticas para
ordenação da árvore de jogos, que é essencial para o bom desempenho do YBWC e da poda
alpha-beta em geral; a análise do impacto do ambiente de processamento distribuído nas
habilidades de aprendizado não supervisionadas do jogador. Este trabalho mostra que,
com a aplicação das técnicas no D-VisionDraughts, reduzimos expressivamente o tempo
necessário para a etapa de busca e, através de torneios realizados com o VisionDraughts,
o desempenho geral do agente distribuído foi nitidamente melhor.
Abstract
The objetive of this work is to propose a draughts learning system, the D-VisionDraughts
(Distributed VisionDraughts): a distributed draughts player agent based on neural networks
that learns by reinforcement. The D-VisionDraughts is trained in a distributed
processing environment in order to achieve a high level of play without expert game analysis
and with minimal human intervention as possible (distinctly from the world draughts
champion Chinook). The D-VisionDraughts corresponds to a distributed version of the
eficient VisionDraughts player, where the latter corresponds to a MLP (multilayer perceptron)
neural network that learns by means of temporal diferences. The role of the neural
network is to evaluate how much a board state is favorable to the agent (prediction). This
value will lead the search module to determine the best action (in this case, the best move)
of the current board state of the game. Another factor that has an important impact on
the search eciency, which is analyzed in this work, is the degree of ordering of the game
tree. Thus, the main contributions of this work are: the replacement of the serial algorithm
used in VisionDraughts, the minimax with alpha-beta pruning, by the distributed
algorithm Young Brothers Wait Concept (YBWC); the use of heuristics for game tree
ordering, that is essential for the proper performance of YBWC and alpha-beta pruning
in general; the impact analysis of the high-performance processing environment on the
unsupervised learning skills of the player. This work shows that with the techniques used,
the time required to perform a game tree search was signicantly reduced and through
tournaments played with VisionDraughts the overall performance of the distributed agent
is improved.
Palavras-chave
Damas, Aprendizagem de máquina, Aprendizagem por reforço, Aprendizagem
por diferenças temporais, Redes neurais articiais, Poda alpha-beta, Tabelas de
transposição, Aprofundamento iterativo, Busca paralela, Draughts, Machine learning, Reinforcement learning, Temporal differences
learning, Articial neural network, Alpha-beta pruning, Transposition table, Iterative deepening, Parallel search
Citação
BARCELOS, Ayres Roberto Araújo. D-VisionDraughts: uma rede neural jogadora de damas que aprende por reforço em um ambiente
de computação distribuída. 2011. 139 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2011.