Three projects, one question:
how does decision-making break?

Connect 4 — Adversarial Search with Minimax & Alpha-Beta Pruning

Problem Framing

Connect 4 appears simple: drop pieces, connect four, win. But the game tree has over 4 trillion possible positions. An AI that evaluates every possibility would take years to make a single move. The question isn’t whether minimax works in theory — it’s how to make it work in practice.

Approach

I implemented the classic minimax algorithm with alpha-beta pruning — a technique that eliminates branches of the search tree that can’t possibly affect the final decision. The core insight: if you’ve already found a move that guarantees a certain outcome, you can skip evaluating any alternative that the opponent would never allow you to reach.

Beyond pruning, I built a custom heuristic evaluation function that scores board positions based on: potential winning lines, center control (columns 3–4 are statistically dominant), and threat patterns. This allows the AI to make intelligent decisions at limited search depths rather than requiring full tree traversal.

Technical Depth

• ›Time complexity (unoptimised): O(b^d), where b ≈ 7 and d = depth. At depth 10, this is ~282 billion nodes.
• ›With alpha-beta pruning: Reduces to O(b^(d/2)) in the best case — from 282 billion to ~530,000 nodes at depth 10.
• ›Move ordering (centre-first) improves pruning by ~40% over random ordering — but more sophisticated ordering would require additional computation, creating a second-order optimisation problem.

Outcome

Demonstrates understanding of adversarial search, game tree theory, pruning techniques, and heuristic design. The benchmarking infrastructure (measuring nodes evaluated, pruning rates, and wall-clock time at various depths) shows attention to empirical verification over theoretical assumption.

N-Queens — Constraint Satisfaction and Backtracking

Problem Framing

Place N queens on an N×N chessboard such that no two queens attack each other. The search space grows factorially — for N=12, there are over 479 million possible placements to check naively. The challenge isn’t finding a solution; it’s understanding how constraint propagation can collapse exponential spaces into tractable problems.

Approach

I implemented a backtracking solver with forward-checking constraint propagation. When a queen is placed, the algorithm immediately eliminates all squares it attacks from future consideration. This transforms the search space dynamically — each placement doesn’t just add a queen; it reshapes what’s possible.

I also built a comparative mode: the same problem solved with naive backtracking (no propagation) versus forward-checking, with real-time visualisation of both approaches.

Technical Depth

Why it works: each constraint propagation step is O(N), but it eliminates entire subtrees that would otherwise require O(N!) exploration. The propagation cost is negligible compared to the subtree cost it prevents.

Outcome

Demonstrates constraint satisfaction fundamentals, the power of propagation techniques, and the value of visualisation for understanding algorithm dynamics. The comparative mode makes abstract complexity differences viscerally concrete.

Mastermind — Logical Deduction and Entropy-Based Search

Problem Framing

Mastermind is an information game: you make guesses, receive feedback (correct digits in correct positions, correct digits in wrong positions), and deduce the secret code. The naive approach is brute force — try all possibilities until feedback matches. But humans don’t solve Mastermind that way. The interesting question: can we formalise human-like deductive reasoning?

Approach

I implemented two solving strategies:

1. 01Constraint filtering. After each guess, eliminate all codes inconsistent with the feedback. Simple, effective, but memoryless — it doesn’t account for information gain.
2. 02Entropy-based guessing (Knuth-style). Choose guesses that maximise expected information gain — guesses that most evenly partition the remaining possibility space, regardless of whether the guess itself could be correct.

The second approach often produces counterintuitive guesses (codes that can’t possibly be the answer) because they eliminate more uncertainty than “safe” guesses.

Technical Depth

Possibility space: 6⁴ = 1,296 possible codes. Entropy calculation requires evaluating every remaining candidate against every possible guess — O(n²) per turn. For small n this is negligible. For larger code spaces (6-digit, 8-colour), the overhead becomes significant.

Outcome

Demonstrates information theory application to search problems, comparison of greedy vs. information-optimal strategies, and awareness of the human-AI intuition gap. The side-by-side visualisation of both approaches makes the information-theoretic concept tangible.

These implementations are complete as learning tools. If I were to scale them into production-grade systems, here’s what would change.

Performance Layer

• ›Move core algorithms to C++ or Rust for memory-efficient game tree traversal
• ›Implement iterative deepening with transposition tables for Connect 4 (cache repeated positions across search branches)
• ›Parallelise N-Queens constraint propagation across multiple workers for N > 20

Architecture Layer

• ›Decouple game logic from visualisation into a proper MVC structure
• ›Build a unified benchmark harness that compares algorithms across games using standardised metrics (nodes/second, pruning efficiency, solve time)
• ›Expose algorithms via API for integration into larger systems

AI Integration

• ›Replace hand-coded heuristics in Connect 4 with learned evaluation functions (supervised learning on expert games, or self-play reinforcement learning)
• ›Use Monte Carlo Tree Search (MCTS) as a comparison baseline — especially relevant since MCTS powers modern game AI (AlphaGo, MuZero)
• ›For Mastermind: experiment with neural network-based guessing policies trained on information-gain maximisation

Multi-User & Real-Time

• ›Real-time multiplayer Connect 4 with server-side AI opponents at selectable difficulty (depth limits)
• ›Collaborative N-Queens solver: multiple users place queens simultaneously, with live constraint visualisation showing how each placement affects others
• ›Mastermind tournaments: human vs. human, human vs. AI, AI vs. AI — with Elo-style rating to quantify strategy strength