alpha beta

[adams161]

in looking at my code i notice i have soemthing like this:
search( ply){

generatemoves();

while moves

makemove();

val=search(ply-1 .. other stuff)

unmake move

if(val>alpha)
alpha=val;

if(val>=beta)
return beta.
end loop

return alpha

I eliminated hashing nullmove and a bunch of stuff from this psedo code but what i had a question about was the beta cuttoff. I do val=search() then for the beta cuttoff if val>=beta return beta.

Does it matter if i'm not checking if alpha is greater than beta? I always assumed you could not have a beta cuttoff unless alpha got changed or val had to be first > alpha, i.e. alpha could never be equal or greater than beta at the start of search but only when alpha changes. is this correct?

Mike

[hgm]

Norbally alpha < beta, or it would already have been pointless to go to this node. Another way to see this is because current -beta and -alpha where alpha' and beta' in the parent. So if alpha >= beta now, than in the parent is must have been that alpha' >= beta'. And if that were true, you would already have done a beta cutof after the move that made alpha' such.

Following the line back there must at some point have been a plase where an alpha got changed to be >= beta, or it must already have been the case in the root (and that would then be a bug).

If you also hand out scores without search, like in QS, where you have something like

curEval = Evaluate();
if(curEval > alpha) alpha = curEval;

things are a little different: such a change can also make alpha >= beta, and you have to test for cutoff there as well.

[Gerd Isenberg]

Does it matter if i'm not checking if alpha is greater than beta? I always assumed you could not have a beta cuttoff unless alpha got changed or val had to be first > alpha, i.e. alpha could never be equal or greater than beta at the start of search but only when alpha changes. is this correct?

In PVS most nodes are null-windows with beta == alpha + 1.
In such > 99% none-pv nodes both conditions are equivalent. Thus, your alpha update, which makes alpha greater/equal beta is not necessary.

Code: Select all

if(val > alpha)
   alpha=val;

if(val >= beta)
   return beta. 

Therefor the cheapest is the other way around and to don't waste time to "illegally" update alpha.

Code: Select all

if(val >= beta)
   return beta; // return val for fail soft
if(val > alpha) // only taken at pv-nodes with wide alpha-beta window
  alpha = val;

The following is also correct, but worse and takes two conditions in the most common case as well, even if the inner is predicted correctly most of the time ...

Code: Select all

if(val > alpha)
{
   alpha = val;
   if ( alpha >= beta)
      return beta;
}

[adams161]

Hi,

In some cases you may know a move might change alpha, but you know it doesnt change beta or at least that is the guess. For example a hash postion that you cant just return on because not enough depth but you know the move had changed alpha not beta. Or a killer move that your saving, should you only save a killer move if it changes beta or is there any advantages if it changes alpha? Basicly is it only useful to move order if you think something is going to force a cutoff, or can there be some use if you think the move will improve the score but from what you know doesnt cause a cuttoff.

Mike

[bob]

Hi,

In some cases you may know a move might change alpha, but you know it doesnt change beta or at least that is the guess. For example a hash postion that you cant just return on because not enough depth but you know the move had changed alpha not beta. Or a killer move that your saving, should you only save a killer move if it changes beta or is there any advantages if it changes alpha? Basicly is it only useful to move order if you think something is going to force a cutoff, or can there be some use if you think the move will improve the score but from what you know doesnt cause a cuttoff.

Mike

You are getting way ahead of yourself... If you don't have sufficient draft (depth) for a hash entry, you know _nothing_ about the move/position, other than the move was best in some other search to less depth. that doesn't say a thing in any sort of absolute terms, it just suggests that the move _might_ be the best one here, although it is often wrong (a significant amount of time in fact)...

But, historically, in a given position, the best move for depth=n is the best move for depth=n+1, which is why we save and later try the hash move first...

That is exactly what killer moves are, except they are less specific, because they don't go with a specific position, they go with a specific ply and are therefore more general / less specific. That's why we don't try killers before the hash move, the hash move is specific to this position, not this ply. That's why we don't try killers before captures, captures are more specific and are more likely to cause a beta cutoff than any other move (often the hash move is a capture, for this very reason).