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