An efficient move generator is an essential part of a strong chess engine. The rules of chess determine the movement of different pieces. Most pieces move quite nicely, but there are expections which make the implementation of a move generator more difficult than it would be without them. The purpose of this post is to examine how to pieces move and how to implement a generic move generator.
But first, it is appropriate to mention here that it is not always necessary to generate all moves for all positions during the search. Many chess engines do this, while others generate the moves in stages like: checks, captures, other moves. If the search fails high after a move, it is not necessary to go through all the rest of the moves and the effort used when generating them is wasted. On the other hand, generating one move at a time will probably be difficult and add extra instructions. However, in zero window search, it can be so that only one move is searched at every other ply. It would be possible to use separate move generation routines for every other ply then. But for simplicity, we try to construct a generic move generator.
It would be nice to have a move generator without branching. This is difficult, but I think it can be done. If the branching cannot be avoided, the threads inside a warp will have to execute all the branches in many cases. Some of the benefits of parallellism are then lost. So we try to replace ifs with table lookups. That is why we need to see if the piece movement can be generalized. The following table lists some properties of the pieces:
| Piece | Sliding | Directions | Max. moves | Specialities |
|---|---|---|---|---|
| Pawn | No | 3 | 4 | Capture and non-capture different, promotion, double move, en passant |
| Knight | No | 8 | 8 | |
| Bishop | Yes | 4 | 13 | |
| Rook | Yes | 4 | 14 | Castling |
| Queen | Yes | 8 | 27 | |
| King | No | 8 | 8 | Castling, checks |
So basically, pawns are the nastiest pieces and kings are also bad. Majority of the problems with the kings can be avoided by loosening the requirements. Checks can be handled separately and not as a part of move generation.
Generic move rules could consist of the piece to move, change in the board index (= direction), maximum steps it can "slide" (this equals one for non-sliding pieces), a condition for the move to be valid, and an extra action to take in addition to moving the piece. This leads to a table like:
| Piece | Direction | Max. steps | Condition | Action |
|---|---|---|---|---|
| Pawn | -8 | 1 | Destination square empty | |
| Pawn | -16 | 1 | Only 2nd row pawn, destination square and middle square empty | Set EP square |
| Pawn | -7 | 1 | Destination square occupied by enemy piece or EP square | |
| Pawn | -9 | 1 | Destination square occupied by enemy piece or EP square | |
| Pawn | -8 | 1 | 7th row pawn, destination square empty | Change to knight |
| Pawn | -8 | 1 | 7th row pawn, destination square empty | Change to bishop |
| Pawn | -8 | 1 | 7th row pawn, destination square empty | Change to rook |
| Pawn | -8 | 1 | 7th row pawn, destination square empty | Change to queen |
| Pawn | -7 | 1 | 7th row pawn, destination square occupied by enemy piece | Change to knight |
| Pawn | -7 | 1 | 7th row pawn, destination square occupied by enemy piece | Change to bishop |
| Pawn | -7 | 1 | 7th row pawn, destination square occupied by enemy piece | Change to rook |
| Pawn | -7 | 1 | 7th row pawn, destination square occupied by enemy piece | Change to queen |
| Pawn | -9 | 1 | 7th row pawn, destination square occupied by enemy piece | Change to knight |
| Pawn | -9 | 1 | 7th row pawn, destination square occupied by enemy piece | Change to bishop |
| Pawn | -9 | 1 | 7th row pawn, destination square occupied by enemy piece | Change to rook |
| Pawn | -9 | 1 | 7th row pawn, destination square occupied by enemy piece | Change to queen |
| Knight | -17 | 1 | ||
| Knight | -15 | 1 | ||
| Knight | -10 | 1 | ||
| Knight | -6 | 1 | ||
| Knight | 6 | 1 | ||
| Knight | 10 | 1 | ||
| Knight | 15 | 1 | ||
| Knight | 17 | 1 | ||
| Bishop | -9 | 7 | ||
| Bishop | -7 | 7 | ||
| Bishop | 7 | 7 | ||
| Bishop | 9 | 7 | ||
| Rook | -8 | 7 | Clear a castling flag | |
| Rook | -1 | 7 | Clear a castling flag | |
| Rook | 1 | 7 | Clear a castling flag | |
| Rook | 8 | 7 | Clear a castling flag | |
| Queen | -9 | 7 | ||
| Queen | -8 | 7 | ||
| Queen | -7 | 7 | ||
| Queen | -1 | 7 | ||
| Queen | 1 | 7 | ||
| Queen | 7 | 7 | ||
| Queen | 8 | 7 | ||
| Queen | 9 | 7 | ||
| King | -9 | 1 | Clear castling flags | |
| King | -8 | 1 | Clear castling flags | |
| King | -7 | 1 | Clear castling flags | |
| King | -1 | 1 | Clear castling flags | |
| King | 1 | 1 | Clear castling flags | |
| King | 7 | 1 | Clear castling flags | |
| King | 8 | 1 | Clear castling flags | |
| King | 9 | 1 | Clear castling flags | |
| King | -2 | 1 | Long castling allowed | Clear castling flags, move rook |
| King | 2 | 1 | Short castling allowed | Clear castling flags, move rook |
The moves could be generated by look ups to such a table. In addition, it is required that the destination square is not off the board. Implementing the conditions is the hard part. Usually they can be formulated as tests if certain bits are set. The actions in the table can be seen as removing one piece and adding another piece.
To avoid ifs in the control flow, a move can be made so that if the condition is false, the move has no effect on any variable. Otherwise the move is made and the appropriate variables are updated. When returning from the search, the move is undone, and the execution continues from the next move at the previous level. The return pointer is then actually an index to the move generation table.
All this might sound confusing, but to avoid branching, I think this is necessary.
No comments:
Post a Comment