Polyglot Opening Book for Micro-Max on STM32

1. What Is a Polyglot Book and Why It Is Needed

Polyglot is the standard binary opening book format used by most chess engines (Stockfish, Houdini, Fruit, etc.). Each entry contains:

• key (4 bytes) — Zobrist hash of the position
• move (2 bytes) — move in packed format
• weight (1 byte) — weight (probability of move selection)

The micro-Max engine (by H.G. Müller) is a minimalist engine under 2 KB of source code. It plays well in the middlegame but, due to shallow search (fixed node limit), it can make suboptimal moves in the opening. An opening book solves this: the first 2–6 moves are taken from a precomputed database, then control is handed to the engine.

2. System Architecture

The solution is split into two parts:

• On PC (offline): A Python script with Stockfish generates debut_book.c — an array of positions and best moves.
• On STM32 (firmware): polyglot.c computes the Zobrist hash of the current position and looks it up in debut_book[] via binary search.

3. Conventions and Data Conversion

The main challenge: micro-Max and Polyglot use different coordinate systems, piece encodings, and color conventions. Without correct conversion, Zobrist hashes will not match and the book will not work.

3.1 Coordinates: 0x88 ↔ 0x3F

Micro-Max uses 0x88 notation: square = rank * 16 + file, where rank 0 = a8 (top), rank 7 = a1 (bottom). Valid squares: 0x00–0x77, odd bits 4–7 = off-board.

Polyglot (and the Python chess library) uses linear numbering 0x3F: a1=0, h1=7, a8=56, h8=63.

C conversion (sq88_to_063):

// 0x88 → 0x3F WITH rank inversion
static int sq88_to_063(int sq) {
    return (7 - (sq >> 4)) * 8 + (sq & 7);
}

Python conversion (corrected — NO rank inversion):

# Python chess lib: square is already 0x3F, NO inversion needed
# chess.square_file(sq) = file (0-7)
# chess.square_rank(sq) = rank (0-7), rank 0 = rank 1 (white side)
sq063 = rank_ * 8 + file_   # NO (7 - rank_) inversion!

3.2 Piece Types: Micro-Max ↔ Polyglot

Micro-Max stores the piece type in the lower 3 bits of the b[] array. The numbering does not match the Polyglot standard.

Conversion array mm_to_std[8]:

/*           0  1  2  3  4  5  6  7  */
/* MM type:   -  P  P  N  K  B  R  Q  */
/* Std type:  0  1  1  2  6  3  4  5  */
static const int mm_to_std[8] = {0, 1, 1, 2, 6, 3, 4, 5};

3.3 Colors and Side to Move

In micro-Max, color is encoded by a bit in the square value:

• Bit 3 (8) = white → value in range 8–15
• Bit 4 (16) = black → value in range 16–23

Side to move: In micro-Max, k=8 means white to move, k=16 means black to move. In the Zobrist hash, if side_val != 8 (black to move), ZobristTable[768] is XORed.

/* Side to move: k=8 → white (no XOR), k=16 → black (XOR) */
if (side_val != 8) {
    h ^= ZobristTable[768];
}

3.4 Castling Rights

Castling is encoded in the Zobrist hash by 4 separate numbers (indices 769–772):

Additionally, the king must be on its home square:

• White king: b[0x74] == 12 (e1, type 4 + 8)
• Black king: b[0x04] == 20 (e8, type 4 + 16)

Function can_castle():

static int can_castle(int white, int kingside) {
    if (white) {
        if (b[0x74] != 12) return 0;            /* white king on e1 */
        if (kingside  && b[0x77] != 14) return 0;/* white rook on h1 */
        if (!kingside && b[0x70] != 14) return 0;/* white rook on a1 */
    } else {
        if (b[0x04] != 20) return 0;            /* black king on e8 */
        if (kingside  && b[0x07] != 22) return 0;/* black rook on h8 */
        if (!kingside && b[0x00] != 22) return 0;/* black rook on a8 */
    }
    return 1;
}

3.5 En Passant

If a pawn just moved two squares forward, micro-Max stores the “skipped” square in variable E1. In the Zobrist hash this is XORed with a number from the range 773–780 (one per file a–h):

/* En passant */
if (E1 != 0 && !(E1 & 0x88)) {
    h ^= ZobristTable[773 + (E1 & 7)];
}

4. Project Files

5. Zobrist Hashing

Zobrist hash is the XOR of pseudo-random numbers, one per position component:

• Pieces on squares: 12 types (6 pieces × 2 colors) × 64 squares = 768 numbers (indices 0–767)
• Side to move: 1 number (index 768)
• Castling: 4 numbers (indices 769–772)
• En passant: 8 numbers (indices 773–780)

Total: 781 numbers, each 64-bit.

Index Structure

index = color * 384 + (piece_type - 1) * 64 + square_063

  color:      0 = black, 1 = white (C)  /  0 = white, 1 = black (Python)
  piece_type: 1 = pawn, 2 = knight, 3 = bishop, 4 = rook, 5 = queen, 6 = king
  square:     0..63 (a1=0, h8=63)

  color * 384:   0 (first color) or 384 (second color)
  piece * 64:    0, 64, 128, 192, 256, 320

C function compute_zobrist()

uint64_t compute_zobrist(int side_val) {
    uint64_t h = 0;
    int sq;

    for (sq = 0; sq < 128; sq++) {
        if (sq & 0x88) continue;      /* skip off-board */
        int p = b[sq];
        if (p == 0) continue;        /* empty square */
        int mm_type = p & 7;
        int std_type = mm_to_std[mm_type];
        int color = (p & 8) ? 1 : 0;  /* white=1, black=0 */
        int sq063 = sq88_to_063(sq);

        h ^= ZobristTable[color * 384 + (std_type - 1) * 64 + sq063];
    }

    if (side_val != 8) h ^= ZobristTable[768];  /* black to move */
    if (can_castle(1, 1)) h ^= ZobristTable[769];
    if (can_castle(1, 0)) h ^= ZobristTable[770];
    if (can_castle(0, 1)) h ^= ZobristTable[771];
    if (can_castle(0, 0)) h ^= ZobristTable[772];

    if (E1 != 0 && !(E1 & 0x88))
        h ^= ZobristTable[773 + (E1 & 7)];

    return h;
}

Python function zobrist_key_stm32() (corrected v7.0)

MM_TO_STD = [0, 1, 1, 2, 6, 3, 4, 5]

def get_mm_type(piece):
    if piece.piece_type == chess.PAWN:   return 2 if piece.color else 1
    elif piece.piece_type == chess.KNIGHT: return 3
    elif piece.piece_type == chess.BISHOP: return 5
    elif piece.piece_type == chess.ROOK:   return 6
    elif piece.piece_type == chess.QUEEN:  return 7
    elif piece.piece_type == chess.KING:   return 4
    return 0

def zobrist_key_stm32(board, ZT):
    key = 0
    for sq in chess.SQUARES:
        piece = board.piece_at(sq)
        if piece is None:
            continue
        mm_type = get_mm_type(piece)
        std_type = MM_TO_STD[mm_type]
        # FIXED: white=0, black=1
        color = 0 if piece.color else 1
        file_ = chess.square_file(sq)
        rank_ = chess.square_rank(sq)
        # FIXED: NO rank inversion
        sq063 = rank_ * 8 + file_
        z_index = color * 384 + (std_type - 1) * 64 + sq063
        key ^= ZT[z_index]
    if not board.turn:  # black to move
        key ^= ZT[768]
    # Castling
    if board.castling_rights & chess.BB_H1: key ^= ZT[769]
    if board.castling_rights & chess.BB_A1: key ^= ZT[770]
    if board.castling_rights & chess.BB_H8: key ^= ZT[771]
    if board.castling_rights & chess.BB_A8: key ^= ZT[772]
    # En passant
    if board.ep_square is not None:
        key ^= ZT[773 + chess.square_file(board.ep_square)]
    return key & 0xFFFFFFFF

Verified Keys (debug_keys.py validation)

The following 4 keys from the 19-entry reference book were reproduced exactly by the corrected Python function:

6. polyglot.c — C Implementation

The file contains three key functions. Addresses are from the IAR linker map file.

6.1 compute_zobrist(int side_val)

See Section 5. Returns the 64-bit Zobrist hash of the current position on board b[]. Address: 0x800'4663, size: 0xF8.

6.2 polyglot_find_move(uint32_t key, uint16_t *out_move)

Binary search in the sorted array debut_book[]:

int polyglot_find_move(uint32_t key, uint16_t *out_move) {
    extern const polyglot_entry_t debut_book[];
    extern const int debut_book_size;

    int l = 0, r = debut_book_size - 1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (debut_book[m].key == key) {
            *out_move = debut_book[m].move;
            return 1;       /* found */
        } else if (debut_book[m].key < key) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return 0;               /* not found */
}

Address: 0x800'475B, size: 0x42.

6.3 polyglot_to_mm(uint16_t pg_move, int *from88, int *to88)

Converts a Polyglot move (6+6 bits) to 0x88 coordinates for micro-Max:

void polyglot_to_mm(uint16_t pg_move, int *from88, int *to88) {
    int from063 = pg_move & 0x3F;
    int to063   = (pg_move >> 6) & 0x3F;

    *from88 = (7 - (from063 / 8)) * 16 + (from063 % 8);
    *to88   = (7 - (to063   / 8)) * 16 + (to063   % 8);
}

Address: 0x800'47C9, size: 0x48. Polyglot move: bits 0–5 = “from” square (0x3F), bits 6–11 = “to” square, bits 12–14 = promotion piece (0 = none, 1 = knight, 2 = bishop, 3 = rook, 4 = queen).

Python move encoding (corrected v7.0):

def move_to_polyglot(move):
    from_sq = move.from_square
    to_sq = move.to_square
    file_from = chess.square_file(from_sq)
    rank_from = chess.square_rank(from_sq)
    file_to = chess.square_file(to_sq)
    rank_to = chess.square_rank(to_sq)
    # FIXED: NO rank inversion
    sq063_from = rank_from * 8 + file_from
    sq063_to = rank_to * 8 + file_to
    return (sq063_from & 0x3F) | ((sq063_to & 0x3F) << 6)

7. main.c — Integration into the Game Loop

7.1 Global Variables

int side, one, book_pending = 0;   /* book_pending — book flag */
uint16_t pg_move;                /* move from book */
uint32_t book_key;              /* Zobrist key */
int from88, to88;               /* coordinates for engine */

7.2 Book Block (before the input wait loop)

/* === OPENING BOOK === */
if (book_pending) {
    book_pending = 0;
    NVIC_DisableIRQ(USART1_IRQn);
    USART1->CR1 &= ~USART_CR1_RE;

    book_key = (uint32_t)(compute_zobrist(k) & 0xFFFFFFFFU);

    if (polyglot_find_move(book_key, &pg_move)) {
        uart1_write('B');                        /* marker: book move */
        polyglot_to_mm(pg_move, &from88, &to88);

        /* Write move to c[] — as if human entered it */
        c[0] = 'a' + (from88 & 7);
        c[1] = '8' - (from88 >> 4);
        c[2] = 'a' + (to88 & 7);
        c[3] = '8' - (to88 >> 4);
        c[4] = '\n';
        data_count = -1;

        goto skip_wait;  /* skip the input wait loop */
    }

    uart1_write('D');                            /* marker: engine search */
    USART1->CR1 |= USART_CR1_RE;
    NVIC_EnableIRQ(USART1_IRQn);
}

7.3 After D() — Set Book Flag

if (side != k) {
    half_m++;

    if (side == 8) book_pending = 1;  /* white moved → black from book */

    char ssd = sd == 0 ? 'w' : 'b';
    /* ... move display ... */
}

7.4 After nxt: Label

nxt:;

side = k;
k ^= D(k, -I, I, Q, 1, j++, O, 8, 2) - I ? 0 : 24;

8. The book_pending Mechanism

Key idea: the book move is fed into the engine via the same path as a human move — through the c[] array, parsing, GameHistory validation, and the D() call. This guarantees the move is checked for legality and correctly applied.

Why this is reliable: The book move goes through D(k, -I, I, ...) with K and L set from the book. D() checks legality (if the move is impossible, D() will not return I and k will not change). This prevents “hanging” on an impossible book move.

9. Book Generation (Python + Stockfish)

The book is generated offline on a PC. The Python script uses three stages:

Stage 1: Main Openings (4 positions)

Generates positions after the 4 principal first moves: e2e4, d2d4, c2c4, g1f3. These are positions where black is to move (1 ply deep).

Stage 2: Continuations (~400 positions)

For each of the 4 main openings:

1. Get top-5 best black responses from Stockfish (depth 12, multipv=5)
2. For each response, enumerate all white replies (3rd ply)
3. Save the resulting position (black to move again, 3rd ply)

This yields ~4 × 5 × 20 ≈ 400 positions with deep, strong continuations.

Stage 3: Random Fill (~596 positions)

Fill the remaining slots up to BOOK_SIZE = 1000 with random positions at odd plies (3, 5, 7, 9, 11, 13) — always black to move.

Entry Structure in debut_book.c

typedef struct {
    uint32_t key;     /* Zobrist hash (lower 32 bits) */
    uint16_t move;    /* Polyglot move: from(6) | to(6) | promo(3) */
    uint8_t  weight;  /* weight (1 = best move, see note) */
} polyglot_entry_t;

Example Entries

const polyglot_entry_t debut_book[] = {
    {0x12345678U, 0x0F12U, 1},  /* position → e2e4 */
    {0x9ABCDEF0U, 0x1C30U, 1},  /* position → c7c5 */
    /* ... 998 entries ... */
};
const int debut_book_size = 1000;

Validation Tool: debug_keys.py

A diagnostic script that loads zobrist_table.h, computes Zobrist keys for 4 known positions (after 1.e4, 1.c4, 1.d4, 1.Nf3) using all 16 combinations of parameters (rank inversion, color mapping, castling, en passant), and finds the combination that matches the known keys from debut_book.c.

Result: invert_rank=False, color_white_is_1=False, include_castling=True, include_ep=True — all 4 keys matched.

10. Full Data Flow (Diagram)

11. Troubleshooting

12. Memory Consumption

Based on the IAR linker map file micro_Max_ver4_2.map (1000 entries):

Flash (32 KB total on STM32F103C6)

Book footprint: 8,004 bytes (8 KB) for 1000 entries × 7 bytes + 4 bytes size variable. Free space allows ~851 more entries (up to ~1851 total).

RAM (10 KB total on STM32F103C6)

Scaling

13. Bug History & Fixes

All bugs discovered and fixed during development of the Polyglot book integration:

Validation: debug_keys.py

A diagnostic script that loads zobrist_table.h, computes Zobrist keys for 4 known positions using all 16 combinations of parameters, and finds the correct one. Output:

*** FOUND! ***
  invert_rank = False
  color_white_is_1 = False
  include_castling = True
  include_ep = True

  1.e4 (black):  0x66FF886D (expected 0x66FF886D) ✓
  1.c4 (black):  0x9941BC1A (expected 0x9941BC1A) ✓
  1.d4 (black):  0xD75F281A (expected 0xD75F281A) ✓
  1.Nf3 (black): 0x835FB199 (expected 0x835FB199) ✓

14. Communication Protocol: STM32 ↔ Server

The STM32 communicates with a Python chess server over UART/Wi-Fi (ESP-01). The protocol is text-based.

Message Formats

Move Lifecycle