Dann Corbit wrote: ↑Tue Dec 22, 2020 12:39 am
One alternative could be to store the next best score from the previous iteration (and possibly the next best move so we can search it first) along with alpha and beta.
In Principal Variation Search, we don't know the next best move. We only know it if MultiPV > 1.
At least in MadChess. I do PVS even at the root. I definitely remember testing this and confirming PVS at the root is stronger than a full alpha / beta window at the root.
Good point, that idea does not work with pvs search
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
I tried to implement Aspiration windows in Drofa two times, both were unsuccessful.
But on the first try i still had TT bug in the engine that made aspiration search very bad (plagued TT with worthless entries basically).
In the second try engine searched much less nodes, but still was ~-7 elo.
I suppose the Devil in the details here. You have to get everything right in order for it to work.
i`ll try one or two more times to implement this.
With like every top engine using it I more or less sure it is working technique, but the tricky one.
emadsen wrote: ↑Mon Dec 21, 2020 9:17 pmOtherwise I feel I'm subverting the correctness of the alpha / beta algorithm.
With pruning and reductions (especially LMR), that has gone out of the window long since anyway.
Is that a bad pun? Window, ha ha. Well, there never was correctness anyway because that assumes perfect static eval which is only true for draw-by-rule, stalemate, and checkmate. I see your point though. I just don’t see any advantage in aspiration windows over what I already get from PVS. Whereas I see a massive advantage in LMR.
I just run some experimentations that strongly disagree with your findings.
The aspiration windows algorithm is definitely worth on my engines. I got the following results, with self play using SPRT stop condition:
- Dumb : +54.2 +/- 7.3 Elo (834 games)
- Amoeba : +131.6 +/- 12.2 Elo (260 games)
Because of self play and SPRT, the Elo differences are probably exagerated, but obviously significant.
Are you sure your implementation is correct and optimal?
I've never had any luck with aspiration windows for Maverick. I've always assumed it was down to a poorly tuned evaluation function and generally weak-ish engine.
I've always thought that when searching the first move, the hash table would guide the search down the previous PV and the window would quickly close.
One point: do you have a fixed width for your window after each research, or are you gradually opening the window? For example...
First search: alpha = pv_score - 25; beta = pv_score + 25
Second search on fail high: alpha = pv_score - 25; beta = pv_score + 125
Third search on fail high: alpha = pv_score - 25; beta = pv_score + 300
Fourth search on fail high: alpha = pv_score - 25; beta = +inf
abulmo2 wrote: ↑Fri Dec 25, 2020 1:43 am
I just run some experimentations that strongly disagree with your findings.
The aspiration windows algorithm is definitely worth on my engines. I got the following results, with self play using SPRT stop condition:
- Dumb : +54.2 +/- 7.3 Elo (834 games)
- Amoeba : +131.6 +/- 12.2 Elo (260 games)
Because of self play and SPRT, the Elo differences are probably exagerated, but obviously significant.
Are you sure your implementation is correct and optimal?
If you want to test rating difference then SPRT is not the right test and you need to use fixed number of games.
abulmo2 wrote: ↑Fri Dec 25, 2020 1:43 am
I just run some experimentations that strongly disagree with your findings... Are you sure your implementation is correct and optimal?
Interesting. Thank you Richard for running these tests. I always am willing to admit the possibility I screwed up something in my code.
Steve Maughan wrote: ↑Fri Dec 25, 2020 11:15 amI've never had any luck with aspiration windows for Maverick. I've always assumed it was down to a poorly tuned evaluation function and generally weak-ish engine... Do you have a fixed width for your window after each research, or are you gradually opening the window?
I tried gradually opening the window by +/- 25, 50, 100, 200, 500, etc but eventually settled on +/- 100, 500, infinite.
abulmo2 wrote: ↑Fri Dec 25, 2020 1:43 am
I just run some experimentations that strongly disagree with your findings.
The aspiration windows algorithm is definitely worth on my engines. I got the following results, with self play using SPRT stop condition:
- Dumb : +54.2 +/- 7.3 Elo (834 games)
- Amoeba : +131.6 +/- 12.2 Elo (260 games)
Because of self play and SPRT, the Elo differences are probably exagerated, but obviously significant.
Are you sure your implementation is correct and optimal?
If you want to test rating difference then SPRT is not the right test and you need to use fixed number of games.
I ran a gauntlet test with Dumb (aspiration on/off) and found +50.9 Elo (+/- 12, 100 games × 19 opponents) in favour of the engine with the aspiration windows. So the result is on par with the SPRT.