When we have a zero-sum game with only two players involved, we are able to improve Minimax, taking advantage of the principle that one player's loss is the other's gain. In this way, it is able to provide the same results as the Minimax algorithm. However, it does not track whose move it is.
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 a 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 we are developing 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 add a new function to the BoardAI class as follows:
- Create the
Negamaxfunction:public static float Negamax( Board board, int maxDepth, int currentDepth, ref Move bestMove) { // next steps here } - Validate the base case:
if (board.IsGameOver() || currentDepth == maxDepth) return board.Evaluate(); - Set the initial values:
bestMove = null; float bestScore = Mathf.NegativeInfinity;
- Loop through all the available 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 recursedScore; Move currentMove = null;
- Start the recursion:
recursedScore = Negamax(b, maxDepth, currentDepth + 1, ref currentMove);
- Set the current score and update the best score and move, if necessary:
float currentScore = -recursedScore; if (currentScore > bestScore) { bestScore = currentScore; bestMove = m; }
The base algorithm works the same but, as we did before, there are some advantages. At each step in the recursion, the scores from the previous steps have their sign inverted. Instead of choosing the best option, the algorithm changes the sign of the score, eliminating the need to track whose move it is.
As Negamax alternates the viewpoints between players at each step, the evaluate function used is the one with no parameters.