Proposta de um agente para o jogo de dominó de 4 pontas utilizando o algoritmo expectiminimax

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.