Jan 2, 2007

[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.


The_Duck said...

How are you getting the program to search the previous iteration's principal variation on the next search?

Jonatan Pettersson said...

If you look at my current code I have a way of extracting the principal variation by passing around a local variation list in the alphaBeta()-method. (explained in one of my earlier posts)

To start searching that variation in the next iteration, first I save the best line found in the previous search to a global variable. This is done so I can reset the principal variation variable used in alphaBeta.

Then I have a check in the beginning of the alphaBeta()-method, which adds the right move from the global 'previous best line'-variable to the first spot in available moves, then add the rest of the available moves. This is done if a boolean 'usingPreviousLine' is set to true, and we're at the correct depth.

Once we get a new alpha value we know we have searched all of the first line (since the first line always results in a new alpha), and there I switch 'usingPreviousLine' to false which disables adding moves from the previous best line.

I have not yet decided if I should use this setup or if it's time to add a 'sortMoves()' method which takes care of both adding the best line and any other sorting we might need.

In any case I will explain it in detail in my next post.

The_Duck said...

Ah, I see. If alpha is anything other than -infinity, then you aren't on the first line searched.

I implemented a hash table where I store the value and best move at every node that was searched with depth > 0. Then on the next iteration the program looks up the best move for whatever node its currently searching in the hash table, and tries that move first. It also detects transpositions within the current search iteration. I'm not sure how well this is actually working...