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
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)
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: ...
Game Mechanics
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: ...
Zobrist Hashing
Zobrist Hashing What problem Zobrist hashing solves In a chess engine, we constantly need to: Identify identical positions reached via different move orders Detect threefold repetition Cache evaluations in a transposition table (TT) But: Comparing full board state is too slow Copying board state is too expensive The Core Idea Goal: Convert a chess position into a single 64-bit number (the “hash” or “key”) that: Uniquely identifies the position (with very high probability) Can be incrementally updated when making moves Enables O(1) position comparison What a Zobrist key represents A Zobrist key is a 64-bit integer (Key in Stockfish) representing: ...
Representation of The Game State
Representation of The Game State The Position Class The Position class is the core data structure in Stockfish that represents the complete state of a chess game at any given moment. It stores the board, pieces, game state, and provides methods to query and manipulate the position. class Position { public: static void init(); Position() = default; Position(const Position&) = delete; Position& operator=(const Position&) = delete; // FEN string input/output Position& set(const std::string& fenStr, bool isChess960, StateInfo* si, Thread* th); const std::string fen() const; // Position representation Bitboard pieces() const; Bitboard pieces(PieceType pt) const; Bitboard pieces(PieceType pt1, PieceType pt2) const; Bitboard pieces(Color c) const; Bitboard pieces(Color c, PieceType pt) const; Bitboard pieces(Color c, PieceType pt1, PieceType pt2) const; Piece piece_on(Square s) const; Square ep_square() const; bool empty(Square s) const; template<PieceType Pt> int count(Color c) const; template<PieceType Pt> const Square* squares(Color c) const; template<PieceType Pt> Square square(Color c) const; // Castling int can_castle(Color c) const; int can_castle(CastlingRight cr) const; bool castling_impeded(CastlingRight cr) const; Square castling_rook_square(CastlingRight cr) const; // Checking Bitboard checkers() const; Bitboard discovered_check_candidates() const; Bitboard pinned_pieces(Color c) const; Bitboard check_squares(PieceType pt) const; // Attacks to/from a given square Bitboard attackers_to(Square s) const; Bitboard attackers_to(Square s, Bitboard occupied) const; Bitboard attacks_from(Piece pc, Square s) const; template<PieceType> Bitboard attacks_from(Square s) const; template<PieceType> Bitboard attacks_from(Square s, Color c) const; Bitboard slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const; // Properties of moves bool legal(Move m) const; bool pseudo_legal(const Move m) const; bool capture(Move m) const; bool capture_or_promotion(Move m) const; bool gives_check(Move m) const; bool advanced_pawn_push(Move m) const; Piece moved_piece(Move m) const; Piece captured_piece() const; // Piece specific bool pawn_passed(Color c, Square s) const; bool opposite_bishops() const; // Doing and undoing moves void do_move(Move m, StateInfo& st, bool givesCheck); void undo_move(Move m); void do_null_move(StateInfo& st); void undo_null_move(); // Static Exchange Evaluation bool see_ge(Move m, Value value) const; // Accessing hash keys Key key() const; Key key_after(Move m) const; Key material_key() const; Key pawn_key() const; // Other properties of the position Color side_to_move() const; Phase game_phase() const; int game_ply() const; bool is_chess960() const; Thread* this_thread() const; uint64_t nodes_searched() const; bool is_draw() const; int rule50_count() const; Score psq_score() const; Value non_pawn_material(Color c) const; // Position consistency check, for debugging bool pos_is_ok(int* failedStep = nullptr) const; void flip(); private: // Initialization helpers (used while setting up a position) void set_castling_right(Color c, Square rfrom); void set_state(StateInfo* si) const; void set_check_info(StateInfo* si) const; // Other helpers void put_piece(Piece pc, Square s); void remove_piece(Piece pc, Square s); void move_piece(Piece pc, Square from, Square to); template<bool Do> void do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto); // Data members Piece board[SQUARE_NB]; Bitboard byTypeBB[PIECE_TYPE_NB]; Bitboard byColorBB[COLOR_NB]; int pieceCount[PIECE_NB]; Square pieceList[PIECE_NB][16]; int index[SQUARE_NB]; int castlingRightsMask[SQUARE_NB]; Square castlingRookSquare[CASTLING_RIGHT_NB]; Bitboard castlingPath[CASTLING_RIGHT_NB]; uint64_t nodes; int gamePly; Color sideToMove; Thread* thisThread; StateInfo* st; bool chess960; }; Class Design Decisions 1. Non-Copyable Position(const Position&) = delete; Position& operator=(const Position&) = delete; Cannot be copied (copy constructor and assignment deleted) Why? Positions are heavy objects with complex state Must be moved or passed by reference/pointer Prevents accidental expensive copies 2. Default Constructor Position() = default; Creates uninitialized position Must call set() to initialize with FEN string Core Data Members 1. Board Representation - MailBox Piece board[SQUARE_NB]; // SQUARE_NB = 64 Mailbox representation: Direct lookup “what piece is on square X?” board[e4] → returns W_KNIGHT or NO_PIECE Fast for: “piece_on(Square s)” 2. Bitboard Representation Technically we need 12 bitboards to represent the all the pieces on chessboard. ...
C++ Used in Stockfish
C++ Used in Stockfish Stockfish is written in a style of C++ that prioritizes performance, predictability, and compile-time resolution over traditional object-oriented design. Rather than heavy use of classes, inheritance, or virtual functions, the engine relies on enums, inline functions, templates, bitwise operations, and plain data structures. This makes the code extremely fast, cache-friendly, and suitable for deep search loops executed billions of times. Enums as Core Types Enums form the backbone of Stockfish’s type system. Instead of using classes for concepts like pieces, squares, colors, or moves, Stockfish represents them as enums with carefully chosen integer values. ...
Bitboard representation of Chess Board
Bitboard-Based Game Representation in Stockfish Stockfish represents the chessboard using bitboards: 64-bit unsigned integers where each bit corresponds to a square on the board. typedef uint64_t Bitboard; Bit 0 (LSB) → A1 Bit 63 (MSB) → H8 This representation allows the engine to manipulate entire sets of squares using fast bitwise operations, which is critical for performance. Piece Encoding enum Piece { NO_PIECE, W_PAWN = 1, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING, B_PAWN = 9, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING, PIECE_NB = 16 }; Numeric Structure Piece Value Binary W_PAWN 1 0001 W_KING 6 0110 B_PAWN 9 1001 B_KING 14 1110 Key observations: ...
History of Chess Engines
History of Chess Engines Programming a Computer for Playing Chess (1950) by Claude Shannon is the foundational paper of computer chess and one of the earliest works in artificial intelligence. Written at a time when programmable computers were still experimental, the paper does not attempt to build a chess program, but instead asks a deeper question: what would it even mean for a machine to play chess intelligently under severe computational limits? Shannon shows that perfect play is theoretically possible but practically impossible, and develops a principled framework based on approximate evaluation, game-tree search, selectivity, and bounded rationality. Nearly every major idea used in modern chess engines—minimax, heuristic evaluation, quiescence, selective search, opening books, randomness, and even learning—appears here in conceptual form. The paper remains important not as a historical curiosity, but because it correctly identifies the permanent constraints and core ideas that still govern strong chess-playing programs today. ...
Format String Vulnerability
Format String Vulnerabilities Why Information Leaks Matter in Modern Exploitation The ASLR Problem Modern systems use Address Space Layout Randomization (ASLR) to randomize memory locations: Stack addresses change every execution Heap addresses randomized Library (libc) addresses randomized Code addresses randomized (with PIE) The dilemma: You can overflow a buffer and control the return address (this is again assuming we somehow defeated the canary) But you don’t know WHERE to point it (shellcode location unknown) Even ROP gadget addresses are randomized You need to LEAK memory addresses first! Format string vulnerabilities are one of the most powerful information leak primitives. ...