mnk-game-engine: Minimax Solver for Generalized Board Games

A minimax game engine for generalized (m, n, k)-games — the family of two-player perfect-information board games that includes Tic-Tac-Toe, Connect Four, Gomoku, and more. Features full game-tree search with alpha-beta pruning, achieving up to 97% state-space reduction on standard boards.

---

What This Project Does

A complete adversarial search engine that solves arbitrary (m, n, k)-games optimally. Two players take turns placing marks on an m x n board; the first to align k marks in a row (horizontally, vertically, or diagonally) wins. The engine computes provably optimal moves via minimax and uses alpha-beta pruning to make larger boards tractable.

Core contributions:

• Full minimax with alpha-beta pruning — the engine explores the complete game tree, guaranteeing optimal play for both sides; pruning eliminates provably irrelevant subtrees without sacrificing correctness
• Generalized (m, n, k) support — not hardcoded for 3x3; handles arbitrary board dimensions and win-length requirements through a single parameterized Game class
• Quantified pruning impact — benchmarks across five board configurations demonstrate that alpha-beta reduces the 4x3 search from 276M states (18 min) to 31K states (0.13s) — a 99.99% reduction
• Correctness guarantees — 15-test suite verifies win detection in all orientations, pruning equivalence (same result as unpruned search), optimal play (AI vs AI always draws on 3x3), and immediate win/block detection
• Interactive human vs AI — play against the engine in the terminal; it recommends optimal moves and responds optimally as the opponent

---

Results

Benchmarked on empty-board first-move decisions. All pruned results produce the same optimal action as the full search. Classical Tic-Tac-Toe solves in 63ms; alpha-beta makes 4x3 boards tractable where full minimax takes over 18 minutes.

Board	k	Pruning	States Visited	Time	Reduction
3x3	3	Off	549,945	1.73s	—
3x3	3	On	18,296	0.06s	96.7%
4x3	3	Off	276,911,232	1078s	—
4x3	3	On	30,935	0.13s	99.99%
4x3	4	Off	1,213,687,968	7742s	—
4x3	4	On	267,300	1.83s	99.98%
4x4	4	On	499,829,622	4168s	—

---

Architecture

flowchart TD
    subgraph Engine ["mnk_game/engine.py"]
        Init["Game(m, n, k, to_prune)"]
        Board["Board State<br/>(m x n grid)"]
        Actions["Valid Action<br/>Generation"]
        Win["Win Detection<br/>(4-direction scan)"]
        MaxNode["max() — recursive"]
        MinNode["min() — recursive"]
        AB["Alpha-Beta<br/>Pruning"]
    end

    subgraph Interface ["Entry Points"]
        CLI["main.py<br/>Human vs AI"]
        API["Python API<br/>from mnk_game import Game"]
        Bench["tests/test_performance.py<br/>Benchmark Runner"]
    end

    subgraph Outputs ["Outputs"]
        Move["Optimal Action<br/>(row, col)"]
        Stats["Stats: time,<br/>states visited"]
        CSV["benchmarks/results.csv"]
    end

    CLI --> Init
    API --> Init
    Bench --> Init

    Init --> Board
    Board --> Actions
    Actions --> MaxNode
    Actions --> MinNode
    MaxNode <--> MinNode
    MaxNode --> AB
    MinNode --> AB
    MaxNode --> Win
    MinNode --> Win

    MaxNode --> Move
    MaxNode --> Stats
    Bench --> CSV

Loading

---

Key Engineering Highlights

Area	Detail
Alpha-beta pruning	Prunes subtrees where alpha >= beta, reducing 4x3 search from 277M to 31K states — makes boards intractable under full minimax solvable in under a second
Efficient win detection	Scans only from the last-played cell outward in four directions (horizontal, vertical, both diagonals) rather than scanning the entire board — O(k) per check instead of O(mnk)
State copying discipline	Each recursive call creates an independent board copy ([row[:] for row in state]), keeping the search tree side-effect-free without needing undo-move bookkeeping
Pruning correctness	Test suite verifies that pruned and unpruned search produce identical optimal outcomes — pruning never changes the result, only the number of states explored
Configurable search	to_prune flag toggles alpha-beta at construction time, enabling direct A/B comparison of pruned vs full minimax on the same board configuration
Zero dependencies	Entire engine runs on the Python standard library — no NumPy, no external packages, trivial to install and run anywhere

---

Project Structure

.
├── mnk_game/
│   ├── __init__.py                # Public API: from mnk_game import Game
│   └── engine.py                  # Game state, minimax, alpha-beta pruning
├── tests/
│   ├── test_game.py               # 15 unit tests — correctness, pruning, optimal play
│   └── test_performance.py        # Benchmark runner across board configurations
├── benchmarks/
│   └── results.csv                # Timing and state-count data
├── main.py                        # Interactive human vs AI entry point
├── .gitignore
├── LICENSE
└── README.md

---

Quickstart

# 1. Clone
git clone https://github.com/catalinatan/mnk-game-engine.git
cd mnk-game-engine

# 2. Play against the AI (no install needed)
python main.py

No dependencies beyond Python 3.7+. No virtual environment required.

---

Usage

Play against the AI

python main.py

You play as X (Max). The engine recommends optimal moves and responds as O (Min).

      0     1     2
  -------------------
 0 |  X  |  O  |  ·  |
  -------------------
 1 |  ·  |  X  |  ·  |
  -------------------
 2 |  O  |  ·  |  ·  |
  -------------------

Custom board sizes

from mnk_game import Game

# 4x4 board, 4 in a row to win, with pruning
game = Game(m=4, n=4, k=4, to_prune=True)
game.initialize_game()
game.play()

AI vs AI simulation

from mnk_game import Game

game = Game(3, 3, 3, to_prune=True)
game.initialize_game()

player = "max"
result = None

while result is None:
    action, _, _ = game.max_decision() if player == "max" else game.min_decision()
    game.take_action(player, action)
    game.drawboard()
    result = game.compute_result(game.board)
    player = game.select_next_player(player)

game.print_result(result)  # Always a tie with optimal play

Programmatic access

from mnk_game import Game

game = Game(3, 3, 3, to_prune=True)
game.initialize_game()

action, exec_time, states_visited = game.max_decision()
print(f"Best move: {action}, searched {states_visited} states in {exec_time:.3f}s")

---

API Reference

game = Game(m, n, k, to_prune=True)

Method	Returns	Description
initialize_game()	—	Reset to empty m x n board
max_decision()	(action, time, states)	Optimal move for Max (X)
min_decision()	(action, time, states)	Optimal move for Min (O)
take_action(player, action)	—	Apply move to board
compute_result(state)	1 / -1 / 0 / None	Check terminal state
is_valid(action)	bool	Move legality check
check_win(state, r, c)	0 / 1 / 2	Win check from position
drawboard()	—	Print board to stdout
play()	—	Interactive game loop

---

Tests

# Run all 15 tests
python -m unittest discover tests -v

# Or with pytest
python -m pytest tests/ -v

# Run performance benchmarks → benchmarks/results.csv
python -m tests.test_performance

Test coverage includes: board initialization, move validation, win detection (horizontal, vertical, both diagonals), minimax correctness, alpha-beta pruning equivalence, state-count reduction, immediate win detection, opponent-blocking, optimal play verification (AI vs AI always draws on 3x3), and larger board support.

---

Algorithm

The engine implements minimax with alpha-beta pruning for two-player zero-sum games:

• Minimax exhaustively explores the game tree. Max maximizes the evaluation (+1 win, 0 draw, -1 loss) while Min minimizes it. Both players assume optimal opponent play.
• Alpha-beta pruning maintains bounds on the achievable value (alpha for Max, beta for Min) and prunes entire subtrees when a branch provably cannot improve on the current best — cutting search time by orders of magnitude without changing the result.
• Correctness invariant: two optimal agents always draw on 3x3 Tic-Tac-Toe, verified across both pruned and unpruned search in the test suite.

---

License

Released under the MIT License.