TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Robert Hyatt

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

 Post subject: Re: optimal aspiration window for stockfish question    Posted: Thu Mar 15, 2012 8:11 pm 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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Uri Blass Mon Mar 12, 2012 11:14 am
Ed Schroder Mon Mar 12, 2012 12:55 pm
Marco Costalba Mon Mar 12, 2012 6:47 pm
Don Dailey Mon Mar 12, 2012 9:41 pm
Robert Hyatt Wed Mar 14, 2012 10:18 pm
Marco Costalba Thu Mar 15, 2012 6:15 am
Robert Hyatt Thu Mar 15, 2012 2:06 pm
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
Robert Hyatt Thu Mar 15, 2012 9:55 pm
Miguel A. Ballicora Thu Mar 15, 2012 10:23 pm
Robert Hyatt Fri Mar 16, 2012 3:29 am
Robert Hyatt Fri Mar 16, 2012 3:41 am
Rémi Coulom Fri Mar 16, 2012 8:38 am
Robert Hyatt Fri Mar 16, 2012 5:20 pm
Karlo Bala Jr. Fri Mar 16, 2012 11:30 am
Robert Hyatt Fri Mar 16, 2012 5:26 pm
Ed Schroder Fri Mar 16, 2012 6:31 pm
Robert Hyatt Fri Mar 16, 2012 7:16 pm
Vincent Diepeveen Sat Mar 17, 2012 1:44 pm
Robert Hyatt Sat Mar 17, 2012 4:11 pm
Marco Costalba Sat Mar 17, 2012 5:28 pm
Robert Hyatt Sun Mar 18, 2012 3:28 am
Lucas Braesch Sun Mar 18, 2012 5:55 am
Joona Kiiski Sun Mar 18, 2012 9:02 am
Robert Houdart Mon Mar 12, 2012 10:44 pm
Robert Houdart Tue Mar 13, 2012 9:18 am
Uri Blass Tue Mar 13, 2012 10:12 am
Karlo Bala Jr. Wed Mar 14, 2012 7:46 pm
Robert Hyatt Thu Mar 15, 2012 9:49 pm
Lucas Braesch Wed Mar 14, 2012 4:10 pm
Eelco de Groot Wed Mar 14, 2012 7:30 pm
Lucas Braesch Thu Mar 15, 2012 2:03 am
Marco Costalba Thu Mar 15, 2012 6:13 am
Eelco de Groot Tue Mar 13, 2012 10:20 am
Uri Blass Tue Mar 13, 2012 12:57 pm

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumChess Players ForumForum Help and Suggestions
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