Theory · Algorithms · Formulas · Strategy
TrapGrid is a two-player combinatorial strategy game based on the classic Isolation concept. Players move on a 7×7 grid. Every cell a player leaves behind becomes permanently blocked. The player who cannot make a valid move loses.
BFS is the backbone of the heuristic. It performs a flood-fill from a player's current position and counts every empty cell reachable without crossing blocked or occupied cells. This count equals the player's territory — how much of the board they still own. A player with large territory has more room to manoeuvre; a player cornered into a small pocket is losing.
visited[7][7] boolean grid, all false. Push the player's position onto a queue. Mark it visited. Set count = 0.count. For each of 4 neighbours: skip if out-of-bounds, already visited, or not CELL_EMPTY.count equals the number of reachable cells — the player's territory score.Territory Map: Running BFS from both players simultaneously produces a coloured zone map. Cells reachable only by P1 are green, only by P2 are blue, and cells reachable by both (contested) are purple.
Minimax is a recursive algorithm for two-player zero-sum games. The AI (maximiser) tries to pick the move that leads to the highest heuristic score. The opponent (minimiser) is assumed to play perfectly and will always choose the move that is worst for the AI. The algorithm explores all possible futures up to a given depth, then evaluates leaf nodes with the heuristic function.
+100,000 (AI wins) or -100,000 (AI loses). At depth 0, call the heuristic.Alpha-Beta pruning is an optimisation layered on top of Minimax. It maintains two values — alpha and beta — which represent the best already-explored options for the maximiser and minimiser respectively. When β ≤ α, the current branch cannot influence the final decision and is cut (pruned). This can reduce the number of nodes from O(b^d) to O(b^(d/2)), effectively doubling the searchable depth.
-∞. Updated when MAX finds a better move. If a MIN node's value drops below alpha, MAX already has something better — prune remaining siblings.+∞. Updated when MIN finds a worse move for MAX. If a MAX node's value exceeds beta, MIN already has something better — prune remaining siblings.| Property | Plain Minimax | Minimax + Alpha-Beta |
|---|---|---|
| Time complexity | O(b^d) | O(b^(d/2)) best case |
| Nodes at depth 5 (b≈4) | ~1024 | ~32 best case |
| Depth at same cost | 3–4 | 5–8 with move ordering |
| Move ordering benefit | None | Critical — sorts to maximise cuts |
| Correctness | Exact | Exact (same result) |
Alpha-Beta pruning works best when the strongest moves are searched first. If the first move examined is already close to optimal, subsequent branches are quickly cut. TrapGrid uses a quick pre-sort of all legal moves using a lightweight BFS evaluation before calling the full Minimax tree.
At depth-0 leaf nodes (and for logging/display), the game state is evaluated by a weighted multi-component heuristic. A positive result means the AI is winning; negative means the human is ahead. The formula balances long-term territory ownership with immediate tactical pressure.
A fixed depth is wasteful — in the endgame when very few moves are available, a depth-5 search may explore only a handful of nodes. Conversely, branching is high mid-game. TrapGrid uses adaptive depth: the base depth is 5 but automatically scales up to 8 when both players have few remaining moves, making the AI near-perfect in critical endgame situations.
| Min Available Moves | Phase | Search Depth | Why |
|---|---|---|---|
| > 6 | Mid-game | 5 | High branching factor — depth 5 is already expensive |
| 5–6 | Early Endgame | 6 | Fewer branches — can afford to look one ply deeper |
| 3–4 | Late Endgame | 7 | Very few branches — two extra plies come cheap |
| ≤ 2 | Critical | 8 | Near-terminal — near-perfect play possible, small tree |
Linear scoring misses critical positions. A player with 1 immediate move vs 2 is not just "1 unit worse" — they are on the edge of defeat. TrapGrid uses non-linear step functions for isolation to ensure the AI treats near-trapped states as nearly catastrophic.
immediate == 0 → -200 penalty ensures the AI treats these near-death states with extreme caution.Wall Danger models the danger of being trapped in a corner or edge. Corners have only 2 neighbours (maximum), making them the easiest places to seal someone. Edges have 3. The danger score penalises being in these locations and having few immediate moves simultaneously.
+4. Only 2 adjacent cells. One blocked neighbour = only 1 escape. Two blocked = trapped. Avoid corners at all cost — or use them to trap the opponent!+2. Three adjacent cells. Less dangerous than corners but still restricts movement. The AI avoids edges unless tactically forced.+3 wall danger. Combined with corner/edge position this compounds quickly. danger = 4 + (2-0)×3 = 10 for a trapped corner.TrapGrid has deep strategy despite simple rules. The key insight is that territory matters more than position — a player who secures a large pocket of cells will outlast one who chases the opponent. Understanding the AI's priorities lets you exploit its blind spots.
Parity Rule (critical endgame concept):
| Operation | Time Complexity | Space | Notes |
|---|---|---|---|
| Single BFS | O(R×C) = O(49) | O(49) | Constant on 7×7 board |
| getValidMoves | O(4) = O(1) | O(1) | 4 directions only |
| orderMoves | O(m × 49) | O(m) | m = number of legal moves |
| Minimax (no pruning) | O(b^d) | O(d) | b ≈ 4, d = 5 → ~1024 nodes |
| Minimax + Alpha-Beta | O(b^(d/2)) | O(d) | Best case ≈ 32 nodes at depth 5 |
| Full AI turn (typical) | O(b^d × 49) | O(d × 49) | Sub-second in practice |
| Territory map | O(2 × 49) = O(98) | O(49) | Two BFS runs per update |
| Danger/heatmap | O(49) | O(49) | Manhattan distance per cell |
Game State Space: The total number of distinct TrapGrid positions is bounded by the number of ways to choose which cells are blocked, which are occupied, and who moves next — a massive combinatorial space. Minimax doesn't enumerate all of it; it only searches the sub-tree reachable from the current position, pruning aggressively. This is what makes depth-5 search practical in real-time.