White to move
Captured
Moves
No moves yet.
A classical alpha–beta search engine — the same family as every chess program from the 1950s up to Deep Blue. No neural network, no opening book, no endgame tables.
Everything depends on putting a number on a position. In chess that is surprisingly easy: count the material. Each piece is worth hundredths of a pawn — pawn 100, knight 320, bishop 330, rook 500, queen 900 — and adding them up already plays a recognisable game.
On top sits a piece-square table: a bonus or penalty per square. That is where knowledge such as knights belong near the centre and pawns gain value as they advance enters. The king gets two tables — middlegame, where it hides, and endgame, where it marches to the centre — switched once non-pawn material drops below a threshold.
Go has no such shortcut, which is why the Go engine here uses a completely different algorithm: nobody has written a decent way to judge a Go position by looking at it, so it plays the game out instead.
The search is minimax: assume both sides play their best move, and repeat down the tree. Because chess is zero-sum, both sides can share one routine that negates the score at each level — that is negamax.
Alpha–beta makes it affordable. The search carries two bounds: alpha, the best score already guaranteed to us, and beta, the best the opponent can hold us to. Once a reply proves a line is worse than something already available, the rest of that line is abandoned unexamined — there is no need to know how bad it is, only that it is bad enough to reject.
The result is identical to searching everything, with a large fraction of the tree never visited.
That saving only materialises if strong moves are tried first, since a cut-off needs something good to have been found already. So moves are sorted by a cheap guess: Most Valuable Victim, Least Valuable Aggressor. Capturing a queen with a pawn is examined before capturing a pawn with a queen. Promotions sort near the top for the same reason.
With branching factor b (about 35 in chess) and depth d, the cost depends entirely on how well the moves are ordered:
| Move ordering | Nodes searched | |
|---|---|---|
| None (plain minimax) | O(bd) | every node visited |
| Worst case | O(bd) | no cut-off ever fires |
| Random | O(b3d/4) | |
| Perfect | O(bd/2) | the theoretical floor |
Perfect ordering means the best move is searched first at every node. The pruned tree then holds exactly (Knuth–Moore):
That is the square root of the full tree — the same work reaches twice the depth. Note the top two rows: alpha–beta's worst case is no better than plain minimax, so the entire gain lives in the ordering.
This engine orders captures by MVV-LVA and re-sorts the root each iteration, but has no transposition table or killer heuristics, so quiet moves at interior nodes are essentially unordered — expect nearer O(b2d/3). Quiescence sits outside d entirely, so the true node count also depends on how tactical the position is.
Stopping at a fixed depth creates the horizon effect: if the last move counted is our capture of a defended pawn, the engine records a pawn won and never sees the recapture. Cutting off mid-trade produces a number that is simply wrong.
So at the depth limit the search continues with captures only, until the position is quiet and the material count stable. It may also stand pat: if the position is already good enough without capturing, that is the answer, since nobody is obliged to keep trading.
Rather than search straight to the target depth, the engine searches depth 1, then 2, then 3, each pass replacing the previous best move. The early passes are thrown away, but buy two things:
The clock is checked every 1,024 positions, since reading the time is not free.
A forced mate is scored as a huge number minus the plies it takes. Without that offset every mate looks equally good and the engine would shuffle around in a mating net forever; with it, it prefers the fastest mate and, when losing, the slowest.
Search depth and thinking time.
| Level | Depth | Time limit |
|---|---|---|
| Easy | 2 plies | 0.3 s |
| Medium | 3 plies | 0.9 s |
| Hard | 4 plies | 2.2 s |
Every level extends those plies with quiescence, so tactics reach deeper than the numbers suggest. Easy also picks at random among moves within about nine tenths of a pawn of the best — varied, beatable play without deliberate blundering. To do that it gives up alpha–beta at the top level, needing true scores for every candidate rather than only knowing which one won.
This is a deliberately compact engine: no transposition table, so positions reached by different move orders are searched again from scratch; no killer-move or history heuristics; no null-move or late-move reductions; no opening book, no endgame tablebase. Four plies plus quiescence finds short tactics reliably and misses anything deeper, and because the evaluation is only material and piece squares, it plays without a plan — no notion of pawn structure, king safety beyond a table, or the initiative.
It does know the rules properly: castling rights, en passant, underpromotion, and draws by stalemate, the fifty-move rule, threefold repetition and insufficient material.