Publicação: D-MA-Draughts: um sistema multiagente jogador de damas automático que atua em um ambiente de alto desempenho
Carregando...
Arquivos
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
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.
Palavras-chave
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)
Citação
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. DOI https://doi.org/10.14393/ufu.di.2013.255