futile futility pruning attempt

[Ferdy]

Try this if there is improvement.

Code: Select all

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

        if (score + eval_queen <= alpha)
            return score;
   }

   for(Move x : moves) {
       etc
   }
}

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)?

There are 3 cases of futility pruning that I know of.
1. Position futility pruning
2. Move futility pruning
3. Game futility pruning

The example above is of case 1.

Case 2 is something like,

Code: Select all

while (m = getMove()) {
    if futileMove(m)
        continue
}

Case 3 is when your position at the root is very bad and you just resign the game. Not found in uci but winboard engines.

I view futility pruning from the player who is the side to move. He can ask the questions, is this position hopeless? Or am I in a hopeless position? Or is the move I am trying to make is hopeless? Or am I already lost?

[Karlo Bala]

Hi,

Currently my fut. prun code looks like this:

Code: Select all

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

        if (score + eval_queen < alpha)
            return score;
   }

   for(Move x : moves) {
       etc
   }
}

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?

I suggest that you first try the "Move Count Based Pruning". If it works, then you can make it more aggressive using a futile margin.

The code could be like this:

Code: Select all

for (moves)
{
  if (!in_check && !pv && alpha > -WIN && !check && !capture && !push7rank && movenum > 4 + depth*depth) // 4*depth or 1<<depth, whatever you like
     continue; // prune

  makemove()
  search(...)
  unmakemove()
  ...

}

[Sven]

Try this if there is improvement.

Code: Select all

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

        if (score + eval_queen <= alpha)
            return score;
   }

   for(Move x : moves) {
       etc
   }
}

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)?

There are 3 cases of futility pruning that I know of.
1. Position futility pruning
2. Move futility pruning
3. Game futility pruning

The example above is of case 1.

Case 2 is something like,

Code: Select all

while (m = getMove()) {
    if futileMove(m)
        continue
}

Case 3 is when your position at the root is very bad and you just resign the game. Not found in uci but winboard engines.

I view futility pruning from the player who is the side to move. He can ask the questions, is this position hopeless? Or am I in a hopeless position? Or is the move I am trying to make is hopeless? Or am I already lost?

Case 3 should be irrelevant in this thread. Case 1 is interesting but as far as I know we almost always think of case 2 if we talk about "futility pruning" in chess engine programming. I also think that case 1 is a very risky kind of pruning, and I guess it is not what the OP intended to do.

[Ferdy]

Try this if there is improvement.

Code: Select all

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

        if (score + eval_queen <= alpha)
            return score;
   }

   for(Move x : moves) {
       etc
   }
}

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)?

There are 3 cases of futility pruning that I know of.
1. Position futility pruning
2. Move futility pruning
3. Game futility pruning

The example above is of case 1.

Case 2 is something like,

Code: Select all

while (m = getMove()) {
    if futileMove(m)
        continue
}

Case 3 is when your position at the root is very bad and you just resign the game. Not found in uci but winboard engines.

I view futility pruning from the player who is the side to move. He can ask the questions, is this position hopeless? Or am I in a hopeless position? Or is the move I am trying to make is hopeless? Or am I already lost?

Case 3 should be irrelevant in this thread.

It is not irrelevant, it is there to better understand the concept of futility.

Case 1 is interesting but as far as I know we almost always think of case 2 if we talk about "futility pruning" in chess engine programming. I also think that case 1 is a very risky kind of pruning, and I guess it is not what the OP intended to do.

The advantage of case 1 is that you can have the full evaluation of the position which can be useful in other areas too, unlike case 2 where it could be expensive to call the full eval after every move to determine if move is futile or not although there are other means to achieve effective pruning. The risks in case 1 can be minimized by adding other conditions and better tuned margins.

[Sven]

Case 1 is interesting but as far as I know we almost always think of case 2 if we talk about "futility pruning" in chess engine programming. I also think that case 1 is a very risky kind of pruning, and I guess it is not what the OP intended to do.

The advantage of case 1 is that you can have the full evaluation of the position which can be useful in other areas too, unlike case 2 where it could be expensive to call the full eval after every move to determine if move is futile or not although there are other means to achieve effective pruning. The risks in case 1 can be minimized by adding other conditions and better tuned margins.

Have you ever seen "case 1" (you call it "position futility pruning") being used in any serious engine so far? Even SF does not use it as far as I know (and SF uses almost all search techniques that are considered valid today).

"Case 2" can be implemented in two ways (as I pointed out several times in this thread): either at the parent node (within the move loop) or at the child node (at the top of search()). When applying it at the parent node you do not need to call eval() after each move, instead you can use the saved score from the current node (saved above the move loop for that purpose) and calculate the expected gain for the current move that might become pruned.

Comparing advantages of "case 1" and "case 2" in terms of things like less calls of eval() is a moot point in my opinion since both kinds of pruning differ a lot from each other. Note that "case 1" pruning does not even take into account whether the moving side which appears to be "lost" (e.g. a queen below alpha) can simply recapture the queen, or can give check (which could be checkmate or a forced mate in 2 or win the queen or ...). It turns the current node into a leaf without considering available moves. I don't know how this risk could be reduced effectively. Margin = 2*queen_value ?

[tttony]

Hi,

Currently my fut. prun code looks like this:

Code: Select all

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

        if (score + eval_queen < alpha)
            return score;
   }

   for(Move x : moves) {
       etc
   }
}

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?

I tested this simillar, it's reversed or called in SF static null move pruning http://www.talkchess.com/forum/viewtopi ... at&start=0 in my old engine and it worked fine but I returned the margin(eval - piece_value) score instead of beta

[Ferdy]

Case 1 is interesting but as far as I know we almost always think of case 2 if we talk about "futility pruning" in chess engine programming. I also think that case 1 is a very risky kind of pruning, and I guess it is not what the OP intended to do.

The advantage of case 1 is that you can have the full evaluation of the position which can be useful in other areas too, unlike case 2 where it could be expensive to call the full eval after every move to determine if move is futile or not although there are other means to achieve effective pruning. The risks in case 1 can be minimized by adding other conditions and better tuned margins.

Have you ever seen "case 1" (you call it "position futility pruning") being used in any serious engine so far? Even SF does not use it as far as I know (and SF uses almost all search techniques that are considered valid today).

It does not matter if the engine using it is serious or not the point is the method of pruning exists. You seemed to imply that techniques not in Stockfish is invalid . What happened to you?

Fortunately Stockfish seemed to have it and they call it razoring with some refinements that is using qsearch value.

Code: Select all

// Step 6. Razoring (skipped when in check)
    if (   !PvNode
        &&  depth < 4 * ONE_PLY
        &&  eval + razor_margin[depth] <= alpha
        &&  ttMove == MOVE_NONE)
    {
        if (   depth <= ONE_PLY
            && eval + razor_margin[3 * ONE_PLY] <= alpha)
            return qsearch<NonPV, false>(pos, ss, alpha, beta, DEPTH_ZERO);

        Value ralpha = alpha - razor_margin[depth];
        Value v = qsearch<NonPV, false>(pos, ss, ralpha, ralpha+1, DEPTH_ZERO);
        if (v <= ralpha)
            return v;
    }

[Sven]

Case 1 is interesting but as far as I know we almost always think of case 2 if we talk about "futility pruning" in chess engine programming. I also think that case 1 is a very risky kind of pruning, and I guess it is not what the OP intended to do.

The advantage of case 1 is that you can have the full evaluation of the position which can be useful in other areas too, unlike case 2 where it could be expensive to call the full eval after every move to determine if move is futile or not although there are other means to achieve effective pruning. The risks in case 1 can be minimized by adding other conditions and better tuned margins.

Have you ever seen "case 1" (you call it "position futility pruning") being used in any serious engine so far? Even SF does not use it as far as I know (and SF uses almost all search techniques that are considered valid today).

It does not matter if the engine using it is serious or not the point is the method of pruning exists. You seemed to imply that techniques not in Stockfish is invalid . What happened to you?

Fortunately Stockfish seemed to have it and they call it razoring with some refinements that is using qsearch value.

Nothing happened to me. Of course I did not want to imply that techniques that are not in Stockfish are invalid. But despite your opinion as well as that of Tony (see his recent reply in this thread), I strongly disagree that the pruning method described in this thread has any serious value. I'm pretty sure it neither was nor is present in Stockfish, Komodo, or any other strong engine, and it is not "reverse futility pruning", "static null move pruning" or anything similar. Both look very different, they do not prune with a condition like "eval + margin <= alpha" at the top of a node (but with "eval - margin >= beta" which is quite the opposite).

It is also not "razoring", even though it may look "close" to it. The big difference to "razoring" is that the latter is not applied at PV nodes or nodes which have a TT move (both conditions are not present in the OP code snippet) and - most important - that "razoring" only prunes if qsearch() confirms the fail-low somehow. I would not call the addition of the two missing conditions and the qsearch() confirmation step a "refinement", it turns the whole thing into something completely different in my view. Not using a confirmation like qsearch() to avoid missing an own "strong" move that would avoid to fail low is obviously hilarious, so why should someone consider it serious?

But we don't need to continue this battle, maybe in fact we are not too far away from each other It seems obvious to me that the OP wanted to implement futility pruning but failed to do it right. Now there are various ways for him to improve his code, and in the end he might get both futility pruning *and* razoring to work