Move geneartion for non sliding pieces - Jonas-DaiMa/chess-game Wiki

This page contains descriptions of the general logic behind finding possible moves for all non-sliding pieces. Those pieces are kings, knights and pawns

Prerequisites to follow along:

White Pawn Moves

A white pawn has 4 possible moves that it can make initially:

       2
    3  1  4
       P

It can move 1 or 2 steps forward as well as an attack on the diagonal left or right. Moving forward requires there to be no opponent or own pieces in front of it. If the pawn has already moved once, it can no longer move two squares forward per move. Attacking on the diagonal requires that an opponent piece is placed on that diagonal.

It can be summed up to these 4 moves:

In the pawn-bitboard below, we want to simulate all its possible moves. We do so by setting the bit at every possible move position from the pawns current position.

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  0  0
3  0  0  0  1  0  0  0  0
2  0  1  0  0  0  0  1  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H

Finding Possible moves

Since there are 4 possible pawn moves these bits can basically be simulated with 4 bitshift operations.

Single-push

To simulate the pawn moving one step forward, we can bitshift the pawn bitboard 8 to the left. (Pawn-bitboard << 8) We also need to make sure there are currently no other pieces blocking this square. - (Pawn-bitboard << 8) & empty-squares

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  1  0  0  0  0
3  0  1  0  0  0  0  1  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  1  1  0  0  0  0  0
6  1  1  1  1  1  1  1  1
5  1  1  1  1  1  1  1  1
4  1  0  1  1  1  1  1  1
3  1  1  0  0  1  1  1  1
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  1  0  0  0  0
3  0  1  0  0  0  0  1  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H

Double-push

Simulating double-push is not as simple as bit-shifting by 16. If we only bitshift 16, we do not account for a blocking piece on the square right in front. Therefore the possibility of moving two steps is dependent on if single-push is possible. If so we can bitshift an additional 8 bits to the left (single-push << 8). Double-move is only possible if the pawn is located on its initial square. To account for this we can check if the result of single-push is on rank 3 ((single-push & rank3) << 8). To also account for possible blocking pieces we use bit-wise on empty-squares ((Single-push & Rank-3) << 8) & Empty-squares.

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  1  0  0  0  0
3  0  1  0  0  0  0  1  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  0  0
3  1  1  1  1  1  1  1  1
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  0  0
3  0  1  0  0  0  0  1  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  1  0  0  0  0  1  0
3  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  1  1  0  0  0  0  0
6  1  1  1  1  1  1  1  1
5  1  1  1  1  1  1  1  1
4  1  0  1  1  1  1  1  1
3  1  1  0  0  1  1  1  1
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  1  0
3  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H

Diagonal left attack

Simulating left diagonal attack is very similar to single push. Instead of bitshifting 8 to the left, we instead bitshift by 9. (Pawn-bitboard << 9) This simmulates the piece has moved one square up and left. Then we also need to take into account if an opponent piece is already there. ((Pawn-bitboard << 9)& Opponent-pieces) We cannot attack if there is no opponent piece.

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  0  0
3  0  0  0  1  0  0  0  0
2  1  1  0  0  0  0  1  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  1  1  1  1  1  1  1  1
7  1  0  0  1  0  1  1  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  1  0  0  1
3  0  1  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  0  0  0  1
3  1  0  0  0  0  1  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  1  1  1  1  1  1  1  1
7  1  0  0  1  0  1  1  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  1  0  0  1
3  0  1  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  0  0  0  1
3  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  0  0  0  1
3  1  0  0  0  0  1  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  1  1  1  1  1  1  1  0
7  1  1  1  1  1  1  1  0
6  1  1  1  1  1  1  1  0
5  1  1  1  1  1  1  1  0
4  1  1  1  1  1  1  1  0
3  1  1  1  1  1  1  1  0
2  1  1  1  1  1  1  1  0
1  1  1  1  1  1  1  1  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  1  0  0  1
3  0  1  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  0  0  0  0
3  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H

Diagonal right attack

Diagonal right is very similar to diagonal left. The only difference is that here we bitshift by 7 (Pawn bitboard << 7). We also have to be aware of pawns on the H file this time. A pawn on the H file has no diagonal to its right, we therefore have to make use of a not-A-file bitboard similar to not-H-file bitboard used above. We then end up with the following operation ((Pawn bitboard << 9) & not-A-file & Opponent pieces)

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  1  0  0  0
3  0  1  1  0  0  0  0  1
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  1  1  1  1  1  1  1
7  0  1  1  1  1  1  1  1
6  0  1  1  1  1  1  1  1
5  0  1  1  1  1  1  1  1
4  0  1  1  1  1  1  1  1
3  0  1  1  1  1  1  1  1
2  0  1  1  1  1  1  1  1
1  0  1  1  1  1  1  1  1
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  1  0  0  1
3  0  1  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  1  0  0  0
3  0  1  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H

En passant

TODO

Final board

Now we've calculated all possible pawn moves. We can now use the bitwise or operator to combine all moves into one bitboard: For black pawns the same rules apply, its just the opposite. If you want to simulate moving one piece, you instead have bitshift 8 to the right and so on.

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  1  0  0  0  0
3  0  1  0  0  0  0  1  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  1  0
3  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  0  0  0  0  0
3  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  1  0  0  0
3  0  1  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  1  1  1  0  1  0
3  0  1  0  0  0  0  1  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H

lookup-king-moves

A king can move in 8 different directions

           1  2  3
           8  K  4
           7  6  5

A king can move in any of these directions as long as there is non of its own pieces on that square already and doing so will not result in moving to a square attacked by an opponent piece(check). The move generation of kings are much similar to the move generation of pawns. Therefore this section will go in much less detail than the pawns description.

Finding possible moves

Calculating each move is fairly simple and requires only 4 bitboards

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  0  0
3  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  1  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  0  0
3  0  0  0  1  0  0  0  0
2  0  1  0  0  1  0  1  0
1  0  0  0  0  1  0  0  0
   A  B  C  D  E  D  G  H
8  0  1  1  1  1  1  1  1
7  0  1  1  1  1  1  1  1
6  0  1  1  1  1  1  1  1
5  0  1  1  1  1  1  1  1
4  0  1  1  1  1  1  1  1
3  0  1  1  1  1  1  1  1
2  0  1  1  1  1  1  1  1
1  0  1  1  1  1  1  1  1
   A  B  C  D  E  D  G  H
8  1  1  1  1  1  1  1  0
7  1  1  1  1  1  1  1  0
6  1  1  1  1  1  1  1  0
5  1  1  1  1  1  1  1  0
4  1  1  1  1  1  1  1  0
3  1  1  1  1  1  1  1  0
2  1  1  1  1  1  1  1  0
1  1  1  1  1  1  1  1  0
   A  B  C  D  E  D  G  H

To avoid moving outside of the board just like with pawns, we utilize some helper bitboards not-H-file and not-A-file. If the king is on A, we don't want to calculate positions to the left and if the king is on H we do not want to calculate positions to the right (Since they will be off the board).

See the directions page to get an overview of the number of bitshifts to calculate a move in a specific direction.

This is how each single move is calculated:

  1. ((king bitboard & not-A-file) << 9)
  2. (king bitboard << 8)
  3. ((king bitboard & not-H-file) << 7)
  4. ((king bitboard & not-H-file) >>> 1)
  5. ((king bitboard & not-H-file) >>> 9)
  6. (king bitboard >>> 7)
  7. ((king bitboard & not-A-file) >>> 7)
  8. ((king bitboard & not-A-file) << 1)

Last but not least each we need to make sure that there is not one of our own pieces on those squares. The way we can do that is by taking the inverse of Own pieces bitboard using the bitwise NOT operator '~' (~Own pieces bitboard)

Then we can use the bitwise and operator '&' to remove all moves where our own pieces already are located

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  0  0
3  0  0  0  0  0  0  0  0
2  0  0  0  1  1  1  0  0
1  0  0  0  1  0  1  0  0
   A  B  C  D  E  D  G  H
8  1  1  1  1  1  1  1  1
7  1  1  1  1  1  1  1  1
6  1  1  1  1  1  1  1  1
5  1  1  1  1  1  1  1  1
4  1  1  1  1  1  1  1  1
3  1  1  1  0  1  1  1  1
2  1  0  1  1  0  1  0  1
1  1  1  1  1  0  1  1  1
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  0  0  0  0  0  0
4  0  0  0  0  0  0  0  0
3  0  0  0  0  0  0  0  0
2  0  0  0  1  0  1  0  0
1  0  0  0  1  0  1  0  0
   A  B  C  D  E  D  G  H

lookup-knight-moves

A knight can move in 8 different directions

          2       3
      1               4
              N
      8               5
          7       6

A knight can move in any of these directions as long as there is non of its own pieces on that square already.

Finding possible moves

Calculating each move is fairly simple and requires only 6 bitboards

8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  1  0  0  0  0  0
4  0  0  0  0  0  0  1  0
3  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  0  0  0  0  0  0  0
6  0  0  0  0  0  0  0  0
5  0  0  1  0  0  0  0  0
4  0  0  0  0  0  0  1  0
3  0  0  0  1  0  0  0  0
2  0  1  0  0  1  0  1  0
1  0  0  0  0  1  0  0  0
   A  B  C  D  E  D  G  H
8  0  1  1  1  1  1  1  1
7  0  1  1  1  1  1  1  1
6  0  1  1  1  1  1  1  1
5  0  1  1  1  1  1  1  1
4  0  1  1  1  1  1  1  1
3  0  1  1  1  1  1  1  1
2  0  1  1  1  1  1  1  1
1  0  1  1  1  1  1  1  1
   A  B  C  D  E  D  G  H
8  0  0  1  1  1  1  1  1
7  0  0  1  1  1  1  1  1
6  0  0  1  1  1  1  1  1
5  0  0  1  1  1  1  1  1
4  0  0  1  1  1  1  1  1
3  0  0  1  1  1  1  1  1
2  0  0  1  1  1  1  1  1
1  0  0  1  1  1  1  1  1
   A  B  C  D  E  D  G  H
8  1  1  1  1  1  1  1  0
7  1  1  1  1  1  1  1  0
6  1  1  1  1  1  1  1  0
5  1  1  1  1  1  1  1  0
4  1  1  1  1  1  1  1  0
3  1  1  1  1  1  1  1  0
2  1  1  1  1  1  1  1  0
1  1  1  1  1  1  1  1  0
   A  B  C  D  E  D  G  H
8  1  1  1  1  1  1  0  0
7  1  1  1  1  1  1  0  0
6  1  1  1  1  1  1  0  0
5  1  1  1  1  1  1  0  0
4  1  1  1  1  1  1  0  0
3  1  1  1  1  1  1  0  0
2  1  1  1  1  1  1  0  0
1  1  1  1  1  1  1  0  0
   A  B  C  D  E  D  G  H

Calculating the moves of knights share the same problems as with pawns and kings. Moving outside the board is a real possibility and since the pawn can move two squares to either direction, it can now occour on the H G A and B files. To avoid moving outside of the board we utilize some helper bitboards not-H-file, not-HG-file, not-AB-file, and not-AB-file. If the knight is on A, we don't want to calculate positions to the left and if the knight is on H we do not want to calculate positions to the right (Since they will be off the board).

See the directions page to get an overview of the number of bitshifts to calculate a move in a specific direction.

This is how each single move is calculated:

  1. ((knight bitboard & not-AB-file) << 10)
  2. ((knight bitboard & not-A-file) << 17)
  3. ((knight bitboard & not-H-file) << 15)
  4. ((knight bitboard & not-HG-file) << 6)
  5. knight-so-e-e ((knight bitboard & not-HG-file) >>> 10)
  6. knight-so-so-e ((knight bitboard & not-H-file) >>> 17)
  7. knight-so-so-w ((knight bitboard & not-A-file) >>> 15)
  8. knight-so-w-w ((knight bitboard & not-AB-file) >>> 6)

Last but not least each we need to make sure that there is not one of our own pieces on those squares. The way we can do that is by taking the inverse of Own pieces bitboard using the bitwise NOT operator '~' (~Own pieces bitboard)

Then we can use the bitwise and operator '&' to remove all moves where our own pieces already are located

8  0  0  0  0  0  0  0  0
7  0  1  0  1  0  0  0  0
6  1  0  0  0  1  1  0  1
5  0  0  0  0  1  0  0  0
4  1  0  0  0  1  0  0  0
3  0  1  0  1  1  0  0  0
2  0  0  0  0  0  1  0  1
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H
8  1  1  1  1  1  1  1  1
7  1  1  1  1  1  1  1  1
6  1  1  1  1  1  1  1  1
5  1  1  0  1  1  1  1  1
4  1  1  1  1  1  1  0  1
3  1  1  1  0  1  1  1  1
2  1  0  1  1  0  1  0  1
1  1  1  1  1  0  1  1  1
   A  B  C  D  E  D  G  H
8  0  0  0  0  0  0  0  0
7  0  1  0  1  0  0  0  0
6  1  0  0  0  1  1  0  1
5  0  0  0  0  1  0  0  0
4  1  0  0  0  1  0  0  0
3  0  1  0  0  1  0  0  0
2  0  0  0  0  0  1  0  1
1  0  0  0  0  0  0  0  0
   A  B  C  D  E  D  G  H