???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: https://tede.ufam.edu.br/handle/tede/5010
Tipo do documento: Dissertação
Título: Proposta de um agente para o jogo de dominó de 4 pontas utilizando o algoritmo expectiminimax
Autor: Silva, Endrews Sznyder Souza da 
Primeiro orientador: Costa Filho, Cícero Ferreira Fernandes
Primeiro coorientador: Costa, Marly Guimarães Fernandes
Resumo: 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 %.
Abstract: 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.
Palavras-chave: Algoritmos genéticos
Jogo de dominó
Busca expectiminimax
Á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: SILVA, Endrews Sznyder Souza da. Proposta de um agente para o jogo de dominó de 4 pontas utilizando o algoritmo expectiminimax. 2015. 91 f. Dissertação (Mestrado em Engenharia Elétrica) - Universidade Federal do Amazonas, Manaus, 2015.
Tipo de acesso: Acesso Aberto
URI: http://tede.ufam.edu.br/handle/tede/5010
Data de defesa: 4-Sep-2015
Appears in Collections:Mestrado em Engenharia Elétrica

Files in This Item:
File Description SizeFormat 
Dissertação - Endrews Sznyder Souza da Silva.pdfReprodução Total Autorizada2,86 MBAdobe PDFThumbnail

Download/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.