Pawn — The Foundation

The pawn is where every game, and every engine, begins. It moves one step at a time, but those small steps build the whole frontline. This chapter covers the foundation Eschess is built on: how the board is represented, and how the engine searches for a move.

From squares to bits: BitBoard

The obvious way to store a chess position is an array of 64 squares, each holding a piece. It works, but it’s slow: asking “where can this pawn move?” means looping over squares and branching on every one.

The faster idea is a bitboard: a single 64-bit integer where each bit is one square, 1 for occupied and 0 for empty. One can store a 64-bit bitboard per piece type per color (so in total 12 bitboards in the system). Now a question like “advance every white pawn one rank” isn’t a loop at all; it’s a single left-shift by 8.

hex: 0x000000000000FF00
uint64: 65280
popcount: 8

Click any square to flip its bit. Each square is one bit of a 64-bit integer (LERF: a1 = bit 0, h8 = bit 63). "Push north" left-shifts the whole board by 8 — every piece advances one rank in a single instruction.

Try it: load the white pawns and hit push north. The entire rank moves forward in one operation. This is the whole appeal of bitboards! By mapping the board’s geometry onto bitwise arithmetic, move generation becomes shifts, masks, and ANDs that the CPU runs in a handful of cycles.

In the code, Little-Endian Rank-File (LERF) mapping is used. square index = rank * 8 + file, so a1 is bit 0 and h8 is bit 63. Directions become fixed shifts, like north << 8, south >> 8, east << 1, with file masks to stop pieces wrapping around the board edge.

Building the rules: Moves, Attacks, Checks

A bitboard is just a static map of bits. To play chess, the engine needs to translate the physical geometry of the board into bitwise operations. This begins with move generation.

At the lowest level, Eschess calculates pseudo-legal moves. These are moves a piece can technically make based on its movement rules, assuming we completely ignore whether the move leaves our own King in check. Here is how the engine computes the pseudo-legal movement rules for all six pieces:

Pawn Moves

Pieces that move differently than they capture, shifting strictly forward while attacking diagonally.

python/engine/board.py · CBoard._pawn_pseudo

def _pawn_pseudo(self, square: int, color: Color) -> U64:
    occ = self.occupied()
    enemy = self.colors[color.opponent()]
    bits = square_to_bits(square)
    result: U64 = 0

    if color == Color.WHITE:
        push1 = shift_n(bits) & ~occ
        result |= push1
        if bits & RANK_2:
            result |= shift_n(push1) & ~occ  # Double push
        result |= shift_nw(bits) & enemy
        result |= shift_ne(bits) & enemy
        if self.en_passant_square is not None:
            ep_bits = square_to_bits(self.en_passant_square)
            result |= (shift_nw(bits) | shift_ne(bits)) & ep_bits
    # ... (Black logic mirrors this southward) ...
    return result

While _get_pseudo_legal dictates movement, get_attacks dictates threat. These are not always identical: pawns push forward but strike diagonally, and sliding pieces project threat along rays even if blocked by their own color.

Building the Attack Map Iterates through all pieces to create a unified 64-bit mask of every square currently under threat by the opponent.

python/engine/board.py · CBoard.get_attacks

def get_attacks(self, color: Color) -> U64:
    """All squares attacked by color (used for check and castling safety)."""
    occ = self.occupied()
    result: U64 = 0
    
    # ... iterates through all pieces ...
    for square in bits_to_squares(self.get_specific_pieces(color, PieceType.BISHOP)):
        # Note: 'friendly' mask is 0, so rays piece through their own ranks for threat calculation
        result |= self._bishop_attacks(square, occ, 0) 
        
    return result

With the Attack Map built, finding out if a player’s King is in check is computationally trivial, simply through using a bitwise AND (&) on bit representing the King’s square & the opponent’s Attack Map. But, a chess engine cannot just play pseudo-legal moves; it must play strictly legal moves that won’t leave one’s own King in check.

To filter the list, Eschess uses the make / unmake pattern: it temporarily plays a move, checks if its own King is safe, and immediately undoes it.

Make / Unmake Pattern Tests every pseudo-legal move by playing it, checking the King's safety, and reverting the board state.

python/engine/board.py · CBoard.get_legal_moves

def get_legal_moves(self, square: int) -> U64:
    # ... get pseudo moves + castling pseudo ...
    legal: U64 = 0
    for dest in bits_to_squares(pseudo):
        self.make_move(square, dest)
        if not self.is_in_check(color):
            legal |= square_to_bits(dest)
        self.unmake_move()
    return legal

Compressing the state: Zobrist Hashing

Representing the board efficiently is only half the battle; the search algorithm needs a way to identify identical positions instantly. If the engine arrives at the exact same board state through two different move orders (a transposition), theoretically it shouldn’t waste time searching it twice.

To do this, a Zobrist key can help flatten the entire 12-layered bitboard configuration into a single, highly uniform 64-bit integer. By the use of the bitwise XOR (^), it achieve $O(1)$ incremental updates. Moving a piece becomes a sequence of incredibly cheap bit toggles:

XOR out the piece from its departure square (erasing its signature).
XOR in the piece to its arrival square (baking in its new position).
XOR the turn flag to flip the side to move.

♜︎ a8

♞︎ b8

♝︎ c8

♛︎ d8

♚︎ e8

♝︎ f8

♞︎ g8

♜︎ h8

♟︎ a7

♟︎ b7

♟︎ c7

♟︎ d7

♟︎ e7

♟︎ f7

♟︎ g7

♟︎ h7

♟︎ a2

♟︎ b2

♟︎ c2

♟︎ d2

♟︎ e2

♟︎ f2

♟︎ g2

♟︎ h2

♜︎ a1

♞︎ b1

♝︎ c1

♛︎ d1

♚︎ e1

♝︎ f1

♞︎ g1

♜︎ h1

Transposition demo

seed

play sequence

key 0xBF0FC3F0D2FBB33C

XOR decomposition (32 terms)

WR a1 0x1DD49D823A7929C3

⊕ WK b1 0xE7453C3F855CF125

⊕ WB c1 0xC175D25E76E62B9E

⊕ WQ d1 0x565A393692246202

⊕ WK e1 0xC5E3715DFD0344D2

⊕ WB f1 0xBF8955D177261E18

⊕ WK g1 0x55AD90D0573136A1

⊕ WR h1 0x53C4F09D7EE4D311

⊕ WP a2 0xE3478476919E1837

⊕ WP b2 0x923A868B8D193254

⊕ WP c2 0x814242E524A43F0C

⊕ WP d2 0x27F2AE0E1C6C6F0D

⊕ WP e2 0x3214093CD1357612

⊕ WP f2 0xDC98A77D4EC83ACD

⊕ WP g2 0x484A8A5F914D589A

⊕ WP h2 0x598A6B83C43F2FA3

⊕ BP a7 0x7B386FF597973A15

⊕ BP b7 0xFF00D38E3D85F69E

⊕ BP c7 0x17B422156A6D834E

⊕ BP d7 0x51628120237AF9CF

⊕ BP e7 0x4C25F9BD32191415

⊕ BP f7 0xBC4F8F40565A09A5

⊕ BP g7 0xC9C37FAAA468F7FC

⊕ BP h7 0xF2AD25D47293481C

⊕ BR a8 0x29CF8031F68DBCDA

⊕ BK b8 0x2B406A591B7C0E57

⊕ BB c8 0x0F3738DA2E83B7E4

⊕ BQ d8 0xFD56B46F9ACF8F2A

⊕ BK e8 0x612C0FDA807BFCB0

⊕ BB f8 0x5164F34108F166B0

⊕ BK g8 0x0C3EA72E9D0B0C55

⊕ BR h8 0x434162CAD9ADD4F4

= key 0xBF0FC3F0D2FBB33C

From the simple explorer, one can also observe that if a sequence of moves transposes into a known layout, XOR ensure the resulting keys match exactly, regardless of the order the moves were played. This single 64-bit key is the primary passport used to query the transposition table during search.

Evaluating the state: Material and Position

The final stage before searching is to define what is a “good move”. In its classical form, Eschess evaluates a board by focusing on:

Who has more stuff? (Material). A Queen is worth 900 points, a Rook 500, a Pawn 100. The engine sums up the pieces on the board.
Who has better placement? (Position/Structure). A knight in the center of the board is vastly superior to a knight stuck in the corner.

This simple math of Material + Piece-Square bonuses spits out a single integer. Positive means White is winning, negative means Black is winning.

More details are explained in Chapter 4: Bishop.

Searching the tree: Minimax

With the board mapped and the rules enforced, the engine can finally look ahead. Eschess bases its search on Minimax, an algorithm that explores the game tree assuming both players make their absolute best moves, scores the resulting leaves, and backs those values up the tree.

But a naive Minimax tree grows exponentially, making it far too slow for real-time play. To transform a theoretical algorithm into a competitive engine, we layer on techniques that aggressively prune the tree and prioritize the most promising lines.

Alpha-beta pruning

Skips branches that cannot change the result, drastically reducing the search space.

python/engine/search.py · Search.minimax

maximizing = board.turn == Color.WHITE
best_eval, best_move = None, None

for move in legal_moves:
    from_square, to_square, promotion = move
    board.make_move(from_square, to_square, promotion)
    eval_score, _ = self.minimax(board, depth - 1, alpha, beta, ply + 1)
    board.unmake_move()

    if maximizing:
        if best_eval is None or eval_score > best_eval:
            best_eval, best_move = eval_score, move
        alpha = max(alpha, best_eval)   # White raises the floor
    else:
        if best_eval is None or eval_score < best_eval:
            best_eval, best_move = eval_score, move
        beta = min(beta, best_eval)     # Black lowers the ceiling

    if beta <= alpha:
        break   # window closed: nothing in this branch can change the result

Pruning is the idea worth seeing in motion. The tree below is a tiny search: the root wants to maximize, the layer below wants to minimize, and the leaves are fixed scores. Step through it and watch the [α, β] window tighten until whole branches become unreachable and fade out, never searched at all.

Enter MAX node with window [−∞, +∞].

step 1 / 35

Squares show each node's type until it resolves to a score. The [α, β] label above a node is its live search window. When α reaches β the remaining children are unreachable, so they fade out unsearched. Same leaves, fewer nodes visited.

Both runs return the same root score. Alpha-beta just refuses to look at moves that cannot matter, which is what lets the same time budget reach a deeper search.

Together, these turn a brute-force tree into something that searches deeply enough to play real chess. It’s still the solid frontline the rest of the engine advances behind.