Futile attempts at futility pruning

[cdani]

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]

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]

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.

[cdani]

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

[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).

[bob]

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...