# Should Monte Carlo tree search be able to consistently beat me in the connect four game?

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?

• Doesn't MCTS rely on huge amount of training? How did you train your agent in a PC (I'm genuinely interested).
– user9947
May 9, 2020 at 6:45
• 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. May 9, 2020 at 12:17
• @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. May 9, 2020 at 16:52
• @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. May 9, 2020 at 18:38
• @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? :) May 10, 2020 at 8:51