Problem
The Sim game is played on the complete graph K₆ — six vertices, every pair connected by one of 15 edges. Two players alternate colouring edges, one Red and one Blue. You lose if you complete a monochromatic triangle in your own colour. Ramsey's theorem (specifically R(3,3) = 6) guarantees that one of the two players will eventually be forced into a losing triangle: a draw is impossible.
I wrote a terminal implementation in C with a computer opponent. You choose to play first (Red) or second (Blue), and the computer takes the other side.
Approach
State. The 15 edges of K₆ are stored as a flat array — index 0 is edge 1–2, index 14 is edge 5–6 — and each cell is empty, Red or Blue. A hard-coded list of the 20 triangles of K₆ tells whether a colour has completed one.
Search. The computer solves the game rather than approximating it. For every empty edge it plays the move, recursively finds the opponent's best reply, and scores the move as a win, draw or loss (+1, 0, −1). It takes a winning move as soon as it finds one; otherwise it prefers a draw, and falls back to a losing move only when nothing else remains.
Memoisation. Each position is encoded as a base-3 number over the 15 edges — 3¹⁵ ≈ 43 million possible boards — and the best move for that position is cached in a one-byte table entry: the edge index plus a win/draw/loss flag. Once a position is solved, it is never searched again.
Adapting to turn order. When you choose Blue, the computer opens as Red. The board encoding is normalised to the computer's colour, so the same cache serves both turn orders.
Interface. The board prints as a row of 15 edge cells above an index key; you type the index of the edge you want to colour, and the computer replies in turn.
What it demonstrates
- A concrete instance of Ramsey's theorem — every game on K₆ ends with someone forming a triangle.
- Exhaustive game-tree search with memoisation: the full tree is far too large to walk naively, but caching solved positions makes perfect play practical.
- A graph-theoretic structure wearing a game-theoretic skin, which is most of why I built it.
Stack
C · exhaustive minimax (win/draw/loss) · memoised table over a base-3 board encoding · terminal I/O.
What I'd explore next
- A graphical front end that draws the six vertices and coloured edges, in place of the index key.
- Symmetry reduction — relabelling the six vertices collapses many equivalent positions — to shrink the 43-million-entry table.
- Larger boards, where exhaustive search stops being feasible and pruning or a learned evaluation becomes necessary.