Generating Moves

Move generation is one of the most time consuming task a chess engine has to do.  It's main job is to build a set (or partial set) of moves at a given position for the search algorithm to dive into.

There are several types of move generators used in KKFChess for:

• Pseudo legal capturing moves and promotions (both capturing and non-capturing)

• Pseudo legal non-capturing moves and/or non-capturing promotions (caller selectable)

• All pseudo legal moves

• Legal capturing moves with promotions (both capturing and non-capturing)

• Legal non-capturing moves with non-capturing promotions

• Legal moves

• Pseudo check evasions and blocks

• Drop moves (for crazyhouse)

Some of these generators can generate moves only for a given set of pieces.  The most frequently used ones are the pseudo legal generators which are used mainly during non-root searches.  Legal moves are always generated at root.

For a normal chess game, KKFChess will generate and search "material gaining" moves first before the "non-material gaining" ones.  Material gaining moves are capturing or promoting moves.  Non-material gaining moves are non-capturing and non-promoting moves.

Pawn Moves

Pawn moves are generated using the bitboard method.  First, the targets (either empty square or squares with enemy pieces) are identified then each each of these squares a move is created.  Special moves like the first pawn move, en passant and promotions are also generated.

The trick of using the "sideways" bitboard comes into play when generating pawn captures.  Suppose there are white pawns on a4, f4 and h4 and black pieces at b5 and g5.  The bit pattern for the white and black are:

The square that the white pawns can capture "into" are found by shifting the white pawns' pattern left by 9 and right by 7, giving:

Note that the shifting automatically handles the attack squares for pawns on the a and h-file and no special coding is needed. This is exactly why a "rotate" bitmap is used instead of a "normal" bitboard (try it yourself - you'll have unwanted bits from the a or h-file after shifting if not handled properly).

Knight Moves

To generate the knight moves, each knight is picked off the knight's bitboard and perform a simple square sweep on the array board.  An attack mask is used for finding possible captures before looking into the board array when generating captures.

Sliding Piece Moves

As KKFChess don't have all the rotated bitboards, it generate moves for sliding pieces with a direction scan on the array board.  I found the speed acceptable since in most positions the "range" of sliding pieces are very small.  An attack mask is used for finding possible captures before looking into the board array when generating captures.

King Moves

As with the knight moves king moves are generated by scanning the 8 squares next to the king.  Castling moves are generated, depending on the castling rights and the enemy control of the path of the king.

King captures are not generated for atomic chess since they are illegal.

Crazyhouse Drop Moves

Drops moves are easy to generate, just place a piece you are holding and place it on any empty square with exception that pawns cannot be place on the first or last rank.  Drop moves can be used to block checks.

Pseudo Check Evasions and Blocks

This generator first finds out what pieces are attacking the king and their directions (for sliding pieces).  If there are 2 or more attackers on the king, only king moves are generated, otherwise a king move, a blocking move or a move that captures the checking piece is generated.  Unblockable checks by non-sliding pieces are also handled.

Checking For Legal Moves

In a normal game of chess, moving a king into check is illegal but for variants like suicide and atomic allows moves that leave the king(s) to be attacked.

Since a king is just a regular piece in suicide chess, hence no checks are possible and all moves generated are legal apart from those that do not capture a piece if a capture is possible.

For atomic chess, the two kings can actually touch since in such a position, a direct capture of the the enemy king will cause own king to be caught in the explosion.  This implies that kings cannot capture enemy pieces either.  Another rule of atomic chess allows you to leave you king attacked if your next move will win the game by capturing or exploding the enemy king the attacking piece.

For losers chess, one must capture if there are legal capturing moves, just like suicide chess.  King checks must be dealt with like normal chess, the king can be checkmated.

Special code had been implemented to detect whether a move will expose the king to a check by looking at possible attacker along the line of the king and the moving piece after the move is made..