Artificial Intelligence

/// problem

Sudoku is a constraint-satisfaction problem with a search space that explodes as the initial puzzle gets sparser. We wanted to see how different solver strategies hold up across difficulty tiers.

/// approach

Implemented five algorithms: simple backtracking, backtracking with forward checking, backtracking with AC3 arc consistency, simulated annealing, and a genetic algorithm. Ran each on four puzzles per difficulty (easy, medium, hard, evil), tracking assignments and backtracks for the DFS family and conflict scores over iterations for the stochastic ones.

/// takeaway

AC3 was the clear winner, often zero backtracks even on evil puzzles. Neither stochastic method ever produced a complete solution within the iteration caps; both plateaued a handful of conflicts short of done. Confirmed the hypothesis, and got a real feel for how brittle exploration/exploitation tuning is in practice.

/// problem

An agent in a cave with hazards (bottomless pits and Wumpuses) has to classify its next move as SAFE, UNSAFE, or RISKY using only the breeze and stench perceptions from adjacent cells along the path it already took. The job was to build an inference engine that reaches the right verdict purely from logical deduction.

/// approach

Modeled the agent's knowledge as first-order logic clauses over Pit, Wumpus, Breeze, and Stench predicates with cell coordinates. Built the knowledge base from the safe path's perceptions plus global at-most-N and at-least-N Wumpus-count constraints, simplified via unit propagation, then ran resolution-based forward chaining with proof by contradiction. Tested across twelve puzzles spanning easy, medium, and hard caves, tracking clauses, unifications, and resolutions per verdict.

/// takeaway

The engine got the right verdict on all twelve puzzles. The hypothesis that harder caves would force more work didn't hold; verdict type (RISKY requires both SAFE and UNSAFE proofs to fail) and how logically entangled the query cell was mattered far more than cave size. One medium puzzle blew up to roughly 2 million operations because the query cell sat deep in the constraint graph, which also showed how critical early knowledge-base simplification is.

/// problem

Posterior probabilities in Bayesian networks are easy to ask but expensive to compute exactly as networks grow. We wanted to compare an exact method against an approximate one across networks of increasing size, and see where each one breaks down.

/// approach

Implemented variable elimination (exact: factor reduction, multiplication, marginalization, and normalization, with a greedy min-degree elimination ordering) and Gibbs sampling (approximate: MCMC resampling each non-evidence variable conditioned on its Markov blanket, with a smoothing factor to keep near-deterministic probabilities from collapsing the chain). Tested on three networks of growing size: Child (20 nodes), Insurance (27 nodes), and Win95pts (76 nodes), under varying evidence conditions, comparing both algorithms' outputs against known ground-truth distributions.

/// takeaway

Variable elimination hit every ground-truth value exactly across all three networks. Gibbs sampling stayed within 0.01 to 0.02 of truth on the small networks but drifted up to roughly 0.2 off on Win95pts under specific evidence configurations, which we traced to near-deterministic conditional probabilities slowing convergence. The smoothing factor turned out to be load-bearing: without it, Gibbs sampling didn't work at all on Win95pts.

/// problem

A car has to navigate a racetrack from start to finish in the fewest time steps, with stochastic actions (20% chance the chosen acceleration fails) and two crash regimes: reset to the nearest valid cell (soft) or restart from the beginning (hard). We wanted to see how model-based and model-free RL trade off speed against risk.

/// approach

Implemented three algorithms: Value Iteration (model-based, full knowledge of the transition model, Bellman backups to convergence), Q-Learning (model-free, off-policy, ε-greedy with decayed exploration), and SARSA (model-free, on-policy, same exploration but updating against the action actually taken). Ran each on three tracks (W, U, "2") under both crash regimes, 10 runs per configuration, recording path length, episodes to converge, and learning curves.

/// takeaway

Value Iteration produced the shortest paths as expected and served as the ground-truth baseline. The model-free split fell out cleanly along the on/off-policy axis: Q-Learning learned aggressive trajectories that worked under the soft penalty but went erratic and long under restart, while SARSA folded exploration risk into its value estimates and consistently chose safer, more central lines that paid off in the high-penalty regime. Confirmed the textbook intuition that on-policy methods are the right tool when bad actions are expensive.