Fix a bug created by Aspiration Windows->Massive ELO loss

[AndrewGrant]

Hey,

I recently implemented a very simple Aspiration Window wrapper around the root of the search. After running my test sets I found a ~30 ELO gain and committed the changes. I then discovered a bug with how I was storing Transposition Entries in the root search, now that the bounds are not always -INF, INF.

Originally, I would store at the end of rootSearch like this:

storeTranspositionEntry(&Table, depth, board->turn, PVNODE, best, bestMove, board->hash);


Obviously now that I am using Aspiration Windows the node is not guaranteed to be a PVNODE, so I used code to correctly identify the node type like this:


if (best > oldAlpha && best < beta) // Where oldAlpha is the Alpha value at the start of the search
storeTranspositionEntry(&Table, depth, board->turn, PVNODE, best, bestMove, board->hash);
else if (best >= beta)
storeTranspositionEntry(&Table, depth, board->turn, CUTNODE, best, bestMove, board->hash);
else if (best <= oldAlpha)
storeTranspositionEntry(&Table, depth, board->turn, ALLNODE, best, bestMove, board->hash);

This seemed like a simple bug fix, and I even suspected to gain some ELO out of it, since I would no longer be wrongly storing information about the root. But I was very wrong. In testing, these changes actually drop the ELO by about ~25.

I presume there is another bug somewhere which is being made more profound as a result of adding Aspiration Windows.

Does anyone have any thoughts as to were the source of the trouble may be? (It's not LAZY eval, I don't do that)

[hgm]

It seems to me the info you store would be never used, so who cares what you store? Any occurrence of the root elsewhere in the tree would be a repetition, and thus should get a draw score irrespective of the scoreand bound type stored for it in the TT.

[AndrewGrant]

Are you defining a repetition as the position occurring twice? I've only been assigning draw scores to positions that hit 3 repetitions. Never thought about this.... I suppose I should be using draw scores for positions that occur twice... not thrice.

I suppose I should never even being storing transpositions at the root then (I don't use them to backtrack PV).

I'll change my definition of repetition and see what the results are. Thanks for the response.

[Dirt]

Most programmers think a single repetition should be scored as a draw but most users think that's a bug. It's a never ending argument.

[Evert]

Most programmers think a single repetition should be scored as a draw but most users think that's a bug. It's a never ending argument.

It's not quite that simple.
There is nothing to be gained by searching a position again if it repeats from an earlier point in the search: you can only search it again to a shallower depth, so it's a waste of time (or worse).
Where things get a bit icky is if the repetition occurs against the game history; then it's not necessarily pointless to search it (again? Maybe, maybe not).

[Uri Blass]

Most programmers think a single repetition should be scored as a draw but most users think that's a bug. It's a never ending argument.

It's not quite that simple.
There is nothing to be gained by searching a position again if it repeats from an earlier point in the search: you can only search it again to a shallower depth, so it's a waste of time (or worse).
Where things get a bit icky is if the repetition occurs against the game history; then it's not necessarily pointless to search it (again? Maybe, maybe not).

Not searching does not mean returning a draw score.

If you get a position that already was in the game but not twice then you can return for example previous score that you already had in the search or previous score that you already had in the search divided by 2(assuming the remaining depth is smaller then the real depth that you practically got in previous search).

If the remaining depth is higher than the depth that you had in previous search(can happen mainly in game with pondering when the opponent thought for a long time in the last move) then I think that it make sense to search and not stop in repetition.

It is only common sense and of course you need to do testing to see if you practically get an improvement from this idea or not.

[Edsel Apostol]

Don't retrieve and store hash table entries in the root (ply=0). It doesn't make sense. It will only return immediately after a re-search. For example, you have alpha = -100, beta = 100, you have returned a score of 150, you now do a research of the same depth with a wider window of lets say alpha = -100, beta = 200, now when you probe the hash table it will return immediately with a score of 150, without doing any re-search at all. What you can do is to retain the best move of the last iteration, and use that as the first move to be searched in succeeding iterations and re-search.

[AndrewGrant]

That's simply not true. For two reasons.

1) I don't probe the hash in rootSearch
2) a value of 150 with window -100,100 will not cause any sort of early return. It's not a PV node, and it can't close the window.

[Edsel Apostol]

That's simply not true. For two reasons.

1) I don't probe the hash in rootSearch
2) a value of 150 with window -100,100 will not cause any sort of early return. It's not a PV node, and it can't close the window.

So you are not probing the hash table at the root (ply=0), but you said you are storing transposition entry at the end of root search? What should be the benefit of doing that? When the search encounters again that same position deep down the tree that you have a value from the hash table? Should that position be scored as draw instead? My opinion is that you should just remove that storing of hash entry at the root as it doesn't achieve anything.

[Evert]

Not searching does not mean returning a draw score.

If you get a position that already was in the game but not twice then you can return for example previous score that you already had in the search or previous score that you already had in the search divided by 2(assuming the remaining depth is smaller then the real depth that you practically got in previous search).

I thought about that, but the issue is that if you have a repetition in the search, then you don't have a reliable score for this node yet, so it's not so obvious what the score to return should be.

The advantage of returning a draw-score is that it at least has some rule-backing in that a third repetition is a draw (rather: can be claimed as such). Even without that, you can argue that it's the best thing to do, as follows.

If you find that your best option in the current position is to play a line that repeats the position, then the current position represents a (local) optimum in the evaluation for both sides, and neither side can make progress. If neither side can make progress towards winning the game, the game should be a draw (either by rule or agreement).

If the remaining depth is higher than the depth that you had in previous search(can happen mainly in game with pondering when the opponent thought for a long time in the last move) then I think that it make sense to search and not stop in repetition.

It never makes sense to search the position again for a repetition in the search. Unless you extend by more than one ply several times, you're not going to have a higher remaining depth than you did the first time you encountered it, so you're just inviting horizon effects.
If the repetition is against the game history it's a different matter.