TalkChess.com

Hi,

For fun I implemented transposition tables in my chess engine (anything to avoid that move-generator-rewrite which is so neccessary...) and it seems to have a hit-rate of 1-2% with 7 ply's (plies?).

My questions:
- is 1-2% in 7 plies/ply's a reasonable value?
- when doing iterative deepening, I assume I need to start over with a clean table, right? because else no moves will be tested (they'll all have hits in the table, well mostly)


regards

Hello,

1-2% is pretty low, of course depending on position (I get ~17% for startpos, where hit = TT cutoff, unless I made a mistake somewhere). Don't clear hashtable. Ever.
There is obviously something very wrong with your implementation.
Hope that helps.

Martin

Not sure about 7 plies (that is a shallow search depth) but typically I'd expect something >30% hit rate over the course of search.

--Jon

flok wrote:- when doing iterative deepening, I assume I need to start over with a clean table, right? because else no moves will be tested (they'll all have hits in the table, well mostly)

Do you want your engine to play chess or do you want your engine to "test moves"?

You should certainly not clear the table between iterations. The main advantage of the transposition table (in opening and middle game) is that it gives you a move that is very likely the best move (or at least good enough to cause a cut off).

In case you haven't thought about this yet, you do have to store a "remaining depth" value in each entry that tells you to what depth a particular position has been searched. If you need to search a position with depth 8 and the transposition table says depth 7, you cannot use the stored score for a cutoff, but you can and must use the stored move as the first move to search.

syzygy wrote:You should certainly not clear the table between iterations. The main advantage of the transposition table (in opening and middle game) is that it gives you a move that is very likely the best move (or at least good enough to cause a cut off).

In case you haven't thought about this yet, you do have to store a "remaining depth" value in each entry that tells you to what depth a particular position has been searched. If you need to search a position with depth 8 and the transposition table says depth 7, you cannot use the stored score for a cutoff, but you can and must use the stored move as the first move to search.

Yes, I thought (from reading the wikipedia article on this topic) that one should store a board-hash with a score and then use it; in case you arrive at a setup multiple times while doing the current (-> for the current move) search.

Implementing the remaining-depth part was easy and indeed works pretty well! In a quick test I saw situations where the first few depths were "skipped" (more or less) because of the transtab hits.
And it successfully came through the litmus test (it played either e6 or e5 after e4)!

I'm not seing the 17-30% hit-rate (not even with 11671106 elements which is roughly 1GB - each element/hash uses 92 bytes in my implementation).
I differed from the wikipedia (http://en.wikipedia.org/wiki/Zobrist_hashing) implementation by also including the "first move"-status of a piece.
http://pastebin.com/C8sp3Pes
Also the transtab itself is not very exciting:
http://pastebin.com/GFqnePsk


regards

flok wrote:I differed from the wikipedia (http://en.wikipedia.org/wiki/Zobrist_hashing) implementation by also including the "first move"-status of a piece.

Why? To avoid useful transposition hits and lower the effectiveness of the transposition table?

92 bytes per entry seems way too much. You do not need more than 64 bits to store a key "uniquely" identifying a position (it's not unique, but it is sufficient and in fact 32 bits are already enough). I would not know what to do with the remaining 84 bytes. 16 bytes per position is easily enough.

In case you don't (it's not clear to me from your code): the Zobrist hash should be calculated incrementally (in makemove()). That is the point of using Zobrist: it is so easy to update it incrementally.

Locking hash entries is a waste of time.

There is no need to make the hash key positive by and'ing with 0x7f...f.

You should really store the best move / the move that caused a fail-high. This is the main advantage of using a transposition table in the opening and middle game.

It is not efficient to have separate arrays for key / score / depth (/ move).

flok wrote:Hi,

For fun I implemented transposition tables in my chess engine (anything to avoid that move-generator-rewrite which is so neccessary...) and it seems to have a hit-rate of 1-2% with 7 ply's (plies?).

My questions:
- is 1-2% in 7 plies/ply's a reasonable value?
- when doing iterative deepening, I assume I need to start over with a clean table, right? because else no moves will be tested (they'll all have hits in the table, well mostly)


regards

You should start to see a practical benefit at 5 ply. At 7 ply you should see a pretty nice benefit.

It's really tricky getting transposition tables right so keep plugging along!

Feel free to look at how I do it (hash.h/hash.cpp here: https://github.com/jdart1/arasan-chess/tree/master/src).

--Jon

flok wrote:I differed from the wikipedia(http://en.wikipedia.org/wiki/Zobrist_hashing) implementation by also including the "first move"-status of a piece.

Why? To avoid useful transposition hits and lower the effectiveness of the transposition table?

Because you need to know if a king is still allowed to do castling.

92 bytes per entry seems way too much.<...>
In case you don't (it's not clear to me from your code): the Zobrist hash should be calculated incrementally (in makemove()).

Those are optimalizations I do when I'm sure all is correct.

Locking hash entries is a waste of time.

Won't that give interesting effects in a multithreaded search?

There is no need to make the hash key positive by and'ing with 0x7f...f.

If I don't do that, the module might return negative values. A long in java is always signed.

You should really store the best move / the move that caused a fail-high. This is the main advantage of using a transposition table in the opening and middle game.

Yes, I'm doing that.

It is not efficient to have separate arrays for key / score / depth (/ move).

Java does not have structs. I could use class for it but that would only use more memory. I could sacrifice a couple of bits from the long (64b) value and use that to store the score/depth but that would increase the chance for hash collisions.

Assuming you are doing PVS, you need to store with the score whether it is an exact score, upper bound, or lower bound. (If you are not doing PVS - in which the first move is searched with a wide window and subsequent move with a zero-width window - you should).

As others have noted you can get away with not locking using Bob Hyatt's lockless hashing idea (see http://chessprogramming.wikispaces.com/ ... Hash+Table).

--Jon