Aspiration windows

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
G.B. Harms
Posts: 42
Joined: Sat Aug 08, 2009 12:18 pm
Location: Almere

Re: Aspiration windows

Post by G.B. Harms » Sun Jan 08, 2012 11:45 am

lucasart wrote:I've been doing quite a few experiments with those, and could never come up with anything elo increasing. So I currently do a search with (alpha,beta) = (-INF,+INF).

I wonder how other engine developers do that, and if they managed to find a way that actually improves anything.

Amongst my several attempts, the most "logical" one would be

Code: Select all

do {
  score = search(..., depth, alpha, beta)
  if &#40;score <= alpha&#41;
    alpha=-INF;
  else if &#40;score >= beta&#41;
    beta = +INF;
&#125; while &#40;score <= alpha || score >= beta&#41;;
// set aspiration window for the next depth
alpha = score - 150;
beta = score + 150;
this pseudo code is of course embedded in the iterative deepening loop.[/code]
It looks it will jump out of the loop after the first iteration. It may also be better to do alpha=max(-INF, alpha-margin); beta=min(+INF, beta+margin). I reset to -INF,+INF immediately after a fl or fh because, until now, I could not test an improvement by gradually opening the window and code is (a tiny bit) more readable with simple method to open it fully at once.

User avatar
Rebel
Posts: 6175
Joined: Thu Aug 18, 2011 10:04 am

Re: Aspiration windows

Post by Rebel » Sun Jan 08, 2012 1:36 pm

zamar wrote:AFAIK the recipe that all top engines are using is:

- Use very small aspiration window (only something like 8cp - 16cp).
- Use very low effective branching factor (~1.6)
Yep.

Some possible refinements,

1. Use a somewhat bigger window in case of score fluctuations between iterations.

2. Use a somewhat bigger window in case of more than 2 best move changes within an iteration. 2 is arguable of course.

This will result in many researches, but for some reason it seems to pay off. Also you must note that with low EBF + small aspiration window, you may want to adjust your time management to be more aggressive compared to high EBF without aspiration window.

IMO all these three issues (aspiration window, EBF and time management) are so closely related that you cannot tune one without also tuning the others.
Yep.

Engin
Posts: 881
Joined: Mon Jan 05, 2009 6:40 pm
Location: Germany
Full name: Engin Üstün

Re: Aspiration windows

Post by Engin » Sun Jan 08, 2012 6:46 pm

yup

yes i am using a small window too, about 8cp, but if the alpha or beta change at a score of mate i will search with full window.

jacobbl
Posts: 80
Joined: Wed Feb 17, 2010 2:57 pm

Re: Aspiration windows

Post by jacobbl » Sun Jan 08, 2012 10:00 pm

You are saying one should use a low ebf, just as if it's a parameter you can choose. One of my largest struggles is to lower my ebf. Could you please enlighten me on what you mean with: "Use a low ebf"?

Regards
Jacob

zamar
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: Aspiration windows

Post by zamar » Sun Jan 08, 2012 10:14 pm

jacobbl wrote:You are saying one should use a low ebf, just as if it's a parameter you can choose. One of my largest struggles is to lower my ebf. Could you please enlighten me on what you mean with: "Use a low ebf"?

Regards
Jacob
Sure! Old chess programs use various extensions and few reductions. This results in high-branching factor >= 2.0.

AFAIK Modern top chess program use very few extensions and are very aggressive in reductions and prunings.

For starters you could try:
- Take out every extensions except checks and single-move
- LMR reducing two plies for non-captures (at least at the end of the move list).
- Null move with R=3,4,5,6 (higher reduction closer to root)
- Prune neg. SEE moves close to leafs
- Prune moves at the end of the move list in close to leafs

Of course every chess engine is a different beast and not every idea can work in every program. But the current tendency is to favor reductions and prunings instead of extensions.
Joona Kiiski

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Aspiration windows

Post by Evert » Sun Jan 08, 2012 10:14 pm

Correct me if I'm wrong, but you only need an exact score for the best move, so for any other move you don't adjust the window and research when they fail low because that's the expected behaviour. Right?
Your pseudo-code sample seems to always research when a move fails low, even if you expect it to.

Or am I completely missing something?

Sven
Posts: 4004
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Aspiration windows

Post by Sven » Mon Jan 09, 2012 8:58 am

Evert wrote:Correct me if I'm wrong, but you only need an exact score for the best move, so for any other move you don't adjust the window and research when they fail low because that's the expected behaviour. Right?
Your pseudo-code sample seems to always research when a move fails low, even if you expect it to.

Or am I completely missing something?
In the pseudo code given above the "search(...)" call is meant as the search of the root node, it is the code for one single iteration, i.e. (part of) the body of the iteration loop:

Code: Select all

for &#40;iteration = 1; iteration <= maxIteration; iteration++) &#123;
    // now the code above
&#125;
What you wrote applies for the root node search itself which is not shown above.

Sven

User avatar
Rebel
Posts: 6175
Joined: Thu Aug 18, 2011 10:04 am

Re: Aspiration windows

Post by Rebel » Mon Jan 09, 2012 11:04 am

zamar wrote:
jacobbl wrote:You are saying one should use a low ebf, just as if it's a parameter you can choose. One of my largest struggles is to lower my ebf. Could you please enlighten me on what you mean with: "Use a low ebf"?

Regards
Jacob
Sure! Old chess programs use various extensions and few reductions. This results in high-branching factor >= 2.0.

AFAIK Modern top chess program use very few extensions and are very aggressive in reductions and prunings.

For starters you could try:
- Take out every extensions except checks and single-move
- LMR reducing two plies for non-captures (at least at the end of the move list).
- Null move with R=3,4,5,6 (higher reduction closer to root)
- Prune neg. SEE moves close to leafs
- Prune moves at the end of the move list in close to leafs

Of course every chess engine is a different beast and not every idea can work in every program. But the current tendency is to favor reductions and prunings instead of extensions.
You Stockfish guys are a shining example how computer chess is supposed to be.

User avatar
JVMerlino
Posts: 1083
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Aspiration windows

Post by JVMerlino » Tue Jan 10, 2012 5:10 pm

zamar wrote:
jacobbl wrote:You are saying one should use a low ebf, just as if it's a parameter you can choose. One of my largest struggles is to lower my ebf. Could you please enlighten me on what you mean with: "Use a low ebf"?

Regards
Jacob
Sure! Old chess programs use various extensions and few reductions. This results in high-branching factor >= 2.0.

AFAIK Modern top chess program use very few extensions and are very aggressive in reductions and prunings.

For starters you could try:
- Take out every extensions except checks and single-move
- LMR reducing two plies for non-captures (at least at the end of the move list).
- Null move with R=3,4,5,6 (higher reduction closer to root)
- Prune neg. SEE moves close to leafs
- Prune moves at the end of the move list in close to leafs

Of course every chess engine is a different beast and not every idea can work in every program. But the current tendency is to favor reductions and prunings instead of extensions.
Regarding "prune moves at the end of the move list in close to leafs", what is the criteria for this? Or do you really just prune all of these moves and hope you don't miss something? How close is "close to leafs"?

jm

User avatar
JVMerlino
Posts: 1083
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Aspiration windows

Post by JVMerlino » Tue Jan 10, 2012 5:12 pm

zamar wrote:AFAIK the recipe that all top engines are using is:

- Use very small aspiration window (only something like 8cp - 16cp).
- Use very low effective branching factor (~1.6)

This will result in many researches, but for some reason it seems to pay off. Also you must note that with low EBF + small aspiration window, you may want to adjust your time management to be more aggressive compared to high EBF without aspiration window.

IMO all these three issues (aspiration window, EBF and time management) are so closely related that you cannot tune one without also tuning the others.
Is there some limit on how often you will research? In other words, if your search window starts at +/- 8cp, and the next depth produces a mate score, you're not really going to get to that score 8cp at a time, are you?

Or, maybe I should just look at the Stockfish code. :)

jm

Post Reply