Answers.Body: <p>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. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-09T18:48:34.883Z
Answers.Text: 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 :)
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-10T06:20:44.697Z
Answers.Text: @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.
Answers.UserDisplayName: Swakshar Deb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-11T07:39:00.167Z
Answers.Text: @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.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-09T09:13:28.107Z
Answers.LastActivityDate: 2020-05-09T09:42:40.907Z
Answers.LastEditDate: 2020-05-09T09:42:40.907Z
Answers.UserDisplayName: Swakshar Deb
Answers.Body: <p>With the proper implementation, 2 secs is enough to defeat you. I have made an MCTS agent for Gomoku (Connect five), which in that interval is able to generate 80k-60k simulations which are enough to beat a random agent 100% of the time and me most of the time. With connect four you should be able to get even more sims and have an even better agent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-30T13:17:11.563Z
Answers.LastActivityDate: 2024-09-30T13:17:11.563Z
Answers.UserDisplayName: ModderG
Body: <p>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). </p>
  
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-09T12:17:42.723Z
Comments.Text: 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.
Comments.UserDisplayName: mason7663
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-09T16:52:49.880Z
Comments.Text: @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.
Comments.UserDisplayName: Swakshar Deb
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-09T18:38:54.560Z
Comments.Text: @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.
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-09T18:39:42.343Z
Comments.Text: Indeed. I’m not using NNs, just vanilla MCTS
Comments.UserDisplayName: mason7663
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-09T18:41:36.353Z
Comments.Text: @mason7663 I'm not 100% sure how "good" basic MCTS implementations at 1-2 second time controls are generally expected to be at Connect 4. It will depend very much also on how efficient your implementation of the game is (because that influences how many playouts MCTS can run). It also depends on how good you are at the game yourself :) My own implementation of a fairly basic MCTS variant (named UCT) in Ludii beats me. But maybe I'm just bad. You can download at https://ludii.games/downloads.php and tell me how you fare against that one :)
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-09T18:43:28.793Z
Comments.Text: Because Ludii is a general game system, its implementation of Connect 4 (or any other game really) is significantly slower than what you could pull off in a single-game implementation though. So, in theory, this one should be weaker than your own game-specific implementation.
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-09T21:38:42.030Z
Comments.Text: @SwaksharDeb are you saying the tree (and its stats) are stored somewhere and queried/updated on the next action? If so, where are they stored?
Comments.UserDisplayName: mason7663
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-09T21:45:13.350Z
Comments.Text: @DennisSoemers Thank you for your comments. After the iterations (2 seconds of), I'm currently only seeing only three (max) children deep nodes/states from the root node (great grandchildren) – does this mean something has gone wrong? Even if I leave it to run for 10 seconds, I'm still only seeing a max of three descendants. Also, using C=2 (in UCT), the values of the children of the root node are all pretty much the same (around 0.933202). Is this another indication of something going awry?
Comments.UserDisplayName: mason7663
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-10T08:51:12.177Z
Comments.Text: @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? :)
Comments.UserDisplayName: Dennis Soemers
Tags: <machine-learning><reinforcement-learning><monte-carlo-tree-search>
Title: Should Monte Carlo tree search be able to consistently beat me in the connect four game?
UserDisplayName: mason7663
ThreadText: # Should Monte Carlo tree search be able to consistently beat me in the connect four game?
  
  (Asked by: username_0 on 2020-05-09)
  
  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?
  
  **Tags:** machine-learning, reinforcement-learning, monte-carlo-tree-search
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: @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.  
  > **username_2**: @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.  
  > **username_0**: Indeed. I’m not using NNs, just vanilla MCTS  
  > **username_2**: @mason7663 I'm not 100% sure how "good" basic MCTS implementations at 1-2 second time controls are generally expected to be at Connect 4. It will depend very much also on how efficient your implementation of the game is (because that influences how many playouts MCTS can run). It also depends on how good you are at the game yourself :) My own implementation of a fairly basic MCTS variant (named UCT) in Ludii beats me. But maybe I'm just bad. You can download at https://ludii.games/downloads.php and tell me how you fare against that one :)  
  > **username_2**: Because Ludii is a general game system, its implementation of Connect 4 (or any other game really) is significantly slower than what you could pull off in a single-game implementation though. So, in theory, this one should be weaker than your own game-specific implementation.  
  > **username_0**: @SwaksharDeb are you saying the tree (and its stats) are stored somewhere and queried/updated on the next action? If so, where are they stored?  
  > **username_0**: @DennisSoemers Thank you for your comments. After the iterations (2 seconds of), I'm currently only seeing only three (max) children deep nodes/states from the root node (great grandchildren) – does this mean something has gone wrong? Even if I leave it to run for 10 seconds, I'm still only seeing a max of three descendants. Also, using C=2 (in UCT), the values of the children of the root node are all pretty much the same (around 0.933202). Is this another indication of something going awry?  
  > **username_2**: @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? :)  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-05-09. Score: 1
  
  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.
  
  > **Comments:**
  > **username_2**: 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 :)  
  > **username_1**: @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.  
  > **username_2**: @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.  
  
  ---
  
  ### Answer by username_3 on 2024-09-30. Score: 0
  
  With the proper implementation, 2 secs is enough to defeat you. I have made an MCTS agent for Gomoku (Connect five), which in that interval is able to generate 80k-60k simulations which are enough to beat a random agent 100% of the time and me most of the time. With connect four you should be able to get even more sims and have an even better agent.
  
  
  ---
  
  