Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/12460
Document type: Dissertação
Access type: Acesso Aberto
Title: VisionDraughts - um sistema de aprendizagem de jogos de damas baseado em redes neurais, diferenças temporais, algoritmos eficientes de busca em árvores e informações perfeitas contidas em bases de dados
Author: Caexêta, Gutierrez Soares
First Advisor: Julia, Rita Maria da Silva
First member of the Committee: Lopes, Carlos Roberto
Second member of the Committee: Bittencourt, Guilherme
Summary: O objetivo deste trabalho é propor um sistema de aprendizagem de damas, Vision-Draughts, baseado nos trabalhos de Neto e Julia (LS-Draughts) e de Mark Lynch (NeuroDraughts). O NeuroDraughts é um bom jogador automático de damas que utiliza a técnica de aprendizagem por diferenças temporais para ajustar os pesos de uma rede neural artificial multi-camadas cujo papel é estimar o quanto um estado do tabuleiro do jogo, representado em sua camada de entrada através do mapeamento NET-FEATUREMAP, é favorável ao agente jogador. O conjunto de características do jogo é definido manualmente e a busca pela melhor ação a ser executada, a partir do estado corrente do tabuleiro, é realizada através do algoritmo minimax. O LS-Draughts expande o trabalho de Lynch por meio da técnica dos algoritmos genéticos, gerando, automaticamente, um conjunto mínimo e essencial de características do jogo de damas e otimizando, com grande sucesso, o treinamento do agente aprendiz. O VisionDraughts acrescenta dois módulos nas arquiteturas anteriores: um módulo de busca eficiente em árvores de jogos baseado no algoritmo alfa-beta, no aprofundamento iterativo e nas tabelas de transposição, que fornece ao agente jogador maior capacidade de analisar jogadas futuras (estados do tabuleiro mais distantes do estado corrente), um módulo para acessar bases de dados de finais de jogos que permite obter informações perfeitas para combinações de oito ou menos peças no tabuleiro. Foram realizados torneios entre os melhores jogadores obtidos por NeuroDraughts, LS-Draughts e VisionDraughts. Os resultados dos torneios, todos vencidos pelo VisionDraughts, evidenciam a importância dos dois novos módulos na construção de jogadores automáticos de damas: o tempo de execução para o treinamento do jogador foi drasticamente reduzido e seu desempenho significantemente melhorado. Alias, o nome VisionDraughts foi escolhido, justamente, para destacar a importância da capacidade de analisar jogadas futuras para o sucesso do presente trabalho.
Abstract: The objective of this work is to propose a draughts learning system, VisionDraughts, based on works of Neto and Julia (LS-Draughts) and Mark Lynch (NeuroDraughts). The NeuroDraughts is a good automatic draughts player which uses temporal diference learning to adjust the weights of an articial neural network whose role is to estimate how much the board state represented in its input layer by NET-FEATUREMAP is favorable to the player agent. The set of features is manually dened. The search for the best action corresponding to a current board state is performed by minimax algorithm. The LS-Draughts expands the NeuroDraughts, through the genetic algorithms, generating automatically a set of minimal features which are necessary and essential to a game of draughts and optimizing, successfully, the training of the apprentice player. The Vision- Draughts adds two modules to the former architectures: an eficient tree-search module with alfa-beta, iterative deepening and transposition table, providing the player agent larger capacity to analyse future moves (board states more distant from the current board) and a module to access endgame databases, allowing to acquire perfect information to positions with less than 8 pieces on the board. Some tournaments were promoted between the best players obtained by NeuroDraughts, LS-Draughts and VisionDraughts. The tournament's results, all won by the VisionDraughts, show the importance of the new two modules in the building of good automatic draughts players: the runtime required for training the new player was drastically reduced and its performance was significantly improved. Furthermore, the VisionDraughts name was just chosen to emphasize the great importance of analysing future moves in order to the success of this work.
Keywords: Aprendizagem automática
Aprendizagem de máquina
Aprendizagem incremental
Aprendizagem por reforço
Redes neurais
Aprendizagem por diferenças temporais
Teoria dos jogos
Damas
Busca em árvores de jogos
MiniMax
Tabelas de transposição
Aprofundamento iterativo
Bases de dados de finais de jogos
Chaves Zobrist
Tabela Hash
Tratamento de colisões
Automatic Learning
Machine Learning
Incremental Learning
Reinforcement Learning
Neural network
Temporal diference learning
Game theory
Draughts
Checkers
Minimax
Alfa-Beta
Transposition table
Iterative deepening
Endgame databases
Zobrist key
Hash table
Collisions
Aprendizado do computador
Redes neurais (Computação)
Teoria dos jogos
Alfa-Beta
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: CAEXÊTA, Gutierrez Soares. VisionDraughts - um sistema de aprendizagem de jogos de damas baseado em redes neurais, diferenças temporais, algoritmos eficientes de busca em árvores e informações perfeitas contidas em bases de dados. 2008. 141 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2008.
URI: https://repositorio.ufu.br/handle/123456789/12460
Date of defense: 21-Jul-2008
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
Gutierrez Soares.pdf1.32 MBAdobe PDFThumbnail
View/Open


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