Worst advice

[bob]

The frequency is small but with 64-bit hashes and long time controls on modern hardware, collisions are not ignorable.

I used to store the "in check" status for a position in the hashtable, since it costs a little time to determine this dynamically. But that was unreliable. Once in a while you'd get a hash result where that bit was set wrong. Sure, 99.99% of the time or so it worked. But having it not work was fatal, so I took it out. I did see once in a while crashes, playing for hours on a chess server, before removing this.

--Jon

I recently played with a 64 bit hash entry which left 24 bits for the signature. Since I was using 8gb of hash, that turned into 32 + 24 bits and it led me to discover a very tricky condition my legal move check failed to recognize, because there were enough collisions that the oddball case (had to do with check, where moving a piece was legal in one position but not in the one that collided). Took a long time for it to happen, running on 20 cores, until I began to get suspicious about the condition, then I found a position that would crash within 10 minutes or so and tracked it down. My legality check doesn't deal with the case of moving a piece that is pinned on the king since that can't happen, except on collisions... Have not fixed it, but gave up on 8 byte hash entries until I decide what to do. I have a quick "PinnedOnKing()" function for endgames, but did not want to make the legal move test any slower since it is a rare problem (no crashes in over 10M games in fact, until the shorter hash signature became a problem.

[bob]

You HAVE to have collisions. No way to compress all possible chess positions into 64 bits. So collisions will happen. If they can crash your engine or corrupt things, a legality check is required.

Assuming you mean "false positives", then such could indeed crash an engine which didn't use a validity test.

UNLESS the probability of a false positive is much less than the probability of error due to random cosmic ray impact. In Symbolic and Oscar, the transposition table entries all use 128 bit signatures -- and so there is no validity test. Yes, this eats space. But it also reduces time as no post-fetch test needs to be run. Further, a post-fetch test works only if a move is fetched and not just a score or a node count.

There is a cost. Hash entries bloat. Memory bandwidth suffers or else hash efficiency suffers since you now can only get maybe 2.5 hash entries per cache block. All at a cost that 64 bits seems to do just as well at.

[sje]

There is a cost. Hash entries bloat. Memory bandwidth suffers or else hash efficiency suffers since you now can only get maybe 2.5 hash entries per cache block. All at a cost that 64 bits seems to do just as well at.

Yes, for a fixed amount of table storage, there will be fewer entries using 128 bit signatures vs 64 bit signatures. But how much of a real world difference in strength? I've read that doubling the entry count of the main transposition table results in an Elo gain of only 8 to 16 points. How much Elo is lost by having to spend time doing move validation?

There will be some extra burn of memory bandwidth, although I haven't noticed this to be excessive. Note that on a fetch, the second eight bytes of the stored signature are not retrieved if the first eight bytes didn't match the probe signature, so there's some savings.

Also, a post-fetch move validation could prove a valid move but with a false positive signature match. If the move is just being used as a hint for ordering, that's not a big problem. But if the probe is also fetching flags and a score or bound, then the search could be really messed up with no way to identify the cause of bogosity.

For some purposes, using 64 bit or 72 bit or 80 bit signatures might work fine with move validation and a fault tolerant search. A small opening book might be implemented using 48 bit signatures. But for big perft() calculations, from my experience I would not trust signatures with less than 96 bits. And there's no big leap from that to a more natural 128 bit signature length, so that's what get used in Symbolic and Oscar.

----

What I might do is to add a feature to Symbolic which detects the case where a transposition table probe matches the bottom 64 signature bits but not the upper 64 bits. It will then send you an email with the specific details.

[bob]

There is a cost. Hash entries bloat. Memory bandwidth suffers or else hash efficiency suffers since you now can only get maybe 2.5 hash entries per cache block. All at a cost that 64 bits seems to do just as well at.

Yes, for a fixed amount of table storage, there will be fewer entries using 128 bit signatures vs 64 bit signatures. But how much of a real world difference in strength? I've read that doubling the entry count of the main transposition table results in an Elo gain of only 8 to 16 points. How much Elo is lost by having to spend time doing move validation?

There will be some extra burn of memory bandwidth, although I haven't noticed this to be excessive. Note that on a fetch, the second eight bytes of the stored signature are not retrieved if the first eight bytes didn't match the probe signature, so there's some savings.

Also, a post-fetch move validation could prove a valid move but with a false positive signature match. If the move is just being used as a hint for ordering, that's not a big problem. But if the probe is also fetching flags and a score or bound, then the search could be really messed up with no way to identify the cause of bogosity.

For some purposes, using 64 bit or 72 bit or 80 bit signatures might work fine with move validation and a fault tolerant search. A small opening book might be implemented using 48 bit signatures. But for big perft() calculations, from my experience I would not trust signatures with less than 96 bits. And there's no big leap from that to a more natural 128 bit signature length, so that's what get used in Symbolic and Oscar.

----

What I might do is to add a feature to Symbolic which detects the case where a transposition table probe matches the bottom 64 signature bits but not the upper 64 bits. It will then send you an email with the specific details.

The gain for doubling is not a constant. It certainly drops off once the table holds everything needed, assuming a decent replacement policy. Or for the trivial case of going from 2 to 4 entries which will give nothing measurable at all today. A key point is where you are at 1/2 the optimal. Doubling can give a significant Elo gain. You can probably find some old threads on r.g.c.c dealing with this. It is a sort of normal distribution, where you get less until you get into the key zone for number of entries, then Elo jumps quite a bit, then starts to improve less with additional size. I found cases where ttable size could double the search time when it gets too small.

You can probably provide interesting information by matching lower 64 and whole signature and reporting when they don't agree... I did a similar test back in the 90's, but I stored the actual position as 32 bytes, to see how often a collision occurred. With 64 bits back then, it was extremely rare, maybe once every day of searching (24 hours) or so. Not today however.

[sje]

What I might do is to add a feature to Symbolic which detects the case where a transposition table probe matches the bottom 64 signature bits but not the upper 64 bits. It will then send you an email with the specific details.

You can probably provide interesting information by matching lower 64 and whole signature and reporting when they don't agree... I did a similar test back in the 90's, but I stored the actual position as 32 bytes, to see how often a collision occurred. With 64 bits back then, it was extremely rare, maybe once every day of searching (24 hours) or so. Not today however.

I have since added instrumentation to the pathway enumeration (perft) transposition table to track successive high watermarks of matching least significant bit counts for mismatched signatures.

Using a table with 536,870,912 (= 2^29) entries, these high watermarks are:

perft(5) 16 bits
perft(6) 29 bits
perft(7) 37 bits
perft(8) 47 bits
perft(9) 49 bits
perft(10) in progress

The table is probed only for positions with draft >= 2. For a score/move table probed at every node in a search, the high watermarks would be hit at depths two less than the corresponding perft() depths.

Looking at the perft() trend, it appears that five or six extra signature bits are needed per ply. So, perft(14) could be expected to succeed with probability 0.5 when using a 70 bit signature.

Using a 128 bit signature reduces the probability of the above error by about a factor of 2^58. That's about one chance in 288 quadrillion which is why I'm confident that if the Perft(14) project gets the wrong total, it won't be due to false positives.

[sje]

For perft(10), the high watermark is 57 bits:

Code: Select all

New high watermark: 57
PETBase: items: 536,870,912   probe: 2,325,217,295   match: 1,373,888,675   stash: 959,884,183   usage: 483,403,591   load: 0.900409

Statistics at the conclusion of perft(10):

Code: Select all

TT: PETBase: items: 536,870,912   probe: 2,987,932,132   match: 1,753,604,325   stash: 1,246,125,027   usage: 509,408,812   load: 0.948848
Count: 69,352,859,712,417   Pt: 7:05:28.618   Wt: 1:48:45.662   U: 0.978009   10.8667 GHz   92.0244 ps

[sje]

Running a series of perft(7) calculations, a recent high watermark for matching low end bits for mismatching 128 bit signatures:

Code: Select all

New LSB match high watermark: 58
PETBase: items: 536,870,912   probe: 1,505,384,650   match: 854,786,402   stash: 652,406,307   usage: 429,376,467   load: 0.799776

Essentially, if a program probes the transposition table at a rate of 1 MHz, it takes about 25 minutes until the first false positive match when using a 58 bit signature.

I'll let this one run for a few weeks.

Glossary:

PETBase - Pathway Enumeration Table
items - total table entry capacity
probe - probe count, each may have 0, 1, or 2 128 bit signature mismatches
match - number of 128 bit signature matches
stash - number of table entry writes/overwrites
usage - number of table entries in use
load - usage / items

[sje]

After 14+ billion probes, the bit count is up to 59:

Code: Select all

New LSB match high watermark: 59
PETBase: items: 536,870,912   probe: 14,762,947,573   match: 8,172,536,319   stash: 6,610,981,101   usage: 536,870,911   load: 1

Note that there's exactly one unused slot left in the transposition table.

[bob]

After 14+ billion probes, the bit count is up to 59:

Code: Select all

New LSB match high watermark: 59
PETBase: items: 536,870,912   probe: 14,762,947,573   match: 8,172,536,319   stash: 6,610,981,101   usage: 536,870,911   load: 1

Note that there's exactly one unused slot left in the transposition table.

Note that on common hardware I can hit 14 billion nodes in reasonable games. IE 1B nodes in 10 seconds. 10B in 100 seconds. And I have run on better hardware where speeds were beyond 150M nodes per second... And this in real chess, not perft which runs quicker.

[sje]

Note that on common hardware I can hit 14 billion nodes in reasonable games. IE 1B nodes in 10 seconds. 10B in 100 seconds. And I have run on better hardware where speeds were beyond 150M nodes per second... And this in real chess, not perft which runs quicker.

Perft() may run faster per node, but mine will not probe the transposition table for a draft less than two. So, if the average move count of a position is 32, then the average lowest draft entry will be around 1,024. That means that the table is being hit a thousand times less frequently than it would in a search where positions down at the bottom ply are probe candidates.

----

High watermark trace, note the somewhat irregular growth:

Code: Select all

New LSB match high watermark: 1
PETBase: items: 536,870,912   probe: 1   match: 0   stash: 0   usage: 0   load: 0
New LSB match high watermark: 3
PETBase: items: 536,870,912   probe: 3   match: 0   stash: 0   usage: 0   load: 0
New LSB match high watermark: 8
PETBase: items: 536,870,912   probe: 13   match: 0   stash: 2   usage: 2   load: 3.72529e-09
New LSB match high watermark: 9
PETBase: items: 536,870,912   probe: 994   match: 35   stash: 940   usage: 940   load: 1.75089e-06
New LSB match high watermark: 10
PETBase: items: 536,870,912   probe: 2,861   match: 100   stash: 2,742   usage: 2,742   load: 5.10737e-06
New LSB match high watermark: 11
PETBase: items: 536,870,912   probe: 4,162   match: 176   stash: 3,967   usage: 3,967   load: 7.38911e-06
New LSB match high watermark: 13
PETBase: items: 536,870,912   probe: 10,125   match: 1,070   stash: 9,036   usage: 9,036   load: 1.68309e-05
New LSB match high watermark: 21
PETBase: items: 536,870,912   probe: 30,724   match: 7,583   stash: 23,122   usage: 23,122   load: 4.30681e-05
New LSB match high watermark: 31
PETBase: items: 536,870,912   probe: 43,050   match: 12,650   stash: 30,382   usage: 30,382   load: 5.65909e-05
New LSB match high watermark: 35
PETBase: items: 536,870,912   probe: 428,425   match: 176,808   stash: 251,604   usage: 251,599   load: 0.00046864
New LSB match high watermark: 36
PETBase: items: 536,870,912   probe: 960,855   match: 406,264   stash: 554,594   usage: 554,569   load: 0.00103297
New LSB match high watermark: 39
PETBase: items: 536,870,912   probe: 5,118,364   match: 2,361,751   stash: 2,757,553   usage: 2,756,376   load: 0.00513415
New LSB match high watermark: 40
PETBase: items: 536,870,912   probe: 5,252,009   match: 2,426,283   stash: 2,826,711   usage: 2,825,470   load: 0.00526285
New LSB match high watermark: 42
PETBase: items: 536,870,912   probe: 5,803,341   match: 2,710,008   stash: 3,094,620   usage: 3,093,050   load: 0.00576125
New LSB match high watermark: 47
PETBase: items: 536,870,912   probe: 43,296,577   match: 23,773,362   stash: 19,563,417   usage: 19,499,457   load: 0.0363206
New LSB match high watermark: 50
PETBase: items: 536,870,912   probe: 49,368,268   match: 27,290,368   stash: 22,126,743   usage: 22,044,339   load: 0.0410608
New LSB match high watermark: 51
PETBase: items: 536,870,912   probe: 190,262,227   match: 106,652,319   stash: 83,814,737   usage: 82,339,813   load: 0.15337
New LSB match high watermark: 53
PETBase: items: 536,870,912   probe: 1,173,452,763   match: 664,282,633   stash: 510,540,683   usage: 378,076,448   load: 0.704222
New LSB match high watermark: 58
PETBase: items: 536,870,912   probe: 1,505,384,650   match: 854,786,402   stash: 652,406,307   usage: 429,376,467   load: 0.799776
New LSB match high watermark: 59
PETBase: items: 536,870,912   probe: 14,762,947,573   match: 8,172,536,319   stash: 6,610,981,101  usage: 536,870,911   load: 1