futile futility pruning attempt

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

futile futility pruning attempt

Post by flok » Tue Mar 07, 2017 12:58 pm

Hi,

Currently my fut. prun code looks like this:

Code: Select all

int search(...) {
    if (!isCheck && depthLeft == 1) {
        int score = eval();

        if &#40;score + eval_queen < alpha&#41;
            return score;
   &#125;

   for&#40;Move x &#58; moves&#41; &#123;
       etc
   &#125;
&#125;

2 questions:

* am I right to return score when pruning? or should it be alpha? it is a fail-soft application

* the wiki says that you should not do this pruning when either alpha or beta is near the mate score. what is near in this case?

Sven
Posts: 3819
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: futile futility pruning attempt

Post by Sven » Tue Mar 07, 2017 3:19 pm

flok wrote:Currently my fut. prun code looks like this:

Code: Select all

int search&#40;...) &#123;
    if (!isCheck && depthLeft == 1&#41; &#123;
        int score = eval&#40;);

        if &#40;score + eval_queen < alpha&#41;
            return score;
   &#125;

   for&#40;Move x &#58; moves&#41; &#123;
       etc
   &#125;
&#125;
If you do FP at the top of a node you need to check against beta, not alpha, e.g.:

Code: Select all

if &#40;score - eval_queen >= beta&#41;
    return score;
and it should also be "depthLeft == 0". FP prunes futile moves, and you do this either before making them (within the move loop => here you check against alpha) or after making them (here you check against beta since it is now the opponent's viewpoint).
flok wrote:2 questions:

* am I right to return score when pruning? or should it be alpha? it is a fail-soft application
I think there are different opinions about that. I would return the corrected score ("score + eval_queen" resp. "score - eval_queen") since the assumption is that the static eval (which is kind of an estimate) is probably not off by more than your futility margin (eval_queen). But SF 8, for instance, returns "score" at this point.
flok wrote:* the wiki says that you should not do this pruning when either alpha or beta is near the mate score. what is near in this case?
It means, if the score is a mate score and not a score resulting from static eval, for instance:

Code: Select all

if &#40;abs&#40;score&#41; >= MATE_SCORE - MAX_PLY&#41;
Furthermore, "eval_queen" is probably too high as a futility margin. The value of two or three pawns might be a slightly better margin for FP at depth 1.

flok

Re: futile futility pruning attempt

Post by flok » Tue Mar 07, 2017 8:09 pm

Hi!

Hmmm so I succeeded in doing it all the wrong way :-)

Strangely enough all (alpha - score, beta + score, queen versus 2 or 3 pawns) give around -20 elo.
Very strange. I'll look at it again tomorrow.

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

Re: futile futility pruning attempt

Post by Henk » Tue Mar 07, 2017 8:59 pm

I don't understand when depthLeft == 0 then it is in qsearch when not in check and then you start with a stand pad test with margin == 0 that is eval >= ub

Sven
Posts: 3819
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: futile futility pruning attempt

Post by Sven » Wed Mar 08, 2017 9:43 am

Henk wrote:I don't understand when depthLeft == 0 then it is in qsearch when not in check and then you start with a stand pad test with margin == 0 that is eval >= ub
Yes. But you need to call qsearch() to reach that stand-pat test. So applying futility pruning at the child node and only when depthLeft == 0 does not appear to save more than the recursive call to qsearch(). Many engines apply FP at the parent node so for depthLeft == 1 (same as depthLeft == 0 at the child node) they also save making the move.

In practice we often see the extended form where FP is applied for depthLeft <= N, e.g. N=6 (at child node) in SF8. There your argument is no longer relevant. SF8 even does FP at child node *and* at parent node, and I don't want to try explaining it since I did not check carefully how it works.

Sven
Posts: 3819
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: futile futility pruning attempt

Post by Sven » Wed Mar 08, 2017 9:51 am

flok wrote:Hi!

Hmmm so I succeeded in doing it all the wrong way :-)

Strangely enough all (alpha - score, beta + score, queen versus 2 or 3 pawns) give around -20 elo.
Very strange. I'll look at it again tomorrow.
If you get -20 Elo compared to the code you posted (which prunes strong moves that were made at depthLeft==2, not bad moves made at depthLeft==1 !) then you should check whether you did your changes correctly.

Another explanation might be that the code you posted is simply not futility pruning but a different kind of pruning that works for your engine so that removing it makes your engine weaker. You could check this by adding "correct" futility pruning without removing the code above.

Ferdy
Posts: 4043
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: futile futility pruning attempt

Post by Ferdy » Wed Mar 08, 2017 12:10 pm

flok wrote:Hi,

Currently my fut. prun code looks like this:

Code: Select all

int search&#40;...) &#123;
    if (!isCheck && depthLeft == 1&#41; &#123;
        int score = eval&#40;);

        if &#40;score + eval_queen < alpha&#41;
            return score;
   &#125;

   for&#40;Move x &#58; moves&#41; &#123;
       etc
   &#125;
&#125;

2 questions:

* am I right to return score when pruning? or should it be alpha? it is a fail-soft application

* the wiki says that you should not do this pruning when either alpha or beta is near the mate score. what is near in this case?
Try this if there is improvement.

Code: Select all

int search&#40;...) &#123;
    if (!isCheck && &#40;depthLeft == 1&#41; && &#40;beta-alpha == 1&#41; && alpha > MIN_EVAL_SCORE&#41; &#123;
        int score = eval&#40;);

        if &#40;score + eval_queen <= alpha&#41;
            return score;
   &#125;

   for&#40;Move x &#58; moves&#41; &#123;
       etc
   &#125;
&#125;

flok

Re: futile futility pruning attempt

Post by flok » Wed Mar 08, 2017 7:48 pm

Ferdy wrote:Try this if there is improvement.

Code: Select all

int search&#40;...) &#123;
    if (!isCheck && &#40;depthLeft == 1&#41; && &#40;beta-alpha == 1&#41; && alpha > MIN_EVAL_SCORE&#41; &#123;
        int score = eval&#40;);

        if &#40;score + eval_queen <= alpha&#41;
            return score;
   &#125;

   for&#40;Move x &#58; moves&#41; &#123;
       etc
   &#125;
&#125;
Shouldn't that be:

Code: Select all

if (!isCheck && &#40;depthLeft == 1&#41; && &#40;beta-alpha == 1&#41; && beta < MAX_EVAL_SCORE&#41;
&#123;
 if &#40;score - eval_pawn * 3 >= beta&#41;
etc
?

Sven
Posts: 3819
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: futile futility pruning attempt

Post by Sven » Wed Mar 08, 2017 8:01 pm

Ferdy wrote:Try this if there is improvement.

Code: Select all

int search&#40;...) &#123;
    if (!isCheck && &#40;depthLeft == 1&#41; && &#40;beta-alpha == 1&#41; && alpha > MIN_EVAL_SCORE&#41; &#123;
        int score = eval&#40;);

        if &#40;score + eval_queen <= alpha&#41;
            return score;
   &#125;

   for&#40;Move x &#58; moves&#41; &#123;
       etc
   &#125;
&#125;
Would you call that "futility pruning", even though it prunes strong moves instead of futile moves (the opponent's previous move raised the static eval far above his beta)?

Ferdy
Posts: 4043
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: futile futility pruning attempt

Post by Ferdy » Wed Mar 08, 2017 11:42 pm

flok wrote:
Ferdy wrote:Try this if there is improvement.

Code: Select all

int search&#40;...) &#123;
    if (!isCheck && &#40;depthLeft == 1&#41; && &#40;beta-alpha == 1&#41; && alpha > MIN_EVAL_SCORE&#41; &#123;
        int score = eval&#40;);

        if &#40;score + eval_queen <= alpha&#41;
            return score;
   &#125;

   for&#40;Move x &#58; moves&#41; &#123;
       etc
   &#125;
&#125;
Shouldn't that be:

Code: Select all

if (!isCheck && &#40;depthLeft == 1&#41; && &#40;beta-alpha == 1&#41; && beta < MAX_EVAL_SCORE&#41;
&#123;
 if &#40;score - eval_pawn * 3 >= beta&#41;
etc
?
That is possible but that is not futility pruning.

Post Reply