an interesting bug mixed with testing...

[bob]

Yesterday while working on a rewrite of the current book learning code to eliminate a glitch someone had pointed out (if opponent resigns crafty could get wrong learning score at times) I found a odd bit of output that caught my eye. I was doing very shallow searches (5 plies for speed) while testing the new book learning code and for one move I noticed a 5 ply search but a 4 ply variation of moves. Here's what I found:

In SearchRoot() (and only there) I do three types of search: A normal search (on the first branch) and then for the rest of the branches after the first I use PVS. However, the PVS is a bit more complicated when LMR is factored in. The basic idea was this:

ext = SearchExtensions(xxx);

Search extensions can return a +1 if we should extend this move by 1 ply (this move gives check for example), or a 0 if the move should not be extended, or even a -1 if the move should be reduced (LMR).

Next I did a normal PVS search

v = Search(-alpha-1, -alpha, depth - 1 + ext);

Note that was possibly a reduced search.

If that fails high, I then do a LMR research with no reduction:

v = Search(-alpha-1, -alpha, depth - 1)

If that fails high, I am now in a normal PVS position where I failed high on the null window, so to relax the window I research:

v = Search(-beta, -alpha, depth - 1 + ext);

That +ext was a killer. I need it because this could be a check and I want to go one ply deeper. But if it is a reduced value (-1) I do not want to use it as that now makes me do a search to one ply less on the PVS re-search which could find a better score that is inside the alpha/beta window, but which is also one ply shallower than it should be.

I put some checks in to see how often this happens and it is very infrequent. I fixed it by adding

ext = Max(0, ext);

Right before the last (PVS) re-search code. I had already done this in all the other search routines but had missed it here somehow. But that isn't what was interesting. The simple fix above solved the short PV problem and fixed the "quirk" I had noted.

I then decided to run a cluster test to see if it made any difference (I expected little because it was not very frequent when I measured this). And I immediately found this:

Code: Select all

Rank Name               Elo    +    - games score oppo. draws
   3 Crafty-23.0-4     2611    5    5 31128   53%  2587   22%
   4 Crafty-23.0-5     2609    4    4 31128   53%  2587   22%
   5 Crafty-23.0-2     2608    5    5 31128   53%  2587   21%
   6 Crafty-23.0-1     2605    5    5 31128   52%  2587   22%
   7 Crafty-23.0-3     2605    5    5 31128   52%  2587   22%
   8 Crafty-23.0R14-2  2604    4    4 31128   52%  2587   22%
   9 Crafty-23.0R14-3  2604    4    4 31128   52%  2587   22%
  10 Crafty-23.0R14-4  2603    5    5 31128   52%  2587   22%
  11 Crafty-23.0R14-1  2602    4    4 31128   52%  2587   21%
  12 Crafty-23.0R14-5  2601    5    4 31128   52%  2587   22%

Crafty-23.0 is the original version, Crafty-23.0R14 is the new version with just the 1-line change. I ran each test 5 times after I saw the first single run results and it is consistent that the new (fixed) version is somewhat worse than the original. Not by a lot, but still worse. I then ran a longer test and things went the way I expected where the two versions were near equal with the new version being very slightly better.

But a good example of where something looks a little worse at a short time control and a little better at a longer time control.

Note that this is a small speed issue in that the re-search with the bug was a little faster than without. So the search slows down just a bit with this, and the fast games highlight that speed...