SearchAlgorithm.md

Search Algorithm

This page describes the search algorithm used by MicroChess to select the best chess moves, focusing on the minimax algorithm with alpha-beta pruning implemented primarily in MicroChess.ino and supported by chessutil.cpp. The algorithm is optimized to operate within Arduino’s strict memory constraints (less than 2K RAM) while ensuring effective move selection.

Overview

The search algorithm determines the best move by exploring possible future board positions and evaluating them using the evaluation function (see Evaluation). MicroChess uses the minimax algorithm with alpha-beta pruning to efficiently search the game tree, balancing computational efficiency with strategic depth.

Minimax Algorithm

The minimax algorithm works by:

1. Building a Game Tree:
   • Each node represents a board position.
   • Edges represent legal moves generated by move_t (see Move Generation).
   • The tree extends to a specified depth (e.g., 4 plies, configurable in options.h).
2. Evaluating Leaf Nodes:
   • At the maximum depth, the evaluation function (chessutil.cpp) assigns a score to each position.
   • Scores are positive for positions favoring white, negative for black.
3. Propagating Scores:
   • For the maximizing player (e.g., white), select the move leading to the highest score.
   • For the minimizing player (e.g., black), select the move leading to the lowest score.
   • This alternates at each level of the tree, assuming optimal play by both sides.
4. Selecting the Best Move:
   • The root node (current position) chooses the move that leads to the best score after exploring all possibilities.

Alpha-Beta Pruning

Alpha-beta pruning enhances minimax by reducing the number of nodes explored:

• Alpha: The best (highest) score guaranteed for the maximizing player.
• Beta: The best (lowest) score guaranteed for the minimizing player.
• Pruning:
  • If a node’s score exceeds beta (for the maximizer) or falls below alpha (for the minimizer), further exploration of that branch is skipped, as it cannot affect the root’s decision.
  • This significantly reduces computation, critical for Arduino’s limited processing power.
• Implementation:
  • Integrated into the minimax function in MicroChess.ino, maintaining alpha and beta values during recursive calls.
  • Uses move_t scores from the evaluation function to compare against alpha/beta bounds.

Search Depth

• Configurable Depth: Set in options.h via the options_t class (e.g., 4 plies for quick play, deeper for stronger play).
• Trade-Off: Deeper searches improve move quality but increase computation time and memory usage.
• Arduino Optimization: Typically limited to 3-5 plies to stay within 2K RAM and ensure responsive gameplay.

Optimization Techniques

To fit Arduino’s constraints:

• Move Ordering: Prioritizes promising moves (e.g., captures, checks) to improve alpha-beta pruning efficiency, using heuristics from chessutil.cpp.
• Incremental Evaluation: Updates board state incrementally via game_t::makeMove() and undoMove() to avoid recomputing evaluations.
• Memory Efficiency: Stores only essential data (e.g., move_t objects) during search, leveraging board_t’s compact representation.
• Time Limits: Configurable in options.h to cap search time, ensuring real-time performance.

Integration with Other Components

The search algorithm interacts with:

• Move Generation (move.h/cpp): Retrieves legal moves for each position in the game tree.
• Evaluation (chessutil.cpp, pieces.cpp): Scores leaf nodes to guide move selection.
• Game Logic (game.h/cpp): Applies and reverts moves (makeMove(), undoMove()) during tree exploration.
• Board Representation (board.h/cpp): Provides the current board state for move generation and evaluation.
• Options (options.h/cpp): Configures search depth and time limits.
• Statistics (stats.h/cpp): Tracks metrics like nodes searched and time taken for performance analysis.

Example

For the position after 1. e4:

• The algorithm generates white’s legal moves (e.g., Nf3, Nc3, d4).
• For each move, it explores black’s responses (e.g., e5, Nf6) up to the configured depth.
• Leaf nodes are evaluated (e.g., Nf3 scores +10 for piece activity, e5 scores 0 for balance).
• Alpha-beta pruning skips branches where black’s response guarantees a worse outcome for white.
• The best move (e.g., Nf3) is selected and played.

Visual Aids

The search algorithm’s results are visible in:

• LED Strip: Shows the board after the chosen move (see MicroChessSmall.gif).
• Serial Console: Displays the selected move (e.g., "g1f3") and updated board (see MicroChessConsole2.gif). More details are in the Visuals page.

Next Steps

• See Visuals for how search results are displayed.
• Explore Options for configuring search parameters.
• Check Code Structure for an overview of all files.

---

Back to Home | Next: Visuals