Futility pruning question

[Zlaire]

I've probably tried about 20 different setups with futility pruning, all in vain. This is the latest attempt I made:

Code: Select all

// Start generating and searching moves
while&#40;generationState < GEN_END&#41;
&#123;
   switch&#40;generationState&#41;&#123;
   case GEN_HASH&#58; // Get the hash move
   case GEN_CAPS&#58; // Generate captures
   case GEN_KILLERS&#58; // Get killer moves
   case GEN_NONCAPS&#58; // Generate non captures
   case GEN_LOSINGCAPS&#58; // Get losing captures
   &#125;
	
   boolean fprune = false;
   if&#40;generationState == GEN_NONCAPS && depth <= 2 && !isInCheck&#41;&#123;
      eval = evaluate&#40;);

      if&#40;depth == 1 && &#40;eval+200&#41; <= alpha&#41;&#123;			
         fprune = true;
      &#125;
      else if&#40;depth == 2 && &#40;eval+500&#41; <= alpha&#41;&#123;
         fprune = true;
      &#125;
   &#125;

   while&#40;stillMoves&#41;&#123;
      board.makeMove&#40;);
			
      if&#40;fprune && !isInCheck&#40;board&#41;)&#123;
         unmakeMove&#40;);
         continue;					
      &#125;
      // Continue with search as usual
   &#125;	
   generationState++;
&#125;

So basically, the side to move is not in check and not about to make a checking move or capture, and even with 200 points extra it can't reach alpha. So the move is pruned here.

This may be theoretically sound or not, but at the very least I thought there whould be fewer nodes searched with this than without. However depending on the position this results in either a small decrease in visited nodes or a huge increase.

In self-play this results in about 70-80% losses as well.

I'm just stumped, what am I doing wrong here?

[Alessandro Scotti]

Apparently, with this setup you risk throwing away all legal moves in a node if they happen to satisfy the futility criteria.

[Edsel Apostol]

It seems correct but there is a bug. Alessandro is right about his statement. Try adding this:

Code: Select all

if&#40;generationState == GEN_NONCAPS && depth <= 2 && !isInCheck && !firstMove&#41;&#123; 

Edsel

[Tony]

I've probably tried about 20 different setups with futility pruning, all in vain. This is the latest attempt I made:

Code: Select all

// Start generating and searching moves
while&#40;generationState < GEN_END&#41;
&#123;
   switch&#40;generationState&#41;&#123;
   case GEN_HASH&#58; // Get the hash move
   case GEN_CAPS&#58; // Generate captures
   case GEN_KILLERS&#58; // Get killer moves
   case GEN_NONCAPS&#58; // Generate non captures
   case GEN_LOSINGCAPS&#58; // Get losing captures
   &#125;
	
   boolean fprune = false;
   if&#40;generationState == GEN_NONCAPS && depth <= 2 && !isInCheck&#41;&#123;
      eval = evaluate&#40;);

      if&#40;depth == 1 && &#40;eval+200&#41; <= alpha&#41;&#123;			
         fprune = true;
      &#125;
      else if&#40;depth == 2 && &#40;eval+500&#41; <= alpha&#41;&#123;
         fprune = true;
      &#125;
   &#125;

   while&#40;stillMoves&#41;&#123;
      board.makeMove&#40;);
			
      if&#40;fprune && !isInCheck&#40;board&#41;)&#123;
         unmakeMove&#40;);
         continue;					
      &#125;
      // Continue with search as usual
   &#125;	
   generationState++;
&#125;

So basically, the side to move is not in check and not about to make a checking move or capture, and even with 200 points extra it can't reach alpha. So the move is pruned here.

This may be theoretically sound or not, but at the very least I thought there whould be fewer nodes searched with this than without. However depending on the position this results in either a small decrease in visited nodes or a huge increase.

In self-play this results in about 70-80% losses as well.

I'm just stumped, what am I doing wrong here?

if(fprune && !isInCheck(board)){
if (eval>bestScore) bestScore=eval;
unmakeMove();
continue;
}

Tony

[Vempele]

if(fprune && !isInCheck(board)){
if (eval>bestScore) bestScore=eval;
unmakeMove();
continue;
}

Tony

You also need to make sure that the position isn't stored in the transposition table if there's no 'best' move.

[Tony]

if(fprune && !isInCheck(board)){
if (eval>bestScore) bestScore=eval;
unmakeMove();
continue;
}

Tony

You also need to make sure that the position isn't stored in the transposition table if there's no 'best' move.

Why ?

Tony

[hgm]

A few comments:

1) Why Make and UnMake the move if it was futile? It would be more logical to simply write an

Code: Select all

if(!fprune || isInCheck(board)) { ... }

around the entire Make(), Search(), UnMake() stuff.

2) If one non-capture is futile, all will be futile, as the condition is not dependent on the move. So why even generate the non-captures? You could skip them entirely by putting in the switch statement:

Code: Select all

case GEN_NONCAPS:
    if(fprune && !isInCheck(board))
    {    // Generate non captures
    }

3) You always risk the case that all moves are futile. At d=1 this might leave your BestScore at -INF if you do soft fail. With hard fail you would return alpha, and that would be a true upper limit as long as the moves were indeed futile. But -INF is not. Worse yet, depending on how your legal-move and mate logic works, it might start to confuse it for positions with zero legal moves, and award a stalemate score > alpha to them. In any case, if -INF would make its way to the hash, then later searches that visit this position whith alpha much lower (e.g. < eval, so that none of the non-captures is futile anymore) would still think the score is below alpha.

I prevent this by giving futility-pruned moves a 'default' score equal to the futility limit (i.e. eval+200 or eval+500 in your case). These scores follow the usual if(Score>Alpha) path, and can be safely used as upper limits in a soft-fail scheme.

4) Why only do it for non-captures? For captures the condition would be eval + PieceVal[Victim] + 200 < alpha, that you would have to judge on a move-by-move basis, but otherwise the logic is completely the same.

5) If you would happen to know the highest piece of the opponent, and eval + PieceVal[HighestPiece] + 200 < alpha, you know in advance that all captures will be futile too, and you can skip generating these as well ('General futility').

[Zlaire]

1) The reason I make/unmake the move is because that is how I determine if the move is a check.

The first !isInCheck is for the position before the move, and the second after the move is made.

2) Can we be sure that a non-capture is futile even if it is a checking move?

3) This was the main problem, as pointed out by just about everyone here. If all moves are futile (which happens alot more than I thought obviously) -INF would be passed along.

And on top of that my mate logic would think no legal moves were available...

I think I got it fixed now, the version with futility pruning turned on just won 5 straight games while I was typing this. On to implementing what you mention in point 4 and 5.

[hgm]

OK, I misunderstood, and thought that isInCheck was testing the in-check status before the move. Testing if a move delivers check without actually making it should not be so difficult, btw.

If checks can be considered futile, depends on how you treat a position where the STM is in check. If such a player is allowed to stand pat, normal futility considerations apply. If you extend for the evasion, or do anything else that is special and might lead to a lower score than the current eval, checks are non-futile.

Probably you do the latter.

For the future, even in the face of this you could still do all the tricks described above if you would have a routine Generate_Checks, that you would run in stead of Generate_Captures when the futility condition is met. With bitboard such a routine is probably easier to make than for array representations. This might become more efficient if you somehow combine it with King-safety information on the Pawn shield: if the Pawn shield is intact, the only non-captures that can deliver check are R or Q moves to last rank. Generating these moves is far less work than generating all moves with all pieces, and then checking them one-by-one to see if they deliver check. (For R & Q that are already on last rank, you would have to test if they can deliver a discovered check.)

[mjlef]

You should not futility prune if in check, the move gives check, or the move is likely to effect a score change big enough to raise the score above alpha--like making a passed pawn. If your margin of 200 covers this, then it should be good. It certainly does not cover things well enough in NOW. I have king safety and passed pawn evals, endgame rules for pawn races and perfect KPK logic all with huge scores.

Futility pruning is very useful in the capturesearch, but with your rules you cannot use it and are forced to do an expensive full eval before knowing if the score is under alpha. Simple moves like PxP can both expose the opponent king, hurting its king safety, as well as cover your king, and make it a passed pawn. Most dangerous score changing moves are captures, but there are some non-captures jut as bad. I have a pretty long list of things I test for, in the hopes of using smaller futlity margins (more pruning) without tossing out the baby with the bath water. Here is what I remember off the top of my head:

First, figure a maximum scorechange your eval can do in one move. If the eval<(alpha-scorechange), you can safely prune. You might want a different scorechange value for a capture or non-capture move.

Do not prune:
Non-capture moves:
P to 7th (dangerous passed pawn, big score change)
Rook or Queen to 7th (typically a big bonus is given like 1/2 a pawn, and these moves usually change king safety a lot)
King moves if the kings safety against it is high..he could be moving out of danger.

Captures/Promotions:
Do not prune promotions...too likely to change a lot of eval terms.
Capture of queen (bit materail change..could change ratios toward endgame, increasing passed pawn values, making king safety less important)
Capture of bishop if it loses the bishop pair.
pawn captures close to opponent king--likely to effect king safety by attacking it or exposing it
capturing a pawn on the 2nd rank (opponent's passed pawn). Mayeb even 3rd rank.
Capture of last pawn
capture of last piece

I have other conditions, but my measurmeents show even with a binch of rules, the rules only strop about 6% of moves considered from being pruned, although it climbs in the endgame.

I would love to share test kinds of rules with anyone if we want to start a discussion about it. A close to perfect set could let us use very small margins and get a lot more pruning. I would like a ncie, magical fast function which knows the amount the eval is under alpha, and tests the conditions in the order of largest likely score change. It could terminate the test once it either shows some danger, or determines the sum of the likely remaining conditions score change will not be enough.

Mark