This article explains the process of implementing a Tic-Tac-Toe game using the Monte Carlo Tree Search (MCTS) algorithm with deep learning and PyTorch. We will primarily understand how MCTS works and how AI can play the Tic-Tac-Toe game using it.<\/p>\n
Tic-Tac-Toe Game Overview<\/h2>\n
Tic-Tac-Toe is a game played on a 3×3 square grid where two players take turns placing X or O. The player who manages to place three of their marks in a row, column, or diagonal wins the game.<\/p>\n
Step 1: Environment Setup<\/h2>\n
To follow this tutorial, you need to install the necessary packages. Here are the main libraries required.<\/p>\n
pip install torch numpy matplotlib<\/code><\/pre>\nStep 2: Game Environment Implementation<\/h2>\n
First, we implement the Tic-Tac-Toe game environment. We must define the game’s rules and create a class to represent the state.<\/p>\n
\nimport numpy as np\n\nclass TicTacToe:\n def __init__(self):\n self.board = np.zeros((3, 3), dtype=int) # 0: empty, 1: X, -1: O\n self.current_player = 1 # 1: X's turn, -1: O's turn\n\n def reset(self):\n self.board = np.zeros((3, 3), dtype=int)\n self.current_player = 1\n\n def make_move(self, row, col):\n if self.board[row, col] == 0:\n self.board[row, col] = self.current_player\n self.current_player *= -1\n\n def check_winner(self):\n for player in [1, -1]:\n for row in range(3):\n if np.all(self.board[row, :] == player): # Check rows\n return player\n for col in range(3):\n if np.all(self.board[:, col] == player): # Check columns\n return player\n if np.all(np.diag(self.board) == player) or np.all(np.diag(np.fliplr(self.board)) == player):\n return player\n return None if np.any(self.board == 0) else 0 # Game is ongoing\n \n def display(self):\n symbols = {1: 'X', -1: 'O', 0: ' '}\n for row in self.board:\n print(\"|\".join(symbols[x] for x in row))\n print(\"-\" * 5)\n print(\"\\n\")\n\n# Game Test\ngame = TicTacToe()\ngame.make_move(0, 0)\ngame.display()\ngame.make_move(1, 1)\ngame.display()\n <\/code><\/pre>\nStep 3: Monte Carlo Tree Search (MCTS) Algorithm<\/h2>\n
MCTS is a method to solve decision-making problems in uncertain situations. Essentially, this algorithm consists of the following four steps:<\/p>\n
\n- Selection<\/strong>: Select a node from the current tree.<\/li>\n
- Expansion<\/strong>: Expand possible actions from the selected node.<\/li>\n
- Simulation<\/strong>: Play the game from the expanded node to obtain the result.<\/li>\n
- Backpropagation<\/strong>: Update the information for the parent node with the result.<\/li>\n<\/ol>\n
MCTS Class Implementation<\/h3>\n\nimport random\nfrom collections import defaultdict\n\nclass MCTSNode:\n def __init__(self, state, parent=None):\n self.state = state # Current game state\n self.parent = parent\n self.children = [] # Child nodes\n self.wins = 0 # Number of wins\n self.visits = 0 # Number of visits\n\n def ucb1(self):\n if self.visits == 0:\n return float('inf') # Select nodes that have not been visited before\n return self.wins \/ self.visits + np.sqrt(2 * np.log(self.parent.visits) \/ self.visits)\n\nclass MCTS:\n def __init__(self, iterations):\n self.iterations = iterations\n\n def search(self, game):\n root = MCTSNode(state=game)\n\n for _ in range(self.iterations):\n node = self.select(root)\n winner = self.simulate(node.state)\n self.backpropagate(node, winner)\n\n return max(root.children, key=lambda child: child.visits).state\n\n def select(self, node):\n while node.children:\n node = max(node.children, key=lambda child: child.ucb1())\n if node.visits > 0:\n for action in self.get_valid_moves(node.state):\n child_state = node.state.copy()\n child_state.make_move(action[0], action[1])\n child_node = MCTSNode(state=child_state, parent=node)\n node.children.append(child_node)\n return random.choice(node.children) if node.children else node\n\n def simulate(self, state):\n current_player = state.current_player\n while True:\n winner = state.check_winner()\n if winner is not None:\n return winner\n valid_moves = self.get_valid_moves(state)\n move = random.choice(valid_moves)\n state.make_move(move[0], move[1])\n\n def backpropagate(self, node, winner):\n while node is not None:\n node.visits += 1\n if winner == 1: # X wins\n node.wins += 1\n node = node.parent\n\n def get_valid_moves(self, state):\n return [(row, col) for row in range(3) for col in range(3) if state.board[row, col] == 0]\n\n# MCTS Usage Example\nmcts = MCTS(iterations=1000)\nmove = mcts.search(game)\nprint(\"AI's choice:\", move)\n <\/code><\/pre>\nStep 4: Implementing the Game Between AI and User<\/h2>\n
Now, let’s implement a game between the user and the AI using the completed MCTS.<\/p>\n
\ndef play_game():\n game = TicTacToe()\n while True:\n game.display()\n if game.current_player == 1: # User's turn\n row, col = map(int, input(\"Enter the row and column numbers (0, 1, or 2): \").split())\n game.make_move(row, col)\n else: # AI's turn\n print(\"AI is choosing...\")\n move = mcts.search(game)\n game.make_move(move[0], move[1])\n print(f\"AI chose the position: {move}\")\n\n winner = game.check_winner()\n if winner is not None:\n game.display()\n if winner == 1:\n print(\"Congratulations! You won!\")\n elif winner == -1:\n print(\"AI won!\")\n else:\n print(\"It's a draw!\")\n break\n\nplay_game()\n <\/code><\/pre>\nConclusion<\/h2>\n
In this tutorial, we explored the basic guidelines of deep learning and PyTorch. The process of implementing a simple Tic-Tac-Toe AI using Monte Carlo Tree Search can be technically challenging, but it was an extremely interesting experience in the end. We hope to move forward and develop a more complete AI using various algorithms and techniques.<\/p>\n<\/article>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"