bugs in hash tables

[Uri Blass]

Note that the version that was clearly better in solving endgame suites had a significant bug in the hash and maybe this is the reason that in my tests it did not do better in games.

The bug that I had was the following bug:

instead of recording alpha in the hash in case of fail low I recorded the result of the search of the last move(in most cases it was alpha but not always and in case of mates movei returns exact score).

The result was that movei could do unsound pruning and this was the reason that it could not find Na6+ in the following diagram even after
Nd7 failed low to score that was worse than the score of search after Na6+.

[D]kn6/2B5/8/1P6/1K6/P7/8/8 b - - 0 1

Now it can find Na6+ by search after enough time not based on knowledge(enough time may be 10 minutes on a fast machine but my search is still unefficient and I learned that I do not use pvs-principle variation search in another thread).

Note that I thought that I use pvs because movei has the principle variation in an array(similiar to tscp) and does not use MTD and does not need hash to get the pv array but it seems that I did not know what is the meaning of pvs.

I will try to use pvs but I will do things step by step so first I need to check that pruning by hash tables can give me better results in games.

Uri

[Uri Blass]

update about the bug.

This was not the only bug and I found that movei still cannot find Na6 with bigger hash.

The reason was that I also needed to store alpha in the hash in case of exact score because val was not the evaluation of the best move but the evaluation of the last move.

After doing it movei can solve the relevant position in 3 minutes or something like that(do not remember exactly).

I am surprised that spike cannot find Na6 even after 15 minutes of analysis and it gets stuck on Na6 in depth 21 but for a long time does not choose it.

It seems that spike's search is not efficient in that type of position and I expect every program that use hash efficiently to find Na6 even without knowledge for the simple reason that the evaluation of other moves is worse.

Note that movei is a slow searcher that still does not use many tricks in the search so I guess that it can be reduced to 1 minute without evaluation knowledge.

Uri

[Karlo Bala]

update about the bug.

This was not the only bug and I found that movei still cannot find Na6 with bigger hash.

The reason was that I also needed to store alpha in the hash in case of exact score because val was not the evaluation of the best move but the evaluation of the last move.

After doing it movei can solve the relevant position in 3 minutes or something like that(do not remember exactly).

I am surprised that spike cannot find Na6 even after 15 minutes of analysis and it gets stuck on Na6 in depth 21 but for a long time does not choose it.

It seems that spike's search is not efficient in that type of position and I expect every program that use hash efficiently to find Na6 even without knowledge for the simple reason that the evaluation of other moves is worse.

Note that movei is a slow searcher that still does not use many tricks in the search so I guess that it can be reduced to 1 minute without evaluation knowledge.

Uri

How many nodes & depth Movei need to find Na6 with search?

[Uri Blass]

update about the bug.

This was not the only bug and I found that movei still cannot find Na6 with bigger hash.

The reason was that I also needed to store alpha in the hash in case of exact score because val was not the evaluation of the best move but the evaluation of the last move.

After doing it movei can solve the relevant position in 3 minutes or something like that(do not remember exactly).

I am surprised that spike cannot find Na6 even after 15 minutes of analysis and it gets stuck on Na6 in depth 21 but for a long time does not choose it.

It seems that spike's search is not efficient in that type of position and I expect every program that use hash efficiently to find Na6 even without knowledge for the simple reason that the evaluation of other moves is worse.

Note that movei is a slow searcher that still does not use many tricks in the search so I guess that it can be reduced to 1 minute without evaluation knowledge.

Uri

How many nodes & depth Movei need to find Na6 with search?

latest version with 256 mbytes hash tables needs depth 24
and 86,377,445 nodes to find Na6 with search.

Uri

[Uri Blass]

I decided to respnd to post of hgm but I think that this is the relevant thread to respond and not the thread of tournaments
because hgm talked about hash bugs.

Here is his post and my response:

You are all expecting way too much of Joker!

It still has many known shortcomings that I did not get to fixing yet. The rep-draw detection for instance, that causes it to draw many won games because the repetition is masked by a hash hit left in the table from the first time, when the line did not contain a repetition yet. And I recently discovered a design flaw that makes it forget the hash move in PV nodes.

Interesting that when you have bugs because of mistakes that you did I seem not to have bugs that I expect to have.

I expected movei to allow draw by repetition in won position or to fail to mate and draw by the 50 move rules in won positions and it does not happen based on my experience inspite of the fact that movei reports wrong mate scores.

Note that movei does not remember information from previous searches(I do it by having generation number of 16 bits in the hash that is increased by 1 every time that movei starts a new search and movei simply ignore hash hits that have generation number that is different than the generation number of the search that it is doing).

It is done on purpose for the following reasons:

1)I want the search to be deterministic so if movei blunders because of some bug I can reproduce the same behaviour.
2)I am not smart enough to keep information from previous searches and not to have bugs and I consider the task of using hash for pruning without bugs as hard task even without keeping information from previous searches.
3)I do not like to clear the hash because I do not like movei to be significantly slower with big hash tables in blitz.


Movei still store mates based on the distance of the position from mate and not based on the distance of mate from the root and I thought that it may cause movei to delay mate again and again until not being able to mate by the 50 move rule but from experience of watching significant number of games it never happened in the games that I watched.

I also expected movei to allow repetition in won position because of bad use of hash(again bad use that I knew about it but I did not see a simple way to make it better).

It will never play a move that cause repetition by itself because it check if a move cause repetition before using hash for pruning but it may play a move that allows the opponent to force repetition later because of some hash hit that is based on a different path when the opponent is not able to repeat.

Again I never saw it happens.

Uri

[hgm]

Old versions of microMax simply incremented the hash key in the root for each new search, to completely invalidate the entire hash table of the previous search. But it's hash table is always-replace, so there is no danger of obsolete entries hanging on.

But at some point I needed the hash to remain valid, as I needed it for storing the game history (for rep-draw detection). The lack of reproducibility is an evil I just have to learn to live with. (Completely replaying the game is still reproducible, though, as uMax always finishes an iteration.)

Storing the distance to mate seems the correct thing to do, aslong as you also score the distance to mate. All my engines store the distance to mate in the hash, and also use the distance to mate as the mate score. So they adapt the mate score when it passes it towards the root (adding one ply).

I guess that iterative deepening sometimes allows you to get away with scoring mates at different distances the same, as you ten to discover the closest one first, and it will stick.

The problem you mention, about hash hits masking possibilities for the opponent to draw, is a frequent cause of unwanted draws in Joker. But it is especially fatal in combination with only recognizing third occurrence as draw. Because mostly the opponent reaches the threefold rep from a twofold rep, and the twofold rep is then not recognized as a draw and satisfied from the hash. If a two-fold rep is already scored as draw, you don't get into this situation in the first place. Reaching 3rd occurences from a first occurrence happence only rarely, and masking a move from the opponent to a second occurrence is not fatal, as it isn't really draw yet. The repeat will occur on the board, but in the future you will avoid the position from which the opponent could repeat.

But I think simply supressing hash pruning on any repeat is already sufficient to cure the problem in Joker. I am testing the version that does that now.

[Uri Blass]

Old versions of microMax simply incremented the hash key in the root for each new search, to completely invalidate the entire hash table of the previous search. But it's hash table is always-replace, so there is no danger of obsolete entries hanging on.

But at some point I needed the hash to remain valid, as I needed it for storing the game history (for rep-draw detection). The lack of reproducibility is an evil I just have to learn to live with. (Completely replaying the game is still reproducible, though, as uMax always finishes an iteration.)

Storing the distance to mate seems the correct thing to do, aslong as you also score the distance to mate. All my engines store the distance to mate in the hash, and also use the distance to mate as the mate score. So they adapt the mate score when it passes it towards the root (adding one ply).

I guess that iterative deepening sometimes allows you to get away with scoring mates at different distances the same, as you ten to discover the closest one first, and it will stick.

The problem you mention, about hash hits masking possibilities for the opponent to draw, is a frequent cause of unwanted draws in Joker. But it is especially fatal in combination with only recognizing third occurrence as draw. Because mostly the opponent reaches the threefold rep from a twofold rep, and the twofold rep is then not recognized as a draw and satisfied from the hash. If a two-fold rep is already scored as draw, you don't get into this situation in the first place. Reaching 3rd occurences from a first occurrence happence only rarely, and masking a move from the opponent to a second occurrence is not fatal, as it isn't really draw yet. The repeat will occur on the board, but in the future you will avoid the position from which the opponent could repeat.

But I think simply supressing hash pruning on any repeat is already sufficient to cure the problem in Joker. I am testing the version that does that now.

Movei remember the history of the game and the zobrist key of all position in game history so I can use them to detect repetition and I do not probe the big hash tables for that purpose.

I only probe constant array of zobrist keys in order to detect repetition
when the size of the array is enough to be longer then the size of the longest game that can practically happen

zobkey[max_plies_of_game]

Uri

[hgm]

Yes, in Joker I do something similar (but the game history, together with current tree path, is organized as a small hash table there). In uMax I used the main hash only to do it with shortest code, not because it is the best system.

Why do you store the entire game there, and not just the last 50 non-reversibble moves? After 50 moves you don't care anymore if it is a repeat, because a draw claim is possible anyway based on 50-move rule.

[Uri Blass]

Yes, in Joker I do something similar (but the game history, together with current tree path, is organized as a small hash table there). In uMax I used the main hash only to do it with shortest code, not because it is the best system.

Why do you store the entire game there, and not just the last 50 non-reversibble moves? After 50 moves you don't care anymore if it is a repeat, because a draw claim is possible anyway based on 50-move rule.

It is correct that I only need the last 50 non reversable moves for repetition but I want also to support analyze when the human can take back moves and having one big table for all the game is the simplest solution.

I check only the irreversible moves for repetition.

Uri

Uri

[PK-4]

I was intrigued by the beauty of the problem and the failure of strong engines to find the right move b8a6 with deep search. So I added some code to the endgame knowledge base of my engine as described by the following pseudocode:

//nobles are N,B,R,Q
if(lone rivalside king)
{
if(all ownside pawns on one rookfile)
{
if(ownside has no nobles or only bishop of wrong color)
{
if(rivalside king stands on or adjacent to queening square)
return DRAW;
}
}
}
//Q. Why do the indents disappear?

Not surprisingly, my engine now finds b8a6 at search depth of 3.