Futility Methods

[outAtime]

There seems to be no standard for Fuility, and I'm trying to figure out the best way to add it to my search. Different examples I've seen only help to confuse... update PV/ don't update PV, use best_move/don't use best move.....

fruit

Code: Select all

 if( value > best_value )
            {
            best_value = value;
            pv_cat(pv, new_pv, move);

            if( value > alpha )
                {
                alpha = value;
                best_move = move;

                if( value >= beta )
                    goto cut;
 ASSERT(value_is_ok(best_value));

    return best_value;

sf

Code: Select all

 // Step 17. Check for new best move
      if (value > bestValue)
      {
          bestValue = value;
          if (value > alpha)
          {
              if &#40;PvNode && value < beta&#41; // We want always alpha < beta
                  alpha = value;
assert&#40;bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE&#41;;

    return bestValue;

returning alpha...

bison

Code: Select all

if (value > best_value) {
			best_value = value;
			*best_move = *m;
			UpdatePV(ply, m);
			if (value > alpha) {				
				alpha = value;					
				if (value >= beta) 
					break;
return alpha;

sloppy

Code: Select all

if (val > best_val) {
			best_val = val;
			best_move = move;
			if (val > alpha) {
				alpha = val;
				update_pv(pv, new_pv, move);
			}
return alpha;

So from all these examples, is updating the PV just an option? Whats the difference? Also, is updating the best_move just an option?
If I return alpha could I do:

Code: Select all

if (score > best_score && legal_move) {

            best_score = score;
	
if (score > alpha && legal_move) {
		alpha = score;
					
	/* update the pv: */  
return alpha

Or should I update the PV if score>best_score? I'm confused because all these programs are doing things differently and I cant see whats the difference? Do i really need a best_move = move function? Thanks, and sorry for reposting this, I was trying to simplify my question.
[/code]

[Daniel Shawul]

There is a 'fail hard' or 'fail soft' way of doing alpha-beta. The latter returns values outside of the bounds. More here http://chessprogramming.wikispaces.com/Fail-Soft

You should not update PV because in all cases score should be > alpha.

Best_move can be updated if you want to use it elsewhere (maybe store it in the hashtable and use it for move ordering later). But again you know this node is never gonna make it to the PV.

[outAtime]

ok, thanks for the reply. Then why do some of these programs update the PV or best_move if score > best score (the ones returning alpha)? Just for move ordering? Is there a benifit to that? Thanks again for the reply.

[bob]

ok, thanks for the reply. Then why do some of these programs update the PV or best_move if score > best score (the ones returning alpha)? Just for move ordering? Is there a benifit to that? Thanks again for the reply.

You are likely not understanding the code. You only update the PV if best > alpha && best < beta. For best <= alpha there is no best move at all. For best >= beta, you have a best move at this ply (which caused the cutoff) but there is no best move at the next or previous ply, by definition of a fail high.

[outAtime]

ok, great, thankyou very much! This should be correct then:

Code: Select all

if (fut_score == INF) {
				fut_score = eval() + FUT_MARGIN;
				assert&#40;fut_score < INF&#41;;
			&#125;
			
			score = fut_score;	
			/* prune */
			if &#40;fut_score <= alpha&#41; &#123;
				if &#40;score > best_score&#41; &#123;
					best_score = score;
						 						
				&#125;
				continue;
if &#40;score > best_score && legal_move&#41; &#123;

            best_score = score;
if &#40;score > alpha && legal_move&#41; &#123;
	alpha = score;
					
			/* update the pv&#58; */  
return alpha;

I just left out the conditions for futility and the >= beta part for simplicity.