Detecting if move that gives check exists

[Mergi]

you can see there that my trick to known if the move is giving check is just to call InCheck function AFTER the MakeMove

Thats exactly what he doesnt want to do. He wants to know whether there are even such moves in the first place, rather than generating them or even worse, making them on the board.

I think the confusion stems from why you would even need such a functionality in the first place. If you are in a node, that would be cut, you would generate all the checking moves, presumably with a special mask or even just a separate generator. If there are no such moves, you simply get back an empty list, and cut the node. This should be already very very fast.

Why don't you want a function that predicts whether there's any move at all to detect checkmates early? Seeing as checking moves are a subset of all moves, finding out whethere there's any move might be easier than finding out whether there's a very special kind of move, a checking move, right? Yet nobody, at least to my knowledge, is doing checkmate verification before the move loop. If you can predict that there is a move, you might as well generate it.

Even if there's some Emanuels-smart-move-prediction algorithm, that is yet to be discovered, this really seems like a pointless thing to attempt to do.

[R. Tomasi]

I do need a way to determine if such a move might exist in a fast way, without generating the moves. I am sure I will be able to come up with code that does that, but I guess other people (who are smarter than me) have already thought about this, so any ideas or hints are very welcome.

Yes, that's correct.

Do you want to hear about Emanuel's Bit-Based Move Checking Methodology?

Clearly you're not even smart enough to understand my post... so no.

[R. Tomasi]

I think the confusion stems from why you would even need such a functionality in the first place

Please correct me, if I missunderstand the concepts. From what I gather

• normal futility pruning: you check if the futility gap (alpha-eval-posmargin) is above zero. If so, and alpha isn't near a mating score, you're not in check and the move does not give check and isn't a capture, then prune it.
• futility pruning with captures: same as above, but you also prune captures if the futility gap is above the value of the capture victim.
• general futility pruning: if you know the value of the opponents most valuable piece and it is below the futility gap, then you know that every move will be pruned, hence you can skip the node (including movegen) alltogether. However, you're also pruning the moves that give check then. I would like to not prune the node, if that happens, so that it will theoretically be equally sound as futility pruning with captures.

[Mergi]

I think the confusion stems from why you would even need such a functionality in the first place

Please correct me, if I missunderstand the concepts. From what I gather

• normal futility pruning: you check if the futility gap (alpha-eval-posmargin) is above zero. If so, and alpha isn't near a mating score, you're not in check and the move does not give check and isn't a capture, then prune it.
• futility pruning with captures: same as above, but you also prune captures if the futility gap is above the value of the capture victim.
• general futility pruning: if you know the value of the opponents most valuable piece and it is below the futility gap, then you know that every move will be pruned, hence you can skip the node (including movegen) alltogether. However, you're also pruning the moves that give check then. I would like to not prune the node, if that happens, so that it will theoretically be equally sound as futility pruning with captures.

I believe i do understand you (i hope i'm not just blabbering off topic ), but being able to tell whether a node has a checking move without visiting and trying to generate checking moves in that node, just doesn't make sense to me With an algorithm like that, you could predict checkmate/stalemate moves from a parent node!

[R. Tomasi]

I believe i do understand you (i hope i'm not just blabbering off topic ), but being able to tell whether a node has a checking move without visiting and trying to generate checking moves in that node, just doesn't make sense to me With an algorithm like that, you could predict checkmate/stalemate moves from a parent node!

Well, for the moment I'm not claiming that it's an ELO win - it might even turn out that also pruning moves that give check in "normal futility pruning" might be stronger ELO-wise, since you leave out the verification.

I do think there actually exists a concept for detecting checkmate from the parent (mate at a glance), I may be confusing that, though.

At the moment, it is about soundness - I am simply wondering if it's possible to do general futility pruning in a way that theoretically will always give the same result as normal futility pruning.

[Mergi]

Well, maybe you could remember whether there were any checking moves on your last turn. If there were, and it wasn't the move that you are currently exploring, it's likely that there still are (unless the enemy moved their king or blocked the move in some other way). But that's all just a guesswork and it seems extremely dubious to me ... otherwise, I have no idea, but hopefully someone smarter and more knowledgeable can answer your question better

[Mergi]

At the moment, it is about soundness - I am simply wondering if it's possible to do general futility pruning in a way that theoretically will always give the same result as normal futility pruning.

If all you are after is search stability, maybe you can postpone the pruning until after making the move? Like in reverse futility pruning. Before you do such pruning, you check if(KingIsSafe) { prune }

https://www.chessprogramming.org/Revers ... ty_Pruning

But i guess that defeats the whole idea of not generating the moves in the first place, since you not only have to generate them, but also play them on the board.

[R. Tomasi]

At the moment, it is about soundness - I am simply wondering if it's possible to do general futility pruning in a way that theoretically will always give the same result as normal futility pruning.

If all you are after is search stability, maybe you can postpone the pruning until after making the move? Like in reverse futility pruning.

Well, obviously I would hope that it also turns out to be stronger. However that clearly depends on how fast it is possible to detect if there are checking moves in a position.

https://www.chessprogramming.org/Revers ... ty_Pruning

But i guess that defeats the whole idea of not generating the moves in the first place, since you not only have to generate them, but also play them on the board.

Yeah... I guess maybe generating only moves that give check using a special movegen when in a node that elsewise would have been pruned is the best way to go.

[hgm]

What you are looking for is a checks generator. This is a dedicated move generator that only generates moves that deliver checks. Just like you can also have a move generator for only generating captures, or check evasions. Of course the most primitive form of such a dedicated move generator is to generate all moves, and then test those individually for belonging in the desired class. This is usually not the most efficient method, though.

I think Fruit 2.1 contains a dedicated 'checks generator', for the purpose of searching checks (in addition to captures) in the first two levels of QS. Fruit is a mailbox engine, of course. The generator is based on tables (one for each piece type) that contain the squares where you could potentially check for a given piece and King location. For pieces with location-independent moves (like in Chess) you can shrink the required space by tabulating as a function of the square difference.

E.g. for a Rook on a8 and the (enemy) King on e1, the potential checking squares would be a1 and e8. The Rook table always contains two squares for each (rookSqr, kingSqr) pair. By using relative positions (e.g. w.r.t. the Rook, so checkSqr - rookSqr in the table, indexed by kingSqr - rookSqr) the same table entry could be used for a Rook on b8 and a King on f2. Of course the square-number differences have to be unique, as they are in the 0x88 numbering system used by Fruit. (But not when you number 0-63.)

Other piece types might not always have 2 checking squares. (A Knight on a8 can obviously never check a King on e1.) So the lists of checking squares for a given relative (piece, king) vector are variable length. A system based on relative locations would also not take account of the fact that 'potential checking squares' could be off-board. E.g. a Knight on e5 can check a King on e1 in two ways (d3 and f3), but shift the whole constellation to the h-file, and only g3 remains. But being off-board is not really different from being occupied by an own piece, which has to be tested anyway before the potential checking square can be accepted as a move. For sliders it will also have to be tested whether both paths (piece to checking square and checking square to King) are unobstructed. (In an advanced mailbox design this would be done by comparing their length to the tabulated viewDistance in the relevant direction, where length and direction number would also be in the table.)

In mailbox this method is a bit troublesome for the Queen, as this can have 12 potential checking squares. Running through all these tabulated squares then doesn't offer much advantage to running through all Queen moves in the first place. But for Pawns, Knights and Kings it can be a big time saver, as these typically do not have any potential checking squares at all. And a Bishop has none in 50% of the cases (when it is of the wrong shade).

A bitboard equivalent of this algorithm would tabulate the checking squares not as lists of coordinates, but as bitboards. Since that is not a relative coding (unless you would be prepared to shift the bitboard afterwards), it also doesn't make sense to index by a relative coordinates, and you would need a table BitBoard checks[pieceType][sqr][kingSqr]. This is a large table, but bitboard methods are usually based on large tables, so that doesn't disqualify it. And kingSqr would not take on many different values in a search tree, as Kings are not very mobile. So you could arrange it such that the required row or column of the array can be efficiently cached.

For leapers the bitboard with potential checking squares would have to be masked with the own occupied to clear the blocked squares, or by the total occupied, if you are also not interested in checking captures (because you already generated all captures elsewhere). You can then directly extract the sought checks from the remainder. For sliders it is not so simple. You have to extract the potential checking squares, and then one by one verify whether these have a clear path.

The checkSqr - King path can be verified 'in bulk' by generating Rook and Bishop attack sets for the King square, and ORing these. The potential checking squares can then be ANDed with this prepared mask, to leave only the squares where the check would not be obstructed. This reduces the checking opportunities that will have to be extracted, and these then only have to be tested for obstruction on the path from piece to checking square. For this a bitboard engine usually already has a function. Note that for most of the game Kings are typically safely tucked away, so that the prepared mask of squares that 'view' the King has very few squares, and the intersection of it with potential checking squares will almost always be empty.

[R. Tomasi]

...

Thank you for the tips! What you suggest is kind of what I had in mind with my previous post. Instead of pruning the node, one only generates the checks using a special movegen. The method of using lookup tables for each piece and kingsquare - as you suggested - seems the way to go, I think. I'm honestly not sure what results in stronger play: not worrying about checking moves at all or do what I intend to implement. I guess only measurement can tell, and it's probably something that also depends on the rest of the engine...

(Btw, I'm using bitboard based movegen, so everything will be mapped to absolute square indices)