How much elo from futility?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Alessandro Scotti

How much elo from futility?

Post by Alessandro Scotti » Wed Sep 05, 2007 2:47 pm

I have just started testing futility with Hamsters and was wondering what benefits one could expect. It seems strong engines like Toga or Glaurung are using futility and last time I did try it in Kiwi it seemed to help but how much when null move and LMR are in place?
A quick test with Hamsters (more or less standard futility with margins 100,325) started well but ended disappointly in the last Noomen positions, so that eventually the final score was 52.4% vs. the non-futility 51.7% (but it was above 54% after 600 games, lost really a lot in the last 100 games).
I will try a few settings in the next days/weeks and will post some results, hopefully positive. What is your experience?

Uri Blass
Posts: 8335
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: How much elo from futility?

Post by Uri Blass » Wed Sep 05, 2007 3:11 pm

I do not know what is the standard way of using futiliry

I use my original ideas in movei abour pruning and reductions in the last plies.

I do not know how much I gain from pruning in the last plies.

If you give me a pgn of 5000 games I can run the noomen match at 1000 nodes per move and get result of a match of 10,000 games in few hours.

Uri

PK-4

Re: How much elo from futility?

Post by PK-4 » Wed Sep 05, 2007 3:55 pm

Alessandro Scotti wrote:eventually the final score was 52.4% vs. the non-futility 51.7%
It seems only blunders can be corrected in a short time. Running 600+ games takes lots of time even in blitz mode (or was it 40moves/40min ?). If one can not decide about an established technique like futility pruning in that much time then I shudder to think of the effort needed to find the merit of small changes - and I make many such changes. I too would like to get the views of experienced programmers about testing for small improvements.

Regards.

P.K.Mukhopadhyay

MartinBryant

Re: How much elo from futility?

Post by MartinBryant » Wed Sep 05, 2007 5:55 pm

This thread recently
http://64.68.157.89/forum/viewtopic.php ... 80&t=15814
included some stuff about testing regimes.

Hope that's some help.

MartinBryant

Re: How much elo from futility?

Post by MartinBryant » Wed Sep 05, 2007 6:01 pm

I added futility in the most recent version of Colossus.
In a 1000 game match it scored a +15 ELO improvement.
Not quite statistically significant but getting there.

I think the improvement any engine would get would be dependant on various other techniques it has/hasn't got already.

Alessandro Scotti

Re: How much elo from futility?

Post by Alessandro Scotti » Wed Sep 05, 2007 8:30 pm

Hi Martin,
you tried the "classical" futility at d=1 and d=2 correct? I'm still evaluating that but maybe another handful of elo could be obtained with delta pruning and futility at d=3, at least I remember reading this is one of the reasons Toga is stronger than Fruit (which had most of this stuff built in but disabled).

ed

Re: How much elo from futility?

Post by ed » Wed Sep 05, 2007 9:00 pm

I use the following margins:

d=0 -> 0.50
d=1 -> 3.00 (5.00 in endgame)
d=2 -> 5.00

Excluded moves are:

- King in check
- Giving a check
- Captures
- pawns that move to the 7th (2th) row.

Furthermore (and this is crucial) you must have some kind of solution that deals with big evaluation scores (such as a 8.00 bonus for a pawn outside of the quadrant in a pawn-ending, or huge evaluation scores for passers and king-safety) that tend to exceed the margin.

I remember it gave me a 25% speed improvement with hardly any holes the time I implemented futility pruning. Not bad....

Ed

Alessandro Scotti wrote:I have just started testing futility with Hamsters and was wondering what benefits one could expect. It seems strong engines like Toga or Glaurung are using futility and last time I did try it in Kiwi it seemed to help but how much when null move and LMR are in place?
A quick test with Hamsters (more or less standard futility with margins 100,325) started well but ended disappointly in the last Noomen positions, so that eventually the final score was 52.4% vs. the non-futility 51.7% (but it was above 54% after 600 games, lost really a lot in the last 100 games).
I will try a few settings in the next days/weeks and will post some results, hopefully positive. What is your experience?

User avatar
hgm
Posts: 23014
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How much elo from futility?

Post by hgm » Thu Sep 06, 2007 9:53 am

Why would you use different margins at d=0 and d=1 (or d=2 and d=3)? The situation is exactly the same: you are only one ply (three plies) removed from the opponent's stand-pat.

Uri Blass
Posts: 8335
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: How much elo from futility?

Post by Uri Blass » Thu Sep 06, 2007 11:21 am

hgm wrote:Why would you use different margins at d=0 and d=1 (or d=2 and d=3)? The situation is exactly the same: you are only one ply (three plies) removed from the opponent's stand-pat.
I do not understand why the situation is the same.
basically remaining depth=0 and remaining depth=1 are different situations.

I also do not understand what is done exactly.

d=0 is remaining depth=0
What do you do in that case?

Do you do something like the following:
if lazy evaluation>(beta+0.50) and the last move was no checking move return beta;


d=1 means remaining depth=1
It is possible that the side to move has no good move and every move that he does lose(for example if there is a fork against 2 pieces)

It seems more dangerous to prune in this case because you may miss tactics relative to the case of not pruning when in case that the remaining depth is 0 even if there is a fork against 2 pieces you are not going to discover it by qsearch so lazy evaluation can really save time with little risk(assuming that the probability that the real evaluation is significantly different is small)

Uri

User avatar
hgm
Posts: 23014
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How much elo from futility?

Post by hgm » Thu Sep 06, 2007 11:34 am

Uri Blass wrote:Do you do something like the following:
if lazy evaluation>(beta+0.50) and the last move was no checking move return beta;
It depends at which level you are talking. Usually you consider the score at the level where you generate the move, but decide not to search it. There the condition would be

if( CurrentEval + PieceVal[Victim] + 0.5 < Alpha) Score = Alpha;

which is the same thing as ignoring the move.

This is similar to what you propose one level deeper (but saving you the call and return). The difference is that LazyEval is usually something that is done from scratch, while the evaluation estimate used in futility pruning is based on a full evaluation plus an estimate of the differential update (which can be much more accurate for moves that cannot have a large positional impact).

At d=0 you only consider captures, but with futility pruning you ignore captures that cannot possibly raise the evaluation score above Alpha. Because you know the move will at most return that evaluation score, as the opponent can always stand pat in the reply.

That is exactly the same at d=1. The only difference is that at d=1 you also apply it to non-captures. But I see no reason why captures could not have positional gains at least as big as non-captures.

Post Reply