Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-06T19:37:59Z No. of bitstreams: 1 Dissertação - Endrews Sznyder Souza da Silva.pdf: 2926146 bytes, checksum: 1351d4cbe891b8af9ba59b296a41e69c (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-06T19:38:31Z (GMT) No. of bitstreams: 1 Dissertação - Endrews Sznyder Souza da Silva.pdf: 2926146 bytes, checksum: 1351d4cbe891b8af9ba59b296a41e69c (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-06T19:39:45Z (GMT) No. of bitstreams: 1 Dissertação - Endrews Sznyder Souza da Silva.pdf: 2926146 bytes, checksum: 1351d4cbe891b8af9ba59b296a41e69c (MD5) / Made available in DSpace on 2016-06-06T19:39:45Z (GMT). No. of bitstreams: 1 Dissertação - Endrews Sznyder Souza da Silva.pdf: 2926146 bytes, checksum: 1351d4cbe891b8af9ba59b296a41e69c (MD5) Previous issue date: 2015-09-04 / Não informada / Dominoes game is played by millions of people around Brazil and entire world. People usually play this game during family meetings, with friends and in universities. Dominoes game does not have universal version and rules, the way it is played can vary according its region. Although dominoes' version diversity, this game is simple. Dominoes game to is an incomplete information and non-deterministic type. Uncertainty and stochastic characteristic of this game make it difficult to solve by applying artificial intelligence techniques. Thus, this thesis proposes an agent for four-sided dominoes. This dominoes' version is played in Amazonas state. The proposed agent is based on partial expectiminimax algorithm. Partially searching the game tree generates horizon effect, and to reduce it, phase related search will be used in each round phase. Moreover, due to chance events it will be necessary probability modeling to obtain opponent's moves probability values. This thesis proposes eight strategies, which differ from each other in depth search through a round. Each strategy is evaluated against a pair, which uses the basic one and pair with strategy based on genetic algorithm. The best strategy is this work obtained 72,04% of victories in 5000 matches against the basic one, and 58,34% of victories against the strategy based on genetic algorithm. / O jogo de dominó é praticado por milhões de pessoas pelo Brasil e no mundo. As pessoas costumam praticar este jogo em reuniões familiares, círculos de amigos e nas universidades. O jogo de dominó não possui uma versão e regras universais, podendo variar de acordo com a região em que é praticado. Apesar de suas diversas variações, este jogo é simples de jogar. O dominó é um jogo de informação incompleta e não determinístico. As incertezas e a característica estocástica o fazem um jogo complexo de solucionar com as metodologias existentes na área de inteligência artificial. Nesse sentido, esta dissertação propõe uma agente para o jogo de dominó de 4 pontas. Esta versão do jogo de dominó é praticada no Amazonas. O agente proposto é baseado no algoritmo de busca expectiminimax com busca parcial. A busca parcial tem como consequência o efeito de horizonte, e para atenuar este efeito será realizada uma busca por fases dentro de uma rodada. Além disso, devido à presença dos eventos de chance nesse jogo será necessária a modelagem probabilística para os mesmos. Neste trabalho foram definidas oito estratégias com profundidades diferentes em cada fase das rodadas. Cada estratégia será testada contra a estratégia básica de jogo e contra o melhor resultado obtido pela estratégia que utiliza algoritmos genéticos. A melhor estratégia deste trabalho obteve 72,04% de vitórias em 5000 partidas, contra a estratégia básica de jogo. Contra a melhor estratégia que utiliza algoritmos genéticos o percentual de vitorias foi de 58,34 %.

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.