Exportar este item: EndNote BibTex

Use este identificador para citar ou linkar para este item: https://tede.ufam.edu.br/handle/tede/6478
Tipo do documento: Dissertação
Título: Otimização da função de avaliação de Dominó de 4 pontas utilizando Algoritmo genético
Autor: Antonio, Nirvana da Silva 
Primeiro orientador: Costa Filho, Cícero Ferreira Fernandes
Primeiro coorientador: Costa, Marly Guimarães Fernandes
Resumo: 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.
Abstract: 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.
Palavras-chave: Jogo de dominó
Função de avaliação
Algoritmos genéticos
Área(s) do CNPq: ENGENHARIAS: ENGENHARIA ELÉTRICA
Idioma: por
País: Brasil
Instituição: Universidade Federal do Amazonas
Sigla da instituição: UFAM
Departamento: Faculdade de Tecnologia
Programa: Programa de Pós-graduação em Engenharia Elétrica
Citação: ANTONIO, Nirvana da Silva. Otimização da função de avaliação de Dominó de 4 pontas utilizando Algoritmo genético. 2011. 113 f. Dissertação (Mestrado em Engenharia Elétrica) - Universidade Federal do Amazonas, Manaus, 2011.
Tipo de acesso: Acesso Aberto
Endereço da licença: http://creativecommons.org/licenses/by-nc-nd/4.0/
URI: https://tede.ufam.edu.br/handle/tede/6478
Data de defesa: 21-Dez-2011
Aparece nas coleções:Mestrado em Engenharia Elétrica

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Dissertação_Nirvana Antonio.pdf8,88 MBAdobe PDFThumbnail

Baixar/Abrir Pré-Visualizar


Este item está licenciada sob uma Licença Creative Commons Creative Commons