working!

[bob]

Here are a couple of positions where the old version ended a PV with <HT> and the new one does not. What is particularly nice is that now, when I take this extended PV and stuff it into the program and type "score" I get exactly the same score as is printed out with the PV. Here goes:

Code: Select all

old pv:
               25    10.96  -2.71   1. ... a4 2. Ba3 Rh7 3. Rb1 Rh5 4.
                                    Kg4 Ba6 5. Kf4 Kb5 6. Bb2 Rh7 7. Kg3
                                    Bc8 8. Kf4 Bd7 9. Ba3 Rh2 <HT>
new pv&#58;
               25     7.40  -2.70   1. ... a4 2. Ba3 Rh7 3. Rb1 Rh5 4.
                                    Kg4 Ba6 5. Bb2 Rh7 6. Ra1 Kb5 7. Kf4
                                    Bb7 8. Re1 Rh4+ 9. Kg3 Rh8 10. Kf4
                                    Bc6 11. Ra1 Rh4+ 12. Kg3 Rh7 13. Kf4
                                    Rh8 14. Ke3 Rh3+ 15. Kf4 Bd7 16. Ra3
                                    Rh2

verification&#58;
White&#40;17&#41;&#58; score
note&#58; scores are for the white side
                        +-----------white----------+-----------black----------+
material.......  -0.95  |    comp     mg      eg   |    comp     mg      eg   |
pawns..........  -0.03  |    0.25    0.28    0.24  |   -0.28   -0.28   -0.29  |
passed pawns...  -2.43  |    0.00    0.00    0.00  |   -2.43   -1.38   -2.80  |
knights........   0.00  |    0.00    0.00    0.00  |    0.00    0.00    0.00  |
bishops........  -0.04  |    0.37    0.24    0.42  |   -0.41   -0.28   -0.46  |
rooks..........  -0.53  |    0.00    0.00    0.00  |   -0.53   -0.57   -0.52  |
queens.........   0.00  |    0.00    0.00    0.00  |    0.00    0.00    0.00  |
kings..........   0.36  |    0.29    0.00    0.40  |    0.07    0.00    0.10  |
development....   0.00  |    0.00    0.00    0.00  |    0.00    0.00    0.00  |
pawn races.....   0.00  +--------------------------+--------------------------+
total..........  -2.70

The above is position wac230. To verify the PV, I reloaded the position, used the "reada" (read and append) command, and stuffed the PV into the input. Then typed "score".

So far, I am using 16384 PV entries. When I do a store or probe, I look at 8 entries. This is hardly ever done. But be aware, node counts change as when you get the longer PV, the next ply has better move ordering since it plays more of the moves in the PV first. I am not certain about the 16384 size yet, nor the 8 entry bucket. I am going to run some games. I have Crafty complaining if it detects overwrites (it does a hash probe, gets a hit, finds it is EXACT, and within the current A/B bounds, and then goes to the PV hash storage but can't find the matching signature.)

So it looks reasonable. I'll release this once I finish tuning, tweaking, and settle on a reasonable size so that this doesn't need adjusting by the user. Actually looks pretty good, however, and very little effort (only changes are to HashProbe() and HashStore()... and very rarely executed so it doesn't have any cost I could measure... Another nice feature is that it doesn't change a thing in the normal hash table, no lost entries or anything.

Meant to add this to the thread discussing this issue. Somehow that did not happen...

[Dirt]

Nice. The occasional short PV followed by <HT> (hash table, I eventually realized) was frustrating.

[bob]

Nice. The occasional short PV followed by <HT> (hash table, I eventually realized) was frustrating.

It is almost eliminated. There is always a chance that an EXACT hit happens, but the path entry is gone, since that table is way smaller. But after several thousand positions, so far, searched to significant depth, I have not seen one. Also new program is identical in speed, so there is no cost in terms of NPS that is measurable.

[Dann Corbit]

Feature request:
When Crafty is analyzing a position and finds the answer in the EGTB file, when crafty displays the pv, have it chase the pv to the end like Yace does.

IOW...
Crafty:

Code: Select all

EPD Kit revision date: 1996.04.21
unable to open book file [./books.bin].

Initializing multiple threads.
System is SMP, not NUMA.
EGTB access enabled
using tbpath=c:\chess\winboard\nalimov
6 piece tablebase files found
80229kb of RAM used for TB indices and decompression tables
EGTB cache memory =   32M bytes.
pondering disabled.
choose from book moves randomly (using weights.)
choose from 4 best moves.
show book statistics
Warning--  xboard 'memory' option disabled
hash table memory =   32M bytes.
Warning--  xboard 'memory' option disabled
pawn hash table memory =   16M bytes.


Crafty v23.3 JA (1 cpus)

White(1): setboard 4k1n1/8/8/8/8/3B4/1R6/2K5 w - -
White(1): go
              time surplus   0.00  time limit 57.00 (+27.00) (3:00)
              depth   time  score   variation (1)
                4->   0.04  Mat13   1. Rb8+ <EGTB>
              time=0.04  mat=5  n=90  fh=100%  nps=1.0M
              extensions=7 qchecks=4 reduced=0 pruned=0
              predicted=0  evals=10  50move=0  EGTBprobes=1  hits=1
              SMP->  splits=0  aborts=0  data=0/65536  elap=0.04

mate in 13 moves.

White&#40;1&#41;&#58; Rb8+
              time used&#58;   0.06
Black&#40;1&#41;&#58;

Yace:

Code: Select all

max_PV_WB = 256
book_holes = 8
margin_book_learn_white = -45
margin_book_learn_black = -45
null_high = 3.50
white ( 1): setboard  4k1n1/8/8/8/8/3B4/1R6/2K5 w - -
Stored 0 learned positions into hash table
white ( 1): go
tbscore = 32754
usetime = 19.93, mintime = 9.97 maxtime = 49.83 tl 598.00 ml 40 tu 0.00
         1   0.003   6.09  1t  1.Rb7 {510}
         2   0.006  Mat19  1t+ 1.Re2+ {EGTB} {510}
         3   0.009  Mat19  1t  1.Re2+ {EGTB} {510}
         7   0.012  Mat13  1t+ 1.Rb8+ {EGTB} {510}
         8   0.015  Mat13  1t  1.Rb8+ {EGTB} {510}
        31   0.018  Mat13  1.  1.Rb8+ {EGTB} {510}
        32   0.022  Mat13  2t  1.Rb8+ {EGTB} {510}
        60   0.024  Mat13  2.  1.Rb8+ {EGTB} {510}
        61   0.028  Mat13  3t  1.Rb8+ {EGTB} {510}
        89   0.031  Mat13  3.  1.Rb8+ {EGTB} {510}
        90   0.034  Mat13  4t  1.Rb8+ {EGTB} {510}
       118   0.037  Mat13  4.  1.Rb8+ {EGTB} {510}
       119   0.040  Mat13  5t  1.Rb8+ {EGTB} {510}
       147   0.043  Mat13  5.  1.Rb8+ {EGTB} {510}
       148   0.047  Mat13  6t  1.Rb8+ {EGTB} {510}
       176   0.050  Mat13  6.  1.Rb8+ {EGTB} {510}
       177   0.053  Mat13  7t  1.Rb8+ {EGTB} {510}
       205   0.056  Mat13  7.  1.Rb8+ {EGTB} {510}
       206   0.059  Mat13  8t  1.Rb8+ {EGTB} {510}
       234   0.062  Mat13  8.  1.Rb8+ {EGTB} {510}
       235   0.065  Mat13  9t  1.Rb8+ {EGTB} {510}
       263   0.069  Mat13  9.  1.Rb8+ {EGTB} {510}
       264   0.072  Mat13 10t  1.Rb8+ {EGTB} {510}
       292   0.075  Mat13 10.  1.Rb8+ {EGTB} {510}
       293   0.078  Mat13 11t  1.Rb8+ {EGTB} {510}
       321   0.081  Mat13 11.  1.Rb8+ {EGTB} {510}
       322   0.084  Mat13 12t  1.Rb8+ {EGTB} {510}
       350   0.087  Mat13 12.  1.Rb8+ {EGTB} {510}
       351   0.090  Mat13 13t  1.Rb8+ {EGTB} {510}
       379   0.094  Mat13 13.  1.Rb8+ {EGTB} {510}
       380   0.097  Mat13 14t  1.Rb8+ {EGTB} {510}
       408   0.100  Mat13 14.  1.Rb8+ {EGTB} {510}
       409   0.103  Mat13 15t  1.Rb8+ {EGTB} {510}
       437   0.106  Mat13 15.  1.Rb8+ {EGTB} {510}
       438   0.109  Mat13 16t  1.Rb8+ {EGTB} {510}
       466   0.112  Mat13 16.  1.Rb8+ {EGTB} {510}
       467   0.116  Mat13 17t  1.Rb8+ {EGTB} {510}
       495   0.119  Mat13 17.  1.Rb8+ {EGTB} {510}
       496   0.122  Mat13 18t  1.Rb8+ {EGTB} {510}
       524   0.125  Mat13 18.  1.Rb8+ {EGTB} {510}
       525   0.128  Mat13 19t  1.Rb8+ {EGTB} {510}
       553   0.131  Mat13 19.  1.Rb8+ {EGTB} {510}
       554   0.134  Mat13 20t  1.Rb8+ {EGTB} {510}
       582   0.138  Mat13 20.  1.Rb8+ {EGTB} {510}
       583   0.141  Mat13 21t  1.Rb8+ {EGTB} {510}
       611   0.144  Mat13 21.  1.Rb8+ {EGTB} {510}
       612   0.147  Mat13 22t  1.Rb8+ {EGTB} {510}
       640   0.150  Mat13 22.  1.Rb8+ {EGTB} {510}
       641   0.153  Mat13 23t  1.Rb8+ {EGTB} {510}
       669   0.157  Mat13 23.  1.Rb8+ {EGTB} {510}
       670   0.159  Mat13 24t  1.Rb8+ {EGTB} {510}
       698   0.163  Mat13 24.  1.Rb8+ {EGTB} {510}
       699   0.166  Mat13 25t  1.Rb8+ {EGTB} {510}
       727   0.169  Mat13 25.  1.Rb8+ {EGTB} {510}
       728   0.172  Mat13 26t  1.Rb8+ {EGTB} {510}
       756   0.175  Mat13 26.  1.Rb8+ {EGTB} {510}
       757   0.178  Mat13 27t  1.Rb8+ {EGTB} {510}
       785   0.182  Mat13 27.  1.Rb8+ {EGTB} {510}
       785   0.185  Mat13 27f. 1.Rb8+ {EGTB} 1...Kf7! 2.Bc4+! Kg7 3.Bxg8 Kf6!
                               4.Re8 Kf5 5.Re6 Kg5 6.Kd1 Kh5 7.Kd2 Kg5 8.Ke3!
                               Kg4! 9.Bh7! Kg3! 10.Bf5! Kg2 11.Rg6+! Kh2
                               12.Kf2! Kh1 13.Rh6#! {850}
785 Nodes, 0.00% Leavenodes, 4243 Nodes/sec
55 eval, 100.00% score, 5612 genmoves, 0.00% captures le 132/-12
ext: pawn 0, rcp 0, chk 0, repchk 0,
     null 0, prune 0, pe 0, 1rep 0
htable: 82 store, 0 rejected, 845 probe, 96.3% f/p, 992.7% f/s
entries 10666665 age 1 renew 0
interior recognizer probes 0, found 0 egtb probes 401, found 401 max_depth 1
white ( 1): Rb8+
black ( 1):

[bob]

Feature request:
When Crafty is analyzing a position and finds the answer in the EGTB file, when crafty displays the pv, have it chase the pv to the end like Yace does.

Code is already there. If you type "egtb" it will give you the complete PV all the way to the end, putting ! after any move that is an "only best move". I could do this in the normal output, but it is problematic when playing very fast games, in that Crafty often has to make a move faster than the latency for a single disk access.

I could, perhaps, add some sort of option that lets the user turn that on if he wants, when time doesn't matter...

IOW...
Crafty:

Code: Select all

EPD Kit revision date: 1996.04.21
unable to open book file [./books.bin].

Initializing multiple threads.
System is SMP, not NUMA.
EGTB access enabled
using tbpath=c:\chess\winboard\nalimov
6 piece tablebase files found
80229kb of RAM used for TB indices and decompression tables
EGTB cache memory =   32M bytes.
pondering disabled.
choose from book moves randomly (using weights.)
choose from 4 best moves.
show book statistics
Warning--  xboard 'memory' option disabled
hash table memory =   32M bytes.
Warning--  xboard 'memory' option disabled
pawn hash table memory =   16M bytes.


Crafty v23.3 JA (1 cpus)

White(1): setboard 4k1n1/8/8/8/8/3B4/1R6/2K5 w - -
White(1): go
              time surplus   0.00  time limit 57.00 (+27.00) (3:00)
              depth   time  score   variation (1)
                4->   0.04  Mat13   1. Rb8+ <EGTB>
              time=0.04  mat=5  n=90  fh=100%  nps=1.0M
              extensions=7 qchecks=4 reduced=0 pruned=0
              predicted=0  evals=10  50move=0  EGTBprobes=1  hits=1
              SMP->  splits=0  aborts=0  data=0/65536  elap=0.04

mate in 13 moves.

White&#40;1&#41;&#58; Rb8+
              time used&#58;   0.06
Black&#40;1&#41;&#58;

Yace:

Code: Select all

max_PV_WB = 256
book_holes = 8
margin_book_learn_white = -45
margin_book_learn_black = -45
null_high = 3.50
white ( 1): setboard  4k1n1/8/8/8/8/3B4/1R6/2K5 w - -
Stored 0 learned positions into hash table
white ( 1): go
tbscore = 32754
usetime = 19.93, mintime = 9.97 maxtime = 49.83 tl 598.00 ml 40 tu 0.00
         1   0.003   6.09  1t  1.Rb7 {510}
         2   0.006  Mat19  1t+ 1.Re2+ {EGTB} {510}
         3   0.009  Mat19  1t  1.Re2+ {EGTB} {510}
         7   0.012  Mat13  1t+ 1.Rb8+ {EGTB} {510}
         8   0.015  Mat13  1t  1.Rb8+ {EGTB} {510}
        31   0.018  Mat13  1.  1.Rb8+ {EGTB} {510}
        32   0.022  Mat13  2t  1.Rb8+ {EGTB} {510}
        60   0.024  Mat13  2.  1.Rb8+ {EGTB} {510}
        61   0.028  Mat13  3t  1.Rb8+ {EGTB} {510}
        89   0.031  Mat13  3.  1.Rb8+ {EGTB} {510}
        90   0.034  Mat13  4t  1.Rb8+ {EGTB} {510}
       118   0.037  Mat13  4.  1.Rb8+ {EGTB} {510}
       119   0.040  Mat13  5t  1.Rb8+ {EGTB} {510}
       147   0.043  Mat13  5.  1.Rb8+ {EGTB} {510}
       148   0.047  Mat13  6t  1.Rb8+ {EGTB} {510}
       176   0.050  Mat13  6.  1.Rb8+ {EGTB} {510}
       177   0.053  Mat13  7t  1.Rb8+ {EGTB} {510}
       205   0.056  Mat13  7.  1.Rb8+ {EGTB} {510}
       206   0.059  Mat13  8t  1.Rb8+ {EGTB} {510}
       234   0.062  Mat13  8.  1.Rb8+ {EGTB} {510}
       235   0.065  Mat13  9t  1.Rb8+ {EGTB} {510}
       263   0.069  Mat13  9.  1.Rb8+ {EGTB} {510}
       264   0.072  Mat13 10t  1.Rb8+ {EGTB} {510}
       292   0.075  Mat13 10.  1.Rb8+ {EGTB} {510}
       293   0.078  Mat13 11t  1.Rb8+ {EGTB} {510}
       321   0.081  Mat13 11.  1.Rb8+ {EGTB} {510}
       322   0.084  Mat13 12t  1.Rb8+ {EGTB} {510}
       350   0.087  Mat13 12.  1.Rb8+ {EGTB} {510}
       351   0.090  Mat13 13t  1.Rb8+ {EGTB} {510}
       379   0.094  Mat13 13.  1.Rb8+ {EGTB} {510}
       380   0.097  Mat13 14t  1.Rb8+ {EGTB} {510}
       408   0.100  Mat13 14.  1.Rb8+ {EGTB} {510}
       409   0.103  Mat13 15t  1.Rb8+ {EGTB} {510}
       437   0.106  Mat13 15.  1.Rb8+ {EGTB} {510}
       438   0.109  Mat13 16t  1.Rb8+ {EGTB} {510}
       466   0.112  Mat13 16.  1.Rb8+ {EGTB} {510}
       467   0.116  Mat13 17t  1.Rb8+ {EGTB} {510}
       495   0.119  Mat13 17.  1.Rb8+ {EGTB} {510}
       496   0.122  Mat13 18t  1.Rb8+ {EGTB} {510}
       524   0.125  Mat13 18.  1.Rb8+ {EGTB} {510}
       525   0.128  Mat13 19t  1.Rb8+ {EGTB} {510}
       553   0.131  Mat13 19.  1.Rb8+ {EGTB} {510}
       554   0.134  Mat13 20t  1.Rb8+ {EGTB} {510}
       582   0.138  Mat13 20.  1.Rb8+ {EGTB} {510}
       583   0.141  Mat13 21t  1.Rb8+ {EGTB} {510}
       611   0.144  Mat13 21.  1.Rb8+ {EGTB} {510}
       612   0.147  Mat13 22t  1.Rb8+ {EGTB} {510}
       640   0.150  Mat13 22.  1.Rb8+ {EGTB} {510}
       641   0.153  Mat13 23t  1.Rb8+ {EGTB} {510}
       669   0.157  Mat13 23.  1.Rb8+ {EGTB} {510}
       670   0.159  Mat13 24t  1.Rb8+ {EGTB} {510}
       698   0.163  Mat13 24.  1.Rb8+ {EGTB} {510}
       699   0.166  Mat13 25t  1.Rb8+ {EGTB} {510}
       727   0.169  Mat13 25.  1.Rb8+ {EGTB} {510}
       728   0.172  Mat13 26t  1.Rb8+ {EGTB} {510}
       756   0.175  Mat13 26.  1.Rb8+ {EGTB} {510}
       757   0.178  Mat13 27t  1.Rb8+ {EGTB} {510}
       785   0.182  Mat13 27.  1.Rb8+ {EGTB} {510}
       785   0.185  Mat13 27f. 1.Rb8+ {EGTB} 1...Kf7! 2.Bc4+! Kg7 3.Bxg8 Kf6!
                               4.Re8 Kf5 5.Re6 Kg5 6.Kd1 Kh5 7.Kd2 Kg5 8.Ke3!
                               Kg4! 9.Bh7! Kg3! 10.Bf5! Kg2 11.Rg6+! Kh2
                               12.Kf2! Kh1 13.Rh6#! {850}
785 Nodes, 0.00% Leavenodes, 4243 Nodes/sec
55 eval, 100.00% score, 5612 genmoves, 0.00% captures le 132/-12
ext: pawn 0, rcp 0, chk 0, repchk 0,
     null 0, prune 0, pe 0, 1rep 0
htable: 82 store, 0 rejected, 845 probe, 96.3% f/p, 992.7% f/s
entries 10666665 age 1 renew 0
interior recognizer probes 0, found 0 egtb probes 401, found 401 max_depth 1
white ( 1): Rb8+
black ( 1):

[bob]

In doing this, I ran a few experiments while debugging my current code.

In normal Crafty, whenever it displays a PV (in DisplayPV() in utility.c) after it has walked to the end of the PV as each move is displays, it then does a HashProbe() to see if the final position is known, and if so, uses this approach to walk down any positions in the hash table to lengthen the PV. It has always done this.

For my testing, I had a version of Crafty that did the following, all at the same time...

(1) Display the normal PV returned by the search, no "lengthening" as described above.

(2) Display the normal PV, but "lengthened" as above.

(3) Start at the root, and reconstruct the PV (as in the lengthening process above where I just assumed that only the root move was known, and then "probed" my was as far as I could go. This is what the programs that only use hash pv-reconstruction do.)

(4) Use the new approach which stores the partial path with EXACT entries, and on an EXACT match, grafts that partial PV on to the end of the current PV.

Using (1) and (2) produced PVs that did not agree. Not every time, but more often than "rarely". In particular, when (2) produced a "short PV" with <HT> on the end, (1) almost always made that longer, although the <HT> was still stuck on the end since there was no way to know whether we had reached the real end of the PV or not. No surprises there.

(3) was more interesting. It produced some short PVs as expected when key table entries got overwritten. But more interestingly, it produced some PVs that were wrong. Often the last few plies, but sometimes even earlier. I discovered this when I looked at the (4) output. (2) also produced this problem, where the "extended moves" did not quite belong in the PV, but were added anyway.

(4) PVs were perfect, unless I ran a search that overwrote a key path entry. Then I would see an error indicating that I got an EXACT hash match, but when I went to the path HT for that entry, the signature did not match. This is where I decided to go bigger on the path hash as mentioned last night. But as I looked, every time I got a PV from (4), I would go down to the end and compute the score (I have to go to the end as I display the moves anyway) and in every last case, the score at the end matched the backed up score, except when I knew there was a missing path entry as described above. So I proved that these PVs are perfect so long as there is no critical collision on the path HT. And in comparing the PVs from (1) and (3) to (4) I discovered that there were a number of cases where (1) and/or (3) produced a PV that was _longer_ than (4), meaning it was incorrect. And on occasion, the score at the end of that longer PV was significantly different from the score backed up. On a couple of occasions (out of hundreds) the score was off by +/- 3.00... So those "extra moves" tacked on (again, Crafty has been doing this for years) was not so good. And, in fact, I found a few cases where they hurt somewhat, because I always stuff the PV back into the hash before starting the next iteration, just to make sure it is there to guide the search correctly.

Before everyone starts jumping up and down and saying "Bob has solved the trans/ref problem... we won't see any more bogus draws and stuff..." Bob has _not_ solved that. My code _only_ affects EXACT TT entries. There are not very many of them. To do this for _all_ TT entries would be a huge memory expense, plus a big computational expense, and the program would play weaker. But at the present, so long as there is no critical collision in the TT path hash entries, the PVs will now be perfect. I am now trying to clean this up somewhat, and am going to make the path TT dynamic in size using malloc(). I'll make the default reasonable, but it will be possible to change it at will, but it will not be affected by "hash or hashp" settings at all.

It is pretty amazing how the TT data can alter a PV in surprising ways. And it is nice to finally have a perfect PV so that I can debug an odd eval problem, without trying to figure out exactly what position the terminal score came from...

In testing, I even found a couple of positions where the hash hit only provided a score, and no PV, because it happened at the last non-qsearch ply and there was no reasonable capture. I had not anticipated this and copied one bogus move to the real PV, which made it show up quickly as a problem...

[marcelk]

So far, I am using 16384 PV entries. When I do a store or probe, I look at 8 entries. This is hardly ever done. But be aware, node counts change as when you get the longer PV, the next ply has better move ordering since it plays more of the moves in the PV first. I am not certain about the 16384 size yet, nor the 8 entry bucket.

I was wondering: why would you limit yourself to 8 probes for the PV hash table to begin with, and therefore still accept occasional incomplete PVs? These nodes are out of the critical path for NPS and time-to-solution. So as long as you can keep the PV table large enough (larger than the number of EXACT nodes), you could use quadratic chaining or double hashing and give a 100% guarantee to recover the PV, instead of 99.x%.

[bob]

So far, I am using 16384 PV entries. When I do a store or probe, I look at 8 entries. This is hardly ever done. But be aware, node counts change as when you get the longer PV, the next ply has better move ordering since it plays more of the moves in the PV first. I am not certain about the 16384 size yet, nor the 8 entry bucket.

I was wondering: why would you limit yourself to 8 probes for the PV hash table to begin with, and therefore still accept occasional incomplete PVs? These nodes are out of the critical path for NPS and time-to-solution. So as long as you can keep the PV table large enough (larger than the number of EXACT nodes), you could use quadratic chaining or double hashing and give a 100% guarantee to recover the PV, instead of 99.x%.

It was a "first cut". I have yet to decide, and could probably do a complete search (although near the tips, that might show up in time measurements in some positions.)

I am still toying with approaches. One could use fewer bits to hash to a "big bucket" and then search within that bucket. I am using an "age" idea to keep the table from becoming polluted with old entries.

[bob]

Implementation detail:

One has to be careful to not blow the PV array. Cluster testing showed the new version to be about 10 Elo weaker than normal version. Finally discovered that a couple of grafts onto the PV and one can below a 64-entry PV array easily, and step on other data that doesn't need to be wiped out... Particularly annoying in deep endgames where you can search 40-50 plies deep and (try to) produce a PV 100+ moves long thanks to this "fix".