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 | Size | Format | |
---|---|---|---|---|
Diss Ayres.pdf | 3.47 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.