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