Otimização da função de avaliação de Dominó de 4 pontas utilizando Algoritmo genético

• Ano de defesa: 2011
• Autor(a) principal: Antonio, Nirvana da Silva
• Outros Autores: http://lattes.cnpq.br/8672777154277363
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Amazonas; Faculdade de Tecnologia; Brasil; UFAM; Programa de Pós-graduação em Engenharia Elétrica
• Palavras-chave em Português: Jogo de dominó; Função de avaliação; Algoritmos genéticos; ENGENHARIAS: ENGENHARIA ELÉTRICA
• Link de acesso: https://tede.ufam.edu.br/handle/tede/6478

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.