A Tic-Tac-Toe game written in C++20 featuring an AI opponent powered by the Minimax algorithm with memoization (dynamic programming). The project is designed with clean separation of responsibilities and is structured to support arbitrary board sizes, making it easy to extend and experiment with more advanced game AI techniques.
- 🎮 Human vs AI gameplay
- 🧠 Minimax algorithm for optimal decision making
- ⚡ Memoization (DP) to avoid recomputing previously evaluated game states
- ✅ Efficient win detection using only the last played move
- 📏 Configurable board size (
N × N, whereN >= 3) - 🛡️ Robust user input validation
- 🧩 Modular and object-oriented design
The AI explores every possible continuation of the game assuming both players make optimal moves.
- AI (X) acts as the maximizing player.
- Human (O) acts as the minimizing player.
Scoring:
| Result | Score |
|---|---|
| AI Wins | +1 |
| Draw | 0 |
| Player Wins | -1 |
Previously evaluated board states are cached using:
std::unordered_map<std::string, int>This significantly reduces the number of recursive evaluations by reusing computed results for identical board configurations.
Instead of checking every row, column, and diagonal after each move, the engine only examines the row, column, and relevant diagonals affected by the most recent move, reducing unnecessary computation.
- C++20
- STL
- CMake
- Object-Oriented Programming
- Dynamic Programming
- Backtracking
- Recursion
- Alpha-Beta Pruning
- Depth-limited search for larger boards
- Heuristic evaluation for
N × Ngameplay
This project demonstrates practical implementation of:
- Object-Oriented Programming
- Recursive search algorithms
- Backtracking
- Dynamic Programming (Memoization)
- State-space exploration
- Game AI fundamentals
- Efficient board representation and state management
mkdir build
cd build
cmake ..
cmake --build .Execute the generated application and follow the console prompts to play against the AI.