Calculator Game Solver
A Java Swing app that solves the calculator game with dynamic programming, lets you play it interactively with perfect-play hints and a live decision tree, and benchmarks a family of DP solver strategies against each other.
Calculator Game Solver
Practice 5 for the Advanced Algorithms course (21747) at the Universitat de les Illes Balears. A Java Swing application, on a Model–View–Controller architecture, that determines the winner of the calculator game with dynamic programming, lets you play it interactively with perfect-play hints, and benchmarks several solver strategies against each other.
The game
The calculator starts on a number and two players alternate turns adding a digit to the running total; the digit a player may add is constrained by a keypad layout (which keys are reachable from the current one). The player who reaches 31 or goes over loses. Because the game is finite, deterministic and fully observable, the outcome under optimal play is decided by dynamic programming: the value of a position is computed from the values of the positions it can lead to, so the solver can tell — from any state — which player wins and which move preserves that win. The app exposes this as an interactive match with hints, as a full decision tree, and as a benchmark of how different DP formulations scale.
About
- A family of DP strategies — the same game is solved by interchangeable solvers: pure recursion (no memo), top-down memoized (map and array variants), bottom-up tabulation, a symmetric solver that exploits state symmetry, and an alpha-beta solver — chosen through a factory and compared in the benchmark.
- Interactive play — a session service, a hint computer and an auto-match runner drive human-vs-human, human-vs-optimal and auto-play matches, always able to point out the winning move.
- Decision tree — a tree builder expands the game into a tree that the view lays out and renders, so the recursive structure of the game is visible.
- Distinct-game counting — a companion counter enumerates how many essentially different games exist, a combinatorial counterpart to the DP.
- Keypad layouts — a layout generator and neighbour index build the adjacency that constrains the legal moves.
- Two workflows, one shared view — an interactive game tab (calculator display, keypad, live decision tree) and a benchmark tab; the side panels follow the active tab.
Executing the project
Requires a JDK 17 or newer — plain Java with Swing, no external dependencies or build tool. Open the P5/ folder in IntelliJ IDEA and run practice5.Main. Play a match in the game tab and follow the hints and the decision tree; in the benchmark tab compare how the recursive, memoized and tabulated solvers scale.