2

I am very confused in implementing MCTS for a connect 5 game. According to Wikipedia:

Selection: start from root R and select successive child nodes down to a leaf node L.

Lets say it's the AI's turn. The current board state is R. There should be no child nodes of R, right? Then, how can you "select successive child nodes down to a leaf node L"? Because you have no child nodes of R. Does child node L mean every single move the AI can make from R?

If that child node L , which is a game state, is not a victory for neither the AI or the player, you randomly play moves until some wins, and backpropagate up to R. What do you do after backpropagating?

I dont understand how you select child node L. Even before that, I'm not sure how L is created. It sounds very strange because it seems like you are "selecting" a child node on the very first step.

It would be great if some can simplify this. Thanks.

Improve this question
1
  • As I understand it, a child node would be any possible move from the current position (the root). So there would only be no child nodes if there were no possible moves i.e., the game is over. A leaf node would thus be a terminal node, one in which one player has won the game.
    – David Conrad
    Commented May 29, 2017 at 9:55

1 Answer 1

Reset to default
2

At first you have only one node, the root R, which is also the leaf node L of the first round selection step.

There should be no child nodes of R, right? Then, how can you "select successive child nodes down to a leaf node L"?

Just select L = R. (I think the Wikipedia article has some flaws. You don't have to select a leaf node but a node that still has some unexplored children left.)

If that child node L , which is a game state, is not a victory for neither the AI or the player, you randomly play moves until some wins, and backpropagate up to R.

No, according to the Wikipedia article, you need take the expansion step first. Choose any one of the unexplored children of L as the node C. You have to expand the tree to get anywhere.

What do you do after backpropagating?

Repeat the process unless you have run out of time.

I dont understand how you select child node L

That is the real key of the algorithm. You have to traverse the tree from the root until you reach a node that has some unexplored children. For each step you need to choose a node, balancing breadth and depth of the tree. Try the UCT formula for that purpose.

I'd expect it wouldn't be too hard to define a good evaluation function for Connect 5. If that's the case, then Monte Carlo tree search is probably not the most efficient algorithm for the task.

Improve this answer
4
  • Thanks for the answer. However, I have one more question. After the computer chooses a move, and in the next computer turn, fo you rebuild the entire tree again from the new game state?
    – Dashadower
    Commented May 30, 2017 at 11:16
  • Also in the UCT formula, I'm confused about the t variable. Is it equal to the total number of simulations for the root node?
    – Dashadower
    Commented May 30, 2017 at 11:18
  • @Dashadower I think you could keep the tree in memory between rounds. Just choose a new root and leave out extra branches to reflect the changed game state.
    – COME FROM
    Commented Jun 5, 2017 at 6:10
  • @Dashadower The number t is the number of simulations of a considered node in the selection step. The first considered node is always the root. I think you need better sources than the Wikipedia article. See this blog post for example.
    – COME FROM
    Commented Jun 5, 2017 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.