Including a search strategy also makes room for new challenges. Negascouting is the result of narrowing the search by improving the pruning heuristic. It is based on a concept called a search window, which is the interval between the alpha and beta values. So, reducing the search window increases the chance of a branch being pruned.
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
ABNegascoutfunction:public static float ABNegascout ( 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; float adaptiveBeta = beta;
- 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 the recursion:
Move currentMove = null; float recursedScore; int depth = currentDepth + 1; float max = Mathf.Max(alpha, bestScore);
- Call the recursion:
recursedScore = ABNegamax(b, player, maxDepth, depth, ref currentMove, -adaptiveBeta, max);
- Set the current score and validate it:
float currentScore = -recursedScore; if (currentScore > bestScore) { // next steps here } - Validate for pruning:
if (adaptiveBeta == beta || currentDepth >= maxDepth - 2) { bestScore = currentScore; bestMove = currentMove; } - Otherwise, take a look around:
else { float negativeBest; negativeBest = ABNegascout(b, player, maxDepth, depth, ref bestMove, -beta, -currentScore); bestScore = -negativeBest; } - Stop the loop if necessary. Otherwise, update the adaptive value:
if (bestScore >= beta) return bestScore; adaptiveBeta = Mathf.Max(alpha, bestScore) + 1f;
This algorithm works by examining the first move of each node. The following moves are examined using a scout pass with a narrower window based on the first move. If the pass fails, it is repeated using a full-width window. As a result, a large number of branches are pruned and failures are avoided.