Futility Methods

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
outAtime
Posts: 226
Joined: Sun Mar 08, 2009 2:08 pm
Location: Canada

Futility Methods

Post by outAtime » Fri Jan 21, 2011 3:26 pm

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 &#40;value > best_value&#41; &#123;
			best_value = value;
			*best_move = *m;
			UpdatePV&#40;ply, m&#41;;
			if &#40;value > alpha&#41; &#123;				
				alpha = value;					
				if &#40;value >= beta&#41; 
					break;
return alpha;
sloppy

Code: Select all

if &#40;val > best_val&#41; &#123;
			best_val = val;
			best_move = move;
			if &#40;val > alpha&#41; &#123;
				alpha = val;
				update_pv&#40;pv, new_pv, move&#41;;
			&#125;
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 &#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
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]
outAtime

Daniel Shawul
Posts: 3758
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Futility Methods

Post by Daniel Shawul » Fri Jan 21, 2011 3:36 pm

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
Posts: 226
Joined: Sun Mar 08, 2009 2:08 pm
Location: Canada

Re: Futility Methods

Post by outAtime » Fri Jan 21, 2011 3:44 pm

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.
outAtime

bob
Posts: 20559
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Futility Methods

Post by bob » Fri Jan 21, 2011 3:56 pm

outAtime wrote: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
Posts: 226
Joined: Sun Mar 08, 2009 2:08 pm
Location: Canada

Re: Futility Methods

Post by outAtime » Fri Jan 21, 2011 4:08 pm

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

Code: Select all

if &#40;fut_score == INF&#41; &#123;
				fut_score = eval&#40;) + 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.
outAtime

Post Reply