Graph History Interaction 2 questions

[Jouni]

1. Is this only Stockfish problem, not in Komodo or Houdini?
2. Does this happen only in endgames (and with tablebases)?

[bob]

It is a problem that seems to be unsolvable without completely killing hash table usage and the associated endgame performance gains... And it affects EVERY program that uses hashing.

[Uri Blass]

I think that it is possible to solve at least part of the problem of the fifty move rules draws with no reduction in playing strength.

I suggest simply to ignore the fifty move rule as long as the evaluation is close to draw without the 50 move rule(this means the engine continue to search also after a position is drawn by the 50 move rule and does not return a draw score).

The idea is that as long as one side cannot win without the 50 move rule the same side also cannot win with the 50 move rule.

If you see a clear advantage for one side(let say more than a pawn) then only at this point stop ignoring the 50 move rule because it is possible that in part of the lines the advantage that you see for one side is misleading and practically it is a draw by the 50 move rule.

[MikeB]

I think that it is possible to solve at least part of the problem of the fifty move rules draws with no reduction in playing strength.

I suggest simply to ignore the fifty move rule as long as the evaluation is close to draw without the 50 move rule(this means the engine continue to search also after a position is drawn by the 50 move rule and does not return a draw score).

The idea is that as long as one side cannot win without the 50 move rule the same side also cannot win with the 50 move rule.

If you see a clear advantage for one side(let say more than a pawn) then only at this point stop ignoring the 50 move rule because it is possible that in part of the lines the advantage that you see for one side is misleading and practically it is a draw by the 50 move rule.

Hash tables (TT or transposition tables) do not contain game state ( specifically, the 50 move rule draw counter) - so a position that is saved in the TT table could be scored a mate or could be scored a draw , given the game state, i.e , the precise move count of the 50 move status. Later in the game , the position comes, up and the game state is different. What was scored a draw, with the new game state , is now a lost. Or what was score a win before, the position is now a draw.

Simply ignoring the 50 move rule will not help. For those that play ICCF, there is a another wrinkle , the 50 move rule is not enforce with 7 pieces left on the board. As Bob indicated it appears every fix loses Elo. It does not happen that ofter , but when it does happen , it is big and very noticeable and to the untrained eye , it looks like a bug. It has been around since hash tables were first used and no one has come up with a surefire method, that does not cost Elo. It can be solved very easily, just include the game state in the hash tables, but that wipes away the benefit of using hash tables and ends up costing Elo.

It used to be that you rarely saw this as the searches would have to get very deep for this to have an impact - but with current hardware today , using 8 or more cores, you see it in games where the move is made is three seconds - it is virtually unfixable without losing Elo in a very deep search where the engine has to make a move in 3.5 seconds no matter what rules you try to apply, e.g., ply counter greater than 90, don't use TT etc. The situation is always win vs draw or draw vs lost , it is never win vs lost, so a position is misplayed and wins turn to draw , or a draw turns to a lost. Some of the adjudication rules that are applied today will also mask GHI, as games may be deemed draw or win prior to the GHI even happening. It usually seen when engines play to the bitter end and the 50 move rule ply counter gets over 90 (45 moves * 2). It is totally independent of EGTB, except for the fact that may be many moves that provide mate or many moves that provide draw, typically the shortest matescore might be given preference and that short mate score may have been from moves ago and it may nonger berate give the game state. With many moves gin the draw score, it may just be bad luck that the wrong move with draw score was picked for the move since it now loses. Perhaps always using matescore or draw score that is from the current search, ie., it was derived from the current game state, should always be given preference over a tt score when available will help.

[koedem]

I haven't worked on this problem at all so the following may be completely stupid, but what if for 50 moves rule you split up your table into two parts, the "normal" large part which works just as it does right now, and then a second small table that has some 50 move rule logic (e.g. have plies left be part of the key and then only probe entries with the exact plies left) and which only gets written to or read from if there's less than N plies left where N may be 10 or 20 or something like that.

So for most of the games this doesn't change anything since we only use the normal part of the TT but for the few near 50 move rule positions the logic might help (at the cost of efficiency I guess).

[Alayan]

i'll quote what I wrote on SF's github :

A theoretically better solution instead of trying to store 50mr exact counters is to store bounds.

e.g., we search position A with 50mr counter = N and find a draw. We then store this in hash, and for any 50mr counter >= N we return a draw too (higher 50mr counter can only make it more drawish). But if 50mr counter < N, then we don't know if the draw value is valid, and we do another search. If for M < N, we find out that it's still a draw, we can update the bound to M. If instead we find that it's winning with counter = M, then we can store this as a second bound and assume that it's also winning with counter <= M (lower 50mr counter can never make it any less winning). If the position is then searched with 50mr counter between M and N, we'd have to do another search and update one of the bounds.

Of course, SF eval often doesn't tell us "this is winning" and "this is drawn", so a difficulty with this approach arise if we'd find a lot of steps, i.e. search eval going slowly down with higher 50mr counter. We don't really want to store more than two values, so if .eg. we get +2 for count A, +1 for count B > A, and 0 for count C > B, there has to be some implementation decision to know what to do, and it will be imperfect.

For endgame positions like the one behind this issue, though, with TB usage, a draw bound and a win bound only would work fine.

This still involves significant overhead, but it doesn't destroy TT efficiency anywhere as much as using exact 50mr would.

In theory, some positions would suffer from extra overhead because we hit the position with ascending/descending 50mr counters. But in practice, most positions won't be anywhere as unlucky

[MikeB]

i'll quote what I wrote on SF's github :

A theoretically better solution instead of trying to store 50mr exact counters is to store bounds.

e.g., we search position A with 50mr counter = N and find a draw. We then store this in hash, and for any 50mr counter >= N we return a draw too (higher 50mr counter can only make it more drawish). But if 50mr counter < N, then we don't know if the draw value is valid, and we do another search. If for M < N, we find out that it's still a draw, we can update the bound to M. If instead we find that it's winning with counter = M, then we can store this as a second bound and assume that it's also winning with counter <= M (lower 50mr counter can never make it any less winning). If the position is then searched with 50mr counter between M and N, we'd have to do another search and update one of the bounds.

Of course, SF eval often doesn't tell us "this is winning" and "this is drawn", so a difficulty with this approach arise if we'd find a lot of steps, i.e. search eval going slowly down with higher 50mr counter. We don't really want to store more than two values, so if .eg. we get +2 for count A, +1 for count B > A, and 0 for count C > B, there has to be some implementation decision to know what to do, and it will be imperfect.

For endgame positions like the one behind this issue, though, with TB usage, a draw bound and a win bound only would work fine.

This still involves significant overhead, but it doesn't destroy TT efficiency anywhere as much as using exact 50mr would.

In theory, some positions would suffer from extra overhead because we hit the position with ascending/descending 50mr counters. But in practice, most positions won't be anywhere as unlucky

I saw your post from 9 days ago, and it sounds like it may merit some consideration , but have you or anyone tried testing your theory yet?

[Uri Blass]

<snipped>

Simply ignoring the 50 move rule will not help.

I believe simply ignoring the 50 move rule and continue to search is going to help if you do it only in part of the cases(I do not claim to solve 100% of the cases when there is a problem but at least you can probably avoid cases when the evaluation is 0.00 for a lot of moves before the blunder).

Thinking about it again the best idea I can think about it
is to start every search without considering the 50 move rule and only if you see a significant advantage for one side and search deep enough so the 50 move rule may be relevant in the search start to do something different.

Deep enough is dependent on the search depth and the fifty move conunter in the root of the tree.

I also think that it is a mistake to store draws because of the fifty move rule as 0.00 and it is better to have at least some concept of better side based on previous search because the position that you store in the hash may be not a draw if you get it again with a different fifty move counter and you do not know in advance that you will not get it with a different move counter.

[MikeB]

I also think that it is a mistake to store draws because of the fifty move rule as 0.00 ..

That has been one of the suggested "solutions" since the hash tables were first incorporated 30+ years ago . But that doesn't solved the fake mate scores. (Stockfish has a hack not to show a fake mate score, but it will show a fake +99 centipawn score as if that helps).

[Uri Blass]

I also think that it is a mistake to store draws because of the fifty move rule as 0.00 ..

That has been one of the suggested "solutions" since the hash tables were first incorporated 30+ years ago . But that doesn't solved the fake mate scores. (Stockfish has a hack not to show a fake mate score, but it will show a fake +99 centipawn score as if that helps).

I think that you mean fake 99 pawns score because fake 99 centipawn score should help.

For the problem of fake mate scores or fake 99 pawns score
I think that at some point during the game when stockfish show a clearly winning score but still not mate
it may be better to start treat positions with different 50 move counter as different positions even if the pieces are on the same places even if it means stockfish is slower because being slow and safe may be better than being fast with the risk of blundering because of the 50 move rule.

I do not know what is the correct winning score to do it and it should be a score when the advantage from not having fake big scores is bigger than the demage of searching slower.