Program that will give all available moves given the state of a board, including check

Question

I am trying to write a program that will give out every possible move for every piece (one move deep) given the state of a board. I have already done this such that it works with everything except check. It will allow the king to move itself into check, and it will allow a piece to be moved out of the way such that it places the king in check. I can't think of an efficient way of removing these moves from the set of moves I generate.

I am storing the board as a list of lists, where each list is a row on the board. Black is at the top and white is at the bottom. Lowercase is black, uppercase is white.

P = pawn, R = rook, N = Knight, Q = Queen, K = King.

Therefore, the starting board looks like this:

board = [["r", "n", "b", "q", "k", "b", "n", "r"],
         ["p", "p", "p", "p", "p", "p", "p", "p"],
         ["", "", "", "", "", "", "", ""],
         ["", "", "", "", "", "", "", ""],
         ["", "", "", "", "", "", "", ""],
         ["", "", "", "", "", "", "", ""],
         ["P", "P", "P", "P", "P", "P", "P", "P"],
         ["R", "N", "B", "Q", "K", "B", "N", "R"]]

So for example, board[7][2] is "B".

The moves are stored as a list of lists, where each sub list contains the current coordinates of the piece and a list of all available moves for said piece.

For example

[[[1, 0], [[2, 0], [3, 0]]], ...]

As the pawn at 1, 0 can move forward either once or twice.

These are then stored in two separate lists, white_moves and black_moves.

So, I think the best way to prevent the king from moving into check is seeing if any of the moves generated for the king are in the opponent's moves, and then removing them from the king's moves if they are.

Like

king_moves = set(king_moves) - set(enemy_moves)

However, I can't think of a good way of determining if the movement of one of our pieces will result in the king being exposed and thus in check.

EDIT: I also need to deal with situations like this

Answer 1

You seem to be writing a move generator.

Conventionally, a set of legal moves is generated by first generating a list of pseudo-legal moves (i.e. all moves which could be made, ignoring the fact that the king needs special treatment) and then filtering out moves which leave the king in check.

The legal move generator in Stockfish (one of the strongest chess engines) does exactly this - moveList is initialised to a list of pseudo-legal moves, which is then iterated over to filter out illegal moves with pos.legal.

You can implement the detection of legal moves by simply 'making the move' (creating a board state after the move) and then checking if any piece attacks the king, though of course more efficient implementations are possible.

Answer 2

Here is some Pascal Source code from Borland 1985 that uses an AttackTab to determine whether a figure is attacked or not. Since you are interested in the algorithm this code might give you some insight.

Unfortunately I don'get the syntax highlighting to work.

MoveGenerator

MODULE MoveGenerator;
{$speed}
{$include: 'types.inc'}
VAR [EXTERN]
{$include: 'var.inc'}

{
± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ±

  MOVGEN.CH  include module for SCHACH.PAS
  Last modified:  01/12/85

  This module contains the Move generator and various other
  procedures.

± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ±
}

{ Tables for calculating whether a Piece Attacks a Square }
TYPE
  SetOfPiece = BYTE;
  BitTabType = ARRAY[King..Pawn] OF SetOfPiece;
CONST
  BitTab =BitTabType (1,2,4,8,#10,#20);

VAR   { A constant, which is calculated in CalcAttackTab.
        Gives the squares which a Piece in the middle of the
        table can Move to }
      AttackTab : ARRAY[-#77..#77] OF
                    RECORD
                       { A set of King..Pawn.
                         Gives the Pieces, which can
                         Move to the Square }
                       PieceSet :  SetOfPiece;
                       Direction: INTEGER;  { The Direction from
                                              the Piece to the Square }
                    END;

PROCEDURE CalcAttackTab;
{ Calculates AttackTab }
VAR   Dir:    DirType;
      Sq :   INTEGER;
       i :   BYTE;
BEGIN
   FOR Sq:=-#77 TO #77 DO
      WITH AttackTab[Sq] DO
      BEGIN
         PieceSet:=0;
         Direction:=0;
      END; { with }
   FOR Dir:=7 DOWNTO 0 DO
   BEGIN
      FOR i:=1 TO 7 DO
         WITH AttackTab[DirTab[Dir]*i] DO
         BEGIN
            IF Dir<4 THEN
               PieceSet:=BitTab[Queen]+BitTab[Rook]
            ELSE
               PieceSet:=BitTab[Queen]+BitTab[Bishop];
            Direction:=DirTab[Dir];
         END;
      WITH AttackTab[DirTab[Dir]] DO
         PieceSet:=PieceSet+BitTab[King];
      WITH AttackTab[KnightDir[Dir]] DO
      BEGIN
         PieceSet:=BitTab[Knight];
         Direction:=KnightDir[Dir];
      END;
   END;
END; { CalcAttackTab }

FUNCTION PieceAttacks(APiece : PieceType;
                      AColor : ColorType;
                      ASquare,
                      Square :  SquareType) : BOOLEAN;
{ Calculates whether APiece placed On ASquare Attacks the Square }
VAR   Sq : EdgeSquareType;
BEGIN
   IF APiece = Pawn THEN
      { Pawn Attacks }
      PieceAttacks := abs(Square - ASquare - PawnDir[AColor]) = 1
   ELSE
      { Other Attacks: Can the Piece Move to the Square? }
      WITH AttackTab[Square - ASquare] DO
         IF (PieceSet AND BitTab[APiece]) <> 0 THEN
            IF (APiece = King) OR (APiece = Knight) THEN
               PieceAttacks := TRUE
            ELSE
            BEGIN
               { Are there any blocking Pieces in between? }
               Sq := ASquare;
               REPEAT
                  Sq := Sq + Direction;
               UNTIL (Sq = Square) OR (Board[Sq].Piece <> Empty);
               PieceAttacks := Sq = Square;
            END
         ELSE
            PieceAttacks := FALSE;
END { PieceAttacks };

FUNCTION Attacks(AColor : ColorType;   Square : SquareType) : BOOLEAN;
{ Calculates whether AColor Attacks the Square }

FUNCTION PawnAttacks(AColor: ColorType; Square: SquareType):
            BOOLEAN;
{ Calculates whether AColor Attacks the Square with a Pawn }
VAR   Sq: EdgeSquareType;
BEGIN
   PawnAttacks:=TRUE;
   Sq := Square - PawnDir[AColor] - 1;   { Left Square }
   IF (Sq AND #88) = 0 THEN
      WITH Board[Sq] DO
         IF (Piece = Pawn) AND (Color = AColor) THEN RETURN;
   Sq := Sq + 2;                       { Right Square }
   IF (Sq AND #88) = 0 THEN
      WITH Board[Sq] DO
         IF (Piece = Pawn) AND (Color = AColor) THEN RETURN;
   PawnAttacks := FALSE;
END; { PawnAttacks }


VAR   i :  IndexType;

BEGIN { Attacks }
   Attacks := TRUE;
   IF PawnAttacks(AColor,Square) THEN   { Pawn Attacks }
      RETURN;
   { Other Attacks:  Try all Pieces, starting with the smallest }
   FOR i := OfficerNo[AColor] DOWNTO 0 DO
      WITH PieceTab[AColor,i] DO
         IF IPiece <> Empty THEN
            IF PieceAttacks(IPiece,AColor,ISquare,Square) THEN
              RETURN;
   Attacks := FALSE;
END { Attacks };



PROCEDURE CalcCastling(InColor : ColorType; VAR Cast : CastType);
{ Calculates whether InColor can castle }

FUNCTION Check(Square : SquareType; InPiece : PieceType) : BOOLEAN;
{ Checks whether InPiece is placed On Square and has never moved }
VAR
  Dep : DepthType;
BEGIN
  Check := FALSE;
  WITH Board[Square] DO                           { Check Square }
    IF (Piece = InPiece) AND (Color = InColor) THEN
    BEGIN
      Dep := Depth - 1;                            { Check all moves }
      WHILE MovTab[Dep].MovPiece <> Empty DO
      BEGIN
        IF MovTab[Dep].New1 = Square THEN RETURN;
        Dep := Dep - 1;
      END;
      Check := TRUE;
    END;
END; { Check }

VAR   Square : SquareType;
BEGIN
   Square := 0;
   IF InColor = Black THEN Square := #70;
   Cast :=[];
   IF Check(Square + 4,King) THEN
   BEGIN                                                        { Check King }
      IF Check(Square  ,Rook) THEN Cast := Cast +[Long];      { Check a-Rook }
      IF Check(Square + 7,Rook) THEN Cast := Cast +[Short];   { Check h-Rook }
   END;
END { CalcCastling };

FUNCTION RepeatMove(MOVE : MoveType) : BOOLEAN;
{ Check if Move is a Pawn Move or a capture }
BEGIN
  WITH MOVE DO
    RepeatMove := (MovPiece <> Empty) AND (MovPiece <> Pawn)
                 AND (Content = Empty) AND NOT Spe;
END; { RepeatMove}

FUNCTION FiftyMoveCnt : INTEGER;
{ Counts the Number of moves since Last capture or Pawn Move.
  The game is a Draw when FiftyMoveCnt = 100 }
VAR   Cnt : INTEGER;
BEGIN
  Cnt := 0;
  WHILE RepeatMove(MovTab[Depth - Cnt]) DO
    Cnt := Cnt + 1;
  FiftyMoveCnt := Cnt;
END;

FUNCTION Repetition(Immediate : BOOLEAN) : INTEGER;
{ Calculates how many times the position has occured before.
  The game is a Draw when Repetition = 3.
  MovTab[Back..Depth] contains the previous moves.
  When Immediate is set, only Immediate Repetition is checked }

VAR   LastDep,CompDep,TraceDep,CheckDep,SameDepth : DepthType;
      TraceSq,CheckSq : SquareType;
      RepeatCount : INTEGER;
LABEL 10;
BEGIN
   Repetition := 1;
   RepeatCount := 1;
   SameDepth := Depth + 1;                     { Current position }
   CompDep := SameDepth - 4;          { First position to compare }
   LastDep := SameDepth;
   { MovTab[LastDep..Depth] contains previous relevant moves  }
   WHILE RepeatMove(MovTab[LastDep - 1]) AND
         ((CompDep < LastDep) OR NOT Immediate) DO
      LastDep := LastDep - 1;
   IF CompDep < LastDep THEN RETURN;     { No Repetition Possible }
   CheckDep := SameDepth;
   REPEAT
      CheckDep := CheckDep - 1;           { Get Next Move to test }
      CheckSq := MovTab[CheckDep].New1;
      TraceDep := CheckDep + 2;          { Check if Move has been }
      WHILE TraceDep < SameDepth DO
      BEGIN
        IF MovTab[TraceDep].Old = CheckSq THEN GOTO 10;
        TraceDep := TraceDep + 2;
      END;

      { Trace the Move backward to see whether
        it has been 'undone' earlier }
      TraceDep := CheckDep;
      TraceSq := MovTab[TraceDep].Old;
      REPEAT
         IF TraceDep - 2 < LastDep THEN RETURN;
         TraceDep := TraceDep - 2;
         WITH MovTab[TraceDep] DO  { Check if Piece has been moved before }
            IF TraceSq = New1 THEN
               TraceSq := Old;
      UNTIL (TraceSq = CheckSq) AND (TraceDep <= CompDep + 1);
      IF TraceDep < CompDep THEN                      { Adjust evt. CompDep }
      BEGIN
        CompDep := TraceDep;
        IF ODD(SameDepth - CompDep) THEN
        BEGIN
          IF CompDep = LastDep THEN RETURN;
          CompDep := CompDep - 1;
        END;
        CheckDep := SameDepth;
      END;
   { All moves between SameDepth and CompDep have been checked,
     so a Repetition is Found }
   10 : IF CheckDep <= CompDep THEN
      BEGIN
         RepeatCount := RepeatCount + 1;
         Repetition := RepeatCount;
         IF CompDep - 2 < LastDep THEN RETURN;
         SameDepth := CompDep;               { Search for more repetitions }
         CompDep := CompDep - 2;
         CheckDep := SameDepth;
      END;
   UNTIL FALSE;
END { Repetition };

FUNCTION KillMovGen(MOVE : MoveType) : BOOLEAN;
{ Tests whether a Move is Possible.

   On entry :
      Move contains a full description of a Move, which
      has been legally generated in a different position.
      MovTab[Depth - 1] contains Last performed Move.

   On RETURN :
      KillMovGen indicates whether the Move is Possible
}
VAR   CastSq  : SquareType;
      Promote : PieceType;
      CastDir : CastDirType;
      Cast    : CastType;
BEGIN
   KillMovGen := FALSE;
   WITH MOVE DO
   BEGIN
      IF Spe AND (MovPiece = King) THEN
      BEGIN
         CalcCastling(Player,Cast);         { Castling }
         IF New1 > Old THEN
            CastDir := Short
         ELSE
            CastDir := Long;

         IF CastDir IN Cast THEN   { Has King or Rook moved before? }
         BEGIN
            CastSq := (New1 + Old) DIV 2;
            { Are the squares Empty? }
            KillMovGen := (Board[New1].Piece = Empty) AND
                          (Board[CastSq].Piece = Empty) AND
                             ((New1 > Old) OR
                             (Board[New1 - 1 ].Piece = Empty)) AND
                          { Are the squares unattacked? }
                          NOT Attacks(Opponent,Old) AND
                          NOT Attacks(Opponent,New1) AND
                          NOT Attacks(Opponent,CastSq);
         END;
      END
      ELSE
      IF Spe AND (MovPiece = Pawn) THEN
      BEGIN
         { E.p. capture }
         WITH MovTab[Depth - 1] DO
            { Was the Opponent's Move a 2 Square Move }
            IF MovPiece = Pawn THEN
               IF abs(New1 - Old) >= #20 THEN
                  { Is there a Piece On the Square? }
                  WITH Board[MOVE.Old] DO
                     IF (Piece = Pawn) AND (Color = Player) THEN
                        KillMovGen := MOVE.New1 = (New1 + Old) DIV 2;
      END { if }
      ELSE
      BEGIN
         IF Spe THEN                      { Normal test }
         BEGIN
            Promote := MovPiece;            { Pawnpromotion }
            MovPiece := Pawn;
         END;

         { Is the Content of Old and New1 squares correct? }
         IF (Board[Old].Piece = MovPiece) AND
            (Board[Old].Color = Player) AND
            (Board[New1].Piece = Content) AND
           ((Content = Empty) OR
            (Board[New1].Color = Opponent)) THEN

            IF MovPiece = Pawn THEN             { Is the Move Possible? }
               KillMovGen := (abs(New1 - Old) < #20) OR
                             (Board[(New1 + Old) DIV 2].Piece = Empty)
            ELSE
               KillMovGen := PieceAttacks(MovPiece,Player,Old,New1);
         IF Spe THEN
            MovPiece := Promote;
      END;
   END { with };
END; { KillMovGen }

{ Movegeneration variables }

VAR
      Buffer :        ARRAY[1..80] OF   { Buffer (generated moves) }
                        MoveType;
      BufCount,BufPnt : 0..80;            { Counters for Buffer    }

PROCEDURE InitMovGen;
{ The movegenerator.
  InitMovGen generates all Possible moves and places them
  in a Buffer. MovGen will then Generate the moves One by One and
  place them in Next.

  On entry :
     Player contains the Color to Move.
     MovTab[Depth - 1] the Last performed Move.

  On RETURN :
     Buffer contains the generated moves.

     The moves are generated in the order :
        Captures
        Castlings
        Non captures
        E.p. captures }

PROCEDURE Generate;
   { Stores a Move in Buffer }
BEGIN
  BufCount := BufCount + 1;
  Buffer[BufCount] := Next;
END; { Generate }

PROCEDURE PawnPromotionGen;
{ Generates Pawnpromotion }
VAR   Promote : PieceType;
BEGIN
  WITH Next DO
  BEGIN
    Spe := TRUE;
    FOR Promote := Queen TO Knight DO
    BEGIN
      MovPiece := Promote;
      Generate;
    END;
    Spe := FALSE;
  END;
END; { PawnPromotionGen }

PROCEDURE CapMovGen;
   { Generates captures of the Piece On New1 using PieceTab }
VAR   NextSq,Sq : EdgeSquareType;
  i :  IndexType;
BEGIN
  WITH Next DO
  BEGIN
    Spe := FALSE;
    Content := Board[New1].Piece;
    MovPiece := Pawn;                   { Pawn captures }
    NextSq := New1 - PawnDir[Player];
    FOR Sq := NextSq - 1 TO NextSq + 1 DO IF Sq <> NextSq THEN
    IF (Sq AND #88) = 0 THEN
      WITH Board[Sq] DO
        IF (Piece = Pawn) AND (Color = Player) THEN
        BEGIN
          Old := Sq;
          IF (New1 < 8) OR (New1 >= #70) THEN
            PawnPromotionGen
          ELSE
            Generate;
        END;
         { Other captures, starting with the smallest Pieces }
    FOR i := OfficerNo[Player] DOWNTO 0 DO
      WITH PieceTab[Player,i] DO
        IF (IPiece <> Empty) AND (IPiece <> Pawn) THEN
          IF PieceAttacks(IPiece,Player,ISquare,New1) THEN
          BEGIN
            Old := ISquare;
            MovPiece := IPiece;
            Generate;
          END;
      END { with };
END; { CapMovGen }

PROCEDURE NonCapMovGen;
{ Generates non captures for the Piece On Old }
VAR
   First,Last,Dir : DirType;
   Direction      : INTEGER;
   NewSq          : EdgeSquareType;

LABEL 10;
BEGIN
  WITH Next DO
  BEGIN
    Spe := FALSE;
    MovPiece := Board[Old].Piece;
    Content := Empty;
    CASE MovPiece OF
      King,
      Knight : FOR Dir := 7 DOWNTO 0 DO
               BEGIN
                 IF MovPiece = King
                    THEN NewSq := Old + DirTab[Dir]
                    ELSE NewSq := Old + KnightDir[Dir];
                 IF (NewSq AND #88) = 0 THEN
                   IF Board[NewSq].Piece = Empty THEN
                   BEGIN
                     New1 := NewSq;
                     Generate;
                   END;
               END;
      Queen,
      Rook,
      Bishop : BEGIN
                 First := 7;
                 Last := 0;
                 IF MovPiece = Rook   THEN First := 3;
                 IF MovPiece = Bishop THEN Last := 4;
                 FOR Dir := First DOWNTO Last DO
                 BEGIN
                   Direction := DirTab[Dir];
                   NewSq := Old + Direction;
                   { Generate all non captures in
                         the Direction }
                   WHILE (NewSq AND #88) = 0 DO
                   BEGIN
                     IF Board[NewSq].Piece <> Empty THEN GOTO 10;
                     New1 := NewSq;
                     Generate;
                     NewSq := New1 + Direction;
                   END;
            10 : END;
               END;
      Pawn :   BEGIN
                 New1 := Old + PawnDir[Player];    { One Square forward }
                 IF Board[New1].Piece = Empty THEN
                   IF (New1 < 8) OR (New1 >= #70) THEN
                     PawnPromotionGen
                   ELSE
                   BEGIN
                     Generate;
                     IF (Old < #18) OR (Old >= #60) THEN
                     BEGIN
                       New1 := New1 + (New1 - Old); { Two squares forward }
                       IF Board[New1].Piece = Empty THEN Generate;
                     END;
                   END;
               END;
    END { case };
  END { with };
END; { NonCapMovGen }

VAR
  CastDir : CastDirType;
  Sq      : EdgeSquareType;
  Index   : IndexType;

BEGIN { InitMovGen }
   WITH Next DO                    { Reset the Buffer }
   BEGIN
      BufCount := 0;
      BufPnt := 0;
      { Generate all captures starting with captures of
        largest Pieces }
      FOR Index := 1 TO PawnNo[Opponent] DO
         WITH PieceTab[Opponent,Index] DO
            IF IPiece <> Empty THEN
            BEGIN
               New1 := ISquare;
               CapMovGen;
            END;
      Spe := TRUE;                           { Castling }
      MovPiece := King;
      Content := Empty;
      FOR CastDir := Short DOWNTO Long DO
         WITH CastMove[Player,CastDir] DO
         BEGIN
            New1 := CastNew;
            Old := CastOld;
            IF KillMovGen(Next) THEN Generate;
         END;

      { Generate non captures, starting with pawns }
      FOR Index := PawnNo[Player] DOWNTO 0 DO
         WITH PieceTab[Player,Index] DO
            IF IPiece <> Empty THEN
            BEGIN
               Old := ISquare;
               NonCapMovGen;
            END;
      WITH MovTab[Depth - 1] DO               { E.p. captures }
         IF MovPiece = Pawn THEN
            IF abs(New1 - Old) >= #20 THEN
            BEGIN
               Next.Spe := TRUE;
               Next.MovPiece := Pawn;
               Next.Content := Empty;
               Next.New1 := (New1 + Old) DIV 2;
               FOR Sq := New1 - 1 TO New1 + 1 DO
                 IF Sq <> New1 THEN
                   IF (Sq AND #88) = 0 THEN
                   BEGIN
                     Next.Old := Sq;
                     IF KillMovGen(Next) THEN Generate;
                  END;
            END;
    END { with };
END; { InitMovGen }

PROCEDURE MovGen;
{ Place Next Move from the Buffer in Next.
  Generate ZeroMove when there is No more moves }
BEGIN
   IF BufPnt >= BufCount THEN
      Next := ZeroMove
   ELSE
   BEGIN
      BufPnt := BufPnt + 1;
      Next := Buffer[BufPnt];
   END;
END; { MovGen }

END.

Answer 3

You can download chess with

pip install chess

then you import chess

import chess
#then you make board
board=chess.Board()
#then you have list of moves with following line
moves=list(board.legal_moves)