Detecting if move that gives check exists

[R. Tomasi]

It seems to me that finding out whether there's a move that would give a check without generating any moves would be very expensive.

That's my gut feeling, too. Therefore this thread...

You could validate without too much overhead whether a move gives a check during the make unmake loop and prune there. Would that not work for you?

I already do that. The idea of what I'm trying to do (and the idea of what HGM describes, as far as I understand) is to save the time of generating the moves for a node alltogether. However I would still want to inspect the node if there is a way to give check. Hence I need a way to determine if there's a checking move that isn't more expensive than just inspecting every move. Not sure if that's feasable, but seems worth thinking about.

[R. Tomasi]

Another approach to tackle this may be to just check if the node should be pruned, basically in the exact way as described on HGMs website, but instead of pruning the node one could then only generate moves that give check.

[Mergi]

Honestly i'm not sure why would you not want to prune positions that might have checking moves. Then you might as well look if there's some fork or other tactic before pruning, but that's just silly. Usually you don't want to prune positions where the king is currently in check, or moves that give check to the enemy king, but trying to look ahead seems ... futile?

[R. Tomasi]

Honestly i'm not sure why would you not want to prune positions that might have checking moves. Then you might as well look if there's some fork or other tactic before pruning, but that's just silly. Usually you don't want to prune positions where the king is currently in check, or moves that give check to the enemy king, but trying to look ahead seems ... futile?

Well, by the same argument the whole concept of general futility pruning would then seem... futile.

[R. Tomasi]

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.

[Chessnut1071]

I'm currently implementing futility pruning in Pygmalion. This is a part of the engine that I do not want to just transfer from my old engine, since I suspect that many of the instabilities and tactical weaknesses that I had in the old engine are due to a bad implementation of futility pruning. At the time I wrote the respective code, I did simply not grasp the concept fully.

Currently I have a working Implementation in Pygmalion that seems to be tactically stable. I do not prune moves that give check. Now, a straight-forward improvement would be to implement "general futility pruning" in a way that is similar to what HGM describes on his Micro-Max homepage (https://home.hccnet.nl/h.g.muller/deepfut.html). However, I want to keep the philosophy of not pruning moves that give check. Therefore I would like to not prune the entire node, if the side to move might have a move that gives check.

Obviously, the whole idea of HGMs "general futility pruning" is to prune the node before any moves are generated, therefore 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.

Assuming you mean does the move result in a check:

The quickest way to do that is with a pre-computed move matrix including every possible move a K,Q,R,B can make from each of 8 positions {64 * 9] = 576 elements on every square. A separate [64 *3] for pawns, and [64 * 9] for knights. Label the vectors 1-8, 9 for the knight and 10 for the king's square. I use [8,-8,1,-1,9,-9,7,-7], [7,9], [6, 10, 15, 17,-6,-10,-15,-17] for the knight.

Then, overlay the piece positions on the board, cutting off the vectors that intersect the Check array.

The rest is quick and easy, If a queen move falls anywhere on a vector marked 1-8, it's check. Rooks 1-4, and bishops 5- 8.

the Check array is computed before your search ply, so there's no looping, just a quick lookup. If there is no check the array vector will be 0, so simply multiply the Check vector square by the move. Zero = no check, non-zero = check.

This is very fast. It reduces the speed of my engine about 9%, but, it more than makes up for it in solution time.

[R. Tomasi]

Assuming you mean does the move result in a check:

I do not, unfortunately.

The quickest way to do that is with a pre-computed move matrix including every possible move a K,Q,R,B can make from each of 8 positions {64 * 9] = 576 elements on every square. A separate [64 *3] for pawns, and [64 * 9] for knights. Label the vectors 1-8, 9 for the knight and 10 for the king's square. I use [8,-8,1,-1,9,-9,7,-7], [7,9], [6, 10, 15, 17,-6,-10,-15,-17] for the knight.

Then, overlay the piece positions on the board, cutting off the vectors that intersect the Check array.

The rest is quick and easy, If a queen move falls anywhere on a vector marked 1-8, it's check. Rooks 1-4, and bishops 5- 8.

the Check array is computed before your search ply, so there's no looping, just a quick lookup. If there is no check the array vector will be 0, so simply multiply the Check vector square by the move. Zero = no check, non-zero = check.

This is very fast. It reduces the speed of my engine about 9%, but, it more than makes up for it in solution time.

That is very interesting nevertheless, and I will certainly consider using that as a replacement for my current "does the move result in check?" function. But I don't want to know if a move results in check, I want to know if there is a move that results in check at all in a position (without having to generate the moves). In other words: given a position, I want to know if any of the possible moves results in a check.

[pedrojdm2021]

For frutility pruning i have something like this:

Code: Select all

               // make current move
                if (board.MakeMove(currentMove))
                {
                    mflag = MoveUtility.Get_flag(currentMove);

                    // ------------------[ Apply futility pruning ]------------------------ /

                    /*  
                        condition to consider futility pruning:
                        We apply futility pruning if:
                        - the futility flag is set
                        - we have searched at least 1 move before
                        - the move is not a tactical move (promotions, or captures)
                        - the move does not give check
                    */

                    if (futility_prune && searched_moves > 0 && mflag.Is_Capture() == false && mflag != MoveFlag.EnPassant && 
                        mflag.Get_promotion() == 0 && board.InCheck(board.sideToMove) == false)
                        {
                            board.UnMakeMove(currentMove);
                            continue;
                        }
                        
                   // code continues here....

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

I use this to detect checks:
https://www.chessprogramming.org/Square ... all_Pieces

that's all, no fancy "magic" there

i understand that it may not be the super-fast solution, but for now it works, and you don't need to mantain any kind of attack_maps or something like that.

Good luck with your engine

[Chessnut1071]

I'm currently implementing futility pruning in Pygmalion. This is a part of the engine that I do not want to just transfer from my old engine, since I suspect that many of the instabilities and tactical weaknesses that I had in the old engine are due to a bad implementation of futility pruning. At the time I wrote the respective code, I did simply not grasp the concept fully.

Currently I have a working Implementation in Pygmalion that seems to be tactically stable. I do not prune moves that give check. Now, a straight-forward improvement would be to implement "general futility pruning" in a way that is similar to what HGM describes on his Micro-Max homepage (https://home.hccnet.nl/h.g.muller/deepfut.html). However, I want to keep the philosophy of not pruning moves that give check. Therefore I would like to not prune the entire node, if the side to move might have a move that gives check.

Obviously, the whole idea of HGMs "general futility pruning" is to prune the node before any moves are generated, therefore 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.

Assuming you mean does the move result in check, otherwise, it's a straight forward compare against the king's position.

The fastest way I found is to pre-compute all the moves for K, Q, R, B, in one (64*9] = 576 matrix, with a [63*3] pawn matrix and a [64*9] knight matrix.
1) Label the vectors from a queen 1-8 [8,-8,1,-1,9,-9,7,-7]. The pawns [7,9] the knights [6,10,15,17,-6,-10,-15,-17].
2) Next, overlay the pieces positions and cutoff the check vectors that intersect the check vectors.
3) the rest is easy, if the move falls on a zero check move, it's not a check. If a queen, any vector labeled 1-8 is a check, A rook, 1-4, a bishop 5-8. Use 9 for a knight an 10 for the king's position.

The check matrix is pre-computed before the search ply and only requires a lookup, no looping. My engine only suffers a 9% drop in speed using this method

[klx]

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?