Iterative deepening and the principal variation

[AndrewShort]

I recently improved my implementation of iterative deepening to feed the principal variation into the next iteration, meaning the PV from the last iteration is tried first (it sorts first). I thoroughly tested it to make it really is doing that, and it is working perfectly.

However, surprisingly, I found no significant improvement over feeding just the root move of the previous iterations's PV (the first move of the PV). I was expecting a large improvement.

I presently do not have QS or SEE implemented, and I suspect that is the problem. Because I don't have those implemented, a later iteration is in fact returning quite a different PV than before, whereas with QS and SEE, the iterations should return very similar PVs, hence improving iterative deepening.

[In my implementation of ID, I am incrementing the depth by 1, not 2, because with no QS and no SEE, the scores vary widely from one depth to another, but they do not vary widely if I skip by 2 (same side to move). So skipping by 2 allows me to use a smaller aspiration window]

Does that sound right? Is not having QS or SEE my problem? Or have you found that feeding the PV into the next iteration is generally no better than just feeding the root?

[bob]

I recently improved my implementation of iterative deepening to feed the principal variation into the next iteration, meaning the PV from the last iteration is tried first (it sorts first). I thoroughly tested it to make it really is doing that, and it is working perfectly.

However, surprisingly, I found no significant improvement over feeding just the root move of the previous iterations's PV (the first move of the PV). I was expecting a large improvement.

I presently do not have QS or SEE implemented, and I suspect that is the problem. Because I don't have those implemented, a later iteration is in fact returning quite a different PV than before, whereas with QS and SEE, the iterations should return very similar PVs, hence improving iterative deepening.

[In my implementation of ID, I am incrementing the depth by 1, not 2, because with no QS and no SEE, the scores vary widely from one depth to another, but they do not vary widely if I skip by 2 (same side to move). So skipping by 2 allows me to use a smaller aspiration window]

Does that sound right? Is not having QS or SEE my problem? Or have you found that feeding the PV into the next iteration is generally no better than just feeding the root?

You are overlooking the hash move. Most of the time, the hash move will stick around from one iteration to the next and that would be the PV move. This is only a problem when you run a very fast program (or use very fast hardware) with a hash table that is not large enough...

[Dann Corbit]

I recently improved my implementation of iterative deepening to feed the principal variation into the next iteration, meaning the PV from the last iteration is tried first (it sorts first). I thoroughly tested it to make it really is doing that, and it is working perfectly.

However, surprisingly, I found no significant improvement over feeding just the root move of the previous iterations's PV (the first move of the PV). I was expecting a large improvement.

I presently do not have QS or SEE implemented, and I suspect that is the problem. Because I don't have those implemented, a later iteration is in fact returning quite a different PV than before, whereas with QS and SEE, the iterations should return very similar PVs, hence improving iterative deepening.

[In my implementation of ID, I am incrementing the depth by 1, not 2, because with no QS and no SEE, the scores vary widely from one depth to another, but they do not vary widely if I skip by 2 (same side to move). So skipping by 2 allows me to use a smaller aspiration window]

That makes no sense to me. If you skip only one ply, it is the other side's turn to move.

Does that sound right? Is not having QS or SEE my problem? Or have you found that feeding the PV into the next iteration is generally no better than just feeding the root?

Do you have a hash table? It seems fairly likely that you will fish the pv node out of the hash table anyway.

[AndrewShort]

well, I do have a hash table, and I am sorting the hash move 1st. It's just that when I'm sorting the princ variation first, the hash move (if different) ends up 2nd, not 1st (by design). I only sort the principal variation once, so it affects very few sorts. The rest of the sorts use hash best move on top.

in effect what I'm seeing is that feeding the PV into the next iteration is not much better than feeding just the root move, I guess because my sorting (with hash move, etc) is already pretty good.

is that what you meant?

[wgarvin]

well, I do have a hash table, and I am sorting the hash move 1st. It's just that when I'm sorting the princ variation first, the hash move (if different) ends up 2nd, not 1st (by design). I only sort the principal variation once, so it affects very few sorts. The rest of the sorts use hash best move on top.

in effect what I'm seeing is that feeding the PV into the next iteration is not much better than feeding just the root move, I guess because my sorting (with hash move, etc) is already pretty good.

is that what you meant?

He probably meant that at the end of the iteration, most of the PV nodes are still in the hash table, so the hash moves from those nodes give you almost as much info as feeding an entire PV into it does...

I think some programs don't represent the PV anywhere other than the hash table? Should a hash replacement scheme prefer not to replace PV nodes?

[Dann Corbit]

well, I do have a hash table, and I am sorting the hash move 1st. It's just that when I'm sorting the princ variation first, the hash move (if different) ends up 2nd, not 1st (by design). I only sort the principal variation once, so it affects very few sorts. The rest of the sorts use hash best move on top.

in effect what I'm seeing is that feeding the PV into the next iteration is not much better than feeding just the root move, I guess because my sorting (with hash move, etc) is already pretty good.

is that what you meant?

He probably meant that at the end of the iteration, most of the PV nodes are still in the hash table, so the hash moves from those nodes give you almost as much info as feeding an entire PV into it does...

I think some programs don't represent the PV anywhere other than the hash table? Should a hash replacement scheme prefer not to replace PV nodes?

A hash replacement scheme should never replace a PV node unless it has already been played or is no longer possible to play. Which nodes are pv nodes is the most important information contained in the hash table, by far.

[bob]

well, I do have a hash table, and I am sorting the hash move 1st. It's just that when I'm sorting the princ variation first, the hash move (if different) ends up 2nd, not 1st (by design). I only sort the principal variation once, so it affects very few sorts. The rest of the sorts use hash best move on top.

in effect what I'm seeing is that feeding the PV into the next iteration is not much better than feeding just the root move, I guess because my sorting (with hash move, etc) is already pretty good.

is that what you meant?

He probably meant that at the end of the iteration, most of the PV nodes are still in the hash table, so the hash moves from those nodes give you almost as much info as feeding an entire PV into it does...

I think some programs don't represent the PV anywhere other than the hash table? Should a hash replacement scheme prefer not to replace PV nodes?

The problem is, you can't recognize a PV node...

[wgarvin]

The problem is, you can't recognize a PV node...

But as you finish searching nodes and unmake moves and go back up to the parent, can you mark the "best child" with a flag? I.e. a flag that means, "The best move, or hash move, in some parent node led to this node".

Then replacement would just always prefer to replace non-flagged ones instead of flagged ones.

[Dann Corbit]

well, I do have a hash table, and I am sorting the hash move 1st. It's just that when I'm sorting the princ variation first, the hash move (if different) ends up 2nd, not 1st (by design). I only sort the principal variation once, so it affects very few sorts. The rest of the sorts use hash best move on top.

in effect what I'm seeing is that feeding the PV into the next iteration is not much better than feeding just the root move, I guess because my sorting (with hash move, etc) is already pretty good.

is that what you meant?

He probably meant that at the end of the iteration, most of the PV nodes are still in the hash table, so the hash moves from those nodes give you almost as much info as feeding an entire PV into it does...

I think some programs don't represent the PV anywhere other than the hash table? Should a hash replacement scheme prefer not to replace PV nodes?

The problem is, you can't recognize a PV node...

There are some programs that reconstruct the pv purely from the hash (admittedly, this does not work perfectly). I have also seen programs that tag one of the flag bits if it is a pv node (but this is also problematic because pv nodes can change during the search). However, on average the best nodes from the transposition table should approximate closely the pv nodes.

[AndrewShort]

So it seems to me that if you already have hash-best-move implemented, that the only benefits of iterative deepening are:

(1) the ability to time-out with a good move at hand
(2) increased efficiency by filling up the hash table between iterations

Seems to me you don't have to bother with passing each iteration the previous iteration's PV, as the hash table gives you all that benefit already.