## Futility Methods

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

### Futility Methods

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&#40; value > best_value )
&#123;
best_value = value;
pv_cat&#40;pv, new_pv, move&#41;;

if&#40; value > alpha )
&#123;
alpha = value;
best_move = move;

if&#40; value >= beta )
goto cut;
ASSERT&#40;value_is_ok&#40;best_value&#41;);

return best_value;
``````
sf

Code: Select all

`````` // Step 17. Check for new best move
if &#40;value > bestValue&#41;
&#123;
bestValue = value;
if &#40;value > alpha&#41;
&#123;
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: 4103
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

### Re: Futility Methods

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

### Re: Futility Methods

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: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

### Re: Futility Methods

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

### Re: Futility Methods

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