Move Generation

1. King

1.1 Basics

As described from the previous page, we can automate the generation of bitboards through calculating all squares around it with values: square << (-9, -8, -7, -1, +1, +7, +8, +9)

But this goes wrong with the king on the edge of the board. Case 1:

King attacks warp / wrap around to the other side. How do we fix this? A simple check to see if the king is on the (bitboard) A file, then remove / stop moves generated on the H file (and vice versa)

Another check should be made to ensure the calculation does not go out of bounds. Simply perform a check something like (square + direction) < 64 && (square + direction) >= 0.

1.2 Attacks

How would we figure out attacks? We can utilize our custom bitwise operations to calculate legal moves from static pieces using pieceLegalMoves & ~ourPieces. Here is an example:

But what about the opponents bishop on b8? After capturing the knight on d6, we put ourselves in check.

We need to see if the move from the king is in check after we move it. To do this, I applied the easist method: Copy the board position and make the move. If the king is in check, the move is illegal, revert the board position back to its original state:

The image above is the correct solution to solving king attacks. For Pseudo-legal move generation which my Chess Engine uses, moves follow piece rules but may leave the king in check, thus needs extra validation after making the move.

There is a slightly faster way to do this via Attack and Defend Maps and pinned pieces map. By keeping an incremental track of where each piece is, what squares it attacks, and pinned pieces, we can reduce move generation time by a lot. For instance, if our rook is absolutely pinned to our king, we cannot move it, so why bother calculating moves when we know they will all put the king in check, thus being illegal.

1.3 Castling

Coming soon...

2. Pawns

1.1 Basics

Pawns, which may look fairly insignificant, actually are quite complex. Let's sequentially go through what moves they can make in bullet points:

• Pawns cannot go on rank 1 or 8 (either is a promotion / illegal)
• Starting rank, pawns can move 1 or 2 squares forward (double move)
• Pawns can capture either left or right diagonally in front of them
• When a pawn reaches the 2nd to last rank, it can promote to a Knight, Bishop, Rook, or Queen
• After doing a double move on their first turn, the square behind them becomes the "en passant" square for one turn only, where an opposing pawn can capture one square behind them IF it is directly beside it.

We need two separate precomputed tables otherwise black pawns would be promoting where white pawns are. Using the same principles as before for captures (this time forward diagonal ones), we can get our precomputed pawn moves (however double pawn pushes & en passants are calculated manually, as for pawn move generation they would be mostly redundant since they happen only once)

1.2 Examples

Validation & Test Positions

1. Perft

Heard of it before? It stands for "Performance test", and chess engine developers LOVE it. To put simply, when you designed your move generator, how would you know it actually works on a larger scale? That's where perft comes in.

1.1 Iterative deepening & bottlenecks

In my own engine, I created a function with parameter depth. Assuming I called perft(6), it would first generate all moves, copy the board state, and make each (legal) move, and call perft(depth - 1) and revert the board position. By doing this, it would go through every single move in the current position.

Depth 6 for the starting position is fine (for me) as the time is fairly short. When going to depth perft(7), the number of moves grow so exponential that the time taken is 26 times more than perft(6) completion time!! Later on, I will show you how your chess engine can cut down on searches through pruning techniques and position evaluation.

2. Test Positions & Results

Having found Position Perft Results, I incorporated most of those positions from the Chess Programming Main Page into my engine with their final results (nodes calculated) for testing. The page has varied test positions with useful information and variation in each position.

Some of the positions here have even highlighted bugs found in old chess engines, which the starting position was sometimes not enough for a valid, reliable perft. The positions tested captures, castling, promotions, checks, discovered checks, double checks, and checkmates.

Running my Chess Engine, here are the correct results for the following chess positions:

Performance test results for rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1:

Performance test results for r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

Performance test results for 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -:

Performance test results for r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1:

Performance test results for r2q1rk1/pP1p2pp/Q4n2/bbp1p3/Np6/1B3NBn/pPPP1PPP/R3K2R b KQ - 0 1:

Performance test results for rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8:

Performance test results for r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10: