Monte Carlo Tree Searching UCT implementation

Question

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...

Answer 1

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!