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:
Negamax
function:public static float Negamax( Board board, int maxDepth, int currentDepth, ref Move bestMove) { // next steps here }
if (board.IsGameOver() || currentDepth == maxDepth) return board.Evaluate();
bestMove = null; float bestScore = Mathf.NegativeInfinity;
foreach (Move m in board.GetMoves()) { // next steps here } return bestScore;
Board b = board.MakeMove(m); float recursedScore; Move currentMove = null;
recursedScore = Negamax(b, maxDepth, currentDepth + 1, ref currentMove);
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.