ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

optimal aspiration window for stockfish question
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Robert Hyatt



Joined: 27 Feb 2006
Posts: 20340
Location: Birmingham, AL

PostPost subject: Re: optimal aspiration window for stockfish question    Posted: Thu Mar 15, 2012 8:11 pm Reply to topic Reply with quote

While I have tests running, here is some more info about my opinion of how this stuff should work.

Point 1. You want to (optimally) do exactly one re-search to resolve any fail-high or fail-low. More than one is inefficient and causes you to search a tree that you would normally not traverse. In the last iteration or two this can be expensive.

Point 2. In doing that one re-search, you don't want to increase the search window beyond what is necessary to capture the true score. Why? take a case where you are going to win a positional advantage of +.3 over what you saw at the previous iteration, and your aspiration is +/- old score + .2... You fail high. Where you set the beta bound can be important. For example, if you don't get it to +.3, you will fail high again, which is a waste. If you set it to +.31, that would be the perfect bound because you would not fail high, nor would you have to deal with any paths in the PV search that produce a score that is more than 0.01 better than what we know is the real score. The farther you advance beta, the more "crap" works its way into the search and the tree grows. Hence the potential advantage of a null-window search we often mention.

So, we have a conundrum. We want to adjust the bound just enough to "catch" the true score, without going too far. If we don't adjust it enough, we get another fail high which is inefficient. If we adjust it too far, we search a larger tree than optimal (the reason for doing an aspiration search in the first place) which is again inefficient. So we want to do a "Goldilocks and the three bears" approach and get it just right.

Intuition tells me that the following, tuned a bit, is probably the right answer.

First, we can assume a positional fail-high needs to increase the margin by P, to catch (say) 90% of the positional fail-highs. If we initially increase the bound by this, 90% of the positions where we are only seeing a positional gain will be searched and produce an exact score. 10% of those will require a second re-search. We could increment by P again, or we could drop to the next step.

Second, if we get a fail high, and then a second fail high, we know that the true score is P+N better than the previous score. What can we guess about N. My thought is 1.0. We assume that if we are gaining more than P centipawns, that we are most likely winning a whole pawn. So the second re-search would be original + P + PAWN. And that will handle most of the cases. What next, assuming we fail high again. One could assume that maybe we should then add P again and re-search, and if that fails, add PAWN again and re-search. Something tells me that the better approach might be what we were doing in Cray Blitz:

assume previous iteration score was S, and that P = 0.25

Next iteration:

alpha=S-P, beta=S+P, search
if fail_high
beta=S-P, beta=S+P+P (winning a positional advantage)
if fail_high
beta=S+P+P+PAWN (maybe winning a pawn)
if fail_high
beta=S+P+P+3*PAWN (maybe winning a piece, not so common)
if fail_high
beta=S+P+P+9*PAWN (maybe winning a queen)
if fail_high
beta=infinity (must be a mate)

The downside is that there is nothing that says you just win an advantage, or a pawn, or a piece, or a queen, you can win a 2.5 pawn advantage by disrupting the opponent king, for example. In Crafty, I removed that queen option and just went positional, pawn, piece, infinity. Minimal re-searches. Minimal waste. Problem is, if you are winning a rook, you now have to search lines where you have the unforced chance to win a queen and you can't prune such branches with beta too high.

A lot of this is really moot on the fail-high side, because there you are likely simply discovering how quickly you will win the game.

But take this the other direction and it becomes more important, because when a move fails low, you want to quickly discover how bad.

BTW there are some more efficient ways to deal with fail-highs, assuming you don't mind dealing with incomplete information.

Belle (Ken Thompson) did this first, I used it for a long while in Cray Blitz...

When you fail high, no need to re-search since you know this is a new best move. Keep searching. If you end the iteration, good, start the next and search normally. Only sticking point is that if you get a second move that fails high, you are in a quandry, which is better. Re-search one with a wider window to get an exact score, then re-search the second with alpha=new best score, and beta = new-best-score + 1. If that move fails low, the first one is best. Keep going. If the second move fails high, remember but don't research unless another move fails high. Repeat as necessary.

The down side is that you don't know how good a move is since you don't resolve the fail-high immediately. That was a problem for me, because I use the score to control time allocation. Suppose you fail low, losing a pawn. And find another move that fails high. Does it save the pawn? Or does it lose the pawn but gain a tiny bit of positional advantage back? For the former, I can stop using extra time, while for the latter, I want to keep searching to find a way to save the pawn. But if I don't know the true score, I can't make that decision. So the PVS implementation used by Ken and myself way back has a hole in it that I don't like, and do not use today for that reason.
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
optimal aspiration window for stockfish question Uri Blass Mon Mar 12, 2012 11:14 am
      Re: optimal aspiration window for stockfish question Ed Schroder Mon Mar 12, 2012 12:55 pm
            Re: optimal aspiration window for stockfish question Marco Costalba Mon Mar 12, 2012 6:47 pm
                  Re: optimal aspiration window for stockfish question Don Dailey Mon Mar 12, 2012 9:41 pm
                        Re: optimal aspiration window for stockfish question Robert Hyatt Wed Mar 14, 2012 10:18 pm
                              Re: optimal aspiration window for stockfish question Marco Costalba Thu Mar 15, 2012 6:15 am
                                    Re: optimal aspiration window for stockfish question Robert Hyatt Thu Mar 15, 2012 2:06 pm
                                          Re: optimal aspiration window for stockfish question Robert Hyatt Thu Mar 15, 2012 5:30 pm
                                                Re: optimal aspiration window for stockfish question Robert Hyatt Thu Mar 15, 2012 8:11 pm
                                                      Re: optimal aspiration window for stockfish question (update Robert Hyatt Thu Mar 15, 2012 9:55 pm
                                                            Re: optimal aspiration window for stockfish question (update Miguel A. Ballicora Thu Mar 15, 2012 10:23 pm
                                                                  Re: optimal aspiration window for stockfish question (update Robert Hyatt Fri Mar 16, 2012 3:29 am
                                                                        Re: test results Robert Hyatt Fri Mar 16, 2012 3:41 am
                                                                              Re: test results Rémi Coulom Fri Mar 16, 2012 8:38 am
                                                                                    Re: test results Robert Hyatt Fri Mar 16, 2012 5:20 pm
                                                                              Re: test results Karlo Bala Jr. Fri Mar 16, 2012 11:30 am
                                                                                    Re: test results Robert Hyatt Fri Mar 16, 2012 5:26 pm
                                                                                          Re: test results Ed Schroder Fri Mar 16, 2012 6:31 pm
                                                                                          Re: test results Robert Hyatt Fri Mar 16, 2012 7:16 pm
                                          Re: optimal aspiration window for stockfish question Vincent Diepeveen Sat Mar 17, 2012 1:44 pm
                                                Re: optimal aspiration window for stockfish question Robert Hyatt Sat Mar 17, 2012 4:11 pm
                                                      Re: optimal aspiration window for stockfish question Marco Costalba Sat Mar 17, 2012 5:28 pm
                                                            Re: optimal aspiration window for stockfish question Robert Hyatt Sun Mar 18, 2012 3:28 am
                                                                  Re: optimal aspiration window for stockfish question Lucas Braesch Sun Mar 18, 2012 5:55 am
                                                                        Re: optimal aspiration window for stockfish question Joona Kiiski Sun Mar 18, 2012 9:02 am
                  Re: optimal aspiration window for stockfish question Robert Houdart Mon Mar 12, 2012 10:44 pm
                        Re: optimal aspiration window for stockfish question Robert Houdart Tue Mar 13, 2012 9:18 am
                              Re: optimal aspiration window for stockfish question Uri Blass Tue Mar 13, 2012 10:12 am
                                    Re: optimal aspiration window for stockfish question Karlo Bala Jr. Wed Mar 14, 2012 7:46 pm
                                          Re: optimal aspiration window for stockfish question Robert Hyatt Thu Mar 15, 2012 9:49 pm
                  Re: optimal aspiration window for stockfish question Lucas Braesch Wed Mar 14, 2012 4:10 pm
                        Re: optimal aspiration window for stockfish question Eelco de Groot Wed Mar 14, 2012 7:30 pm
                              Re: optimal aspiration window for stockfish question Lucas Braesch Thu Mar 15, 2012 2:03 am
                                    Re: optimal aspiration window for stockfish question Marco Costalba Thu Mar 15, 2012 6:13 am
      Re: optimal aspiration window for stockfish question Eelco de Groot Tue Mar 13, 2012 10:20 am
            Re: optimal aspiration window for stockfish question Uri Blass Tue Mar 13, 2012 12:57 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads