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:
BoardAI
class:using UnityEngine; using System.Collections; public class BoardAI { }
Minimax
function:public static float Minimax( Board board, int player, int maxDepth, int currentDepth, ref Move bestMove) { // next steps here }
if (board.IsGameOver() || currentDepth == maxDepth) return board.Evaluate(player);
bestMove = null; float bestScore = Mathf.Infinity; if (board.GetCurrentPlayer() == player) bestScore = Mathf.NegativeInfinity;
foreach (Move m in board.GetMoves()) { // next steps here } return bestScore;
Board b = board.MakeMove(m); float currentScore; Move currentMove = null;
currentScore = Minimax(b, player, maxDepth, currentDepth + 1, ref currentMove);
if (board.GetCurrentPlayer() == player) { if (currentScore > bestScore) { bestScore = currentScore; bestMove = currentMove; } }
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.