MoveGeneration.md

Move Generation

This page explains how MicroChess generates and validates legal chess moves, focusing on the move_t class and related logic defined in move.h and move.cpp. Move generation is a critical component of the chess engine, ensuring all possible moves are considered efficiently within Arduino’s memory constraints (less than 2K RAM).

Overview

Move generation involves identifying all legal moves for a given board position, including standard moves (e.g., pawn advances, knight jumps) and special moves (castling, en passant, pawn promotion). MicroChess optimizes this process to minimize memory usage and computational overhead, supporting the minimax algorithm with alpha-beta pruning.

The move_t Class

The move_t class, defined in move.h and implemented in move.cpp, represents a single chess move. Key attributes include:

• From Square: The starting square (0-63, corresponding to a1-h8).
• To Square: The destination square (0-63).
• Evaluation Score: A score assigned during move evaluation, used to rank moves.
• Captured Piece: (Optional) Stores the piece type and color captured, if any.
• Special Move Flags: Indicate castling, en passant, or promotion.

Key Methods

• Constructor: Initializes a move with from/to squares and optional flags.
• isValid(): Checks if the move is legal based on board state and chess rules.
• Getters/Setters: Access or modify move attributes (e.g., getFrom(), setScore()).

Move Generation Process

Move generation is handled by functions in move.cpp, which:

1. Identify Pieces: Scan the board (via board_t) to find pieces of the current player’s color.
2. Generate Moves per Piece:
   • Pawns: Forward moves (one or two squares from initial rank), captures (diagonal), en passant, and promotions (on reaching rank 8 or 1).
   • Knights: L-shaped jumps (e.g., from e4 to f6, d6, etc.).
   • Bishops: Diagonal moves, stopping at obstacles.
   • Rooks: Horizontal/vertical moves, stopping at obstacles.
   • Queens: Combines bishop and rook moves.
   • Kings: One-square moves in any direction, plus castling (if legal).
3. Validate Moves:
   • Ensure moves stay within the board (0-63).
   • Check for legal captures (opponent’s piece or en passant).
   • Verify the king is not left in check after the move.
4. Store Moves: Collect valid moves in a list or array for evaluation by the search algorithm.

Special Moves

MicroChess handles all standard chess special moves:

• Castling:
  • Kingside (O-O) or queenside (O-O-O) is allowed if:
    • The king and rook have not moved.
    • No pieces block the path between them.
    • The king is not in check and does not pass through or land on a checked square.
  • Represented in move_t with a special flag and dual-square update (king and rook).
• En Passant:
  • Occurs when a pawn advances two squares and an opponent’s pawn can capture it as if it moved one square.
  • Tracked in board_t and validated in move_t.
• Pawn Promotion:
  • When a pawn reaches the 8th (white) or 1st (black) rank, it promotes to a queen, rook, bishop, or knight.
  • Specified in move input (e.g., "e7e8q" for queen promotion).

Optimization Techniques

To fit Arduino’s constraints:

• Incremental Generation: Generates moves for one piece at a time, reducing memory usage.
• Bit Fields: Uses compact move_t structures to store move data.
• Precomputed Patterns: Leverages fixed movement patterns for knights and kings to speed up generation.
• Early Filtering: Discards illegal moves (e.g., those leaving the king in check) during generation.

Integration with Other Components

Move generation interacts with:

• Board Representation (board.h/cpp): Queries board_t for piece positions and occupancy.
• Game Logic (game.h/cpp): Ensures moves are legal in the current game state (e.g., not in check).
• Evaluation (chessutil.cpp, pieces.cpp): Assigns scores to generated moves for ranking.
• Search Algorithm (MicroChess.ino): Feeds generated moves into the minimax algorithm for selection.

Example

For a white pawn on e2 in the starting position:

• Possible moves: e2e3 (one square forward), e2e4 (two squares forward).
• If an opponent’s piece is on d3 or f3, captures (e2d3, e2f3) are generated.
• These moves are validated and stored as move_t objects for evaluation.

Visual Aids

Move generation affects the visual output:

• LED Strip: Updated after each move (see MicroChessSmall.gif).
• Serial Console: Shows move notation (e.g., "e2e4") and updated board (see MicroChessConsole2.gif). More details are in the Visuals page.

Next Steps

• Explore Game Logic for how moves are applied and tracked.
• See Evaluation for move scoring.
• Check Code Structure for an overview of all files.

---

Back to Home | Next: Game Logic