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
transposition tables
Moderators: hgm, Rebel, chrisw
-
- Posts: 2559
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: transposition tables
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
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
-
- Posts: 4367
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: transposition tables
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
--Jon
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: transposition tables
Do you want your engine to play chess or do you want your engine to "test moves"?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)
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.
Re: transposition tables
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.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.
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
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: transposition tables
Why? To avoid useful transposition hits and lower the effectiveness of the transposition table?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.
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).
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: transposition tables
You should start to see a practical benefit at 5 ply. At 7 ply you should see a pretty nice benefit.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
It's really tricky getting transposition tables right so keep plugging along!
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
-
- Posts: 4367
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: transposition tables
Feel free to look at how I do it (hash.h/hash.cpp here: https://github.com/jdart1/arasan-chess/tree/master/src).
--Jon
--Jon
Re: transposition tables
Because you need to know if a king is still allowed to do castling.Why? To avoid useful transposition hits and lower the effectiveness of the transposition table?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.
Those are optimalizations I do when I'm sure all is correct.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()).
Won't that give interesting effects in a multithreaded search?Locking hash entries is a waste of time.
If I don't do that, the module might return negative values. A long in java is always signed.There is no need to make the hash key positive by and'ing with 0x7f...f.
Yes, I'm doing that.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.
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.It is not efficient to have separate arrays for key / score / depth (/ move).
-
- Posts: 4367
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: transposition tables
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
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