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

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.