Tic-Tac-Toe Game With AI Agent

Overview

The AI-Powered Tic-Tac-Toe is a Python-based project that scales the classic game to an expanded 9x9 grid. Rather than human-only play or basic rule-based scripts, this project implements a highly optimized adversarial agent capable of evaluating deep strategic lines to play competently against humans.

By combining the Minimax Search Algorithm with Alpha-Beta Pruning, the agent predicts future board states under strict latency constraints. The expanded grid introduces a massive search space, which the agent tackles through key heuristic optimizations including move prioritization, threat detection, and state memoization.

Core Mechanics & AI Implementation

1. Minimax with Alpha-Beta Pruning

The AI predicts future board states using a depth-limited Minimax algorithm configured to a maximum depth of 4. To prevent the combinatorial explosion of searching a 9x9 grid, Alpha-Beta Pruning is integrated to cut off search branches that are mathematically proven to be suboptimal. This ensures the agent evaluates deep strategic lines while keeping response times under 500ms.

2. Strategic Optimizations

The expanded grid size introduces unique computational challenges that the AI handles through custom heuristics and optimizations:

• Move Prioritization: Instead of evaluating all 81 squares, the algorithm calculates the distance of empty cells to existing pieces. It prioritizes and strictly evaluates only the top 15 closest moves, focusing the computational power on active "hotzones".
• Threat Detection & Scoring: The agent scans all possible 4-cell windows (horizontal, vertical, diagonal) to assign weighted scores based on piece counts. Immediate threats apply massive score multipliers (+500 for AI, -600 for human) to force the AI to prioritize blocking imminent losses over building its own lines.
• State Caching (Memoization): The agent converts the 2D grid into an immutable tuple and caches previously evaluated board scores in a dictionary. This prevents redundant calculations when the Minimax tree reaches the same board state through different move orders.

Technical Architecture

• Language: Python 3.x
• Interfaces: The project features a graphical user interface built with pygame (including hover effects and real-time visual feedback) alongside a lightweight command-line console version.
• Data Structures: Heavily utilizes Python dictionaries for high-speed memoization and tuples for immutable state tracking during the Minimax recursion.

Further Reading & Source Code

For a deep dive into the heuristic evaluation and alpha-beta implementation, please visit the repository: https://github.com/LPH1110/tdtu_ai_final_N14/tree/main/source/task2.