Move generation

Move generation is the computational process by which a program identifies the legal moves available from a given game state in computer chess and generally other strategy games. In general game playing, the engine must produce only valid moves before evaluation can begin. Pseudo-legal moves follow basic movement rules, and fully legal moves satisfy all higher-level constraints such as check (chess). Because the number of possible positions grow exponentially with search depth, move generation has a major effect on speed and search.

The field developed alongside early chess programming in the 1950s and later progressed through new board representations, data structures and hardware support. Early systems depended on simple array-based boards and strict square-by-square testing, while later programs used methods such as the mailbox board, rotated bitboards and magic bitboards. Some engines also used move generation using custom chips, like Belle and Deep Blue.

In the context of computer chess and in general strategic games, move generation refers to the specific computational process where an algorithm identifies every legal transition from a given state.^[1] This fundamental component of a general game playing engine must follow the defined rules of the game to ensure the search algorithm only evaluates valid positions. Developers often distinguish between pseudo-legal moves, which follow basic piece movement patterns, and strictly legal moves that also include complex restrictions like check (chess).

The total number of potential outcomes grow exponentially as the search depth increases.^[2] Bitboards represent the game state through 64-bit integers. Bitboards use bitwise operations to calculate piece movements efficiently.^[3] Pseudo-legal generation speeds up the calculation process further by temporarily ignoring whether a move accidentally leaves the king in check. Advanced systems integrate precomputed attack tables for "sliding pieces" like rooks and queens to eliminate redundant real-time processing.^[4]

Move generation developed during the 1950s alongside the foundational concepts of Alan Turing and Claude Shannon.^[5][6] Early programs ran on massive mainframe computers and relied on piece-centric array systems to determine valid board moves, because physical computer memory was limited, engineers had to write highly restrictive instructions that checked every square on the board sequentially.^[7]

During the 1970s, researchers at Northwestern University created the Chess series of programs, which introduced advanced board representations to reduce redundant processing loops.^[8] The introduction of the mailbox board design provided quick out-of-bounds error handling; at the same time, university labs started experimenting with custom microchips engineered to execute move generation tasks directly in hardware.^[9]

The Belle chess engine demonstrated that offloading the move generation loop to custom circuitry could increase the number of nodes evaluated per second, and this hardware approach led to Deep Blue.^[10]

Calculating sliding attacks for rooks and bishops remained a problem because other pieces blocked them, requiring programs to track board occupancy, so software engineers resolved this issue by using rotated bitboards. However, rotated bitboards still needed additional processing time to keep the various board views synchronized after every single move.^[11] To overcome the computational overhead of rotated bitboards, developers invented magic bitboards to handle sliding piece generation using hashing. The engine only verifies the legality of a move if the search algorithm decides to explore that specific branch, which saves valuable computing cycles on paths that are pruned.^[12]

Move generation depends on memory architecture, state tracking, and algorithmic verification to populate the game tree. The data structure chosen for move representation must pack original squares, target squares, and special flags into compact bit fields to conserve system memory.^[13] The generator then processes these structures through either pseudo-legal or strict legal move filters. Pseudo-legal generation speeds up the initial phase by delaying king safety checks while legal generation immediately validates all spatial and tactical constraints before passing data to the search loop.^[14]

In abstract strategy game programming, a pseudo-legal move represents any action that follows basic piece mechanics but ignores broader constraints like immediate loss conditions.^[15] The engine checks whether the move follows to movement rules of the game. but this calculation does not check if the move violates the rules of its corresponding game. Generating these moves requires very little computation because the system skips complex safety verification steps.^[16]

A legal move must satisfy every rule of the game and also preserve all mandatory safety requirements in the game states. Engines filter out illegal moves by simulating the action and analyzing the next board position.^[17] If the simulated state reveals that the player or the engine has violated a core rule or allowed an instant defeat in the game, the engine rejects the move.^[15]

In game theory and computer game playing, a move representation defines the internal data structure used to encode a player's legal action within a specific board state. This architectural choice directly determines the computational efficiency of the broader move generation subsystem across various strategic games like chess, shogi, and Go. Developers often pack critical execution data into a single 16-bit or 32-bit integer by using bitmask operators to save cache memory and minimize overhead.^[18] This compressed format typically holds the starting coordinate, the arrival coordinate, the moving piece type, and the distinct flag bits for special moves in chess like castling, en passant, or piece promotion.^[19]

Board representation is the internal model a game engine uses to store the current position, and for board games it can be built in several ways. The bitboard method represents a board game by encoding various information about the position.^[20] Move generation reads that encoded position to determine the legal continuations, so the representation has to make occupied squares, piece types, and other such rule data available to query.^[5]

The choice of move generator applies to how it works during search. Specifically, the move generation is used many times, meaning an efficient generator is needed to maintain performance. This efficiency can be achieved by storing all possible moves in precomputed data so the program can access them quickly.^[21] For non-sliding pieces, this lets the program filter destination squares directly from cached move sets, while sliding pieces need extra data tied to rank, file, or diagonal occupancy because their legal moves depend on the current line on the board.^[22]

Move generation methods define the specific instructions and computer code used to calculate all valid actions a general game playing engine can execute from a specific state. Within these generation methods, move generation works as the core component that fills the search tree, directly determining the speed and accuracy of the next evaluation phase. Programs apply rule-based generation to enforce complex game constraints sequentially, ensuring total legality at the cost of processing speed.^[23]

Piece-based generation scans only the active pieces on the board to find potential actions.^[24] General game playing engines simplify this process by using table-driven and lookup-based methods, which pull precalculated moves from memory to bypass real-time computation.^[25]

Bitboards, and other similar variants like PEXT Bitboard, rotated bitboards, use parallel bitwise operations on binary arrays to find valid moves instantly.^[26] Incremental and cached generation methods reuse calculations from previous turns, updating only the specific parts of the board that changed.^[27]

Rule-based move generation uses explicit code to apply the rules of a game to a specific state.^[28] A specialized function basically implements all of the rules to strictly verify which actions are valid. This process generates a list of all the legal moves as output, ensuring the software knows all rules before it begins any strategic search. Incremental generation will usually work faster than listing every option immediately, allowing the engine to process strictly necessary branches first.

Piece-based move generation is an algorithmic approach in computer chess that scans the board to locate individual pieces and calculates their legal destinations one by one.^[29] In move generation, this strategy isolates each active piece on the chessboard to determine it's valid moves.^[30]

The engine uses specialized data structures like mailbox arrays or bitboards to identify piece coordinates sequentially. For each piece found, the system applies sliding piece or stepper piece rules to find empty squares or enemy captures.

• Bitboard
• Evaluation function
• Zobrist hashing
• Move ordering

• Move generation on TSCP Chess