How to test whether a move gives check

[gflohr]

In want to improve my move ordering and want to find out whether a move gives check but without actually doing it.

At the point where I need that information I know:

- which piece moves
- in case of captures the captured piece
- a possible promotion
- is the move an en passant capture
- the square of the opponents king
- of course, the from and to squares

I am using (magic) bitboards.

What would be the best strategy to find out whether the move gives check? One idea would be to do that check only from a certain depth on and just do/undo the move. Or is there something smarter?

Or is it just not worth the effort? At the moment I try the PV move first, then one from the TT, and then captures and promotions in MVV/LVA order.

[dangi12012]

One fast way is to have the king send out Queen Rays and & with enemy sliders of that type.
Rook ray from king sees a Rook | Queen
Bishop ray from king sees Bishop | Queen
Knight lookup from king sees a enemy knight

Pawns is the fastest with (king >> 9 | king >> 7) & EnemyPawn (or other way around also dont forget masking off left and right file)

Its generally faster to already know what is pinned and not pinned etc. But its VERY VERY hard to do that in a fast way (which I needed to do for my movegen http://www.talkchess.com/forum3/viewtop ... =7&t=78230)

Problem is that "which piece moves" is almost irrelevant because of discovered check, Enpassant discovered check, Double check and Promotion check. Castling check - Or even my favourite: promotion double check.

Generally you can use the "which piece moves" info only for pawn (not on last rank, and not enpassant) and knights. Regardless you would have to check for a discovered check.

[j.t.]

Or is it just not worth the effort? At the moment I try the PV move first, then one from the TT, and then captures and promotions in MVV/LVA order.

I would first check if it actually reduces the number of nodes searched. If you don't prune check giving moves, then this should be the only metric that matters (of course averaged over many positions). For this, you don't need a speed optimized way to check for check, just use the functions you already have.
If you find that it really helps bringing the number of nodes searched down, then you can start optimizing.

[gflohr]

One fast way is to have the king send out Queen Rays and & with enemy sliders of that type.
Rook ray from king sees a Rook | Queen
Bishop ray from king sees Bishop | Queen
Knight lookup from king sees a enemy knight
...

What you describe is how to test whether the king is in check after the move was done and I already have that code in place and working.

I was asking for a way to find out whether a move gives check without having to actually do the move.

I think the fastest way must be something like this in pseudo-code:

Code: Select all

    if piece == king
        return false
    if piece < bishop {
        attack_mask = attack_masks[piece][king_square]
        if ((1 << to) & attack_mask)
            return true
    }
    if (castling) {
        if (rmagic(king_square, occupancy) & (1 << rook_to))
            return true
        else
            return false
    }
    move_xor = (1 << from) | (1 << to)
    rooks = my_rooks | my_queens
    bishops = my_rooks | my_queens
    if piece == bishop || piece == queen
        bishops ^= move_xor
    if piece == rook || piece == queen
        rooks ^= move_xor
    occupancy ^= move_xor
    if (en_passant)
        occupancy ^= (1 << ep_square)
    if (rmagic(king_square, occupancy) & (my_rooks | my_queens)
        return true;
    if (bmagic(king_square, occupancy) & (my_bishops | my_queens)
        return true;

If the moving piece is a pawn or knight, I can lookup precalculated tables for an early exit. If it is a castling move, only the rook can give check if the opponent's king is on the d or f file and.

And otherwise I have to use magic bitboards and check whether the king is attacked.

That will be slightly faster than doMove/undoMove but the problem is that I have to do it for every move, when I want to use the result for sorting.

[gflohr]

I would first check if it actually reduces the number of nodes searched. If you don't prune check giving moves, then this should be the only metric that matters (of course averaged over many positions). For this, you don't need a speed optimized way to check for check, just use the functions you already have.
If you find that it really helps bringing the number of nodes searched down, then you can start optimizing.

Yes, that is a good idea. If I always search to the same depth I will see the net effect of the better move ordering and if there is a positive one I can optimize the check detection later.

[R. Tomasi]

FWIW this is how that function looks in Pygmalion. Obviously you will not be able to just plug it into your engine, but it may help to have a blue-print:

Code: Select all

static bool isMoveCritical_Implementation(const stackType& stack, const movebitsType& moveBits) noexcept
{
	const boardType& position{ stack.position() };
	const playerType movingPlayer{ position.movingPlayer() };
	const playerType otherPlayer{ movingPlayer.next() };
	const squareType to{ motorType::move().toSquare(position, moveBits) };

	// We need to know where the enemy king lives
	const squareType otherking{ stack.kingSquare(otherPlayer) };

	// We need our own occupancy bitboard as it would be after the move...
	const squaresType ownOccupancy{ position.playerOccupancy(movingPlayer) };
	const squaresType ownDelta{ motorType::move().ownOccupancyDelta(position, moveBits) };
	const squaresType occOwn{ ownOccupancy ^ ownDelta };

	// Does he live on a square that is attacked by one of our knights?
	const squaresType knightsDelta{ motorType::move().pieceOccupancyDelta(position, knight, moveBits) };
	const squaresType ownKnights{ (position.pieceOccupancy(knight) ^ knightsDelta) & occOwn };
	const squaresType attackedByOwnKnights{ movegenKnight.attacks(ownKnights,squaresType::all()) };
	if (attackedByOwnKnights[otherking])
		return true;

	// Does he live on a square that is attacked by one of our pawns?
	const squaresType pawnsDelta{ motorType::move().pieceOccupancyDelta(position, pawn, moveBits) };
	const squaresType ownPawns{ (position.pieceOccupancy(pawn) ^ pawnsDelta) & occOwn };
	if (movingPlayer == whitePlayer)
	{
		const squaresType pawnsTemp{ ownPawns.up() };
		const squaresType attackedByOwnPawns{ pawnsTemp.right() | pawnsTemp.left() };
		if (attackedByOwnPawns[otherking])
			return true;
	}
	else
	{
		const squaresType pawnsTemp{ ownPawns.down() };
		const squaresType attackedByOwnPawns{ pawnsTemp.right() | pawnsTemp.left() };
		if (attackedByOwnPawns[otherking])
			return true;
	}

	// We need the total occupancy bitboard as it would be after the move...
	const squaresType otherOccupancy{ position.playerOccupancy(otherPlayer) };
	const squaresType otherDelta{ motorType::move().otherOccupancyDelta(position, moveBits) };
	const squaresType occOther{ otherOccupancy ^ otherDelta };
	const squaresType occTotal{ occOther | occOwn };
	const squaresType unoccupied{ ~occTotal };

	// Is he attacked horizontally by sliding pieces?
	const squaresType queensDelta{ motorType::move().pieceOccupancyDelta(position, queen, moveBits) };
	const squaresType queens{ position.pieceOccupancy(queen) ^ queensDelta };
	const squaresType rooksDelta{ motorType::move().pieceOccupancyDelta(position, rook, moveBits) };
	const squaresType rooks{ position.pieceOccupancy(rook) ^ rooksDelta };
	const squaresType ownSlidersHV = occOwn & (rooks | queens);
	const squaresType criticalSquaresHV{ movegenSlidersHV.inverseAttacks(otherking, unoccupied) };
	if ((criticalSquaresHV & ownSlidersHV) != squaresType::none())
		return true;

	// Is he attacked diagonally by sliding pieces?
	const squaresType bishopsDelta{ motorType::move().pieceOccupancyDelta(position, bishop, moveBits) };
	const squaresType bishops{ position.pieceOccupancy(bishop) ^ bishopsDelta };
	const squaresType ownSlidersDiag = occOwn & (bishops | queens);
	const squaresType criticalSquaresDiag{ movegenSlidersDiag.inverseAttacks(otherking, unoccupied) };
	if ((criticalSquaresDiag & ownSlidersDiag) != squaresType::none())
		return true;

	// The move seems not to be giving check
	return false;
}

DISCLAIMER: I do not claim that this is the fastest or optimal way to do it.

[Brunetti]

Code: Select all

    if piece == king
        return false

Code: Select all

If it is a castling move, only the rook can give check if the opponent's king is on the d or f file

[fen]8/8/8/8/8/8/8/R3K2k w Q - 40 41[/fen]


Alex

[dangi12012]

Also if its pseudo legal you need to test for check anyways.
Exception to that rule is the forbidden castling when a passing square is seen by an enemy.

[gflohr]

Code: Select all

    if piece == king
        return false

Code: Select all

If it is a castling move, only the rook can give check if the opponent's king is on the d or f file

[fen]8/8/8/8/8/8/8/R3K2k w Q - 40 41[/fen]


Alex

Good catch! Thank you!

[alessandro]

The task of detecting if a move checks opponent king, and what kind of check is it (a direct check? discovery check? double check? checkmate) has been implemented in AdaChess since long time.
When I started the implementation I've found almost no info on the web. So I had to design it by myself. After it, I've published the perft-statistic data on the chessprogramming wiki at https://www.chessprogramming.org/Perft_Results and now I am happy to see that some other programmers are implementing the same feature.

The real point in my opinion is not "how to implement" it, but how to implement it (correctly and) in the most efficient way considering the data structure you choose to implement your engine.

You need four foundamental information: the position of the opponent king, the moving piece (and of course also starting and destination square), a way to find if two squares are somehow connected in a specific sliding-direction (I mean, if those squares are on the same rank/file/diagonal/anti-diagonal/none-of-them) and a way to quickly find attacks along that sliding-direction.

Take into account that many possibilities have to be investigated. And you always need to search for direct checks and for discovery checks. You may not need to detect checkmates, but I do. Fo the checkmate scenario, I've implement a makemove (called Play in AdaChess) and a takeback (called Undo) specifically for this, to make it as efficient as possible.

It's fast? It's efficient? In my opinion the overall code is very efficient, and the speed reduction, compared to the same engine without this information, is almost irrelevant. If you don't keep track of this information, your move generator will be slighlty faster but then into the search you will have to test every time if the king is in check. On the other side, if you keep track of the information your move generator is sligtly slower but you have the information ready to be used into the search. Since the engine spend around its 5-10% of the time in generating moves, making it a bit slower or a bit faster is irrelevant for "weak" engines.

You can have a full view of my source code if you download the engine from my website, here is the function that do the job, should be enough easy to read and understand even if it is Ada language. I suggest you, don't focus on each single line of the code, but try to understand the overall design of the functionality, the idea behind it, in order to be able to implement your own.
Note that a bitboard engine, thanks to bitwise operations, might have more powerful tools and significantly reduce the complexity.

Code: Select all

 
   ------------------------------
   -- Move_Checks_Opponen_King --
   ------------------------------

   function Move_Checks_Opponent_King (Chessboard : in out Chessboard_Type; Move : in Move_Type) return Check_Type is
      Type_Of_Check       : Check_Type := No_Check;
      Side                : Color_Type;
      King_Position       : Square_Type;
      Direction           : Direction_Type := 0;
      Discovery_Direction : Direction_Type := 0;
      Ep_Direction        : Direction_Type := 0;
      Ep_Captured         : Square_Type := 0;
      Type_Of_Castle      : Castle_Type := No_Castle;
      White_King_Position : Square_Type renames Chessboard.White_King_Position;
      Black_King_Position : Square_Type renames Chessboard.Black_King_Position;
   begin

      if Chessboard.Side_To_Move = White then
         Side := White;
         King_Position := Black_King_Position;
      else
         Side := Black;
         King_Position := White_King_Position;
      end if;

      ------------------
      -- Direct Check --
      ------------------

      if Move.Piece in Knight_Type or else Move.Promotion in Knight_Type then
         for Offset of Knight_Offsets loop
            if Move.To + Offset = King_Position then
               Type_Of_Check := Direct_Check;
            end if;
            exit when Type_Of_Check /= No_Check;
         end loop;

      elsif Move.Piece = White_Pawn and then Move.Promotion = Empty then
         if Move.To + North_West = Black_King_Position
           or else Move.To + North_East = King_Position then
            Type_Of_Check := Direct_Check;
         end if;

      elsif Move.Piece = Black_Pawn and then Move.Promotion = Empty then
         if Move.To + South_East = King_Position
           or else Move.To + South_West = White_King_Position then
            Type_Of_Check := Direct_Check;
         end if;

      else
         -- Find the direction where the attack come from, if any
         Direction := Find_Sliding_Direction (Move.To, King_Position);

         if Direction /= No_Direction then

            Chessboard.Square (Move.From) := Empty;
            Chessboard.Square (Move.To) := (if Move.Promotion = Empty then Move.Piece else Move.Promotion);

            if Attacks_To (Direction) (Chessboard.Square, Side, King_Position) then
               Type_Of_Check := Direct_Check;
            end if;

            Chessboard.Square (Move.From) := Move.Piece;
            Chessboard.Square (Move.To) := Move.Captured;
         end if;

      end if;

      --------------------------------------
      -- Discovery Check and Double Check --
      --------------------------------------

      if Move.Flag = Capture_En_Passant then
         Ep_Captured := (if Move.Piece in White_Piece_Type'Range then Move.To + South else Move.To + North);
         Chessboard.Square (Ep_Captured) := Empty;
      end if;

      Discovery_Direction := Find_Sliding_Direction (Move.From, King_Position);

      if Move.Piece in King_Type | Pawn_Type then
         -- In this case, before removing the piece to look for discovery attack,
         -- be sure that piece is not moving along discovery line itself!
         if Discovery_Direction = Find_Sliding_Direction (Move.To, King_Position) then
            Discovery_Direction := No_Direction; -- Reset it, then skip discovery check lookup
         end if;
      end if;

      if Discovery_Direction /= No_Direction then
         Chessboard.Square (Move.From) := Empty;

         if Attacks_To (Discovery_Direction) (Chessboard.Square, Side, King_Position) then
            Type_Of_Check := (if Type_Of_Check = No_Check then Discovery_Check else Double_Check);
         end if;

         Chessboard.Square (Move.From) := Move.Piece;
      end if;

      ----------------
      -- En-passant --
      ----------------

      if Move.Flag = Capture_En_Passant then
         Ep_Direction := Find_Sliding_Direction (Ep_Captured, King_Position);
         if Ep_Direction /= Discovery_Direction and then Ep_Direction /= Find_Sliding_Direction (Move.To, King_Position) then
            if Attacks_To (Ep_Direction) (Chessboard.Square, Side, King_Position) then
               Type_Of_Check := (if Type_Of_Check = No_Check then Discovery_Check else Double_Check);
            end if;
         end if;
         Chessboard.Square (Ep_Captured) := (if Move.Piece in White_Piece_Type'Range then Black_Pawn else White_Pawn);
      end if;

      ------------
      -- Castle --
      ------------

      -- Actually, in case of castles an additional investigation has to be done
      -- to verify if the rook involved in the castle is directly checking the
      -- opponent king

      if Type_Of_Check = No_Check and then Move.Flag = Castle then

         if Move.From = E1 and then Move.To = G1 then
            Type_Of_Castle := White_Kingside;
         elsif Move.From = E1 and then Move.To = C1 then
            Type_Of_Castle := White_Queenside;
         elsif Move.From = E8 and then Move.To = G8 then
            Type_Of_Castle := Black_Kingside;
         elsif Move.From = E8 and then Move.To = C8 then
            Type_Of_Castle := Black_Queenside;
         else
            raise Invalid_Castle_Move;
         end if;


         case Type_Of_Castle is
            when No_Castle => null;

            when White_Kingside =>
               Chessboard.Square (G1) := White_King;
               Chessboard.Square (E1) := Empty;
               Chessboard.Square (F1) := White_Rook;
               if Attacks_From_South (Chessboard.Square, White, Black_King_Position) then
                  Type_Of_Check := Direct_Check;
               elsif Attacks_From_East (Chessboard.Square, White, Black_King_Position) then
                  Type_Of_Check := Direct_Check;
               end if;
               Chessboard.Square (F1) := Empty;
               Chessboard.Square (G1) := Empty;
               Chessboard.Square (E1) := White_King;

            when White_Queenside =>
               Chessboard.Square (D1) := White_Rook;
               Chessboard.Square (E1) := Empty;
               Chessboard.Square (C1) := White_King;
               if Attacks_From_South (Chessboard.Square, White, Black_King_Position) then
                  Type_Of_Check := Direct_Check;
               elsif Attacks_From_West (Chessboard.Square, White, Black_King_Position) then
                  Type_Of_Check := Direct_Check;
               end if;
               Chessboard.Square (D1) := Empty;
               Chessboard.Square (E1) := White_King;
               Chessboard.Square (C1) := Empty;

            when Black_Kingside =>
               Chessboard.Square (G8) := Black_King;
               Chessboard.Square (E8) := Empty;
               Chessboard.Square (F8) := Black_Rook;
               if Attacks_From_North (Chessboard.Square, Black, White_King_Position) then
                  Type_Of_Check := Direct_Check;
               elsif Attacks_From_East (Chessboard.Square, Black, White_King_Position) then
                  Type_Of_Check := Direct_Check;
               end if;
               Chessboard.Square (E8) := Black_King;
               Chessboard.Square (G8) := Empty;
               Chessboard.Square (F8) := Empty;

            when Black_Queenside =>
               Chessboard.Square (E8) := Empty;
               Chessboard.Square (C8) := Black_King;
               Chessboard.Square (D8) := Black_Rook;
               if Attacks_From_North (Chessboard.Square, Black, White_King_Position) then
                  Type_Of_Check := Direct_Check;
               elsif Attacks_From_West (Chessboard.Square, Black, White_King_Position) then
                  Type_Of_Check := Direct_Check;
               end if;
               Chessboard.Square (E8) := Black_King;
               Chessboard.Square (D8) := Empty;
               Chessboard.Square (C8) := Empty;
         end case;
      end if;

      ---------------
      -- Checkmate --
      ---------------

      if Type_Of_Check /= No_Check then
         Chessboard.Play_Check_Move (Move);
         if not Chessboard.King_Has_Escapes (Type_Of_Check) then
            Type_Of_Check := Checkmate;
         end if;
         Chessboard.Undo_Check_Move;
      end if;

      return Type_Of_Check;

   exception
      when E : others =>
         Ada.Text_IO.Put_Line (Ada.Exceptions.Exception_Name (E));
         Ada.Text_IO.Put_Line (Ada.Exceptions.Exception_Message (E));
         Ada.Text_IO.Put_Line (Ada.Exceptions.Exception_Information (E));
         raise;
   end Move_Checks_Opponent_King;