Ayaan's BBSTime online 00:00

Pyngine write-up

Pyngine by Ayaan Afridi. Python, Tkinter, UCI.

  ==============================================================
  PYNGINE: A CHESS ENGINE IN PURE PYTHON  write-up
  Python 3.12+, no dependencies, Tkinter GUI, UCI protocol
  ==============================================================

  1.0  THE GOAL
  -------------
  A complete chess program written from scratch in Python with
  no dependencies: legal move generation, search, evaluation, a
  desktop app and a UCI interface for standard chess GUIs.
  Python is slow for this, so every speed gain had to be earned,
  and nothing was kept unless the correctness tests stayed
  green.

  Stockfish is never used during play. It only appears in the
  benchmark tools, as a sparring partner.

  2.0  ARCHITECTURE
  -----------------
    constants / move / zobrist
              |
    attacks -> board -> move generation -> perft
              |              |
           notation      evaluation
                             |
    ordering + transposition -> search -> UCI
                                  |
                       GUI and benchmark tools

  Dependencies only point one way. The engine never imports the
  GUI or the benchmarks, so an external engine cannot sneak into
  a normal search.

  Part         Approach                                           
  -----------  -------------------------------------------------  
  Board        Bitboards + mailbox, Zobrist hash, self-checks     
  Moves        Direct legal generation with pin/check masks       
  Search       Iterative deepening negamax, alpha-beta            
               Transposition table, aspiration windows            
               Quiescence search with SEE, LMR, pruning           
               History heuristics for move ordering               
  Evaluation   Hand-written, tapered middlegame/endgame           
  Endgames     Exact 24 KiB king-and-pawn (KPK) bitbase           
  Interfaces   Tkinter desktop app, UCI over stdin/stdout         

  The rest of this section follows the order in which a move
  gets found: how the position is stored, how the legal moves
  are produced, how the search picks one, and how a position is
  scored.

  2.1  THE BOARD
  --------------
  The position is stored two ways at once. Twelve bitboards hold
  one 64-bit integer for each piece type and colour, where bit n
  is set when that piece stands on square n (a1 is 0, h8 is 63).
  Questions like "which squares does this rook hit?" or "is this
  file open?" become a few AND, OR and shift operations on whole
  integers. Next to them, a 64-entry mailbox array answers "what
  is on e4?" in one lookup.

  A move is a plain integer, so the search never allocates an
  object for a move:
    bits  0-5   from square      16-19  captured piece
          6-11  to square        20-23  promotion piece
         12-15  moving piece     24-28  flags: capture, double
                                        push, en passant,
                                        castle, promotion

  make_move updates the bitboards, the mailbox, the castling
  rights, the en passant square, the fifty-move counter and the
  hash, then returns a small undo record. unmake_move restores
  everything from that record. The search walks the whole tree
  on a single board by making and unmaking moves, and never
  copies it.

  Each position also has a 64-bit Zobrist hash. Every piece on
  every square, every castling right, every en passant file and
  the side to move gets its own fixed random key. The keys come
  from SplitMix64 with a fixed seed, so runs are repeatable. The
  hash is the XOR of the keys for everything on the board. XOR
  undoes itself, so a move updates the hash with two to four
  XORs instead of recomputing it. The hash drives repetition
  detection and the transposition table.

  2.2  MOVE GENERATION
  --------------------
  Knight, king and pawn attacks are precomputed for every
  square. Sliding pieces use precomputed rays: for each square
  and each of the eight directions, a bitboard of every square
  from there to the edge. To find what a rook on a1 sees:
    ray north from a1    a2 a3 a4 a5 a6 a7 a8
    pieces on that ray         a4       a7
    nearest blocker            a4
    attacks = ray from a1 XOR ray from a4  =  a2 a3 a4

  The nearest blocker is the lowest set bit for directions that
  go up the board and the highest set bit for directions that go
  down. Python finds both with integer bit tricks.

  The simple way to get legal moves is to generate every
  pseudo-legal move, play it, and throw it away if your own king
  is left in check. That is correct but slow. Instead, Pyngine
  works out three things once per position:
  * Checkers: the enemy pieces attacking the king. If there are
    two, only king moves can be legal. If there is one, every
    other move must capture the checker or land between it and
    the king, so one mask (the checker plus the squares in
    between) filters them all.
  * Pins: an x-ray from the king along rook and bishop lines
    that looks through one of its own pieces. If an enemy slider
    sits behind that piece, the piece is pinned and may only
    move along the line between the king and the pinner.
  * King danger: every square the enemy attacks, worked out with
    the king lifted off the board. Without that, the king could
    step backwards along a rook's line and look safe only
    because it was blocking the rook itself.

  After that, each candidate move costs one or two mask tests.
  En passant is the only move that still gets played out and
  checked, because it removes two pawns from the same rank and
  can expose the king sideways.

  Perft tests all of this. It counts every possible sequence of
  moves to a fixed depth from a known position. The correct
  counts are published, so a single missing or extra move
  anywhere shows up as a wrong total.

  2.3  SEARCH: NEGAMAX AND ALPHA-BETA
  -----------------------------------
  Chess is zero-sum: a position worth +3 to White is worth -3 to
  Black. Negamax uses that to write minimax as a single
  function, where a position's score is the best of minus the
  score of each position one move later. Searching d moves ahead
  this way visits about 35^d positions, which is hopeless beyond
  a few moves.

  Alpha-beta prunes most of that tree without changing the
  answer. The search carries a window. Alpha is the score the
  side to move is already guaranteed through another line. Beta
  is the most the opponent will allow before steering away. As
  soon as one move scores beta or more, the opponent will never
  let the game reach this position, so the remaining moves are
  skipped. That is a beta cutoff. With perfect move ordering,
  alpha-beta visits about the square root of the full tree,
  which roughly doubles the depth reached in the same time.

  Four refinements sit on top:
  * Iterative deepening. Search to depth 1, then 2, then 3,
    until time runs out. Each pass fills the hash table and the
    history tables, so the next pass orders its moves better,
    and there is always a finished answer ready to play.
  * Aspiration windows. From depth 3, each pass starts with a
    window 35 centipawns either side of the last score, because
    a narrow window cuts off more. If the result lands outside
    it, the window doubles and the depth is searched again, up
    to three times before falling back to the full window.
  * Principal variation search (PVS). The first move, usually
    the best one, is searched with the full window. Every later
    move gets a zero-width window that only asks "is this better
    than what I have?". Proving "no" is cheap. A move that
    answers "yes" is searched again with the full window.
  * Draws and mates. Threefold repetition, the fifty-move rule
    and insufficient material score 0. Mate scores count the
    moves to mate, so a mate in two beats a mate in five, and
    mate-distance pruning skips lines that cannot beat a mate
    already found.

  One node of the search, step by step:
    draw by repetition, 50 moves or material?   -> 0
    hash table holds a deep enough answer?      -> return it
    null move: pass the turn, still >= beta?    -> cut
    order the moves (2.5)
    for each move:
      hopeless quiet move? (futility, late)     -> skip
      first move: full window
      later moves: reduced depth, zero window,
                   searched again if it beats alpha
      score >= beta?  -> update killers, history; cut
    store the result in the hash table
    at depth 0, hand over to quiescence (2.6)

  2.4  SEARCHING LESS
  -------------------
  Alpha-beta on its own is exact. The techniques below give up a
  little certainty in exchange for a lot of depth. Each one is
  fenced in by conditions that were found the hard way (section
  4.0).
  * Null-move pruning. If the position already looks worth at
    least beta, the engine passes and lets the opponent move
    twice in a row, searching with the depth cut by 2 extra
    plies (3 at depth 7 and up). If the opponent still cannot
    drag the score below beta, no real move would either, so the
    node is cut. It is skipped in check and when only pawns are
    left, because in zugzwang positions passing would really be
    the best move.
  * Late move reductions. With good ordering, the best move is
    nearly always one of the first few, so quiet moves from the
    fourth one on are searched shallower. The reduction comes
    from a table, roughly ln(depth) x ln(move number) / 2,
    capped at 4. A move with a good history score gets one ply
    less reduction, and one with a very bad score gets one more.
    If a reduced move beats alpha anyway, it is searched again
    at full depth.
  * Futility pruning. Within two plies of the leaves, if the
    static score plus 120 centipawns per ply still cannot reach
    alpha, quiet moves are not worth trying.
  * Late move pruning. Within three plies of the leaves, once
    4+depth^2 moves have been tried, the remaining quiet moves
    are skipped.

  None of these touch captures, promotions, moves that give
  check, castling, pawn moves, the hash move, positions in
  check, nodes on the main line, or scores near mate.

  2.5  MOVE ORDERING
  ------------------
  Alpha-beta is only as good as its move order: the sooner the
  best move is tried, the sooner the rest get cut. Moves come
  out in stages:
    1  hash move       the best move stored for this position
    2  good captures   SEE >= 0, then MVV-LVA
    3  promotions
    4  killer moves    two per ply
    5  countermove     what last refuted their previous move
    6  other quiets    by history score
    7  bad captures    lose material by SEE

  * MVV-LVA (most valuable victim, least valuable attacker)
    tries pawn takes queen before queen takes pawn. Capture
    history adjusts that by how often each capture has actually
    worked.
  * Killers are quiet moves that caused a cutoff at the same
    depth in a neighbouring line. They often work again.
  * History scores every quiet move by side, from-square and
    to-square. A move that causes a cutoff earns depth^2, and
    the quiet moves tried before it lose the same amount. A
    gravity formula keeps the scores bounded, and they are
    halved at the start of each search so that old positions
    fade out. Continuation history does the same thing, keyed on
    the previous move as well.
  * Quiet moves are not scored at all until the hash move and
    the good captures have been tried. That saves work at the
    many nodes where those already cause a cutoff.

  Static exchange evaluation (SEE) plays out every capture on
  one square, with each side always recapturing with its
  cheapest piece, and returns the material result. Pieces lined
  up behind each other, such as two rooks on a file or a bishop
  behind a queen, join in as the front piece leaves. Pinned
  pieces are left out, because they cannot legally recapture.

  2.6  QUIESCENCE SEARCH
  ----------------------
  Stopping at a fixed depth has a blind spot. If the last move
  searched is queen takes pawn, the evaluation sees a pawn won
  and misses pawn takes queen on the next move. This is called
  the horizon effect. So at depth 0 the search does not evaluate
  straight away. It keeps searching captures and promotions
  only, until the position is quiet.
  * Stand pat. The side to move does not have to capture, so the
    static score is a floor. If it already reaches beta, the
    search stops there.
  * In check there is no standing pat: every legal escape is
    searched, and no escape means mate.
  * Captures that lose material by SEE are skipped. So are
    captures that cannot reach alpha even after winning the
    piece plus a 180-centipawn margin (delta pruning). A capture
    that gives check is always searched, because checking
    sacrifices win games.
  * Quiescence results go into the hash table too, stored at
    depth 0.

  2.7  TRANSPOSITION TABLE
  ------------------------
  The same position is often reached by different move orders,
  such as e4 then Nf3, or Nf3 then e4. The transposition table
  remembers what the search learned about each position, indexed
  by the low bits of its Zobrist hash. The table size is a power
  of two, so finding a slot takes one AND.

  Each entry holds the full hash, the depth searched, the score,
  the best move and a bound. Alpha-beta often proves only "at
  least X" (it cut off) or "at most X" (nothing beat alpha), so
  a stored score is marked as exact, a lower bound or an upper
  bound. On a later visit, if the entry is deep enough and its
  bound settles the question, the node returns at once. If it
  does not, the stored best move is still tried first, which is
  the biggest single win for move ordering.
  * Entries left over from earlier searches are always replaced.
    Within one search, the deeper entry wins.
  * Mate scores are stored relative to the node rather than the
    root, so a mate found at one depth reads correctly when the
    position comes up again at another.
  * The hash does not include move history, so near a repetition
    or the fifty-move limit the table is not trusted: the same
    position can be a draw along one path and not along another.

  2.8  EVALUATION
  ---------------
  When the search reaches a quiet position, it needs a number
  for who is better, in centipawns (100 is one pawn). Every term
  is worked out for White and for Black and subtracted, with
  separate middlegame and endgame values.
  * Material and piece-square tables. Each piece has a value
    (pawn 100, knight 320, bishop 335, rook 500, queen 900 in
    the middlegame; pawns rise to 120 and rooks to 515 in the
    endgame), plus a bonus or penalty for the square it stands
    on.
  * Mobility: how many squares each piece attacks.
  * Pawn structure. Doubled pawns -14, isolated pawns -12, pawns
    side by side or protected +5, and passed pawns from +4
    rising to +80 on the seventh rank (+130 in the endgame).
    Pawn structure changes rarely, so it is cached by the two
    pawn bitboards.
  * Pieces. Bishop pair +28, knights on outposts that enemy
    pawns cannot chase away +12 (+8 more if a pawn guards them),
    rooks on open files +20 and half-open files +10, a rook on
    the seventh rank +14, and control of the centre.
  * King safety, middlegame only: pawns in front of the king,
    open files beside it, and -8 for every enemy attack on the
    squares around it.
  * Tempo: +12 for the side to move.

  Tapering blends the two sets of values. The phase counts the
  pieces left on the board: 1 per knight or bishop, 2 per rook
  and 4 per queen, which makes 24 at the start. The score is
  (middlegame x phase + endgame x (24 - phase)) / 24, so
  priorities shift smoothly as pieces come off: king safety
  fades out, and passed pawns count for more.

  Scores are cached by hash in a 65,536-entry table, because the
  same position often gets evaluated several times in one
  search.

  2.9  ENDGAMES: THE KPK BITBASE
  ------------------------------
  King and pawn against king looks simple, but the result
  depends on exact opposition and tempo, and the hand-written
  evaluation got it wrong by about three pawns either way. So
  Pyngine solves the ending completely.

  Mirroring the board keeps the pawn on files a to d, always
  moving up. That leaves 24 pawn squares x 64 x 64 king squares
  x 2 sides to move, or 196,608 positions. They are solved by
  retrograde analysis: start from the positions where the pawn
  has promoted safely and work backwards. A position is won if
  the attacker is to move and has a move into a won position, or
  if the defender is to move and every move leads into one. This
  repeats until nothing changes, and every position left over is
  a draw.

  The result is packed into the source code in about 24 KiB, so
  there is no data file. When the search reaches a king-and-pawn
  ending, it reads the exact answer instead of guessing.

  2.10  TIME AND INTERFACES
  -------------------------
  * Time. With a clock running, each move gets the time left
    minus a 3% reserve, divided by the moves to go (30 if the
    GUI does not say), plus 80% of the increment. Before
    starting the next depth, the engine predicts its cost as
    three times the last pass, a little less once the best move
    has held for two passes. If that will not fit in the time
    left, it stops now instead of throwing away a half-finished
    pass.
  * UCI. The engine speaks the Universal Chess Interface over
    stdin and stdout (uci, position, go, stop, setoption for the
    hash size), and reports depth, score, nodes and the main
    line as it searches, so any standard chess GUI can run it.
  * Desktop app. The Tkinter app runs the search on a background
    thread with a stop signal, so the board keeps redrawing
    while the engine thinks, and shows an evaluation bar beside
    the board.

  3.0  WHAT WORKED
  ----------------
  Every change was measured before and after on the same machine
  (Python 3.13, Windows 11).

  Change                      Before      After        Gain     
  --------------------------  ----------  -----------  -------  
  Direct legal movegen        108 s       15.3 s       7x       
  Eval + SEE hot paths        1,644 NPS   2,313 NPS    +41%     
  Static-eval cache           13.3 s      11.4 s       -14%     
  Scalar eval, one pass       8,348/s     11,636/s     +36%     
  Leaner movegen              25.7 s      18.2 s       -29%     
  Movegen rows: perft depth 5. Eval rows: search benchmarks.

  * Selective search (late-move pruning, futility pruning, SEE
    pruning in quiescence, history-based reductions) cut nodes
    by 55-87% and wall time by 27-77% on three middlegame
    positions, with the same best move, score and line every
    time.
  * Paired A/B runs show what each piece is worth: without
    late-move pruning the search is 1.33x slower, without SEE
    pruning 1.74x, without the quiescence hash table 1.40x.

  4.0  WHAT DIDN'T WORK
  ---------------------
  * Late-move reductions at the root hid a mate in two. An exact
    mate oracle caught it. Reductions now apply only below the
    root at non-PV nodes, and a reduced move that improves the
    score is searched again at full depth.
  * Pruning in quiescence was throwing away checking sacrifices.
    It now keeps checks and promotions and switches off near
    mate scores.
  * King-and-pawn endgames were misjudged by about 3 pawns
    either way. An exact KPK bitbase fixed it: the error went to
    zero and the search reached depth 12 instead of 8.
  * Hash table layout: I tested dictionaries, tuples, slotted
    objects and parallel arrays. Tuples were fastest (2.36M vs
    1.76M ops/s) and arrays used a ninth of the memory, but
    neither showed an end-to-end gain, so the readable slotted
    version stayed.

  5.0  BENCHMARKS
  ---------------
  Test                          Result                            
  ----------------------------  --------------------------------  
  Perft depth 6                 119,060,324 nodes, exact, 648 s   
  Perft depth 5                 4,865,609 nodes in 18.2 s         
  Tactical suite                11/11 solved by depth 5           
  vs Stockfish 18, 1 s/move     5/11 same best move, 3/3 tactics  
  Match vs Stockfish 1320 Elo   9 wins, 3 draws, 8 losses         

  The match was 20 games at 100 ms a move with alternating
  colours and no illegal moves or time losses.

  6.0  HOW I KNOW IT'S RIGHT
  --------------------------
  * Perft node counts match the published values through depth
    6.
  * The fast move generator is checked against the old, slow one
    on 9,841 random positions.
  * Every search leaves the board exactly as it found it. Random
    games are played, fully unwound and compared with the start.
  * 161 automated tests cover rules, search, evaluation, UCI and
    the GUI.

More

Ayaan Afridi's portfolio · Veyra · VFOB · AHL API SDK · Koma