Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/12509
Document type: Dissertação
Access type: Acesso Aberto
Title: D-VisionDraughts: uma rede neural jogadora de damas que aprende por reforço em um ambiente de computação distribuída
Author: Barcelos, Ayres Roberto Araújo
First Advisor: Julia, Rita Maria da Silva
First member of the Committee: Matias Júnior, Rivalino
Second member of the Committee: Bazzan, Ana Lucia Cetertich
Summary: 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.
Keywords: 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
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: BR
Publisher: Universidade Federal de Uberlândia
Institution Acronym: UFU
Department: Ciências Exatas e da Terra
Program: Programa de Pós-graduação em Ciência da Computação
Quote: 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.
URI: https://repositorio.ufu.br/handle/123456789/12509
Date of defense: 23-Feb-2011
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
Diss Ayres.pdf3.47 MBAdobe PDFThumbnail
View/Open


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