Back

Explore Courses Blog Tutorials Interview Questions
0 votes
1 view
in AI and Deep Learning by (50.2k points)

Can you explain to me how to build the tree?

I quite understood how the nodes are chosen, but a nicer explanation would really help me implementing this algorithm. I already have a board representing the game state, but I don't know (understand) how to generate the tree.

Can someone point me to a well-commented implementation of the algorithm (I need to use it for AI)? Or better explanation/examples of it?

I didn't find a lot of resources on the net, this algorithm is rather new...

1 Answer

0 votes
by (108k points)

The game tree is a recursive data structure, therefore after choosing the best move, you end up in a child node which is, in fact, a root node for its subtree. Therefore you can think of a game as a sequence of “the most promising next move” problems represented by a game tree every time (with different root node). Very often in practice, you do not have to remember the path leading to your current state, as it is not a concern in a current game state.

MCTS generally consists of four strategic steps, repeated as long as there is time left. The steps are as follows.

  • In the selection mode, the tree is traversed from the root node until we reach a node E, where we select a position that is not added to the tree yet.

  • Next, during the play-out step moves are played in self-play until the end of the game is reached. The result R of this “simulated” game is +1 in case of a win for Black (the first player in LOA), 0 in case of a draw, and −1 in case of a win for White.

  • Subsequently, in the expansion stepchildren of E are added to the tree.

  • Finally, R is propagated back along the path from E to the root node in the backpropagation step. When time is up, the move played by the program is the child of the root with the highest value. 

For a better understanding of the algorithm you can refer the following link:

https://int8.io/monte-carlo-tree-search-beginners-guide/

Learn more about Artificial Intelligence in this insightful artificial intelligence online course now!

Welcome to Intellipaat Community. Get your technical queries answered by top developers!

28.4k questions

29.7k answers

500 comments

94k users

Browse Categories

...