Utveckling av minimax-baserad agent för strategispelet Stratego
Computer scienceNumerical analysisHybrid architetureHidden informationMinimax algorithmMinimax-based agentSystemsControlDatalogiNumerisk analysSystemKontrollTechnology and Engineering
Stratego is a boardgame not very different from chess, that contains hidden information. Because of this, existing programs play at beginner level. The purpose of this thesis is to adjust a minimax algorithm so that it passes the demands of Stratego, and then build a Stratego agent around it. Tests with existing minimax algorithms leads to the development p-e-minimax. This algorithm uses two different values in its nodes to simulate the different information available to the agent and its opponent. The name of the agent constructed around p-e-minimax is Perspecto. This agent uses a hybrid architecture were a simple strategic search is used in paralell with p-e-minimax. The agent also uses a psychlolgical model to handle the game of the hidden pieces better.Perspecto defeats a commercial program but loses to a human player after an even game. This and the following tests shows that a more advanced strategic search and a more unpredictable psychological model is needed for Perspecto to have a chance aganist a skilled human player.