Efficient AI Strategies with Monte Carlo Tree Search: A Case Study on Tic-Tac-Toe

Session

Computer Science and Communication Engineering

Description

Tic-Tac-Toe, though a simple game, represents a clear environment to study decision-making in artificial intelligence. The challenge lies in enabling an AI to make optimal moves without relying on exhaustive search or handcrafted rules, which often limit adaptability and scalability. Traditional approaches such as Minimax guarantee optimal play but depend on complete state-space evaluation, making them inefficient for larger or more complex problems. To address this, we implement the Monte Carlo Tree Search (MCTS) algorithm, which balances exploration and exploitation through four key stages: selection, expansion, simulation, and backpropagation. By simulating numerous possible plays rather than traversing the entire game tree, MCTS offers a flexible, probabilistic decision-making process that can adapt to uncertain or dynamic domains. In this work, we design and test an MCTS-based AI agent for Tic-Tac-Toe. We evaluate its runtime efficiency, decision quality, and fairness compared to classical approaches. Experimental results show that MCTS consistently produces near-optimal strategies with modest computational requirements, though a noticeable advantage remains for the first player. These findings demonstrate both the strengths and current limitations of MCTS when applied to structured decision problems. Ultimately, this research illustrates how MCTS can provide a scalable foundation for AI decision-making. Beyond Tic-Tac-Toe, the same principles can be extended toward more complex domains such as strategic games, planning tasks, and autonomous systems.

Keywords:

Monte Carlo Tree Search, Tic-Tac-Toe, Simulation-Based Search, Strategic Game Modeling

Proceedings Editor

Edmond Hajrizi

ISBN

978-9951-982-41-2

Location

UBT Lipjan, Kosovo

Start Date

25-10-2025 9:00 AM

End Date

26-10-2025 6:00 PM

DOI

10.33107/ubt-ic.2025.92

This document is currently not available here.

Share

COinS
 
Oct 25th, 9:00 AM Oct 26th, 6:00 PM

Efficient AI Strategies with Monte Carlo Tree Search: A Case Study on Tic-Tac-Toe

UBT Lipjan, Kosovo

Tic-Tac-Toe, though a simple game, represents a clear environment to study decision-making in artificial intelligence. The challenge lies in enabling an AI to make optimal moves without relying on exhaustive search or handcrafted rules, which often limit adaptability and scalability. Traditional approaches such as Minimax guarantee optimal play but depend on complete state-space evaluation, making them inefficient for larger or more complex problems. To address this, we implement the Monte Carlo Tree Search (MCTS) algorithm, which balances exploration and exploitation through four key stages: selection, expansion, simulation, and backpropagation. By simulating numerous possible plays rather than traversing the entire game tree, MCTS offers a flexible, probabilistic decision-making process that can adapt to uncertain or dynamic domains. In this work, we design and test an MCTS-based AI agent for Tic-Tac-Toe. We evaluate its runtime efficiency, decision quality, and fairness compared to classical approaches. Experimental results show that MCTS consistently produces near-optimal strategies with modest computational requirements, though a noticeable advantage remains for the first player. These findings demonstrate both the strengths and current limitations of MCTS when applied to structured decision problems. Ultimately, this research illustrates how MCTS can provide a scalable foundation for AI decision-making. Beyond Tic-Tac-Toe, the same principles can be extended toward more complex domains such as strategic games, planning tasks, and autonomous systems.