In this project I created two Minimax Tree search AIs that would fight one another in a 2D table turn game. Each opponent is accessible to designers allowing them to adjust each agent's health and energy. Additionally, the user is able to implement actions and create new actions all without having to write any code.
Fig: 1. Oates 2021. Example of Minimax AI.
This was a 4 week university project at Falmouth University, created with the Unity Engine and C#.
Research
MiniMax is an algorithm that is used for 2 player games that do not run-in real time; this has resulted in it being used to make agents that can play board games such as chess and drafts. However, this algorithm has found some uses in real time strategy games (N. Yannakakis and Togelius 2018). This algorithm is a good example of AI that’s not Machine Learning as it uses allows computers to behave intelligently without learning and improving (Lazar 2020). After making a decision if an action is playable, then an evaluation function will be used to evaluate the current action, in this case it will add both opponents' health values together. Each row of leaves is every action the agent could play.
To avoid using too much processing power, a technique called alpha beta pruning will be used to remove any unused branches to ensure that they are not taking up space (N. Yannakakis and Togelius 2018). In addition, if the tree search has nodes on the same scores in the same row, then an action will be picked at random also the agent will get given a possible maximum value so that if an action with the highest possible value is found then just pick that action.
The MiniMax function will use a recurring function to call itself multiple times until it’s reached zero, this is achieved by not just calling itself multiple time but reducing its depth parameter by one (Roberts 1985). Once it’s reached the bottom the function will use the data returned by the function to tell which score and action to pick.
Bibliography
LAZAR, Dorian. 2020. 'Understanding the Minimax Algorithm'. Available at: https://towardsdatascience.com/understanding-the-minimax-algorithm-726582e4f2c6. [Accessed Dec 7,].
MUENS, Philipp. 2021. 'Minimax and Monte Carlo Tree Search'. Available at: https://philippmuens.com/minimax-and-mcts. [Accessed Nov 22,].
N. YANNAKAKIS, Georgios and Julians TOGELIUS. 2018. Artificial Intelligence and Games. Springer.
ROBERTS, Eric S. 1985. Thinking Recursively. Canada: John Wiley & Sons. Inc.
Figure List
Figure 1: Oates 2021. Example of Minimax AI. [Video]