Monte Carlo Tree Search for Tic-Tac-Toe

Monte Carlo Tree Search (MCTS) is a powerful decision-making algorithm often used in game AI, particularly when evaluating a large search space. This challenge asks you to implement MCTS to play Tic-Tac-Toe. The goal is to create an AI that can effectively explore the game tree and choose optimal moves, even without a perfect evaluation function.

Problem Description

You are tasked with implementing a basic MCTS algorithm to play Tic-Tac-Toe against a human opponent. The algorithm should consist of four main phases: Selection, Expansion, Simulation, and Backpropagation. The AI should be able to take the current Tic-Tac-Toe board state as input and return the best move (represented as a tuple (row, col) indicating the row and column of the desired move).

Key Requirements:

• Node Representation: Design a Node class to represent states in the game tree. Each node should store information about the board state, the move that led to this state, the node's value (win/loss/draw), and its children.
• Selection: Implement the Selection phase to traverse the tree from the root node, choosing the most promising child node based on a UCT (Upper Confidence Bound 1 applied to Trees) formula.
• Expansion: Implement the Expansion phase to create new child nodes for unexplored states.
• Simulation: Implement the Simulation phase (also known as rollout) to play out the game randomly from the newly expanded node until a terminal state (win, loss, or draw) is reached.
• Backpropagation: Implement the Backpropagation phase to update the values of the nodes along the path from the expanded node back to the root node, based on the outcome of the simulation.
• Move Selection: After a fixed number of iterations, select the move corresponding to the child of the root node with the highest visit count.

Expected Behavior:

The AI should be able to:

• Take a Tic-Tac-Toe board state as input.
• Perform a specified number of MCTS iterations.
• Return the best move (row, col) based on the MCTS results.
• Handle win, loss, and draw conditions correctly.

Edge Cases to Consider:

• Terminal States: The algorithm should correctly identify and handle terminal states (win, loss, or draw) during simulation and backpropagation.
• Fully Explored Nodes: The UCT formula should handle nodes that have already been visited.
• Illegal Moves: The algorithm should not attempt to make illegal moves (e.g., placing a piece on an occupied square).
• Draw Games: The algorithm should handle draw games gracefully.

Examples

Example 1:

Input: board = [['X', 'O', 'X'], ['O', ' ', ' '], [' ', ' ', 'O']]
Iterations = 1000
Output: (1, 1)
Explanation: After 1000 iterations, the MCTS algorithm determines that placing an 'X' at row 1, column 1 is the most promising move.

Example 2:

Input: board = [['X', 'O', 'X'], ['O', 'X', ' '], [' ', ' ', 'O']]
Iterations = 500
Output: (2, 0)
Explanation: After 500 iterations, the MCTS algorithm determines that placing an 'X' at row 2, column 0 is the most promising move.

Example 3: (Edge Case - Game Over)

Input: board = [['X', 'O', 'X'], ['O', 'X', 'O'], [' ', ' ', 'X']]
Iterations = 200
Output: None
Explanation: The game is already over (X wins). The algorithm should return None as there are no valid moves.

Constraints

• Board Size: The Tic-Tac-Toe board is always 3x3.
• Iterations: The number of MCTS iterations will be a positive integer (e.g., 1000).
• Exploration Constant (C): You can choose an appropriate exploration constant (C) for the UCT formula. A value between 1 and 2 is often a good starting point.
• Time Limit: While not strictly enforced, aim for a solution that completes within a reasonable time frame (e.g., a few seconds for 1000 iterations).
• Input Format: The board state will be represented as a 3x3 list of strings, where 'X' represents a player's mark, 'O' represents the opponent's mark, and ' ' represents an empty square.

Notes

• The UCT formula is: UCT(node) = Q(node) + C * sqrt(ln(N(parent)) / N(node))
  • Q(node): Average reward (win/loss/draw) of the node.
  • C: Exploration constant.
  • N(node): Number of visits to the node.
  • N(parent): Number of visits to the parent node.
• The random rollout policy can be a simple random move selection.
• Consider using a helper function to check for winning conditions and draw states.
• Focus on the core MCTS algorithm. A perfect evaluation function is not required. The simulation phase provides the evaluation.
• Start with a small number of iterations and gradually increase it to test your implementation.
• Think about how to efficiently represent the game state and possible moves.