There is still room for improving the Negamax algorithm. Despite its efficiency, the downside of the Negamax algorithm is that it examines more nodes than necessary (for example, board positions). To overcome this problem, we use Negamax with a search strategy called alpha-beta pruning.
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 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
ABNegamaxfunction:public static float ABNegamax( Board board, int player, int maxDepth, int currentDepth, ref Move bestMove, float alpha, float beta) { // next steps here } - Validate the base case:
if (board.IsGameOver() || currentDepth == maxDepth) return board.Evaluate(player); - Set the initial values:
bestMove = null; float bestScore = Mathf.NegativeInfinity;
- Loop through every available move 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);
- Set the values for calling the recursion:
float recursedScore; Move currentMove = null; int cd = currentDepth + 1; float max = Mathf.Max(alpha, bestScore);
- Start the recursion:
recursedScore = ABNegamax(b, player, maxDepth, cd, ref currentMove, -beta, max);
- Set the current score and update the best score and move if necessary. Also, stop the iteration if necessary:
float currentScore = -recursedScore; if (currentScore > bestScore) { bestScore = currentScore; bestMove = m; if (bestScore >= beta) return bestScore; }
Since we know the basic principle of the algorithm, let's concentrate on the search strategy. There are two values: alpha and beta. The alpha value is the lower score a player can achieve, thus avoiding considering any move where the opponent has the opportunity to lessen it. Similarly, the beta value is the upper limit; no matter how tempting the new option is, the algorithm assumes that the opponent won't give the opportunity to take it.
Given the alternation between each player (minimizing and maximizing), only one value needs to be checked at each step.