Game AI CP468 · Spring 2024
Software engineeringAI algorithms · Performance evaluation
With Jaden Ramcharan, exploring how alpha-beta pruning makes a Python minimax bot search more efficiently.
With Jaden Ramcharan
CP468 · 2024
A minimax bot can find a strong move by considering future responses, but exhaustive search repeats work that cannot affect the decision. In CP468, Jaden and I explored whether alpha-beta pruning could reduce that search while preserving the result.
Try the idea / New 2026 portfolio extension
Play against the search, or inspect the same position with and without pruning. The two algorithms seek the same optimal outcome.
Your turn. You are X; AI is O.
Choose any empty square. After the AI replies, its search counts and the reason for its move appear here.
New TypeScript reconstruction of our 2024 experiment. Game searches run in a worker on a bounded 3×3 board. Counts include the root; a cutoff skips remaining siblings. These are live counts, not the original Python timings. No training data or LLM is involved.
The work behind the interface
Co-developed with Jaden Ramcharan. We extended an existing Python minimax bot credited to Matt Kenyon / TheSharperDev, added alpha-beta pruning, compared decision runtime and evaluated gameplay against a random-move opponent. Our report and presentation were joint work; individual function ownership is not documented.
The useful question was not just “is it faster?” It was “what work can we skip without changing the decision?”
The starting bot came from TheSharperDev’s minimax tutorial. We extended it rather than claiming a from-scratch implementation.
A clear baseline makes the contribution understandable: search pruning and comparison.
Alpha-beta carries bounds through recursive minimax search. Once a branch cannot improve the available outcome, its remaining alternatives do not need evaluation. The report describes depth-sensitive terminal scoring.
The goal was to preserve the decision while reducing unnecessary search, not to train a new model.
The report records approximately 26 seconds without pruning and 2 seconds with pruning for the first decision, reaching the same result. A separate 5,000-game run against a random opponent reported 79.94% wins and draws otherwise.
Decision runtime and game outcomes answer different questions. Neither establishes performance against human experts or on larger games.
Outcome & limits
Our 2024 course report recorded an approximately 13× first-decision speedup, derived from 26 ÷ 2. The work combined Python search algorithms, baseline comparison, runtime measurement and experimental communication. The interactive example on this page was made later for this portfolio.
Historical results are reported, not newly reproduced. Hardware, repeated timing trials, variance, seeds and a reproducible environment were not documented. The original code archive has not been inspected here. The random-opponent evaluation is not a universal guarantee; this is classical search, not a trained ML model.
Without → with pruning · reported in our 2024 course project
Against a random-move opponent; evaluation, not training
Against that random opponent; remaining games reported as draws
Proposed · What I’d explore next
Try move ordering and a transposition cache that recognises rotations and reflections. Keep the unmodified search as a repeatable baseline.
Check legal moves and optimal-outcome agreement; count visited states and cache hits; repeat runtime trials including cache overhead.
Add symmetry-normalised board keys to the TypeScript reconstruction, with reproducible benchmark positions and versioned results. Compare cold and warm caches rather than publishing one fast run. This is classical adversarial search, not trained model inference. Move ordering and symmetry caching are proposed, not part of the current demo.