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. ...
Executing Shellcode on Stack
Previously we saw how to overwrite the return address of stack by passing extra bytes to an unbounded buffer. But not everytime we will have a convinient function address to overwrite. The next attempt is to place the code we want to execute directly on the stack itself. Embedding Shellcode in a Buffer Overflow 1. What is Shellcode? Shellcode is machine instructions (usually written in assembly) that perform some action — often spawning a shell (/bin/sh), but can be anything. It is called “shellcode” not because it must open a shell, but because historically it did. 2. Why embed shellcode on the stack? Sometimes you don’t know the address of any useful existing function. Or the binary doesn’t have functions like system("/bin/sh"). In these cases, the attacker places their own code (shellcode) inside the same buffer that overflows. Then somehow point $rip register to the location of shellcode on stack so that CPU starts executing it. 3. Requirements for embedding shellcode 1. Executable stack The stack must have executable permissions. Many modern systems have NX (Non-Executable) protection → stack is not executable. CPU provides setting read, write and executable permissions at individual page level which is enforced at hardware level. This feature has been there since 80286 CPU. Executing shellcode on stack will be impossible just by marking stack pages as non-executable. For learning, we usually compile with flags -z execstack which will make the stack executable. gcc -fno-pie -no-pie -fno-stack-protector -z execstack main.c -o vuln 2. Enough space in the buffer Shellcode must fit entirely inside the buffer or adjacent space. 3. No null bytes When injecting shellcode via string functions like gets, scanf("%s"), strcpy, a null byte will terminate input. Shellcode must avoid 0x00, 0x0A, etc. 4. Stack-Based Shellcode Execution: A Simple Case Without ASLR To build the payload of overflowed string we need to consider various factors, let’s understand it with a simple program: ...
CTF – 3 : 45exiles Shuffle
CTF Writeup: 45exiles Shuffle Challenge Problem Overview Challenge Name: 45exiles Shuffle Core Mechanism: Program reads user input Shuffles the input using rand() with a known seed Compares the shuffled input against a target string stored in memory If they match, you get the flag Key Insight: You can read the target (shuffled) string from memory, but that’s NOT the answer you need to input. You must reverse the shuffle to find the original input. ...
Stack Based Buffer Overflow Attacks
Stack Based Buffer Overflow Attacks A buffer overflow occurs when a program writes more data into a fixed-size buffer than it was designed to hold. A buffer is a contiguous block of memory allocated to store data (e.g., an array/string whose length is defined at compile time). Causes of Buffer Overflow Attacks in C When we talk about buffer overflows, its almost always about buffer overflows in C programs because of the way the following things are designed in C: ...
CTF – 2 : Good Kitty
CTF Challenge: Good Kitty - Writeup Challenge Overview This is a reverse engineering CTF challenge where we need to find the correct password by analyzing a binary that: Calculates a value based on Project Euler problem #3 Encodes it using a custom algorithm Compares user input against the encoded value Initial Analysis Decompiled Code Structure undefined8 main(void) { byte bVar1; ssize_t bytes_read; long input_len; int iVar2; long in_FS_OFFSET; double dVar3; undefined1 local_be; byte is_correct; uint index; long flag; undefined8 local_b0; undefined8 local_a8 [4]; undefined8 local_88; undefined8 uStack_80; undefined8 local_78; char user_input [72]; long local_20; local_20 = *(long *)(in_FS_OFFSET + 0x28); flag = ppeuler_3(); dVar3 = cbrt((double)flag); flag = (long)dVar3; flag = factorial(flag); input_len = 0; do { bVar1 = *(byte *)((long)&flag + input_len); if ((0x19 < (byte)((bVar1 & 0xdf) + 0xbf)) && (9 < (byte)(bVar1 - 0x30))) { bVar1 = bVar1 % 0x3e; if ((byte)(bVar1 - 10) < 0x1a) { *(byte *)((long)&flag + input_len) = bVar1 + 0x37; } else if ((byte)(bVar1 + 0x30) < 0x54) { *(byte *)((long)&flag + input_len) = bVar1 + 0x30; } else { *(byte *)((long)&flag + input_len) = bVar1 + 0x3d; } } input_len = input_len + 1; } while (input_len != 8); // ... rest of code validates input } Key Concepts Learned 1. Understanding Pointer Arithmetic on Stack Variables Question: flag is declared as long flag; (not an array), so what does &flag + index mean? ...