Page 2 of 2
Re: Futile attempts at futility pruning
Posted: Mon Mar 28, 2016 1:53 pm
by cdani
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.
Re: Futile attempts at futility pruning
Posted: Mon Mar 28, 2016 2:07 pm
by Henk
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.
Re: Futile attempts at futility pruning
Posted: Mon Mar 28, 2016 5:17 pm
by mar
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[depth] - 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.
Re: Futile attempts at futility pruning
Posted: Mon Mar 28, 2016 11:15 pm
by cdani
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[depth] - 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
Re: Futile attempts at futility pruning
Posted: Wed Mar 30, 2016 7:34 pm
by flok
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).
Re: Futile attempts at futility pruning
Posted: Wed Mar 30, 2016 9:23 pm
by bob
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(100%) nodes=56881516(56.9M) fh1=93% pred=0 nps=5.6M
chk=288.7K qchk=421.0K fp=27.0M mcp=6.4M 50move=1
LMReductions: 1/1.3M 2/945.4K 3/956.3K 4/632.6K 5/97.8K 6/4.7K
7/29
null-move (R): 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...