top of page
Search

Piece Movement Part 3: Pseudo-Legal Move Generation

  • Writer: Sam Lench
    Sam Lench
  • 6 days ago
  • 5 min read

In the last two posts I covered lookup tables and then magic bitboards. This is required knowledge for this blog post as move generation relies on these.


What is Move Generation?

Now that I've gone over lookup tables and magic bitboards, we know where each piece can attack at any square on the board. This makes move generation a lot easier and more efficient.


Move generation consists of:

  • Find which pieces can move

  • Filter where they can move

  • Filter based on rules (Can't capture own pieces, checks, pins, etc)


This is split into:

  • Pseudo-Legal Moves - Ignore king safety.

  • Legal Moves - Make sure king is not left in check.


This post will focus on pseudo-legal move generation as this is most commonly done before filtering the moves based on king safety. The next post will go over filtering into legal moves.


Representing Moves

To generate moves, we first need to know how a move can be represented in code. There are a few different pieces of information that is necessary here:

  • Where is the piece moving from?

  • Where is the piece going?

  • Is a piece being captured?

  • Is a pawn being promoted?

  • Is the move castling or en passant?


There are a few ways to represent a move. In this blog post I will use a struct.

They can also be represented with a packed integer for better memory efficiency. However, move generation is rarely the bottleneck in a chess engine whilst a struct improves code readability and makes debugging easier.


If you are aiming to make a highly competitive chess engine or you are memory bound, packed integers could be useful for you.

struct Move
{
	int StartingPos;
	int TargetPos;

	bool IsCapture;

	//flags go here 
	//these will be covered in a future blog post

	public Move(int from, int to, bool isCapture)
	{
		StartingPos = from;
		EndingPos = to;
		IsCapture = isCapture;
	}
}

Iterating Over Pieces

Instead of iterating over all 64 squares, we can only look at squares where we know a piece is by iterating over the bits in the bitboard.


To do this, we use a bitscan. This will remove and return the index of the least significant bit, allowing us to only loop over the pieces that exist on the board. I won't go too much into how this works here, but you can view my code for it here. 

ulong knights = whiteKnights;

while(knights)
{
	int knightSquareIndex = PopLeastSignificantBit(ref knights);

	//generate moves for this knight
}

Generating Knight and King Moves

This is the most simple moves to generate, just use the lookup tables.

ulong attacks = knightAttacks[knightSquareIndex];
ulong moves = attacks & ~ownPieces; //make sure cannot capture own pieces

//we can further split this into captures and quiet moves if we want to

ulong captures = moves & enemyPieces; 	//captures only
ulong quietMoves = moves & ~enemyPieces; //non-capture moves only

Splitting the moves seems useless at first, but when we get into Alpha-beta pruning this becomes crucial. I'll go over this in a later blog post, but it all comes down to efficiency in finding the best move for the AI.


Generating Pawn Moves

Pawns are the most complex piece to generate moves for due to the many rules they have to follow:

  • Move forwards, but cannot capture forwards

  • Can capture diagonally, but not move diagonally

  • Move two squares starting from the starting rank

  • Promote when reaching the final rank

  • En passant capturing

Because of these rules, I handled pawn move generation separately from other pieces.


Pawn pushes, due to them only being able to move in a straight line in one direction, are calculated using bitshifts rather than a lookup table. We AND the empty squares as we cannot move pawns into an occupied square as they can only capture on the diagonals.

//for white
ulong emptySquares = ~allPieces;
ulong singlePush = (whitePawns << 8) & emptySquares;

Double pawn pushes can be generated by making sure they're moving from the starting rank and making sure both single and double push squares are empty.

//we AND rank3Mask.
//if a pawn is on rank3 after a single push it must have started on rank 2
//this is for white again, change the ranks and masks for black.

ulong rank3Mask = 0x0000000000FF0000UL;
ulong doublePush = ((singlePush & rank3Mask) << 8) & emptySquares;

To generate pawn capture moves, utilise the lookup tables that should have already been calculated.

//for white, to do this for black, you would use the >> shift.
//notA/HFile so we dont wrap attacks when on the edge of the board.
ulong notAFile = 0xFEFEFEFEFEFEFEFEUL;
ulong notHFile = 0x7F7F7F7F7F7F7F7FUL;

ulong captureLeft = ((whitePawns & notAFile) << 7) & enemyPieces;
ulong captureRight = ((whitePawns & notHFile) << 9) & enemyPieces;

Now we have bitboards for all of the possible moves. We just need to extract the actual moves from these bitboards.

private void GetMovesFromBitboard
(ulong bitboard, int offset, bool isCapture, List<Move> moveList)
{
    while (bitboard != 0)
    {
        //get the index of the target square
        int toIndex = PopLeastSignificantBit(ref bitboard);

        //calculate where the pawn came from
        int fromIndex = toIndex - offset; 

        moveList.Add(new Move(fromIndex, toIndex, isCapture));
    }
}

//To use this
GetMovesFromBitboard(singlePush, 8, false, moveList);  //single push
GetMovesFromBitboard(doublePush, 16, false, moveList); //double push
GetMovesFromBitboard(captureLeft, 7, true, moveList);  //capture
GetMovesFromBitboard(captureRight, 9, true, moveList); //capture

Promotions are detected when the pawn reaches the final rank (8 for white, 1 for black). When the pawn has promoted, it is removed from the pawn bitboard and added to the bitboard of the piece that is promoted to (usually queen, but can be knight, rook or bishop too).


En Passant

En passant is a special move where the move directly after a double pawn push, that pawn can be captured as if it only moved 1 square forward. This is just treated as a normal capture, but I will go into more detail into this in a future post. Note that en passant IS a pseudo-legal move, and should be generated at this point.


Generating Sliding Piece Moves

Sliding pieces are generated using magic bitboards that I went through in a previous post. This allows the generation of sliding pieces efficiently.


  1. Mask the bitboard occupancy to include only relevant blocker squares

  2. Multiply by the magic number for that square

  3. shift to obtain an index

  4. look up this index in the lookup table for the relevant piece

ulong occupancy = allPieces & _rookMasks[from];
int index = (int)((occupancy * _rookMagics[from]) >> _rookShifts[from]);
attacks = _rookAttackTable[from][index];

//cannot capture the same coloured pieces
ulong moves = attacks & ~ownPieces;

Bishops work the same way as the rooks, just using diagonal masks and lookup tables.

Queens combine both rook and bishop attacks.


Castling

Castling is handled separately from normal king moves.

To castle, a few conditions need to be met:

  • The rook involved in castling still exists

  • The king and rook have not moved

  • The squares between them are empty, and not attacked by an enemy piece

  • The king is currently not in check.

Because these are specific rules, I will be going into these in a future blog post, with en passant.


Conclusion

We now have the pseudo-legal move generation for the chess engine! (apart from en passant and castling for now). We can now move all of our pieces efficiently using bitwise operations and bitboards.


However, playing the game now reveals some illegal moves happening such as leaving the king in check. This is expected and will be fixed once we filter for legal moves.


Whats next? In the next post we will look at how en passant and castling is done. After that it will be check detection and ending conditions. The most confusing part of the chess engine is done by this point, well done!

bottom of page