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

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
AndrewGrant
Posts: 583
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

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

Post by AndrewGrant » Thu Jun 09, 2016 11:49 pm

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)

User avatar
hgm
Posts: 24586
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by hgm » Fri Jun 10, 2016 12:04 am

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
Posts: 583
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by AndrewGrant » Fri Jun 10, 2016 12:28 am

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
Posts: 2851
Joined: Wed Mar 08, 2006 9:01 pm
Location: Irvine, CA, USA

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by Dirt » Fri Jun 10, 2016 3:54 am

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.
Deasil is the right way to go.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by Evert » Fri Jun 10, 2016 5:40 am

Dirt wrote: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
Posts: 8765
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by Uri Blass » Fri Jun 10, 2016 6:51 am

Evert wrote:
Dirt wrote: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
Posts: 770
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by Edsel Apostol » Fri Jun 10, 2016 7:36 am

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
Posts: 583
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by AndrewGrant » Fri Jun 10, 2016 8:28 am

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
Posts: 770
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by Edsel Apostol » Fri Jun 10, 2016 8:38 am

AndrewGrant wrote: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.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Fix a bug created by Aspiration Windows->Massive ELO

Post by Evert » Fri Jun 10, 2016 8:59 am

Uri Blass wrote: 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.

Post Reply