PlyOracle

Algorithms & Numeric

A negamax + alpha-beta tic-tac-toe AI playing itself. Negamax folds minimax into one routine by negating the returned score at each ply (score = -negamax(child), a G_SUB 0,x), with a running G_SMAX for the best move and an alpha-beta cutoff that prunes the search. That alternating-sign recursion is a shape the battery other recursive demos never produce. Compiler stress-test #92.

loading core…

Self-running — the AI plays itself; HUD tallies X / O wins and draws.

Click the screen to focus, then watch. Tab away and it pauses.

\1 A 5×5 grid of points is transformed each frame by a matrix built from a short cascade of rotation matrices, then drawn as a wireframe. As the phase advances the whole lattice rotates and shears. Every one of those matrix products returns an 8-byte struct by value. \2 class="rp-code">// Negamax: one routine for both players, because each ply just negates the child score. int16_t negamax(me, opp, alpha, beta, depth) { if (wins(opp)) return -(10 - depth); // opponent won (depth-weighted) if (full || depth>=MAXD) return 0; int16_t best = -32000; for (each empty cell m) { int16_t s = -negamax(opp, me|bit, -beta, -alpha, depth+1); // G_SUB 0,x negate-on-return if (s > best) best = s; // running G_SMAX if (best > alpha) alpha = best; if (alpha >= beta) break; // alpha-beta cutoff (prune) } return best; }

Cleanup handlers are how C code does RAII-style resource release (closing files, freeing locks) without a destructor. Correctly duplicating them onto every exit edge — and only those edges, in the right order — is a real obligation of the front-end + backend, and this demo checks it end to end on the 65816.

Compiler stress-test

Item	What it exercises
negate-on-return	Negamax collapses minimax into one routine by observing that your best score is the negation of your opponent reply: score = -negamax(child). That unary minus on a function return value is a G_SUB 0,x the backend must emit on the recursion return path — a shape the battery other recursive demos (#17, #18) never produce.
running max + cutoff	Each node keeps the best child score with a running G_SMAX and maintains an alpha window; the moment alpha meets beta it breaks out of the move loop (the alpha-beta cutoff), producing a branch-heavy prune control-flow graph interleaved with the recursion.
bitboard tic-tac-toe	The board is two 9-bit masks; win detection is eight line-mask ANDs. Both players are driven by the same negamax, so you watch the search play itself. A search-depth cap keeps the full-width tree inside the SNES frame budget without changing the recursion shape.
exact minimax	Everything is integer, so the chosen moves are deterministic and bit-identical host vs target. A single wrong negation, max, or mis-pruned branch would pick a different move and diverge the self-play CRC.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg and MAME. Hit Verify fidelity to reproduce the build gate's WRAM assert (negamax CRC 0x6146 — a fold of the self-play move sequence) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean.