Principal Variation The principal variation is the sequence of moves that the engine considers best for both sides from the current position. It’s the “main line” — the path through the game tree that alpha-beta search identifies as optimal. When is Principal Variation Used? After search is complete: The PV is the best line the engine found. This is what gets printed to the GUI — “at depth 12, best line is e4 e5 Nf3…”. Totally useful even without ID, just for knowing the answer. ...

Quiescent Search The Horizon Effect The horizon effect is when a chess engine makes a terrible move because it can’t see past its search depth limit. It’s like looking at a situation and thinking “This is fine!” when disaster is just one move beyond what you can see. Why Fixed-Depth Search Fails Fixed-depth search stops at a specific depth, regardless of what’s happening in the position. Depth 10 search: ├─ Move 1, 2, 3, ... 10 ✓ Search these └─ Move 11 ✗ STOP (even if critical!) Example 1: The Hanging Queen ...

Move Picker Stats /// The Stats struct stores moves statistics. According to the template parameter /// the class can store History and Countermoves. History records how often /// different moves have been successful or unsuccessful during the current search /// and is used for reduction and move ordering decisions. /// Countermoves store the move that refute a previous one. Entries are stored /// using only the moving piece and destination square, hence two moves with /// different origin but same destination and piece will be considered identical. template<typename T, bool CM = false> struct Stats { static const Value Max = Value(1 << 28); const T* operator[](Piece pc) const { return table[pc]; } T* operator[](Piece pc) { return table[pc]; } void clear() { std::memset(table, 0, sizeof(table)); } void update(Piece pc, Square to, Move m) { table[pc][to] = m; } void update(Piece pc, Square to, Value v) { if (abs(int(v)) >= 324) return; table[pc][to] -= table[pc][to] * abs(int(v)) / (CM ? 936 : 324); table[pc][to] += int(v) * 32; } private: T table[PIECE_NB][SQUARE_NB]; }; typedef Stats<Move> MoveStats; typedef Stats<Value, false> HistoryStats; typedef Stats<Value, true> CounterMoveStats; typedef Stats<CounterMoveStats> CounterMoveHistoryStats; It is a generic 2-D table indexed by (piece, destination square) ...

Transposition Tables The transposition table is the engine’s memory of previously analyzed positions. Because the same chess position can be reached through different move orders (transpositions), storing results avoids re-searching identical subtrees — this is one of the biggest speedups in modern engines. Stockfish stores a compact 10-byte entry per position. TTEntry — What is stored Each entry stores just enough info to help pruning and move ordering: struct TTEntry { private: friend class TranspositionTable; uint16_t key16; uint16_t move16; int16_t value16; int16_t eval16; uint8_t genBound8; int8_t depth8; }; C++ Used here Structs in C++ In C++, struct and class are almost identical, with one default difference: ...

Minmax with Alpha Beta Pruning Game Tree Search The Goal of a Chess Engine A chess engine is solving: “Given a position, what move leads to the best possible future?” But the engine cannot know the future, so it simulates it. This simulation is called search. The Game Tree Every legal move creates a new position. From that position, the opponent also has moves. This forms a tree: Position ├── Move A │ ├── Opp Move A1 │ │ ├── Move A1a │ │ └── Move A1b │ └── Opp Move A2 │ └── ... └── Move B └── ... This is called the game tree. ...

Move Generation Move generation is one of the core responsibilities of a chess engine: given a Position, the engine must efficiently produce all possible moves available to the side to move. In Stockfish, move generation is designed to be extremely fast because it is executed millions of times during search. Instead of always generating every legal move, Stockfish generates different categories of moves depending on the search phase (captures only, quiet moves, evasions under check, etc.). ...

Static Exchange Evaluation (SEE) SEE simulates a capture sequence on a square to calculate the net material gain/loss. It asks: “If I make this move and we trade pieces on this square, will I gain at least v centipawns?” /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the /// SEE value of move is greater or equal to the given value. We'll use an /// algorithm similar to alpha-beta pruning with a null window. bool Position::see_ge(Move m, Value v) const { assert(is_ok(m)); // Castling moves are implemented as king capturing the rook so cannot be // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always // correct unless in the rare case the rook ends up under attack. if (type_of(m) == CASTLING) return VALUE_ZERO >= v; Square from = from_sq(m), to = to_sq(m); PieceType nextVictim = type_of(piece_on(from)); Color stm = ~color_of(piece_on(from)); // First consider opponent's move Value balance; // Values of the pieces taken by us minus opponent's ones Bitboard occupied, stmAttackers; if (type_of(m) == ENPASSANT) { occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn balance = PieceValue[MG][PAWN]; } else { balance = PieceValue[MG][piece_on(to)]; occupied = 0; } if (balance < v) return false; if (nextVictim == KING) return true; balance -= PieceValue[MG][nextVictim]; if (balance >= v) return true; bool relativeStm = true; // True if the opponent is to move occupied ^= pieces() ^ from ^ to; // Find all attackers to the destination square, with the moving piece removed, // but possibly an X-ray attacker added behind it. Bitboard attackers = attackers_to(to, occupied) & occupied; while (true) { stmAttackers = attackers & pieces(stm); // Don't allow pinned pieces to attack pieces except the king as long all // pinners are on their original square. if (!(st->pinnersForKing[stm] & ~occupied)) stmAttackers &= ~st->blockersForKing[stm]; if (!stmAttackers) return relativeStm; // Locate and remove the next least valuable attacker nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers); if (nextVictim == KING) return relativeStm == bool(attackers & pieces(~stm)); balance += relativeStm ? PieceValue[MG][nextVictim] : -PieceValue[MG][nextVictim]; relativeStm = !relativeStm; if (relativeStm == (balance >= v)) return relativeStm; stm = ~stm; } } The Algorithm 1. Setup Phase: assert(is_ok(m)); Debug check: Verify the move is legal/valid before proceeding. // Castling moves are implemented as king capturing the rook so cannot be // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always // correct unless in the rare case the rook ends up under attack. if (type_of(m) == CASTLING) return VALUE_ZERO >= v; Castling special case: Internally, castling is coded as “king captures own rook,” which would confuse the SEE algorithm. Just assume SEE = 0 for castling moves (safe assumption since you’re not actually capturing anything). ...

Magic Bitboards and PEXT The Problem: Sliding Piece Attacks Why Sliding Pieces Are Hard Non-sliding pieces (knight, king, pawn): Fixed attack pattern regardless of board state Can pre-compute all attacks at startup Simple lookup: StepAttacksBB[piece][square] Sliding pieces (rook, bishop, queen): Attack pattern depends on blocking pieces Can’t pre-compute all possibilities (too many combinations) The Challenge Rook on e4 - different scenarios: Scenario 1: Empty board 8 . . . . X . . . 7 . . . . X . . . 6 . . . . X . . . 5 . . . . X . . . 4 X X X X R X X X ← Attacks entire rank and file 3 . . . . X . . . 2 . . . . X . . . 1 . . . . X . . . a b c d e f g h Scenario 2: Blocked by pieces 8 . . . . . . . . 7 . . . . . . . . 6 . . . . X . . . 5 . . . . X . . . 4 . . X X R X . . ← Blocked at c4 and f4 3 . . . . X . . . 2 . . . . . . . . 1 . . . . . . . . a b c d e f g h (Pieces at: c4, e2, e6, f4) The question: How do we efficiently compute attacks for ANY occupancy pattern? ...

PSQT (Piece-Square Tables) 1. What is PSQT? It is a traditional evaluation technique where every piece gets: a base material value (pawn = 100, queen = 900…) plus a square bonus/penalty depending on where it stands Example intuition: Knights are better in the center → bonus on d4/e4 Pawns advanced are better → bonus on 6th/7th rank King is safer in corner early → penalty for being central in middlegame So evaluation includes: ...

We will go through some of the functions which are part of core game mechanics Game Mechanics 1. Piece Movement 1. do_move Purpose: Execute a move and update all position state incrementally. Critical for performance: This function is called millions of times per second during search. Every optimization matters. Preconditions: Move m must be legal (pseudo-legal moves should be filtered first) newSt must be a different StateInfo object than current state Caller provides givesCheck flag (optional optimization to avoid recalculating) Function Structure Overview Setup and assertions Copy old state → new state Increment counters Handle castling (special case) Handle captures Update position hash Reset en passant Update castling rights Move the piece Handle pawn moves (en passant, promotion) Update incremental scores Finalize state Flip side to move Compute check info /// Position::do_move() makes a move, and saves all information necessary /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal /// moves should be filtered out before this function is called. void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) { assert(is_ok(m)); assert(&newSt != st); ++nodes; Key k = st->key ^ Zobrist::side; // Copy some fields of the old state to our new StateInfo object except the // ones which are going to be recalculated from scratch anyway and then switch // our state pointer to point to the new (ready to be updated) state. std::memcpy(&newSt, st, offsetof(StateInfo, key)); newSt.previous = st; st = &newSt; // Increment ply counters. In particular, rule50 will be reset to zero later on // in case of a capture or a pawn move. ++gamePly; ++st->rule50; ++st->pliesFromNull; Color us = sideToMove; Color them = ~us; Square from = from_sq(m); Square to = to_sq(m); Piece pc = piece_on(from); Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to); assert(color_of(pc) == us); assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us)); assert(type_of(captured) != KING); if (type_of(m) == CASTLING) { assert(pc == make_piece(us, KING)); assert(captured == make_piece(us, ROOK)); Square rfrom, rto; do_castling<true>(us, from, to, rfrom, rto); st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom]; k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto]; captured = NO_PIECE; } if (captured) { Square capsq = to; // If the captured piece is a pawn, update pawn hash key, otherwise // update non-pawn material. if (type_of(captured) == PAWN) { if (type_of(m) == ENPASSANT) { capsq -= pawn_push(us); assert(pc == make_piece(us, PAWN)); assert(to == st->epSquare); assert(relative_rank(us, to) == RANK_6); assert(piece_on(to) == NO_PIECE); assert(piece_on(capsq) == make_piece(them, PAWN)); board[capsq] = NO_PIECE; // Not done by remove_piece() } st->pawnKey ^= Zobrist::psq[captured][capsq]; } else st->nonPawnMaterial[them] -= PieceValue[MG][captured]; // Update board and piece lists remove_piece(captured, capsq); // Update material hash key and prefetch access to materialTable k ^= Zobrist::psq[captured][capsq]; st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]]; prefetch(thisThread->materialTable[st->materialKey]); // Update incremental scores st->psq -= PSQT::psq[captured][capsq]; // Reset rule 50 counter st->rule50 = 0; } // Update hash key k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to]; // Reset en passant square if (st->epSquare != SQ_NONE) { k ^= Zobrist::enpassant[file_of(st->epSquare)]; st->epSquare = SQ_NONE; } // Update castling rights if needed if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to])) { int cr = castlingRightsMask[from] | castlingRightsMask[to]; k ^= Zobrist::castling[st->castlingRights & cr]; st->castlingRights &= ~cr; } // Move the piece. The tricky Chess960 castling is handled earlier if (type_of(m) != CASTLING) move_piece(pc, from, to); // If the moving piece is a pawn do some special extra work if (type_of(pc) == PAWN) { // Set en-passant square if the moved pawn can be captured if ( (int(to) ^ int(from)) == 16 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN))) { st->epSquare = (from + to) / 2; k ^= Zobrist::enpassant[file_of(st->epSquare)]; } else if (type_of(m) == PROMOTION) { Piece promotion = make_piece(us, promotion_type(m)); assert(relative_rank(us, to) == RANK_8); assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN); remove_piece(pc, to); put_piece(promotion, to); // Update hash keys k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to]; st->pawnKey ^= Zobrist::psq[pc][to]; st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1] ^ Zobrist::psq[pc][pieceCount[pc]]; // Update incremental score st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to]; // Update material st->nonPawnMaterial[us] += PieceValue[MG][promotion]; } // Update pawn hash key and prefetch access to pawnsTable st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to]; prefetch(thisThread->pawnsTable[st->pawnKey]); // Reset rule 50 draw counter st->rule50 = 0; } // Update incremental scores st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from]; // Set capture piece st->capturedPiece = captured; // Update the key with the final value st->key = k; // Calculate checkers bitboard (if move gives check) st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0; sideToMove = ~sideToMove; // Update king attacks used for fast check detection set_check_info(st); assert(pos_is_ok()); } Phase 1: Sanity checks and bookkeeping assert(is_ok(m)); assert(&newSt != st); ++nodes; Key k = st->key ^ Zobrist::side; Ensures the move encoding is valid Ensures we don’t overwrite the current state Increments node counter (used for search statistics) Flips side-to-move bit in the Zobrist key, k is a working copy of the hash key, updated incrementally. Phase 2: StateInfo chaining (undo mechanism) std::memcpy(&newSt, st, offsetof(StateInfo, key)); newSt.previous = st; st = &newSt; Copies all fields up to key Fields after key will be recomputed Links the new state to the previous one (stack-style undo) Advances the st pointer Phase 3: Ply counters ++gamePly; ++st->rule50; ++st->pliesFromNull; gamePly: depth from game start rule50: increments unless reset later pliesFromNull: prevents consecutive null moves Phase 4: Decode move and involved pieces Color us = sideToMove; Color them = ~us; Square from = from_sq(m); Square to = to_sq(m); Piece pc = piece_on(from); Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to); assert(color_of(pc) == us); assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us)); assert(type_of(captured) != KING); Determines moving side Determines source and destination squares Determines captured piece (special handling for en passant) Assertions ensure: ...