Testing a transposition table

[jwilson82]

I am to the point where I am ready to add a transposition table to my fledgling engine and I am thinking about the best way to test the implementation. Obviously you can debug a search and verify that things load/probe in a way that makes sense, but those are isolated individual events. Testing against an earlier version should certainly favor the one with the transposition table, but that is anecdotal evidence. Ideally I'd like something I can formalize in a unit test somehow, but search enhancements are tricky to test. Are there known positions where engines will struggle without a table but solve trivially with one? How do other people test things like this?

[sedicla]

I am to the point where I am ready to add a transposition table to my fledgling engine and I am thinking about the best way to test the implementation. Obviously you can debug a search and verify that things load/probe in a way that makes sense, but those are isolated individual events. Testing against an earlier version should certainly favor the one with the transposition table, but that is anecdotal evidence. Ideally I'd like something I can formalize in a unit test somehow, but search enhancements are tricky to test. Are there known positions where engines will struggle without a table but solve trivially with one? How do other people test things like this?

I use the following positions in my engine. Maybe there are others.

("8/k/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1", "Best move would be a1b1, score 2+.\n");
("2k5/8/1pP1K3/1P6/8/8/8/8 w - -", "Best move would be c7, score 9+.\n");

[hgm]

[d]4k3/8/8/8/8/8/4P3/4K3 w - - 0 1

[mvanthoor]

For a transposition table to even work, your Zobrist hashing should be absolutely perfect. Then you can add the transposition table to your Perft function. The values it gives should match up with the values you get without a TT.

- First create a function that (in debug mode) can be called by make_move. It should create the zobrist key from scratch, and compare it to your incremental key. (If you keep the key incrementally, that is; but you should, for speed.)
- Then create the TT, and add it to the perft function. If it works correctly there, you should see a huge perft speedup (somewhere around 75% time savings), and the values should still match up.

If you pass those two tests, you'll probably have a correctly working TT. If the stuff you put in it, and what you do with it when you get it out again, can still be wrong... and I don't really know how to test this. In my tests against lower-rated engines, I've encountered a few that claim to have a TT, but they can't search deeper than my engine; or only 1-2 moves in the middle game. That suggests their TT and/or zobrist hashing isn't working correctly.

[Dann Corbit]

A simple way is to make two versions of your zobrist hashing.
The first one does incremental updates like normal.
The second one does a complete rebuild of the hash given the current chessboard.
In debug mode, every time you are about to update the hash table, compare the incremental value to the full rebuild value.

Typical areas of problem are:
Null move
Undo move
Castle rights
E.P. flag
Edit: and promotion

[Daniel Anulliero]

Here is an interresting position to test your HashTable :
[d]4k3/8/4pPp1/3pP1P1/2pP4/2P2K2/8/8 w - - 1 1

The king must go to help the passer to promote