Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/12544
metadata.dc.type: Dissertação
metadata.dc.rights: Acesso Aberto
Title: D-MA-Draughts: um sistema multiagente jogador de damas automático que atua em um ambiente de alto desempenho
metadata.dc.creator: Tomaz, Lídia Bononi Paiva
metadata.dc.contributor.advisor1: Julia, Rita Maria da Silva
metadata.dc.contributor.referee1: Lopes, Carlos Roberto
metadata.dc.contributor.referee2: Carvalho, Cedric Luiz de
metadata.dc.description.resumo: O objetivo deste trabalho é propor um sistema de aprendizagem de damas, D-MA-Draughts (Distributed Multiagent Draughts): um sistema multiagente jogador de damas que atua em ambiente de alto desempenho. O D-MA-Draughts se baseia na integração e no refinamento de duas arquiteturas bem sucedidas de outros dois jogadores automáticos em damas: MP-Draughts e DVisionDraughts. O primeiro é um sistema mutiagente que não opera em um ambiente de alto desempenho e, o segundo, é um sistema monoagente que atua em ambiente de alto desempenho. Particularmente, o D-MA-Draughts aprimora o MP-Draughts no que diz respeito à dinâmica de interação entre os agentes. Do mesmo modo, ele aumenta o desempenho do D-VisionDraughts com um incremento na acuidade com que representa os tabuleiros e com um incremento na quantidade de processadores do ambiente. O D-MA-Draughts é composto por 26 agentes, sendo um denominado IIGA (Initial Intermediate Game Agent), especialista em fases iniciais e intermediárias do jogo e 25 agentes especializados em fases finais. Cada um destes agentes consiste de uma rede neural multicamadas (MLP) que foi treinada, através dos Métodos das Diferenças Temporais (λ), em um ambiente de processamento distribuído a fim de alcançar um alto nível de desempenho com o mínimo de intervenção humana, distintamente do jogador automático atual campeão mundial, Chinook. A busca pelo melhor movimento é guiada pelo algoritmo de busca distribuído Young Brothers Wait Concept (YBWC). Os estados do tabuleiro são representados pelo mapeamento NET-FEATUREMAP, que é composto por funções que descrevem características inerentes ao próprio jogo de damas. Os agentes especialistas em fases finais de jogo foram treinados para lidar com um determinado perfil de tabuleiros de final de jogo (cluster ). Tais clusters foram obtidos através de redes Kohonen-SOM, a partir de uma base de dados com estados de tabuleiro de final de jogo obtida em partidas reais. Depois de treinados, os agentes do D-MA-Draughts podem atuar em uma partida seguindo duas dinâmicas de jogo. Em ambas as dinâmicas o agente IIGA iniciará a partida. A partir daí, elas vão variar conforme descrito a seguir: na primeira, ao ser atingido um estado caracterizado como final de jogo a rede Kohonen-SOM apontará o agente (dentre os agentes de final de jogo) que representa o cluster cujo perfil\" mais se aproxima daquele do estado corrente do tabuleiro. Deste ponto em diante, tal agente substituirá o IIGA e conduzirá a partida até o final. Na segunda dinâmica, a cada vez que o sistema automático for executar um movimento em situações de final de jogo, a Rede Kohonen-SOM será acionada para indicar qual dos agentes de final de jogo tem perfil\" mais adequado ao estado corrente de final de jogo. Este trabalho mostra que com a arquitetura proposta o D-MA-Draughts conseguiu melhorar o desempenho de seus predecessores. Tais melhorias se devem ao fato de que a maior acuidade com que os estados do tabuleiro são percebidos pelos agentes possibilitou-lhe tomadas de decisão mais precisas. Em contrapartida, melhorar a representação do tabuleiro ocasiona um aumento da carga de processamento do sistema. Neste contexto, o incremento do número de processadores contornou esta situação, além de ter contribuído para aprofundar a visão futura do jogador (look-ahead) durante a busca, o que o tornou mais apto a escolher melhores movimentos.
Abstract: The objective behind this study is the proposal of a Draughts learning system, D-MA-Draughts (Distributed Multi-agent Draughts): a multi-agent Draughts player that operates in high performance environments. D-MA-Draughts is based on the integration and refinement of two other successful automatic Draughts architectures: MP-Draughts and D-VisionDraughts. The first is a multi-agent system, which does not operate in a high performance environment, and the second is a mono-agent system, which operates in a high performance environment. The D-MA-Draughts player, in particular aided in enhancing the MP-Draughts player with respect to the dynamics of the interaction between the agents. Similarly, it increases the performance of D-VisionDraughts by augmenting the accuracy with which it represents the boards along with an increase in the number of processors pertaining to the environment. The D-MA-Draughts player is composed of 26 agents, with one denominated as IIGA (Initial Intermediate Game Agent), which is a specialist in initial and intermediary game states and 25 agents specializing in end game states. Each of these agents consists of a multi-layer neural network (MLP), which was trained through the use of Temporal Difference Methods (λ), in a distributed processing environment, in order to achieve a high performance level with the minimum of human intervention possible, unlike the automatic player of Draughts world champion, Chinook. The search for the best move is guided by the distributed search algorithm denominated as, Young Brothers Wait Concept (YBWC). The board states are represented by NET-FEATUREMAP mapping, which is composed of functions that describe features inherent to the game of Draughts. The specialist agents in the end game states were trained to deal with a specific type of board profile\" of end game states (cluster). These clusters were obtained through Kohonen-SOM networks from a data base with end game board states obtained from real life matches. Once trained, the D-MA-Draughts agents are able to operate in a match by following two dynamics of the game. In both of these dynamics the IIGA agent will start the match. From this point they will vary as follows: in the first, once the board state characterized as the end game has been reached the Kohonen-SOM network will appoint the agent (from within the end game agents), which represents the cluster whose profile\" is closest to the current board state. From here on, agents of this type will substitute the IIGA and conduct the match until the end. In the second dynamic, each time that the automatic system executes a movement in an end game situation, the Kohonen-SOM network will be activated to indicate, which of the end game agents has the most adequate profile\" for the current end game state. This study shows that by using the proposed architecture D-MA-Draughts managed to improve the performance achieved by its predecessors. Such improvements are due to the greater accuracy with which the board states are perceived by the agents allowing them to make more precise decisions. On the other hand, improving the board representation leads to an increase in the system\'s processing load. In this context, the increase in the number of processors circumvented this situation besides contributing to a deeper player future vision or look-ahead during the search, which made it more suitable in choosing the best moves.
Keywords: Sistema jogador multiagente distribuído
Damas
Aprendizagem por reforço de máquina
Redes neurais artificiais
Busca distribuída
Representação de estados por características
Algoritmos de clusterização
Tabelas de transposição
Distributed multi-agent player system
Draughts
Machine reinforcement learning
Artificial neural networks
Distributed search
Representation of states through features
Cluster algorithms
Transposition tables
Jogo de damas por computador
Redes neurais (Computação)
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
metadata.dc.language: por
metadata.dc.publisher.country: BR
Publisher: Universidade Federal de Uberlândia
metadata.dc.publisher.initials: UFU
metadata.dc.publisher.department: Ciências Exatas e da Terra
metadata.dc.publisher.program: Programa de Pós-graduação em Ciência da Computação
Citation: TOMAZ, Lídia Bononi Paiva. D-MA-Draughts: um sistema multiagente jogador de damas automático que atua em um ambiente de alto desempenho. 2013. 156 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2013.
URI: https://repositorio.ufu.br/handle/123456789/12544
Issue Date: 24-May-2013
Appears in Collections:PPGCC - Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
Lidia Bononi.pdf2.78 MBAdobe PDFView/Open


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