A move generator takes a chess position as an input and generates a list of ALL the legal moves as output.
This ensures that your program KNOWS all rules of chess. In short a move generator indicates that the rules of chess are coded in the engine. It is a tedious job to encode all rules of chess because chess is a game of complex rules.
A bug free move generator (along with - make_move + unmake_move) is one third job done.
The complexity of the move generator originates out of the complex rules of chess for different pieces in different situations.
Therefore here we have to understand movement of pieces and their characteristics.
Challenges in move generation:
Challenges due to pieces:
In chess a bishop can move in diagonal crosses only.
A rook can move in straight crosses only.
A queen can move like a rook as well as a bishop.
A king can move like the queen. However, only 1 square.
A knight has his own different way of moving.
A pawn is very different and unique rule.
All these rules of chess need to be coded in the chess engine for move generation.
So how it should be done?
We have to break down these rules into some logical classification and implement algorithm.
For this we need to understand the most important aspect of move generation - direction
Directions:
This is the most important aspect of move generation.
A rook and bishop can move in 4 directions, queen, king and knight can move in 8 directions.
A rook will move along straights and a bishop will move along diagonals.
All pieces (except pawns) move in their determined directions independent of their colour.
However, the direction sense of a pawn depends upon its colour.
Black pawns only move down the board.
White pawns can only move up the board.
All other pieces have the same rules irrespective of their colour.
Also a pawn moves in different direction when it is capturing and different direction when its not capturing.
Compared to this all pieces other than pawns, capture in the same direction in which they move.
Thus, move generation of all pieces other than pawns can be handled together and pawn movements need to be handled separately.
In the code (refer data.c), the lookup array offsets gives the number of directions in which each piece can move.
int offsets[6] = {
0, 8, 4, 4, 8, 8
};
This will not be used for pawns (it shows '0' for pawns)
Other important aspect of directions (besides the number of directions) is what are those directions?
A bishop and a rook can both move in 4 different directions but a bishop moves diagonally and rook moves in a cross sign.
A knight moves in a completely different direction sense.
Therefore, we need to encode directions as well.
The encoding of directions depends upon the encoding of squares of the board.
Directions are defined as the change in square indexes when we move along that particular direction.
e.g. if I have to move up the board from a1 to a2 (or b1 to b2), I have to add -8 to the current square index
Thus the direction "NORTH" = -8.
Thus directions are represented as deltas added to the current square index to reach the consequtive square index in that direction.
Below I have given the deltas for all directions.
Note that diagonal directions like SOUTH WEST is equal to SOUTH + WEST.
This is because - it is same as moving 1 step south and then moving 1 step west.
The main reason that the board is a 1 dimensional array and not a 2 dimensional one is because direction encoding depends upon square encoding. If 2 parameters are required to represent a square then 2 parameters would be required to represent a direction.
NORTH -8
SOUTH 8
EAST 1
WEST -1
SOUTH EAST 9
SOUTH WEST 7
NORTH EAST -7
NORTH WEST -9
Directions for the knight:
NORTH NORTH WEST -17
NORTH NORTH EAST -15
EAST EAST NORTH -6
EAST EAST SOUTH 10
SOUTH SOUTH EAST 17
SOUTH SOUTH WEST 15
WEST WEST SOUTH 6
WEST WEST NORTH -10
Sliders and Leapers:
Chess pieces other than pawns are categorised into 2 types:
a. Sliders: Sliders are rook, bishop and queen. Sliders continue to move in the same direction until they encounter the edge of the board or their own colour piece or opponents piece. They are long range pieces.
b. Leapers: Leapers are knight and king. They have only 1 move in each direction. They are short range pieces.
In the code, the lookup array slide returns wether the piece is slider or not.
BOOL slide[6] = {
FALSE, FALSE, TRUE, TRUE, TRUE, FALSE
};
Other Challenges:
Complex Moves:
Castling is a very complex move to implement. First we have to check castling permissions, we have to check that the side to move should not be in check during castling and we have to check that the squares which the king is going through while castling should not be under attack. After that to make a castle move, we need to move 2 pieces.
En-passant is also considered as a complex move because we have to check en-passant flag first. Another aspect which makes en-passant move to be handled separately is that the captured piece does not lie on the destination square of the moving piece.
Pawn promotion is also a complex move because it is actually 4 separate moves. A pawn can get converted to a knight,bishop,rook or queen. Each conversion is considered as a different move.
Influence of king position on move:
A piece that is pinned to the king cannot move in a way that puts the king in check.
Also a king cannot move into a check.
This is cumbersome and time consuming to implement.
In source code to implement this, first the move is made; then it is validated that the side is not in check. If the side is in check after making move, the move is considered to be invalid and taken back.
Because of this limitation, the move generator does not generate only legal moves.
The "king in check" rule cannot be implemented without actually making the move and checking whether the king is in attack or not.
Psuedo - Legal Move Generator
Due to the above complexities discussed, the complete rule checking for move generation is done in 2 stages.
The pseudo legal move generator would necessarily generate all legal moves + it may generate some moves that are not legal.
The move maker will check other rules and return a boolean value of 'true' if the move is legal.
Else it will return false.