Adversarial Game-Playing Agents for Tic-Tac-Toe: A Comparative Study of Reinforcement Learning and Classical Search

Abstract

This project presents a comparative implementation and analysis of two fundamentally distinct approaches to adversarial game-playing in the domain of Tic-Tac-Toe: model-free reinforcement learning via Q-Learning and exhaustive game-tree search via the Minimax algorithm with alpha-beta pruning. The system provides an interactive web-based environment in which a human opponent may engage either agent under controlled difficulty settings, enabling qualitative observation of emergent strategic behavior across paradigms.

The Q-Learning agent employs a tabular, off-policy temporal-difference method to approximate the optimal action-value function Q*(s, a) through iterative self-play. State-action values are updated according to the Bellman optimality equation with configurable hyperparameters governing the learning rate (α), discount factor (γ), and an ε-greedy exploration-exploitation schedule subject to exponential decay. Two agents are trained concurrently in an adversarial self-play regime over millions of episodes, yielding separate Q-tables for each player mark. While this approach demonstrates the capacity of model-free methods to acquire non-trivial strategic policies without explicit domain knowledge, the resulting agents exhibit characteristic limitations of tabular Q-Learning in partially explored state spaces — namely, suboptimal play in states insufficiently visited during training.

The Minimax agent implements a complete depth-first search of the game tree augmented with alpha-beta pruning for branch elimination and a transposition table for memoization of previously evaluated board states. Given the bounded complexity of Tic-Tac-Toe (an upper bound of 9! = 362,880 terminal game states, substantially reduced by symmetry and pruning), the algorithm guarantees computation of the Nash equilibrium strategy in real time. The evaluation function incorporates depth-penalized scoring to prefer shorter paths to victory, ensuring maximally aggressive optimal play.

A stochastic baseline agent selecting uniformly at random from available actions is additionally provided to establish a lower bound on agent performance.

Gameplay Demo

Methodology

Reinforcement Learning Framework

The Q-Learning agent operates within the standard Markov Decision Process (MDP) formulation:

• State space S: The set of all legal board configurations, represented as 9-tuples over {−1, 0, 1}.
• Action space A(s): The subset of unoccupied board positions for a given state s.
• Reward signal R: A sparse reward scheme assigning +100 for terminal victories, −100 for losses, +75 for draws, and −2 for intermediate transitions to discourage passive play.
• Update rule: Q(s, a) ← Q(s, a) + α [R + γ · max_a' Q(s', a') − Q(s, a)]

Exploration follows an ε-greedy policy with exponential decay (ε ← max(ε_min, ε · λ)), transitioning the agent from uniform exploration to predominantly exploitative behavior over the course of training.

Game-Tree Search

The Minimax algorithm recursively evaluates all reachable game states under the assumption of optimal adversarial play, alternating between maximization (agent's turn) and minimization (opponent's turn) of the evaluation function. Alpha-beta pruning eliminates provably suboptimal branches, reducing the effective branching factor without affecting the computed result. A transposition table further accelerates search by caching evaluations of previously encountered board configurations.

System Architecture

The application employs a client-server architecture:

Component	Technology	Role
Backend	Python / Flask	Game state management, AI agent hosting, RESTful API
Frontend	HTML5 / CSS3 / JavaScript	Interactive board rendering, asynchronous API communication
Persistence	Python pickle	Serialization of learned Q-tables

The server maintains per-session game instances and exposes endpoints for game initialization, player moves, AI move computation, and state queries. AI agents are instantiated at server startup; Q-tables are deserialized from disk to preserve learned policies across sessions.

Difficulty Taxonomy

Level	Agent	Theoretical Guarantee
Easy	Random (Uniform)	None — serves as stochastic baseline
Medium	Q-Learning (Tabular)	Approximate optimality contingent on training coverage
Hard	Minimax (α-β Pruning)	Optimal play — Nash equilibrium strategy; provably unbeatable

Usage

Prerequisites

• Python 3.8+
• Flask (pip install flask or pip install -r requirements.txt)

Execution

# Launch the web server
python app.py

Navigate to http://127.0.0.1:5000 in a web browser. Select a difficulty level and interact with the board to play against the AI agent.

Training (Optional)

To retrain the Q-Learning agents:

python main.py

Training parameters (episode count, learning rate, discount factor, exploration schedule) are configurable within main.py. Trained Q-tables are serialized to ttt_q_table_X_v2.pkl and ttt_q_table_O_v2.pkl.

File Structure

├── app.py                   # Flask server and API routes
├── main.py                  # Game environment, AI agents, training loop
├── templates/
│   └── index.html           # Web interface
├── assets/
│   └── gameplay.gif         # Gameplay demo
├── ttt_q_table_X_v2.pkl     # Serialized Q-table (Player X)
├── ttt_q_table_O_v2.pkl     # Serialized Q-table (Player O)
├── README.md                # Project documentation
└── requirements.txt         # Project dependencies

References

1. Watkins, C.J.C.H., & Dayan, P. (1992). Q-Learning. Machine Learning, 8(3–4), 279–292.
2. Sutton, R.S., & Barto, A.G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
3. Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson. Chapters 5–6: Adversarial Search and Games.
4. Knuth, D.E., & Moore, R.W. (1975). An Analysis of Alpha-Beta Pruning. Artificial Intelligence, 6(4), 293–326.