Futility pruning question

[Tony]

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

From your remarks, I get the impression that you use a lazy eval for your futility pruning decision. ie You're not evaluating after making the move.

Did you test the difference ? In my engine, this seemed too dangerous.

Tony

[hgm]

Well, this is basically the entire purpose of futility pruning, isn't it? To save you the evaluation. This is what CurEval + CapturedMaterial + POSMARGIN means, a (very) lazy eval, biased to err towards the safe side.

If you would base it on the full eval, you might as well call Search and let the stand-pat cutoff handle it. It is not that expensive to make and unmake the move, and it is likely you could not do the full eval anyway without first performing the move.

[Tony]

Well, this is basically the entire purpose of futility pruning, isn't it? To save you the evaluation. This is what CurEval + CapturedMaterial + POSMARGIN means, a (very) lazy eval, biased to err towards the safe side.

If you would base it on the full eval, you might as well call Search and let the stand-pat cutoff handle it. It is not that expensive to make and unmake the move, and it is likely you could not do the full eval anyway without first performing the move.

I think I get it. I just call this lazy eval. When I say futility, I mean that there would be another move of my opponent coming.

My misunderstanding, caused by my different program structure, sorry.

Tony

[hgm]

Well, no reason to apologize, I am still curious what you do: So you were talking about the d=2 case? People also call this futility pruning.

I never understood Heinz' paper about this, in particular why he would use different margins for the d=2 and d=3 case. Seems to me the cases are fully equivalent. At d=2 the stm also has two moves to go (i.e. 3 ply) before the opponent can stand pat. That you are allowed to stand pat yourself after ply 2 does not help for futility, it could at most be a reason to award yourself a beta cutoff without search. But at d=2 every move that attacks a sufficiently large piece to overcome alpha, even if the move itself is a non-capture, is not futile, as you will always be able to capture that piece in the first move of QS.

So using a margin of a Rook at d=2 will cause you to prune many non-futile moves. If your opponent has a Queen, the margin should be a Queen + the maximum positional gain of 2 moves. That would be the same margin then as you would use at d=3.

But the real problem I have with deep futility pruning is the matter of checks. In Chess the value of the highest piece of the opponent is in fact always infinite. To decide a move at d=3 is futile, you must make sure that it does not lead to checkmate two ply later. Basically that requires you to figure out if you have moves that enable a check (and if you already have checks now, there you can't do anything). I haven't found a good way to judge that.

One thing that crossed my mind is only to dis-allow stand pat on checkmate, and ignore other checks. (On the philosophy that other checks are at worst forks that lead to the loss of some other piece than King, that has only a finite value.) Then you have to judge only if after the move checkmate in one would in principle be possible. And in the majority of cases you might be able to rule that out by keeping track of the safe King moves. Only moves that attack the designated escape squares of the King would then be intrinsically non-futile.

e.g. K:g1, P:f2,g2,h2. The opponent has no Q. By playing g2-g3 you provide 'breathing space' to your King, which as now safe moves to f1, h1 and g2, that never can be covered all at once by an enemy piece. As long as you have this optimal King safety you can prune most moves safely at d=3. Only if the opponent plays Be4, covering g2, you start to worry (and if he checks you, of course). Your King safety just dropped to the point where you have become checkmatable, so pruning this move would be criminal.

[Tony]

Hi Harm Geert,

in XiniX I do an evaluation after the makemove, so before calling search again.

If depth remaining is zero ( so I would be calling quiescence afterwards) I might not do a full evaluation, but only a lazy one, and decide not to call quiescence at all if score < alpha+margin. (Actually, lazy eval is only allowed when this is the case)
If I do a full eval and score is < alpha, I don't need to call quiescence at all, since the opponent will take the stand pate score and I save a function call (which is the reason for doing the evaluation before calling search)

If depth remaining is 1 ply, and after doing the full eval, and score is still below alpha, I might decide to take the score ( and not call search again). The thought is that the move to come will only lower the score (exceptions excluded like check, big king unsafety etc).

So my addition to the confusion was based on the fact that in my program I either do lazy eval or (futility) prune, but never both.

Tony

[hgm]

The thought is that the move to come will only lower the score (exceptions excluded like check, big king unsafety etc).

I think this is an invalid assumption: At remaining depth = 1 after the move, any good captures of yourself are also within the horizon. And even if you treat checks special, there are many tactical motifs that are non-futile, but that you would prune this way. And they are not always easy to recognize from the move itself. E.g. an innocently looking Pawn push (not a passer) might chase away the Q to a place where it is no longer can defend a R that you could already win by BxR, QxB, to turn the value of the BxR from +2 to +5. Futility pruning is done in all nodes, so you should be prepared to have winning captures already present on the board that might tip the balance in the first ply of QS, when the all-side is looking for alternatives to improve on them by cranking up the pressure compared to cashing them immediately. Other cases are a threat by the all side (creating a good capture) that was met by a bigger or equal counter-threat by the cut-side. Often you can solve this by evading the counter-threat first, creating a second problem (threat or capture).

Things like that are fairly rare in the tree, of course, but the very reason for doing the search is to find them.

[Tony]

The thought is that the move to come will only lower the score (exceptions excluded like check, big king unsafety etc).

I think this is an invalid assumption: At remaining depth = 1 after the move, any good captures of yourself are also within the horizon. And even if you treat checks special, there are many tactical motifs that are non-futile, but that you would prune this way. And they are not always easy to recognize from the move itself. E.g. an innocently looking Pawn push (not a passer) might chase away the Q to a place where it is no longer can defend a R that you could already win by BxR, QxB, to turn the value of the BxR from +2 to +5. Futility pruning is done in all nodes, so you should be prepared to have winning captures already present on the board that might tip the balance in the first ply of QS, when the all-side is looking for alternatives to improve on them by cranking up the pressure compared to cashing them immediately. Other cases are a threat by the all side (creating a good capture) that was met by a bigger or equal counter-threat by the cut-side. Often you can solve this by evading the counter-threat first, creating a second problem (threat or capture).

Things like that are fairly rare in the tree, of course, but the very reason for doing the search is to find them.

Yes, that's probably why futility has never given me much. I do not allow futility in a some cases ; having a hanging piece is one of them, to exclude a lot of the threaths.

My feeling was that most that is won by pruning, is lost again by search instability. But maybe I'm just doing it wrong.

I have also seen test positions where I need (almost) the same amount of nodes but a ply extra. Not sure how to evaluate that.

Tony