Minimax is an algorithm based on the decision to minimize the possible loss for the worst case (maximum loss). Besides game development and game theory, Minimax is a decision rule and is also used in statistics, decision theory, and philosophy.
This technique was originally formulated for the two-player zero-sum game theory, meaning that one player's win is the opponent's loss. However, in this case, it is flexible enough to handle more than two players.
It is important to know the difference between a dynamic member function and a static member function, as well as recursion. A dynamic member function is bound to the instance of the class, while the static member function is bound to the class itself. The static method allows us to call it without instantiating an object. This is great for general-purpose algorithms, such as the one developed in this recipe.
In the case of recursion, it's not always clear that (unlike iteration) this is an iterative process that requires a base case (also called the stop condition) and a recursive case (the one to keep iterating).
We will create the base class for handling all of our main algorithms and implement the Minimax function as follows:
- Create the
BoardAIclass:using UnityEngine; using System.Collections; public class BoardAI { } - Declare the
Minimaxfunction:public static float Minimax( Board board, int player, int maxDepth, int currentDepth, ref Move bestMove) { // next steps here } - Consider the base case:
if (board.IsGameOver() || currentDepth == maxDepth) return board.Evaluate(player); - Set the initial values depending on the player:
bestMove = null; float bestScore = Mathf.Infinity; if (board.GetCurrentPlayer() == player) bestScore = Mathf.NegativeInfinity; - Loop through all the possible moves and return the best score:
foreach (Move m in board.GetMoves()) { // next steps here } return bestScore; - Create a new game state from the current move:
Board b = board.MakeMove(m); float currentScore; Move currentMove = null;
- Start the recursion:
currentScore = Minimax(b, player, maxDepth, currentDepth + 1, ref currentMove);
- Validate the score for the current player:
if (board.GetCurrentPlayer() == player) { if (currentScore > bestScore) { bestScore = currentScore; bestMove = currentMove; } } - Validate the score for the adversary:
else { if (currentScore < bestScore) { bestScore = currentScore; bestMove = currentMove; } }
The algorithm works as a bounded depth-first search. In each step, the move is chosen by selecting the option that maximizes the player's score and assuming the opponent will take the option for minimizing it, until a terminal (leaf) node is reached.
The move tracking is done using recursion, and the heuristic for selecting or assuming an option depends on the Evaluate function.