Does simple futility prune work

[Chan Rasjid]

The article I have said futiliity prune at horizon works if margin is about 4 pawns.

I tried but it seems bad. My snailchess plays normally w/o futility
but much weaker with it and also sometimes makes clearly losing moves.


1) I strictly tested by limiting final positional eval() to 3.5 pawns
and margin is 4 pawns.
2) horizon depth is certain, taking into consideration extentions.

The psuedo codes is as follow:-

for-all- moves

//before makemove()
if (horizon-depth-move
&& not-check-or-incheck
&& material-side-less-xside<alpha-400
{
//prune move;
continue;
// codes added to ensure no false stalemate
}

makemove()

The logic seems Ok as if we make the move, it enters immediately into
QS and eval() will be a fail-high.


1) Have I miss something ?
2)Does anyone know if fruit, crafty, glarung, slowchess use a simple
futility prune ?

Best Regards
Rasjid

[Chan Rasjid]

Sorry for error.

My material is adjusted for capture/ep/promote.

So code should be

if ( ...
material-side-less-xside+adjustment-for-capture/ep/promote
< alpha-400{

continue;
}


Thanks
Rasjid

[Daniel Mehrmann]

Well, pruning at horizon depth is very dangerous.
You need more params to check this position as in your code.
For example be sure that you don't have a pin.

My experience is thats not a good idea to prune at this point.

daniel

[Chan Rasjid]

Hello,

The "expert" article I have mentioned it was tested ok.

I cannot understand why you mentioned it is dangerous or must check
for pins.

My test limits positional score to 3.5 pawns and logically
my futility is equivalent to entering into QS that eval() which will certainly cause a fail-high.

My experience is logic to do work in chess programming.

Rasjid

[Pallav Nawani]

Hello,

You have to be careful about what moves you prune, and when you prune. Then it will work. Here is some code from my program, where I decide when to prune or not.

Code: Select all

     if(gi.conf.dopruning
       && depth < 4
             && ply > gi.conf.fply
             && !threat
       && !incheck
       && !ISLOSSSCORE(alpha)
       && !ISPROMOTION(bmove)
       && (gi.brd[FRSQ(bmove)]->pc != PAWN
          || (TOSQ(bmove) > H2 && TOSQ(bmove) < A7))
       && can_check(gi, bmove) == 0)


I don't prune when:
(a) Null move returned mate threat
(b) We are in check
(c) Alpha is a Losing checkmate score
(d) The move in question is a pawn promotion, or a pawn move to the 7th rank.
(e) The move is giving check

There is one more thing you need to be careful about: What happens when you prune all the moves in a node? What is the value you will return in that case?

Handle these cases and futility pruning should work.

bye,
Pallav

[Marcus Prewarski]

Futility pruning seems to work for Diablo. At least with it Diablo performs tactically a little better, if it really plays better is harder to say. At horizon depth I use a futility margin of two pawns and at pre horizon I use a futility margin of a rook.

[Chan Rasjid]

Hello Pallav,


(a) Null move returned mate threat
- I currently is not using nullmove

(b) We are in check
(e) The move is giving check

- Not pruned also in my case.

(c) Alpha is a Losing checkmate score
- in which case material never below alpha - ok.

(d) The move in question is a pawn promotion, or a pawn move to the 7th rank.
- My guess for your not prunning the above is more psychological,
ie prunning "good" moves. This seems ok for futility at strictly/certain horizon depth.


There is one more thing you need to be careful about: What happens when you prune all the moves in a node? What is the value you will return in that case?

- the node should then fail low and search returns score= original alpha; also hashed as UB, score= alpha. In my case I will know there is at least one valid move.

I wish very much for a working futility prune as I found a fairly large number of moves pruned. I think futility prune at horizon may work as in your case when more conditions are set. I am surprised it does not work with only basic conditions - ie not check/incheck.

I have now analysed the situation logically (if correct ?)

1) Without hashing, my simple version of futility must work better.
2) With hashing - I think the search may sometime return significanly different scores.
a) On entering QS, a hash probe is usually done first and may return a
fail low with draft>0. The equivalent of futility prune before entering
QS should have been a fail high instead!
b) After searching all moves, the node may fail high with score =
original alpha. As I am using fail soft, w/o futility , I may fail high with
score < alpha and the hash may be UB or EXACT if the score type is
exact.
I only don't expect hashing should be this significant if my analysis is correct.

I still will see how I get it working, needed badly.


Thanks
Rasjid

[Chan Rasjid]

Hello Marcus,

You are lucky if using a margin of 2 pawns, it does not kill your program.
I found prunning at horizon can give a huge time advantage.

Mine just dont work and it gnaws at my head; my head says it should work
as the experts say and I have gone through my codes many times, not
complicated codes.

Rasjid

[Pallav Nawani]

Hi,

Fruit and Crafty both use simple version of futility pruning, check the code.
There is a way you can find out what is going wrong in your engine.

(a) At horizon node, when you find a move that fits the pruning criteria, set a flag.
(b) Then make the move and search it
(c) If the move does not fail low, then dump the fen, the move, and the values of futility criteria as well as final eval of the move.

This may help in figuring out what is happening.

Best regards,
Pallav

[Pallav Nawani]

Hi,

I just remembered:
When I first added delta pruning in qsearch to my engine it greatly decreased the strength of my engine. Later I found that my hashtable implementation had a bug. I fixed it and tried delta pruning again. This time it worked. So maybe check your hashtable implementation for a bug?

This is not exactly the same as pruning at Horizon nodes, but hashtable problems might affect your pruning. I suggest that you play a match between with hashtable and without hashtable version of your program to check whether hashtable is weakening the program. If so, you could have a bug there.

Pallav

[Chan Rasjid]

Thanks Pallav,

That Fruit and Crafty use simple futility prune is enough; I have the source
of Fruit but it is just beyond my ability to understand. I can only decipher TSCP and Gerbil which follow the simple model.

I just have to disable hashing to see what happens. it can be tough as my current hash don't do strange things w/o futility. Just have to check.

Rasjid

[Fabien Letouzey]

Fruit and Crafty both use simple version of futility pruning, check the code.

It's in the code but not activated by default (see UCI options).

Robert Allgeuer measured a small strength increase (but not enough confidence) after the release of 2.0

Fabien.

[Fabien Letouzey]

It's in the code but not activated by default (see UCI options).

I was talking about Fruit, of course.

Fabien.

[Chan Rasjid]

Thanks Fabien,

A small strength increase for a strong program, but maybe more for a weak starter. I found significant number of nodes pruned and if done before makemove at horizon, will leave much time for other things.

Pallav,

I still have problem. still trying.

1) all hash probe/store related things disabled- hash/pawnhash/rep3 that uses hashkeys
2) final positional eval() restricted to 3-6 pawns tested or no restrictions.
3) I have fail soft, don't know if it causes problem.
4) simple futility means ONLY exclude check/incheck moves. Seems excluding promotion don't help but I need to confirm.
5) I have a non-recuresive search. edited to do simple alphabeta
to avoid zero wnd problems if any.

I dont know how to trace bugs thru dump/fen which you mentioned. I
have a debug auto-play that triggers a ton of asserts and all's well.
Problem is when strange moves are made.

w/o futility it plays normal, losing normally.

with futility it makes strange moves, eg simple refusal to recapture, or mate in 10-12 moves which is highly abnormal with my fair eval().

I have gone through the futility codes and there are only few lines of simple codes. The final thing I will check again is if there are bugs when I return scores from search(), non-recursive which is basically more errror prone.

still trying.
Rasjid.

[milix]

Hi Chan,
When I was using futility pruning I had a flag (initialy wasfutile=false) and when I skiped a move I set wasfutile to true. Later, when I did a hashtable store, if the node wasfutile then I stored the score as a lower bound, not as an exact score. Also, in your implementation you must take care what to return if all moves in this node were futile.

[Chan Rasjid]

Hello Anastatio,

My futility is now basically working with all hash-related stuff disabled.
It did strange moves earlier as I did not properly record the first valid score/move when prunning is made before a valid move found.

I basically took care of all that you did. flag recording futility-triggered, etc...

As for "Later, when I did a hashtable store, if the node wasfutile then I stored the score as a lower bound, not as an exact score" -
downgrading "exact" to "lower" may be one way.
It may also be possible to retain "exact" if we "trust" prunning. It need to be tested.

I am now trying blanket futility at horizon only excluding moves that gives check. Even moves when in-check may still be pruned (seems ok)
if we know it is not a mate node, ie ceratinty of at least one valid moves.
The theoretical (?) restrictions may be only to exclude moves that gives check.

My program has heavy overheads between makemove() and eval(). Fuitlity means early fail-low for my program and hopefully may save a lot of time.

I will post again my findings if finally I get everything right.

Best Regards,
Rasjid