How to solve Transposition Table with Aspiration Window?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
tsoj
Posts: 23
Joined: Thu Oct 19, 2017 2:59 pm
Location: Germany, Berlin
Full name: Jost Triller
Contact:

How to solve Transposition Table with Aspiration Window?

Post by tsoj » Wed Nov 28, 2018 9:30 pm

Hi,
today I finally found the problem why aspiration windows never really worked for me.
I had this code:

Code: Select all

Ply newDepth = depth;
Value newAlpha = alpha;
Value newBeta = beta;

// aspiration window
if(height == 0)
{
  Value estimate = -ss.tt->get(newPosition.zobristKey).value;
  if(estimate != NO_VALUE)
  {
    newAlpha = estimate - ASPIRATION_WINDOW;
    newBeta = estimate + ASPIRATION_WINDOW;
    if(newAlpha < alpha)
    {
      newAlpha = alpha;
    }
  }
}
// principal variation search
else if(nodeType == PV_NODE)
{
  newBeta = alpha+1;
}

// late move reduction
if(
  depth >= 2 &&
  moveCounter > 3 &&
  not move.isTactical() &&
  not inCheck &&
  not givingCheck
)
{
  newDepth = depth - 1;
  if(moveCounter > 10)
  {
    newDepth -= depth/4;
  }
}

value = -search(ss, newPosition, newDepth - 1, height + 1, -newBeta, -newAlpha);

if(value > alpha && (newAlpha > alpha || newBeta < beta)) // re-search full window reduced depth
{
  value = -search(ss, newPosition, newDepth - 1, height + 1, -beta, -alpha);
}
if(value > alpha && newDepth < depth) // re-search full window full depth
{
  value = -search(ss, newPosition, depth - 1, height + 1, -beta, -alpha);
}
This does not work: When a node fails low we may return the alpha score that we set with the aspiration window. This might be ok for this aspiration window search. However, in some cases, this alpha score gets stored to the hash table, which probably causes an incorrect full-window search.
I solved this bug by only adding something to the transposition table when I am not in an aspiration window search. However, it seems like the search is with that fix is even slower than without aspiration window.
What were your solutions to this problem? Should I add an extra flag to the hash table if I am in an aspiration window search?

User avatar
hgm
Posts: 22615
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How to solve Transposition Table with Aspiration Window?

Post by hgm » Wed Nov 28, 2018 10:25 pm

I don't think there is anything wrong in returning the aspirated alpha. It is still an upper bound to the score. Perhaps it isn't such a tight upper bound as you could have had with a lower (i.e. unaspirated) alpha. That is because the search spent less effort pushing the score down. Which is why you do aspiration in the first place.

tsoj
Posts: 23
Joined: Thu Oct 19, 2017 2:59 pm
Location: Germany, Berlin
Full name: Jost Triller
Contact:

Re: How to solve Transposition Table with Aspiration Window?

Post by tsoj » Wed Nov 28, 2018 11:14 pm

Yes right, I wasn't thinking straight. It seems like this is something different I just found out that the null-move pruning zero window (-beta, -(beta+1) also has something to do with it...

Post Reply