Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-06-20T18:48:23Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Checklist - Depósito Manaus.pdf: 105199 bytes, checksum: 3dcbfc733ee670e4a6b56f2fcb3ffc00 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-06-20T18:48:35Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Checklist - Depósito Manaus.pdf: 105199 bytes, checksum: 3dcbfc733ee670e4a6b56f2fcb3ffc00 (MD5) / Made available in DSpace on 2018-06-20T18:48:35Z (GMT). No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Checklist - Depósito Manaus.pdf: 105199 bytes, checksum: 3dcbfc733ee670e4a6b56f2fcb3ffc00 (MD5)
Previous issue date: 2011-12-21 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / The 4-sided dominoes game, popular in Amazonas State, is a variation of the dominoes game
probably originated in China. In the 4-sided dominoes, the matches are disputed between two
teams and the players must elaborate strategies based in three main objectives: scoring,
facilitate the future moves of the team and hinder the opponents’ moves. On the other hand, at
anytime the players have knowledge about the pieces held by the other players, which
characterizes the dominoes as an imperfect information game, where the search in the solution
space is more complex than in perfect information games. This work presents the
development of an intelligent agent for the 4-sided dominoes game, in which the choice of the
moves is done through an evaluation function. The evaluation function is based on
information about the present game state to make the selection of the moves according to the
objectives of the game. We proposed four possible strategies to be adopted by the intelligent
agent for the 4-sided dominoes game: a strategy that considers the three main objectives
simultaneously, a strategy that prioritizes only the player himself, a strategy that prioritizes
only the partner and a strategy that only aims to block the opponents’ moves. By prioritizing
different objectives of the game, each strategy is represented by a distinct evaluation function.
The selection of the optimal coefficients for these evaluation functions was made using
Genetic Algorithms, a search technique inspired by Darwin’s Theory of Evolution. The
evaluation criterion used to determine the best solution was the number of wins in 5,000
matches of dominoes and the optimizations were divided in three steps. Initially, for each
strategy, the genetic algorithm maximized the number of wins against a team that adopted the
basic strategy. In the second step, the strategies were optimized by playing against
themselves, where the opponent team used the coefficients optimized in the first step. In the
last step, each strategy was optimized against the other three, where these used the
coefficients optimized in the second step. Due to the stochastic nature of the genetic
algorithm, all optimizations were performed 10 times, allowing the mean and standard
deviation of the results to be obtained. With these informations, statistical tests were applied
in order to determine the significance of the number of wins. The test showed that two
strategies achieved better results than those obtained by the function developed in a previous
work. Comparing the performance between the four proposed strategies, we concluded that
the strategy covering the three main objectives of the game is superior to the others; the
strategies that emphasize only one team player have equivalent performance; and the strategy
that focuses only on hinder the opponents’ have inferior performance to the previous ones.
The best strategy optimized in this work was also evaluated against teams formed by human
players. Against experienced players, the strategy did not show satisfactory performance,
winning only 32% of matches. Nevertheless, against casual players, the intelligent agent won
in 78% of the disputed matches. / O dominó de 4 pontas, popular no Estado do Amazonas, é uma variação do jogo de dominó
possivelmente originado na China. No dominó de 4 pontas, as partidas são disputadas entre
duas duplas e os jogadores devem elaborar estratégias baseadas em três objetivos principais:
pontuar, facilitar jogadas futuras da dupla e dificultar as jogadas dos adversários. Porém, em
nenhum momento os jogadores tem conhecimento sobre as peças em posse dos demais
jogadores, o que caracteriza o dominó como um jogo de informações imperfeitas, onde a
busca no espaço de soluções é uma tarefa mais complexa do que em jogos de informações
perfeitas. Este trabalho apresenta o desenvolvimento de um agente inteligente para o jogo de
dominó de 4 pontas, cuja escolha das jogadas é feita através de uma função de avaliação. A
função de avaliação se baseia em informações sobre o estado presente de jogo para realizar a
escolha das jogadas de acordo com os objetivos do jogo. Foram propostas quatro possíveis
estratégias a serem adotadas pelo agente inteligente para o dominó de 4 pontas: uma estratégia
que considera os três objetivos principais simultaneamente, uma estratégia que prioriza
apenas o próprio jogador, uma estratégia que prioriza apenas o parceiro de dupla e uma
estratégia que somente visa bloquear as ações adversárias. Por priorizarem diferentes
objetivos do jogo, cada estratégia é representada por uma função de avaliação distinta. A
escolha dos coeficientes ótimos para estas funções de avaliação foi realizada utilizando
Algoritmos Genéticos, uma técnica de busca inspirada na Teoria da Evolução de Darwin. O
critério de avaliação usado para determinar a melhor solução foi o número de vitórias em
5000 partidas de dominó e as otimizações foram divididas em três etapas. Inicialmente, para
cada estratégia, o algoritmo genético maximizou a quantidade de vitórias contra uma dupla
que adotava a estratégia básica de jogo. Na segunda etapa, as estratégias foram otimizadas
jogando contra elas mesmas, onde a dupla adversária usou os coeficientes otimizados na
primeira etapa. Na última etapa, cada estratégia foi otimizada contra as outras três, onde estas
utilizavam os coeficientes otimizados na segunda etapa. Devido à natureza estocástica do
algoritmo genético, todas as otimizações foram executadas 10 vezes, permitindo que a média
e desvio-padrão dos resultados fossem obtidos. Com estas informações, foram aplicados
testes estatísticos para determinar a significância da quantidade de vitórias. O teste mostrou
que duas estratégias alcançaram resultados superiores à função desenvolvida em um trabalho
anterior. Comparando o desempenho entre as quatro estratégias propostas, concluiu-se que a
estratégia que abrange os três objetivos de jogo é superior às demais, as estratégias que
priorizam apenas um jogador da dupla apresentam desempenho equivalente e a estratégia que
se foca apenas em atrapalhar os adversários possui desempenho inferior às anteriores. A
melhor estratégia otimizada nesta pesquisa também foi avaliada contra duplas formadas por
jogadores humanos. Contra jogadores experientes, a estratégia não apresentou desempenho
satisfatório, ganhando apenas 32% das partidas. Porém, contra jogadores casuais, ganhou em
78% dos jogos disputados.
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/6478 |
| Date | 21 December 2011 |
| Creators | Antonio, Nirvana da Silva, 3236-2686 |
| Contributors | ppgee@ufam.edu.br, Costa Filho, Cícero Ferreira Fernandes, Costa, Marly Guimarães Fernandes |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Engenharia Elétrica, UFAM, Brasil, Faculdade de Tecnologia |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -5930111888266832212, 500 |
Page generated in 0.002 seconds