Futile attempts at futility pruning

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.
User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Futile attempts at futility pruning

Post by cdani » Mon Mar 28, 2016 11:53 am

Henk wrote:Is there any proof that futility pruning gives an ELO gain. Or does it only give an ELO profit if an engine has a slow evaluation with an inferior LMR implementation.
I don't remember well, but was like 50-100 elo for Andscacs.

Henk
Posts: 5799
Joined: Mon May 27, 2013 8:31 am

Re: Futile attempts at futility pruning

Post by Henk » Mon Mar 28, 2016 12:07 pm

cdani wrote:
Henk wrote:Is there any proof that futility pruning gives an ELO gain. Or does it only give an ELO profit if an engine has a slow evaluation with an inferior LMR implementation.
I don't remember well, but was like 50-100 elo for Andscacs.
Skipper has no evaluation or it almost only counts material so I doubt if in that case futility pruning gives it more points when it plays against engines that make other mistakes. Level 1 is usually skipped by LMR jumping in QSearch. So what remains is level 2 but then you get a margin that does prune less and also chances of more error. So I gave up.

mar
Posts: 1992
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Futile attempts at futility pruning

Post by mar » Mon Mar 28, 2016 3:17 pm

Henk wrote:Is there any proof that futility pruning gives an ELO gain. Or does it only give an ELO profit if an engine has a slow evaluation with an inferior LMR implementation.
Unfortunately I have no data for the specific commit (but my futility margins are untuned).
I found that delta pruning in qs gave about 9 elo.
My version of fpruning does something else (I thought this was late move pruning but it seems I was wrong).
So let's call it cheapo fpruning mixed with late move counter.
What I do is shift the margin down by late move count * constant, like this:

Code: Select all

eval + margin&#91;depth&#93; - late_move_count*late_margin < alpha => prune move
This according to the commit gave 28 elo (my late_margin was 20cp).
Note that I only count quiet moves in late_move_count.

If you already have alpha-beta and qsearch, there are only 2 general ideas that fall in the big elo gain category: nullmove and LMR
Everything else (note: from my experience) is about accumulating enough small changes to make a cummulatively large improvement.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Futile attempts at futility pruning

Post by cdani » Mon Mar 28, 2016 9:15 pm

mar wrote:
Henk wrote:Is there any proof that futility pruning gives an ELO gain. Or does it only give an ELO profit if an engine has a slow evaluation with an inferior LMR implementation.
Unfortunately I have no data for the specific commit (but my futility margins are untuned).
I found that delta pruning in qs gave about 9 elo.
My version of fpruning does something else (I thought this was late move pruning but it seems I was wrong).
So let's call it cheapo fpruning mixed with late move counter.
What I do is shift the margin down by late move count * constant, like this:

Code: Select all

eval + margin&#91;depth&#93; - late_move_count*late_margin < alpha => prune move
This according to the commit gave 28 elo (my late_margin was 20cp).
Note that I only count quiet moves in late_move_count.

If you already have alpha-beta and qsearch, there are only 2 general ideas that fall in the big elo gain category: nullmove and LMR
Everything else (note: from my experience) is about accumulating enough small changes to make a cummulatively large improvement.
I just tried with Andscacs and you have reason. The win is much in the line of what you say. I really reminded very bad :oops:

flok

Re: Futile attempts at futility pruning

Post by flok » Wed Mar 30, 2016 5:34 pm

What is a usual hit-ratio for futility pruning? Meaning the amount of moves it can ignore. My program has a ratio of 5.1% for depth 9 (that is 127088 non-qs nodes).

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

Re: Futile attempts at futility pruning

Post by bob » Wed Mar 30, 2016 7:23 pm

flok wrote:What is a usual hit-ratio for futility pruning? Meaning the amount of moves it can ignore. My program has a ratio of 5.1% for depth 9 (that is 127088 non-qs nodes).
Here are some numbers from Crafty. 15 second search of a middle game position...

Code: Select all

                                     14. Kf3 Rc1
        time=10.09&#40;100%)  nodes=56881516&#40;56.9M&#41;  fh1=93%  pred=0  nps=5.6M
        chk=288.7K  qchk=421.0K  fp=27.0M  mcp=6.4M  50move=1
        LMReductions&#58;  1/1.3M  2/945.4K  3/956.3K  4/632.6K  5/97.8K  6/4.7K
              7/29
        null-move &#40;R&#41;&#58;  3/2.3M  4/331.2K  5/21.8K  6/1.2K  7/12
56.9 M nodes searched, another 27.0M moves were futility pruned (these are moves that are tossed out rather than searched and do NOT attempt to count the size of the sub-tree this eliminates, just the move itself).

LMP (or move count pruning) pruned another 6.4M nodes.

LMR reductions were between 1 and 7 in this example, and null-move R value varied between 3 and 7...

Post Reply