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)
Fix a bug created by Aspiration Windows->Massive ELO loss
Moderators: hgm, Rebel, chrisw
-
- Posts: 1754
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Fix a bug created by Aspiration Windows->Massive ELO loss
#WeAreAllDraude #JusticeForDraude #RememberDraude #LeptirBigUltra
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
-
- Posts: 27798
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Fix a bug created by Aspiration Windows->Massive ELO
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.
-
- Posts: 1754
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: Fix a bug created by Aspiration Windows->Massive ELO
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.
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.
#WeAreAllDraude #JusticeForDraude #RememberDraude #LeptirBigUltra
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
-
- Posts: 2851
- Joined: Wed Mar 08, 2006 10:01 pm
- Location: Irvine, CA, USA
Re: Fix a bug created by Aspiration Windows->Massive ELO
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.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Fix a bug created by Aspiration Windows->Massive ELO
It's not quite that simple.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.
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).
-
- Posts: 10282
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Fix a bug created by Aspiration Windows->Massive ELO
Not searching does not mean returning a draw score.Evert wrote:It's not quite that simple.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.
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).
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.
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: Fix a bug created by Aspiration Windows->Massive ELO
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.
-
- Posts: 1754
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: Fix a bug created by Aspiration Windows->Massive ELO
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.
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.
#WeAreAllDraude #JusticeForDraude #RememberDraude #LeptirBigUltra
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: Fix a bug created by Aspiration Windows->Massive ELO
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.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.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Fix a bug created by Aspiration Windows->Massive ELO
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.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).
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).
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 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.
If the repetition is against the game history it's a different matter.