futility pruning

[flok]

Hi,

After tons of games played I think I got LMR now stable.

Next step: futility pruning.
First step is reading http://chessprogramming.wikispaces.com/Futility+Pruning. As we in the Netherlands say: I cannot make cheese of it.

Futility Pruning in its pure form is implemented at the frontier nodes (depth == 1). It discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move. This is calculated by adding a futility margin (representing the largest conceivable positional gain) to the evaluation of the current position.

So in the top of my search() I call score = evalute() and check if score + some_value < alpha.

If this does not exceed alpha then the futility pruning is triggered (which usually means setting a flag like f_prune = 1).

Ok now what? I set a flag, but what should I do then? Return alpha?

For tactical stability, even in such a node we ought to search the following moves:
captures (either all or less typically only those that are capable of raising the score above alpha + margin)
moves that give check

... or should I then only play capture moves and check-giving-moves and if that gives to play return alpha?


Next question: determing if a move gives check. I think that is a makeMove(), then generate a list of moves, validate which ones are correct and then see if the opponent is in check state. This feels expensive? Or are here smarter ways of finding if a move gives check?



regards

[elcabesa]

more or less the idea is this in the pure form

while( getNextMove)
{
// futility pruning
if(notPVNODE && depth ==1 && moveisnotCapture && move is not ttmove)
if eval + margin < beta
continue; // bypass do move , -search and undo move because I bet it will not produce a beta cutoff
// end futility pruning
do the move
res = -search
undo the move
check res>alpha & beta
}

lot of the conditions I added could be debated

[zd3nik]

I think you will find many differing opinions on this subject.

basically the idea, I think, is if you are at depth == 1 and static eval plus some margin is less than alpha treat the node like a quiescence search node: only search captures and checks.

That's basically what the chessprogramming wiki says too.

Where it gets sticky is, whether you should do this when the side to move is in check, to which I say resoundingly: "no". Queue h.g.m.

As for determining which moves give check, that depends on your move generator. If your move generator isn't capable of generating moves based on whether they give check or not, then you'll have to execute every move to determine whether they produce check, which isn't really that bad. I don't get why you think you also need to generate response moves too, but maybe I am misunderstanding what you said.

STC

[elcabesa]

So in the top of my search() I call score = evalute() and check if score + some_value < alpha.

it's usually called inside the move loop, but you can do it at the start of the search, usually you do the things only when and if you need them. because lot of node are pruned or give a beta cutoff and you don't need to calculate all the stuff you don't need for those nodes.

Ok now what? I set a flag, but what should I do then? Return alpha?

you simply don't check if the move could cause a beta cutoff because you bet that it's futile to try the move

For tactical stability, even in such a node we ought to search the following moves:
captures (either all or less typically only those that are capable of raising the score above alpha + margin)
moves that give check

... or should I then only play capture moves and check-giving-moves and if that gives to play return alpha?

you need to try some moves, I don't think it's very good to discard all the moves, so you usually try the move from the hash table, the check, and capture and promotions.
Futility is for quiet move, if at depth 1 my evbal is well below beta and the capture haven't produced a beta cutoff it's very unlikely that a quiet move will raise the eval above beta

Next question: determing if a move gives check. I think that is a makeMove(), then generate a list of moves, validate which ones are correct and then see if the opponent is in check state. This feels expensive? Or are here smarter ways of finding if a move gives check?

advanced programs known, before making the move, if a move will give check because the moved piece give check or because it causes a discover check

[flok]

I think you will find many differing opinions on this subject.

basically the idea, I think, is if you are at depth == 1 and static eval plus some margin is less than alpha treat the node like a quiescence search node: only search captures and checks.

That's basically what the chessprogramming wiki says too.

Where it gets sticky is, whether you should do this when the side to move is in check, to which I say resoundingly: "no". Queue h.g.m.

Ok, understood. Not as complicated as I thought!

As for determining which moves give check, that depends on your move generator. If your move generator isn't capable of generating moves based on whether they give check or not, then you'll have to execute every move to determine whether they produce check, which isn't really that bad. I don't get why you think you also need to generate response moves too, but maybe I am misunderstanding what you said.

Hmmm that may very well be an inefficiency of my program. I always calculate both move lists (and then verify the color-on-move).

[flok]

I think you will find many differing opinions on this subject.

basically the idea, I think, is if you are at depth == 1 and static eval plus some margin is less than alpha treat the node like a quiescence search node: only search captures and checks.

What about this margin.
I tried 1000 and 350 it both hardly gives any gain.

Code: Select all

constexpr int ChessPiece::evalVal[] = { 100, 325, 325, 500, 975, 10000, 0, 0 };

(pawn, knight, bishop, rook, queen, king)

Then the evaluation consists of:
- position value; rates a position on the board of a piece. those values are in range of -50...50
- total value of all objects
- -15 * number of isolated pawns
- -15 * number of double pawns
- +3 * mobility (so max 217 * 3)
- +15 * passed pawns

[zd3nik]

What about this margin.
I tried 1000 and 350 it both hardly gives any gain.

Code: Select all

constexpr int ChessPiece::evalVal[] = { 100, 325, 325, 500, 975, 10000, 0, 0 };

(pawn, knight, bishop, rook, queen, king)

Then the evaluation consists of:
- position value; rates a position on the board of a piece. those values are in range of -50...50
- total value of all objects
- -15 * number of isolated pawns
- -15 * number of double pawns
- +3 * mobility (so max 217 * 3)
- +15 * passed pawns

The margin depends very much on how your static positional evaluation behaves. So I don't think there is one margin that works for everyone. But you definitely want to strive for the smallest margin you can use without degrading your engine's tactical awareness too much.

Also, futility pruning interacts heavily with other pruning techniques. You might want to measure its effect with/without other pruning techniques like LMR and null move pruning enabled.

Basically you have to figure out what the best approach is for your engine. And it may be more complex than the simple approach described on chessprogramming wiki. For example you may want your eval function to keep track of how many variables effected its final eval score, and if the number of variables is high use a higher futility margin.

STC

[JVMerlino]

I think you will find many differing opinions on this subject.

basically the idea, I think, is if you are at depth == 1 and static eval plus some margin is less than alpha treat the node like a quiescence search node: only search captures and checks.

That's basically what the chessprogramming wiki says too.

Where it gets sticky is, whether you should do this when the side to move is in check, to which I say resoundingly: "no". Queue h.g.m.

As for determining which moves give check, that depends on your move generator. If your move generator isn't capable of generating moves based on whether they give check or not, then you'll have to execute every move to determine whether they produce check, which isn't really that bad. I don't get why you think you also need to generate response moves too, but maybe I am misunderstanding what you said.

STC

There are some engines (e.g. Greko, IIRC) who also implement futility pruning with respect to beta. It is the same concept, except:

if (static_eval - margin > beta) return beta

jm

[pkumar]

Futility is for quiet move, if at depth 1 my evbal is well below beta and the capture haven't produced a beta cutoff it's very unlikely that a quiet move will raise the eval above beta

If alpha<0 then check if at least one legal move - even a quiet move - is possible to rule out stalemate.

[tpetzke]

Next question: determing if a move gives check. I think that is a makeMove(), then generate a list of moves, validate which ones are correct and then see if the opponent is in check state. This feels expensive? Or are here smarter ways of finding if a move gives check?

I don't generate all moves just for that. If a move is a candidate for pruning, so all other pruning conditions match the last condition is to determine whether it gives check. It is however still one of the more costly functions. Profiling always orders it high in the list.

Here is the code in iCE as an inspiration, maybe it helps

Code: Select all

template <EColor side>ECheck TBoard&#58;&#58;moveChecksSidesKing&#40;TMove move&#41;
&#123;
	TBitBoard abb = 0;
	ESquare kSq = bb.sqOfKing&#91;side&#93;, toSq = TMove_TO_SQUARE&#40;move&#41;;
	const EColor attacker = &#40;side == WHITE ? BLACK &#58; WHITE&#41;;

	// start with an active check test
	// does the moved piece check the king directly in its new position
	switch &#40;TMove_MOVED_PIECE&#40;move&#41;)
	&#123;
		case PIECE<attacker>&#58;&#58;PAWN   &#58; abb = bbPattern.PAWNS&#91;attacker&#93;&#91;toSq&#93;; break;
		case PIECE<attacker>&#58;&#58;KNIGHT &#58; abb = bbPattern.KNIGHTS&#91;toSq&#93;; break;
		case PIECE<attacker>&#58;&#58;BISHOP &#58; abb = getBishopAttacks&#40;toSq&#41;; break;
		case PIECE<attacker>&#58;&#58;ROOK   &#58; abb = getRookAttacks&#40;toSq&#41;; break;
		case PIECE<attacker>&#58;&#58;QUEEN  &#58; abb = getBishopAttacks&#40;toSq&#41; | getRookAttacks&#40;toSq&#41;; break;
		case PIECE<attacker>&#58;&#58;KING   &#58; if &#40;TMove_IS_CASTELING&#40;move&#41;) abb = FILE_NO&#91;toSq&#93; == C ? abb = getRookAttacks&#40;ESquare&#40;toSq+1&#41;) &#58; abb = getRookAttacks&#40;ESquare&#40;toSq-1&#41;);
	&#125;
	
	if (&#40;abb & BB_SQUARES&#91;kSq&#93;) != 0&#41; return CHECK;	// king is in the attack pattern of the moved piece on its target square, so this is a checking move

	// look for a passive check when the moved piece opens a file or rank to the king
	// test whether a discovered check is possible, otherwise early exit
	if (!TMove_IS_ENPASSENT&#40;move&#41; && (&#40;bbPattern.QUEENS&#91;kSq&#93; & BB_SQUARES&#91;TMove_FROM_SQUARE&#40;move&#41;&#93;) == 0&#41;) return NO_CHECK;

	// create a new occupied board pattern that simulates the move
	abb = TMove_IS_CAPTURE&#40;move&#41; ? &#40;bb.occupiedSquares & ~BB_SQUARES&#91;TMove_FROM_SQUARE&#40;move&#41;&#93; & ~BB_SQUARES&#91;TMove_CAPTURED_SQUARE&#40;move&#41;&#93;) | BB_SQUARES&#91;toSq&#93; &#58; 
								   &#40;bb.occupiedSquares & ~BB_SQUARES&#91;TMove_FROM_SQUARE&#40;move&#41;&#93;) | BB_SQUARES&#91;toSq&#93;;	

	if (&#40;getBishopAttacks&#40;kSq, abb&#41; & &#40;bb.pcs&#91;PIECE<attacker>&#58;&#58;BISHOP&#93; | bb.pcs&#91;PIECE<attacker>&#58;&#58;QUEEN&#93;)) ||
	    &#40;getRookAttacks&#40;kSq, abb&#41;   & &#40;bb.pcs&#91;PIECE<attacker>&#58;&#58;ROOK&#93;   | bb.pcs&#91;PIECE<attacker>&#58;&#58;QUEEN&#93;))) return DISCOVERED_CHECK;

	return NO_CHECK;
&#125;