0

I've been recently trying to play with MCTS implementation for simple board game. I'd like to make AI play with itself to gather some sample playthroughs. I'd figure out I could make them use the same MCTS tree (for better performance). Or so it looks like.

But would that be valid ? Or I need 2 separate trees for both AI with separate win/plays data to behave correctly ?

Nathan S.
  • 5,244
  • 3
  • 45
  • 55
VGer
  • 26
  • 3
  • Do you mean Monte-Carlo Tree Search? (MCTS) – Nathan S. Apr 02 '20 at 16:33
  • Yes, that is what i meant – VGer Apr 03 '20 at 16:14
  • This question addresses the same issue. Yes, it can be done, the answer to the question describes how it was done in alpha Go. [Why does Monte Carlo Tree Search reset Tree](https://stackoverflow.com/questions/47389700/why-does-monte-carlo-tree-search-reset-tree) – Nathan S. Apr 03 '20 at 19:28
  • Not sure if that answer my question. I did figure out already that discarding and recalculating whole tree from scratch after every move will not make much sense. But can two opposite AI players share the same tree with the same statistical data ? As far as I understand, tree nodes represent moves of both players in turns. But is statistical data gathered from point of view of one player, are still viable for opposite player ? Or there is some bias to be avoided ? – VGer Apr 04 '20 at 17:33

1 Answers1

0

If you are doing self-play and building the tree exactly the same for both players there won't be any bias inherent in the tree - you can re-use it for both players. But, if the players build the MCTS tree in a way that is specific to a particular player, then you'll need to rebuild the tree. In this case you'd need to keep two trees, one for each player, and each player could re-use their own tree but nothing else.

Some things to analyze if you're trying to figure this out:

  • Does the game have hidden information? (Something one player knows that the other player doesn't.) In this case you can't re-use the tree because you'd leak private information to the other player.
  • Do your playouts depend on the player at the root of the MCTS tree?
  • Does you have any policies for pruning moves from either player that aren't applied symmetrically?
  • Do you evaluate states in a way that is not symmetric between players?
  • Do you perform any randomization differently for the players?

If none of these are true, you can likely re-use the tree.

Nathan S.
  • 5,244
  • 3
  • 45
  • 55
  • 1
    Allright, so in basic version of my implementation answer to all question is no, so I can reuse the tree. But then if I implement advanced (more predictive) pruning I will probably have to keep 2 versions of tree - one pruned for player A and one pruned for player B. I get it now. It's AI for board game "Santorini" BTW – VGer Apr 06 '20 at 19:05