[Guide] Iterative Deepening

I have touched this subject briefly in earlier posts. Here is the full explanation.

Simply what we do is add a loop around the first call to alpha-beta. (in Mediocre it is located in the search()-method in the Engine-class)

It looks something like this:

for(current_depth = 1;; current_depth++)
{
   eval = alphaBeta(board, current_depth, -200000, 200000, pv);
   if(timesUp) break;
}

Speed considerations

Since we do a repeated search at every new depth it might seem we are spending a whole lot of extra time for getting search results we have no use for since they get overwritten at the next depth.

It is true that we spend some extra time, but actually it is not a lot. The number of nodes searched might look something like:

1 ply: 22
2 ply: 97
3 ply: 736
4 ply: 3,586
5 ply: 32,193

As you can see, all the nodes combined in the first four plies (4,441) is only a small part of the nodes visited in the deepest search (32,193). So we are actually not adding that much extra work to the engine.

Also the line we get as a result from the previous search depth is quite likely to be the best line at a deeper depth as well. So if we search the previously found line first we have a good chance of getting a lot of cutoffs, and vastly increasing the search speed of the alpha-beta.

We could get series of results looking something like:

1 ply: e4
2 ply: e4 e5
3 ply: e4 e5 Nf3
4 ply: e4 e5 Nf3 Nc6
5 ply: e4 e5 Nf3 Nc6 Bb5

This is the case if every search depth has the same idea of what is the best move. In this case we would see a huge improvement to the speed of the alpha beta, since every first move it searches will turn out to be the best. But we could also get something like:

1 ply: g3
2 ply: b3 d5
3 ply: c4 c5 d3
4 ply: d4 d5 c4 e6
5 ply: e4 c5 Nf3 Nc6 d4

In this case every new depth results in a new line and we would probably not gain that much from using the previous line. This is a rare occurence though, and even with this we would gain some speed since we could cut off the silly lines fast before running in to the new best line.

Time management

I have showed that we gain speed by using iterative deepening. The other advantage is; since we cut off when a certain time is reached we get an easy way of managing the engine's time usage.

WinBoard sends a time-variable after every move that we can use to keep track of our current time. So we do not need to keep an internal timer. From this value we can take a certain percent to use before breaking the search and returning a line.

So with iterative deepening we get both more effective searches and a way to manage the time. All in one simple piece of code.

How it works in Mediocre right now

Since Mediocre can not search very deep at the moment an allocated time of 2 seconds will result in a search to about 5 ply, and the time taken will be around 10 seconds.

This is because the searches up to 4 ply will take less than 2 seconds while the 5th search will about 8 seconds depending on the position. We will have to take this into consideration when deciding how much time to use for a move.

Hopefully with better move ordering and transposition tables etc. we will get a smaller jump between the plies.