| View previous topic :: View next topic |
| Author |
Message |
Uri Blass
Joined: 08 Mar 2006
Posts: 6013
Location: Tel-Aviv Israel
|
 Posted: Mon Mar 12, 2012 11:14 am Post subject: optimal aspiration window for stockfish question |
  |
|
Looking at analysis of stockfish of some position from correspondence game(I omit the moves and only show the scores)
you can see that the score at depth 35 is 1.97 and the score at depth 36
is 1.93 but for some reason stockfish has many fail low and fail high during the process(this is not something rare and the same happened also at depth 24 of the same search).
I wonder if it is not better to start with bigger difference between alpha and beta with big depth and if the programmers tried to optimize the difference between alpha and beta in stockfish as a function of depth.
Did somebody in the stockfish team tested to find the size of the optimal window for different depths to see if it is not better to change it.
35/79 40:24 10,618,711,296 4,378,972 +1.97
36/79- 42:46 11,265,468,653 4,388,811 +1.89
36/79- 43:36 11,486,371,530 4,389,792 +1.81
36/79- 44:35 11,747,022,497 4,390,999 +1.69
36/79+ 46:55 12,371,982,241 4,393,810 +2.06
36/79 55:58 14,833,537,002 4,417,125 +1.93
earlier from the same search
23/56 00:36 130,367,750 3,606,399 +1.37 24/56+ 00:43 158,498,424 3,604,776 +1.45 24/56- 00:46 169,841,034 3,623,584 +1.29 24/56- 00:47 172,222,913 3,627,349 +1.17
24/56- 00:48 175,065,644 3,613,624 +0.98 24/56+ 00:50 183,805,380 3,619,356 +1.53
24/64 01:03 231,112,085 3,634,123 +1.37 |
|
| Back to top |
|
 |
Ed Schroder
Joined: 18 Aug 2011
Posts: 1643
|
| Posted: Mon Mar 12, 2012 12:55 pm Post subject: Re: optimal aspiration window for stockfish question |
|
|
Without knowing which margins are used it looks like a classic case of search irregularities. Surely you can fix an individual case with a wider A/B window but it may hurt the overall performance. I am sure the SF team have done considerable testing here.
From my own countless experiments the old-fashioned way worked best after all. A window of 0.50 for the first move, then for the rest of the moves a small margin of 0.125 making an exception for score drops, the margin is set to 0.25.
But then again, mine is not a modern chess program, re-searches are very expensive due to a big fat old fashioned mailbox EVAL and thus I tend to avoid them as much as I can. |
|
| Back to top |
|
|
Marco Costalba
Joined: 14 Jun 2008
Posts: 2097
|
| Posted: Mon Mar 12, 2012 6:47 pm Post subject: Re: optimal aspiration window for stockfish question |
|
|
| Rebel wrote: |
I am sure the SF team have done considerable testing here.
|
Yes, we have.
At the end of endless trials with differnt formulas and values we end up in starting with a small window value:
| Code: |
delta = Value(16);
alpha = RootMoves[PVIdx].prevScore - delta;
beta = RootMoves[PVIdx].prevScore + delta;
|
That is increased after a fail low/high with the following formula:
| Code: |
if (bestValue >= beta)
{
beta += delta;
delta += delta / 2;
}
else if (bestValue <= alpha)
{
alpha -= delta;
delta += delta / 2;
}
|
I want to add that this is the Ippo* formula and I think that very probably it is what is used in _all_ the top engines from Rybka 3 to Houdini. Although we knew the Ippo formula since when sources were published we moved to that only one year later, after having tried all the possible different combinations: some are weaker, some are equivalent ELO wise, but more complex, so this is the simplest formula (we know) that guarantees top performance.
Answering to Uri: I am not interested in tweaking the engine on a sample position. I only use real games to validate a change. |
|
| Back to top |
|
|
Don Dailey
Joined: 29 Apr 2008
Posts: 4502
|
| Posted: Mon Mar 12, 2012 9:41 pm Post subject: Re: optimal aspiration window for stockfish question |
|
|
| mcostalba wrote: |
| Rebel wrote: |
I am sure the SF team have done considerable testing here.
|
Yes, we have.
At the end of endless trials with differnt formulas and values we end up in starting with a small window value:
| Code: |
delta = Value(16);
alpha = RootMoves[PVIdx].prevScore - delta;
beta = RootMoves[PVIdx].prevScore + delta;
|
That is increased after a fail low/high with the following formula:
| Code: |
if (bestValue >= beta)
{
beta += delta;
delta += delta / 2;
}
else if (bestValue <= alpha)
{
alpha -= delta;
delta += delta / 2;
}
|
I want to add that this is the Ippo* formula and I think that very probably it is what is used in _all_ the top engines from Rybka 3 to Houdini. Although we knew the Ippo formula since when sources were published we moved to that only one year later, after having tried all the possible different combinations: some are weaker, some are equivalent ELO wise, but more complex, so this is the simplest formula (we know) that guarantees top performance.
Answering to Uri: I am not interested in tweaking the engine on a sample position. I only use real games to validate a change. |
That's what we do. We will run a few hundred games at various fixed depth levels and have the instrumentation that gives us the average time per move up to some arbitrary move number. I think we currently use move 70. We think this is superior to just running 100 positions and timing them. We only do this when we want data on something that is supposed to be a speedup - normally we just run time games to measure general improvements and things that involve trade-offs.
_________________
The Optimist thinks this is the best of all possible worlds, the Pessimist fears it is true. |
|
| Back to top |
|
|
Robert Houdart
Joined: 15 Mar 2010
Posts: 1260
|
| Posted: Mon Mar 12, 2012 10:44 pm Post subject: Re: optimal aspiration window for stockfish question |
|
|
| mcostalba wrote: |
| I want to add that this is the Ippo* formula and I think that very probably it is what is used in _all_ the top engines from Rybka 3 to Houdini. |
Houdini doesn't use these formulae.
Please don't spread incorrect assumptions about Houdini.
Regards,
Robert |
|
| Back to top |
|
|
Robert Houdart
Joined: 15 Mar 2010
Posts: 1260
|
| Posted: Tue Mar 13, 2012 9:18 am Post subject: Re: optimal aspiration window for stockfish question |
|
|
| Uri Blass wrote: |
| The more interesting question is which houdini does not use that formula because there are more than one houdini version. |
If you're really interested, no version of Houdini has used the formulae that Marco quoted above.
Houdini uses an aspiration window that widens much faster.
Robert |
|
| Back to top |
|
|
Uri Blass
Joined: 08 Mar 2006
Posts: 6013
Location: Tel-Aviv Israel
|
| Posted: Tue Mar 13, 2012 10:12 am Post subject: Re: optimal aspiration window for stockfish question |
|
|
| Houdini wrote: |
| Uri Blass wrote: |
| The more interesting question is which houdini does not use that formula because there are more than one houdini version. |
If you're really interested, no version of Houdini has used the formulae that Marco quoted above.
Houdini uses an aspiration window that widens much faster.
Robert |
Thanks Robert.
My intuition also tells me that it is better to have less researches(increasing delta faster by a different formula may be a way to do it)
Maybe the stockfish team may try something like
if (bestValue >= beta)
{
beta += delta;
delta += delta*2;
}
else if (bestValue <= alpha)
{
alpha -= delta;
delta += delta *2;
} |
|
| Back to top |
|
|
Eelco de Groot
Joined: 12 Mar 2006
Posts: 2595
Location: Groningen
|
| Posted: Tue Mar 13, 2012 10:20 am Post subject: Re: optimal aspiration window for stockfish question |
|
|
@Uri: It is probably not such a bad idea to let it depend not only on the depth but also the amount of hash. If there are more holes in the hash table because of saturation, it is likely that you will see more failed searches for good PV nodes, and that leads to more fail lows or fail highs. I don't think that a wider window by itself will be more efficient if there are a lot of Fail Lows or Fail Highs, but the fail low or fail high searches will take longer if they find no stored positions in hash. And then it is possibly better to just use a wider window. I don't think Uri's correspondence chess example is really a case where this already applies, because the fail lows all seem to go pretty fast and the endresult is actually lower so the fail lows did their work on the right side as it were. But if Marco wants to test your theory and he needs a timecontrol of at least 40 minutes per move it is going to be rather timeconsuming. But you should be able to simulate my theory of the hash effect on short timecontrols a bit.
_________________
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan |
|
| Back to top |
|
|
Uri Blass
Joined: 08 Mar 2006
Posts: 6013
Location: Tel-Aviv Israel
|
| Posted: Tue Mar 13, 2012 12:57 pm Post subject: Re: optimal aspiration window for stockfish question |
|
|
| Eelco de Groot wrote: |
| @Uri: It is probably not such a bad idea to let it depend not only on the depth but also the amount of hash. If there are more holes in the hash table because of saturation, it is likely that you will see more failed searches for good PV nodes, and that leads to more fail lows or fail highs. I don't think that a wider window by itself will be more efficient if there are a lot of Fail Lows or Fail Highs, but the fail low or fail high searches will take longer if they find no stored positions in hash. And then it is possibly better to just use a wider window. I don't think Uri's correspondence chess example is really a case where this already applies, because the fail lows all seem to go pretty fast and the endresult is actually lower so the fail lows did their work on the right side as it were. But if Marco wants to test your theory and he needs a timecontrol of at least 40 minutes per move it is going to be rather timeconsuming. But you should be able to simulate my theory of the hash effect on short timecontrols a bit. |
The fail low is not justified in my example
stockfish started with 1.97 and the first fail low said lower than 1.89 but the final score was 1.93
35/79 40:24 10,618,711,296 4,378,972 +1.97
36/79- 42:46 11,265,468,653 4,388,811 +1.89
36/79- 43:36 11,486,371,530 4,389,792 +1.81
36/79- 44:35 11,747,022,497 4,390,999 +1.69
36/79+ 46:55 12,371,982,241 4,393,810 +2.06
36/79 55:58 14,833,537,002 4,417,125 +1.93
second example from the same search
The score did not change so fail high and fail low are not justified.
23/56 00:36 130,367,750 3,606,399 +1.37
24/56+ 00:43 158,498,424 3,604,776 +1.45
24/56- 00:46 169,841,034 3,623,584 +1.29
24/56- 00:47 172,222,913 3,627,349 +1.17
24/56- 00:48 175,065,644 3,613,624 +0.98
24/56+ 00:50 183,805,380 3,619,356 +1.53
24/64 01:03 231,112,085 3,634,123 +1.37 |
|
| Back to top |
|
|
Lucas Braesch
Joined: 31 May 2010
Posts: 1824
|
| Posted: Wed Mar 14, 2012 4:10 pm Post subject: Re: optimal aspiration window for stockfish question |
|
|
your initial delta is only 1/16-th of a pawn ? |
|
| Back to top |
|
|
|
|
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
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
