[Guide] Aspiration Windows, Killer moves and Principal Variation Search

I have been playing around with these three lately as mentioned and they seem to be working great. Let us get some facts down.

Aspiration Windows

Since last download (dl9) we have a working iterative deepening in Mediocre. Until now it has been used to cut off the search after a certain time (this is not fully functional yet, but still) and use the last iteration's best line for move ordering.

There is more things you can do with this, one being Aspiration Windows.

In a call to alphaBeta() we have always used;

alpha = -200000 (a very large negative number, -infinity)
beta = 200000 (a very large positive number, +infinity)

This is done to make sure we always get new values for alpha and beta in the search.

But since we now have a previous iteration's result we could estimate what the alpha and beta should be. Instead of using -infinity and +infinity we can use the evaluation returned from the last iteration and put a 'window' around it. So we call alphaBeta() with:

alpha = last_iteration_eval + window_size
beta = last_iteration_eval - window_size

Essentially what we do is assume the last iteration's evaluation is good, and the next iteration will not return evaluations that are too far from it.

A narrower search means more lines are cut off and the search is faster.

The problem is if the returned evaluation from the alphaBeta() called with an aspiration window should be less than alpha or greater than beta, the evaluation have changed too much and we need to call the alphaBeta() again with the same depth and alpha=-infinity, beta=+infinity.

This is of course extra work, but if we set the window_size to a good value it will not happen very often, and the gains will be far better than the losses.

In my iterative deepening code the aspiration windows look something like this (you can see the full code in the next download):

if(eval <= alpha || eval >= beta) // Eval outside window
{
   // We need to do a full search
   alpha = -200000;
   beta = 200000;
   continue; // Call alphaBeta() again with same depth
}

// We didn't fall out of the window, and can move on
// to the next depth with a window set around the eval
alpha = eval -10;
beta = eval +10;
current_depth++;

Notice how we do not change the depth if the evaluation falls outside the window. But if the evaluation is within the window, we can safely call alphaBeta() with the next depth and a new window based on that evaluation.

One thing is consider is the size of the aspiration window. In the example above I used 10, which is a tenth of a pawn. This is a quite small window to use, but since Mediocre does not have that much evaluation features yet it seems to work well, without too many missed windows.

The size of the window is a balancing act that needs to be adjusted to the engine. If you choose a too small window, you will miss the window too often and have to do a lot of researches. If you choose a too large window, the gains from the aspiration windows are lost since we will not get very many cutoffs.

In Mediocre aspiration windows are working very well with no loss of accuracy.

Killer moves heuristic

Killer moves are used to get better move ordering. They are moves that cause beta cutoffs at a certain ply, so when we get to that ply we remember what moves caused the cutoff and search them early.

Mediocre keeps track of two killer moves at each ply. They are handled by an internal class called KillerMoves, which have two arrays primaryKillers and secondaryKillers. If a move causes a beta cutoff we place it in one of the arrays at an index corresponding to the ply it was found in.

For now Mediocre does not keep track of how often a certain move causes a cutoff. It simply puts the move causing a beta cutoff into primaryKillers, and if primaryKillers already holds a move at that ply, we move it to secondaryKillers. I will probably refine this a bit later.

When we sort the moves with sortMoves() we handle the killer moves by themselves and add them early to the top in the final sortedMoves-array. Right now killer moves comes after the previous best line move, but before captures. This might change when more move ordering techniques are added.

Principal Variation Search

The principal variation search works under the assumption of our first move being the best. If we can call alphaBeta() like this after having found our first best move

eval = -alphaBeta(board, ply-1, -alpha -1, -alpha, localpv);

we can cutoff all the moves after it without having to evaluate them fully.

Since we search with a minimal window the search will be very fast, and we are hoping we do not get a value back that is higher than alpha. If we do not the move was indeed the best, and we have confirmed this by a very fast search.

However if we do get back an evaluation that is higher than alpha, we need to research with the ordinary alpha and beta values, since there is a move out there that is better than our first.

While I understand the idea, I have seen no real speed gains in Mediocre by using it. Probably because of the poor move ordering. Atleast there is no noticeable slowdown either, so we might as well keep it for now.