2
$\begingroup$

I've implemented the Monte Carlo tree search (MCTS) algorithm for a connect four game I've built. The MCTS agent beats a random choice agent 90-100% of the time, but I’m still able to beat it pretty easily. It even misses obvious three in a row opportunities where it just needs to add one more token to win (but places it elsewhere instead).

Is this normal behavior, or should the MCTS agent be able to beat me consistently too? I'm allowing it to grow its tree for 2 seconds before getting it to return its chosen action - could it be that it needs longer to think?

Improve this question
$\endgroup$
10
  • $\begingroup$ Doesn't MCTS rely on huge amount of training? How did you train your agent in a PC (I'm genuinely interested). $\endgroup$
    – user9947
    May 9, 2020 at 6:45
  • $\begingroup$ From my understanding, a new tree is grown each time a new state is given to it. The best action from that root state is then returned after it has calculated stats on which action will likely lead to a successful outcome. I have tried creating the tree in two ways: keep expanding the tree and updating the stats until X seconds are over, as well as after X iterations. $\endgroup$
    – mason7663
    May 9, 2020 at 12:17
  • $\begingroup$ @mason7663 you do not need to grow the tree from the beginning, you could also replace the root node with current node and keep the stats as it is and then again perform selection, expansion and backpropagation. $\endgroup$
    – Swakshar Deb
    May 9, 2020 at 16:52
  • $\begingroup$ @DuttaA No, MCTS doesn't require any offline training at all. MCTS can be combined with Deep Neural Nets (for various purposes), as was famously done in AlphaGo etc. That's probably what you're thinking of. But in there, it's the DNNs that require huge amounts of training, not the MCTS. $\endgroup$
    – Dennis Soemers ♦
    May 9, 2020 at 18:38
  • 1
    $\begingroup$ @mason7663 Assuming a 6x7 board, Connect-4 basically has a branching factor of 7 (in most states). So if you can't produce nodes deeper than 3 levels below the root, and you produce one new node per iteration, this suggests you have run at most $7^3 = 343$ MCTS iterations. This sounds very low. In Ludii, my MCTS easily runs $15,000$ iterations per second in Connect 4. This suggests at least that your implementation of the game and/or the algorithm are rather slow. Or maybe you're using a very slow programming language. Are you using Python? :) $\endgroup$
    – Dennis Soemers ♦
    May 10, 2020 at 8:51

1 Answer 1

Reset to default
1
$\begingroup$

You should not let the tree grow for only two seconds rather you should use the simulation number equal to 1000 or something like that. I use the simulation number equal to 10000 for making a single move in the tictactoe game and it was working fine for me. Also, after the agent has chosen the move you do not have to start the statistics(N = visit count, V = expected reward, U = UCT score) from the beginning, you can use the current statistics and replace the root node with the chosen node.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You can limit MCTS by iterations instead of time, but I don't see why you should. It depends on the situation. If you do restrict by iterations, 1000 sounds very low for Connect 4 to me though. In our general game implementation in Ludii (which should be slower than game-specific implementations), my MCTS hits 15K iterations per second in the beginning of a game, quickly getting 30-70K iterations per second in the middle of the game, and a peak of 2.4 million iterations per second for the very last move. Good point about tree reuse though, that can help :) $\endgroup$
    – Dennis Soemers ♦
    May 9, 2020 at 18:48
  • $\begingroup$ @DennisSoemers I can not exactly tell how many iterations it will take to give a better result, I just estimated that. But in my sense growing the tree for only 2 sec that OP does is not enough iteration for getting a better result. $\endgroup$
    – Swakshar Deb
    May 10, 2020 at 6:20
  • $\begingroup$ @DennisSoemers I have just superficially seen the MCTS principle and it seems to me that you need to explicitly enumerate states for finding it's suitability. Hence a lot of training for games with large state space I guess? $\endgroup$
    – user9947
    May 11, 2020 at 2:06
  • $\begingroup$ @DuttaA No, it's just a tree search algorithm. Like minimax, breadth-first search, depth-first search, etc. It can operate on any problem that you can express as a (finite) tree right away, without any offline training required. $\endgroup$
    – Dennis Soemers ♦
    May 11, 2020 at 7:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .