MCTS Explained for Dummies (With Python)

MCTS's Four Steps

1. Selection: Finding Promising Paths

2. Expansion: Exploring New Possibilities

3. Simulation: A Quick Trial Run

4. Backpropagation: Recording the Results

Advantages of MCTS:

1. No Need for Expert Knowledge: "I don't need someone to teach me how to play; I can learn by trying it out myself."

2. Can Handle Complex Situations: "Even if the board is too complex and cannot be fully calculated, I can still find pretty good moves through extensive simulation."

3. Balances Exploration and Exploitation Well: "I know when to try new paths and when to stick to known good ones."

4. Can Stop Thinking Anytime: "I can think as long as you give me time, and when time's up, I'll make a move."

Real-life Example

1. Deep Neural Network Components

• Policy Network
• Supervised Learning Policy Network: Initially trained on a large amount of expert game record data to learn human players' moves, thereby predicting the probability distribution of moves for a given board state.
• Reinforcement Learning Policy Network: Based on the initial policy network, it is further optimized through self-play, enabling the network to explore moves that surpass human play.

• Value Network
• Used to evaluate the board state and directly predict the win rate of the current board state.
• The value network helps to quickly judge the quality of the endgame during the search process, thereby reducing the depth of the search tree and the amount of computation.

2. Monte Carlo Tree Search (MCTS)

• Tree Search Process:
• Starting from the current board state (the root of the tree), MCTS repeatedly performs the four steps of "Selection–Expansion–Simulation–Backpropagation" to explore different move sequences in the search tree.
• In the "Selection" phase, it uses a formula similar to UCT (Upper Confidence Bound for Trees) to balance exploration and exploitation, selecting nodes that are both underexplored and performing well.

• Using Neural Networks to Guide the Search:
• The Policy Network provides prior probabilities to guide which moves may be better during the search process.
• The Value Network is used to evaluate the leaf nodes reached in the search, reducing the reliance on pure random rollouts and improving both the efficiency and accuracy of the search.

• Final Decision:
• After the search process is complete, AlphaGo selects the best move based on the visit count and accumulated evaluations, and that move is used as the next decision.

3. Overall Algorithm Process

1. Initialization:
• Train a supervised learning policy network using expert game records, then further refine it through self-play with reinforcement learning to obtain the final policy network and value network.

2. During the Game:
• For the current board state, input it into the policy network to obtain the prior probabilities of possible moves.
• Use MCTS, combined with the prior information from the policy network and the evaluation from the value network, to simulate multiple possible future moves in the search tree.
• Choose and execute the move that has the highest visit count or the best evaluation based on the search results.

3. Continuous Iteration:
• After each move, rebuild the search tree and use the latest network information for the next search and decision-making step.

Python Example (TicTacToe):

1. Tic Tac Toe Environment (TicTacToe class)
• The Board and Players: It creates a 3x3 board (using zeros for empty spaces) and sets Player 1 to start.
• State Management: You can get a copy of the current board and the active player, or set the board state from an external source.
• Legal Actions: Every empty spot on the board is considered a legal move.
• Making a Move: When you choose a position, the code checks if it's empty. If it is, the current player’s mark is placed there, and then the turn switches to the other player.
• Checking for a Winner: The code examines rows, columns, and diagonals to determine if a player has won. If all spots are filled and there's no winner, it’s a draw.
• Rewards: For a given player, winning gives a reward of 1, a draw gives 0.5, and a loss gives 0.
• Printing the Board: There’s a function to display the board in a human-friendly format.

2. MCTS Node (MCTSNode class)
• Representing a Game State: Each node represents a particular state of the game along with which player's turn it is.
• Tracking the Path: Nodes store the move that got them there, their parent node, and any children nodes.
• Statistics: Each node keeps track of how many times it’s been visited and the total reward (value) accumulated from simulations.
• Expansion and Selection:
• Expansion: If there are moves that haven’t been tried from that state, the node can “expand” by trying a new move and creating a child node for it.
• Selection: If all moves have been tried, the node uses a formula (like UCB) to choose the child node that seems most promising based on past performance and exploration.

3. MCTS Algorithm (MCTS class)
• The Four Steps of MCTS:
• Selection: Starting at the root (current game state), the algorithm walks down the tree, choosing the most promising child nodes until it finds a node that isn’t fully expanded.
• Expansion: It then picks one of the untried moves from that node, creates a new node, and adds it to the tree.
• Simulation: From the new node, the algorithm plays out the game randomly (choosing random legal moves) until the game ends.
• Backpropagation: Once the simulation is finished, the result (win, draw, or loss) is sent back up the tree, updating the statistics (visits and value) of every node along the path taken.
• Choosing the Best Move: After a set number of iterations (like 500), the move corresponding to the child node with the most visits is chosen as the best action.

4. Game Demonstration (play_game function)
• Setup: The game starts with an empty board. One player (Player 1) uses the MCTS algorithm, while the other (Player 2) uses a random move strategy.
• Gameplay Loop:
• The current board is printed.
• Depending on whose turn it is, the code either uses MCTS to select a move or randomly picks a move.
• The selected move is made on the board.
• This loop continues until the game ends.
• Game Over: When the game finishes, the final board is printed, and the outcome (win for X or O, or a draw) is announced.