Side effects of transposition tables

[Alessandro Scotti]

Hi folks,
in the last few weeks trying to improve Kiwi has been as much fun as sticking a pin in my back. I've tried many original and promising ideas, and played literally thousands of test games and eventually had to come to terms with reality: not only my engine sucks, but it sucks in an unpredictable way.
Playing 4 games from the same starting position and no book against version 0.4d could yield 4-0-0, 0-4-0, 0-0-4 or everything in between. Maybe I'm asking too much from a bird, but some more determinism would be definitely appreciated.
The problem seems to be in the transposition tables. I've already a few guards in place that eliminates most blunders of the previous versions, but the fact is if I try to analyze a position from scratch, I almost always get a different PV and best move with respect to that played in the game. This makes it quite difficult to spot and fix problems, because it's often impossible for me to reproduce the program behavior.
I'm now considering clearing the hash table before searching for a move. I could only play a few games with such a version and results are not clear yet. On one side I really like to get consistent and predictable results, but on the other side it is sometimes painful to see that each position has to be re-explored from scratch.
What do you think? It seems other engines do not suffer from the problem, maybe MTD(f) is more sensitive to this kind of stuff?
Comments and suggestions would be very welcome, but I accept pats on the back too...

[Charles Roberson]

Everything I've read states that MTD(f) requires big transposition
tables to be effective.

What are you doing when you don't clear the TT's between
moves played? Are you aging or not?

If you clear the tables you should get the same result as in the
game assuming you can put the program under the same time
constraints as in the actual game.

Maybe you should try turnning TT's off. Easily done -- just
return NotFound from the search.

Then start analysis. Fix bugs then turn back on. If play gets worse
then you have bugs in TT's. I feel for you -- I've been there before.

BTW: I like the "pin in the back" statement. My back feels like that after
hours of debugging and I thought it had something to do with
being over 40.
Good luck.

Charles

[Alessandro Scotti]

Hi Charles,
I do aging on the TT, but usually don't clear it between moves. However, I do a sort of "partial" cleaning at the end of the search that has eliminated some horrible blunders from past versions. Now I usually don't see gross mistakes, but the results are clearly different than those I get when starting a fresh analysis of the position.
I've tried to run a few tests with TT's off, but with MTD(f) that's going to produce *very* long searches...

[Vadim Bykov]

Hi! I have such problems when using quick sort alhoritm. Why? I don't know, may be it was bug in realisation. With simple bubble sort, i have same best move and same count of generated nodes.

[Ross Boyd]

Hi Alessandro,

I don't know that you can stabilise the search when using a TT table, without clearing it between moves.

In my case, I don't clear the hash either and use aging like you do.

Just recently it occurred to me that a source of search instability can be due to the piece list getting 'shuffled' during searches when removing/appending captured pieces. This may have subtle side-effects when there are transpositions in the search and the piece list is not in exactly the same order for the same position... of course, this only applies when two or more of the generated moves have the same move ordering score.

I have not had time to test this theory, yet. Do you think I'm being superstitious?

Ross

[Charles Roberson]

Hi Alessandro,

If you can't turn them off then turn them down.
You probably have alpha, beta and exact returns from a hash probe.
Why not limit yourself the the exacts. This should slow things down
some but my narrow things.

You should double check your replacement scheme. Make sure
you are replacing appropriately -- maybe you have a > inverted to <?
Also, recheck and verify the packing of the data. Both of these are
easy errors to make. My guess is that you have tried this.

Another optioin is a new set of eyes. Send the transposition table
code to someone you trust. Also send the hash coding scheme.
After that you could have an error in the hashcode manipulation
in the search itself.

[Charles Roberson]

This made a considerable difference in NoonianChess:
after I fixed several bugs, I tried various hashcode sizes.
I found a considerable difference as the hashcode size increased.

How many bits do you use for a hashcode? Also, do you use a
pawn or king safety hash? Maybe the problem is there.

A bug in the PE such as unitialization could cause this problem and
the transpoition tables are not the issue at all.

[Alessandro Scotti]

Just recently it occurred to me that a source of search instability can be due to the piece list getting 'shuffled' during searches when removing/appending captured pieces. This may have subtle side-effects when there are transpositions in the search and the piece list is not in exactly the same order for the same position... of course, this only applies when two or more of the generated moves have the same move ordering score.

Hi Ross,
I'm not sure I'm following you... can you tell me a bit more?

[Alessandro Scotti]

If you can't turn them off then turn them down. You probably have alpha, beta and exact returns from a hash probe. Why not limit yourself the the exacts. This should slow things down some but my narrow things.

Hi Charles,
I don't have alpha and beta with MTD(f), just a single value that is usually called gamma. At every node I will get either a fail high or a fail low, and no exact score.
By looking again at the search code, I think I have spot a possible problem though. I usually only store fail highs in the hash table, but there are situations where I store fail lows too. I do that because I fetch the PV from the hash table and I want to preserve those moves if possible. However, when I later re-explore that node I will give that move the "hash table" bonus and search it before every other move. I don't know if this little detail can do much harm, but it doesn't seem entirely correct to reward a move that failed low in a search that consists only of bounds... what do you think?

[Ross Boyd]

Hi Alessandro,

Code: Select all

Just recently it occurred to me that a source of search instability can be due to the piece list getting 'shuffled' during searches when removing/appending captured pieces. This may have subtle side-effects when there are transpositions in the search and the piece list is not in exactly the same order for the same position... of course, this only applies when two or more of the generated moves have the same move ordering score.

Ok, I'll try to clarify the above...

I'm assuming you use piece lists to generate moves. If you use bitboards then none of what I said would apply because bitboards will, for a given position, generate moves in exactly the same order every time.

I use piece lists and 0x88.

Now, with a piece list, every time a capture occurs you must remove the piece from the piece list, right? And when you takeback, you must replace the captured piece back in the piece list.

If you simply append the captured piece to the piece list during takeback, it will change the order of the piece list. This has the side effect of changing the order in which you generate future moves.

Therefore, I think its better during takeback to insert the captured piece where it originally was, to ensure that move generation is always in the same order.

(I should add, although generated moves get re-ordered before searching, the order can still differ if two moves have the same move ordering score. Right?)

You can test all this for yourself by doing a fixed depth search and then do the same search again with the piece list ordered differently. You will get different node counts.

Whether this harms or destabilises the search in any way, I don't know. I suspect that it would reduce the effectiveness of the hash table very slightly, or worse, add a little search instability.

What do you think?

Ross

[Pallav Nawani]

Hi Alessandro,

Whether this harms or destabilises the search in any way, I don't know. I suspect that it would reduce the effectiveness of the hash table very slightly, or worse, add a little search instability.

What do you think?

Ross

It can harm the search, and it can improve the search. I've seen a position where due to different order of generating moves, my program needs two more plies(!) to see a tactical sequence as compared to the older one. Of course this could be due to some bug somehere.

Sometimes this will improve the search, if the move made with the new piece is the best one. On average I think this would even out.

Pallav

[Anonymous]

You can test all this for yourself by doing a fixed depth search and then do the same search again with the piece list ordered differently. You will get different node counts.

Yes. For my engine, I will need to make moves, to format the output for the PV (when SAN output is "needed", not for coordinate notation). And you mentioned shuffling of the piece list will happen. While doing some larger code rearrangement, and thereby also testing Windows and Linux versions I got tired of some too huge output. I set a "noise parameter" (only show PVs after 1 million nodes) in some ini file. Then I was very annoyed, that I could not reproduce old node counts anymore (at a time I have long forgotten that I had changed that noise parameter). Also the node counts under Linux and Windows were different. Took a nice debugging session to find this non bug.

I don't think, it will hurt the search much, however. With not too much effort, one could try. Just remember the old piece list somewhere and copy it back in unmake_move instead of just appending that captured piece.

Regards,
Dieter

[Ross Boyd]

It can harm the search, and it can improve the search. I've seen a position where due to different order of generating moves, my program needs two more plies(!) to see a tactical sequence as compared to the older one. Of course this could be due to some bug somehere.

Sometimes this will improve the search, if the move made with the new piece is the best one. On average I think this would even out.

Pallav

Yes, I've had similar experiences, sometimes it can lead to a move being found earlier, sometimes not.

I just wonder if the hash table is rendered less effective (maybe 0.0001%) by searching moves in a slightly different order.

There is so much to learn... I wonder sometimes what Stefan MK must know about all this. sigh...

Ross

[Ross Boyd]

I don't think, it will hurt the search much, however. With not too much effort, one could try. Just remember the old piece list somewhere and copy it back in unmake_move instead of just appending that captured piece.

Yes, I'm going to fix this so that the ordering is preserved... it may not do anything... except give peace of mind.

Ross

[Alessandro Scotti]

It can harm the search, and it can improve the search. I've seen a position where due to different order of generating moves, my program needs two more plies(!) to see a tactical sequence as compared to the older one. Of course this could be due to some bug somehere.

Hi Pallav,
yes I think good move ordering can do much to improve strength. I've done many experiments lately, especially to replace the history heuristic, but although results in the test suites are good I've still to get significant results in play because the aforementioned problems make testing quite difficult (and the difference to measure pretty small)...

[Alessandro Scotti]

Yes, I'm going to fix this so that the ordering is preserved... it may not do anything... except give peace of mind.

I use bitboards, so I always get moves in the same order. While that hasn't done much for my peace of mind, being able to index moves efficiently could have some interesting applications, although so far I couldn't play too much with it...

P.S. Thanks for the explanation, I see your point now!

[Dann Corbit]

Hi! I have such problems when using quick sort alhoritm. Why? I don't know, may be it was bug in realisation. With simple bubble sort, i have same best move and same count of generated nodes.

The quicksort algorithm is not a stable sort.

What that means is that orders for things with equal evaluation can be switched in position from pass to pass.

More details:
http://www.answers.com/topic/sorting-algorithm

A quicksort algorithm can be made stable by including the original position in the list as part of the comparison operator.

[Anthony Cozzie]

First, make sure your transposition table key algorithm works 100%. I assume you are using an incremental generator, and I can't count the amount of time I've wasted there.

Second, implement a 2-level hash with 1 level replace-always and 1 level depth-first.

Third, look over the logic in your transposition table with a SHARP eye. It is very easy to get wrong. As usual I recommend that people look at the Crafty source. Your goal should be to get 20+ ply instantly on Fine70 (probably the most TT sensitive position ever).

You can't get a strong program without a good transposition table.

anthony

[Pradu]

Here's a real good test suite for the transposition table (assuming that your engine is correct in every other aspect).

http://membres.lycos.fr/albillo/ajedre1a.htm