Testing Transposition Tables

[cms271828]

I'm almost ready to try my engine with a transposition table.
I'm just using a full loop to get the zobrist key at each node, instead of incrementally modifying the zobrist key, but will swap over later.

Are there any ways to test, everything works as it should?
Should I expect to see a deeper ply reached using TT, compared to not using the TT?

Thanks

[hgm]

A fairly sensitive test is to try if you can solve KPK. (w: Ke1, Pe2; b: Ke8). You should see the promotion at 24 ply or so. If your hash table doesn't work properly, you will never get there.

Another good test is Fine #70.

[cms271828]

Hi,

I've put in the transposition table, and it pretty much works, but is really slow.
I'm using a full board scan in order to get the 64-bit key for the position at each node, so I want to now make it incremental.

I'm not sure what the best way to handle this is inside the MAKE_MOVE function.

if KEY is the incrementally changed zobrist key.

Then I need to do KEY ^= side_to_move_random

Then obviously the XOR operations for the moved/captured pieces.

I'm a little unsure about castling rights and ep.

Do I need to XOR out the old castling_rights_random, then XOR in the new one.

Then same thing for the ep_random?

Thanks

[hgm]

There is little benefit in updating the castlings and e.p. part differentially. I only do the keys for moved and captured piece differentially, and at the moment of access XOR in the castling and e.p.-rights part.

[cms271828]

Thanks, but I'm not clear what you mean by moment of access.

[hgm]

When you want to probe the hash, or store into it.

[Zach Wegner]

There is little benefit in updating the castlings and e.p. part differentially. I only do the keys for moved and captured piece differentially, and at the moment of access XOR in the castling and e.p.-rights part.

For speed, you are right. But for simplicity and correctness, I disagree. It is much easier to just XOR in the castling rights and ep status in the make/unmake, and not have to deal with it anywhere else. And "the moment of access" is not always so simple. I use the hashkey all over the place: hash table, rep detection, comparing positions, the opening book, etc.

[hgm]

When my search hits on a new position, I start building the new hash key for that position, so it can be used wherever it is needed in the instance of Search() dealing with that position. This coincides with the first access, as I probe the hash even before doing the MakeMove leading to the new position (there is no need to do the MakeMove if there is a hash hits that leads to pruning).

So just before MakeMove I both make a new differential HashKey, by XORing with the moving and captured piece keys, and make a new access key out of it, as the XOR of the differential key and the castling/e.p. rights keys and side-to-move. The old differential key was saved (once, before starting to make any moves), and is restored from that saved value on UnMake.

The new access key is then used immediately as it is generated for rep-draw probing, and if there is no repeat, for hash probing. If the move is searched, it is again used after this search (and UnMake) to store the hash value.

[cms271828]

Hello,

I've been doing some performance testing, since with a TT, my engine has been really slow.

With TT code commented out:
I got 115M evals / min.

But when I uncommented the Record_Hash(...) calls:
I got about 68M evals / min

The problem line was:

Code: Select all

if(TT[index].key==key)        chosen=index;

Here TT is an array of TTEntry objects,
The class TTEntry, has the 5 fields, move,depth,key,score,type.

So it seems using an object array is killing performance.
Its kind of ironic, java teaches you to use objects, which 95% of the time is a good idea, but not in chess.

Anyway, I built a sample array of longs (64-bit integers)
Instead of the line above, I made a couple of look-ups into this
long array, and the speed came out at:
112M evals / min.

Obviously I can only squeeze 64 bits of info into a long, which is not enough, so perhaps I could use 2 long arrays.
Put the full 64-bit key in one, and the move(21 bits), depth(7 bits), type(2 bits), score(about 15 bits) in the other.

Is that a good idea?
Thanks for any input.

[hgm]

Well, it is normal that your nps drops if you start hash probing. Memory accesses into a big table are extremely costly, on fast CPUs. Packing and unpacking the fetched data should pale compared to that.

What would be definitely worse is storing the key and the other data of the entry not contiguously in memory: you would then need two memory accesses for fetching the data. So if you want to store everything in an array of longs, make sure you use TT[2*index] for the key, and then TT[2*index+1] for the remaining data.

In Joker I use TT entries of only 9 bytes (32-bit key, 8-bit depth, 12-bit move (from+to square), 2-bit special-move indicator, 2-bit bounds, 16-bit score. Still too much to fit in a single long, though, that would require 8 bytes. I considered squeezing the move into 4+5 bits (indicating piece + board step), and using only 5 bits for the depth; that would save me just enough to squeeze it into 64 bits. But the 14% extra TT entries don't seem worth the hassle.

I was able to squeeze the entries for Joker80 (which plays on a 10x8 board) into the same size entries as normal Joker. This took some squeezing, though, as FromSqr and ToSqr numbers no longer fit in 6 bits, on such a board. So I add 80 or 160 to FromSquare to indicate upper bound or lower bound (encoding FromSqr and BoundType in 8 bits), and use a lookup table to encode ToSqr and special-move indicator in another 8-bit field (using 'files' 0-9 (=a-j) for normal moves, 10-19 for promotions and e.p. captures, 20 and 21 for castling and 22-31 for Pawn double moves (which require some extra attention in MakeMove for determining e.p. status)).