‹ All projects

Search & game AI

Hinger AI: Search, Exact Solving and Game-Playing Agents

Graph algorithms, a provable heuristic and an exact solution for the board game Hinger.

Period
Oct 2025 – Nov 2026
Stack
  • Python
  • pytest
  • GitHub Actions
01 / 04Win detection
  1. 01 · Win detection

    Winning moves as articulation points.

    Winning-position detection reduces to finding articulation points in the board graph, implemented in linear time with Tarjan’s algorithm.

  2. 02 · Search

    A heuristic, derived and proved.

    An admissible and consistent heuristic for A* search, derived and proved.

  3. 03 · Exact solving

    The full 5×5 board, solved.

    The full 5×5 board is solved exactly using memoised negamax with symmetry reduction.

  4. 04 · Agents

    Measured against the exact solution.

    Minimax, alpha-beta and Monte Carlo tree search agents, with their move quality evaluated against the exact solution.

Key result

5×5

Full board solved exactly with memoised negamax and symmetry reduction.