Answers.Body: <p>Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory performance, but there is a plethora of extensions/enhancements available.</p>
  
  <p>I don't have experience with the specific game you mentioned (Connect6), but from a quick look at how the game works, I imagine there will be a huge number of transpositions in the search tree (positions that are the same but can be reached through multiple different paths in the search tree). This will especially be very common if you treat placing one stone as a single ply; every "combined move" (of placing two stones in two positions subsequently) can be reached in two different ways, simply by switching the order in which the player places them. There has been research in using Transposition Tables with MCTS, so that may be a promising direction to look into.</p>
  
  <p>I also suspect there will be great value in using Deep (Reinforcement) Learning approaches. If there is a large board on which to place stones, there will likely be many moves that are "absurd" and can easily be dismissed altogether by Deep Learning approaches (e.g., placing stones far away in a corner of the board where none of the "action" is going on). Vanilla MCTS, without Deep Learning extensions, will not be able to recognize and dismiss such absurd moves, and play them way too often (in Play-Out but also Selection phase due to the high branching factor). The most obvious source of inspiration here would be AlphaGo Zero.</p>
  
  <p>Finally, there's definitely some published research on Connect6 AI (and even MCTS in Connect6). For example: <a href="http://web.csie.ndhu.edu.tw/sjyen/Journal/0022011IEEE.pdf" rel="noreferrer">Two-Stage Monte Carlo Tree Search for Connect6</a>. You can likely also find more relevant research by checking that paper's list of References, and <a href="https://scholar.google.nl/scholar?cites=2123165069157963257&amp;as_sdt=2005&amp;sciodt=0,5" rel="noreferrer">checking later papers on google scholar that cite this one</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-08T10:52:44.217Z
Answers.LastActivityDate: 2018-09-08T10:52:44.217Z
Answers.UserDisplayName: Dennis Soemers
Body: <p><a href="https://en.wikipedia.org/wiki/Connect6" rel="nofollow noreferrer">Connect6</a> is an example of a game with a very high branching factor. It is about 45 thousand, dwarfing even the impressive Go.</p>
  <p>Which algorithms can we use on games with such high branching factors?</p>
  <p>I tried MCTS (soft rollouts, counting a ply as placing one stone), but it does not even block the opponent, due to the high branching factor.</p>
  <p>In the case of Connect6, there are stronger AIs out there, but they aren't described in any research papers that I know of.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-09-08T08:25:55.827Z
Comments.Text: There are papers on the website: http://www.connect6.org/index.php/-mainmenu-58
Comments.UserDisplayName: Mercer
Tags: <game-ai><monte-carlo-tree-search><algorithm-request><combinatorial-games><branching-factors>
Title: Which algorithms can we use on games with high branching factors (e.g. Connect6)?
UserDisplayName: Christopher King
ThreadText: # Which algorithms can we use on games with high branching factors (e.g. Connect6)?
  
  (Asked by: username_0 on 2018-09-07)
  
  [Connect6](https://en.wikipedia.org/wiki/Connect6) is an example of a game with a very high branching factor. It is about 45 thousand, dwarfing even the impressive Go.
  
  Which algorithms can we use on games with such high branching factors?
  
  I tried MCTS (soft rollouts, counting a ply as placing one stone), but it does not even block the opponent, due to the high branching factor.
  
  In the case of Connect6, there are stronger AIs out there, but they aren't described in any research papers that I know of.
  
  **Tags:** game-ai, monte-carlo-tree-search, algorithm-request, combinatorial-games, branching-factors
  > **Comments:**
  > **username_1**: There are papers on the website: http://www.connect6.org/index.php/-mainmenu-58  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-09-08. Score: 6
  
  Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory performance, but there is a plethora of extensions/enhancements available.
  
  I don't have experience with the specific game you mentioned (Connect6), but from a quick look at how the game works, I imagine there will be a huge number of transpositions in the search tree (positions that are the same but can be reached through multiple different paths in the search tree). This will especially be very common if you treat placing one stone as a single ply; every "combined move" (of placing two stones in two positions subsequently) can be reached in two different ways, simply by switching the order in which the player places them. There has been research in using Transposition Tables with MCTS, so that may be a promising direction to look into.
  
  I also suspect there will be great value in using Deep (Reinforcement) Learning approaches. If there is a large board on which to place stones, there will likely be many moves that are "absurd" and can easily be dismissed altogether by Deep Learning approaches (e.g., placing stones far away in a corner of the board where none of the "action" is going on). Vanilla MCTS, without Deep Learning extensions, will not be able to recognize and dismiss such absurd moves, and play them way too often (in Play-Out but also Selection phase due to the high branching factor). The most obvious source of inspiration here would be AlphaGo Zero.
  
  Finally, there's definitely some published research on Connect6 AI (and even MCTS in Connect6). For example: [Two-Stage Monte Carlo Tree Search for Connect6](http://web.csie.ndhu.edu.tw/sjyen/Journal/0022011IEEE.pdf). You can likely also find more relevant research by checking that paper's list of References, and [checking later papers on google scholar that cite this one](https://scholar.google.nl/scholar?cites=2123165069157963257&as_sdt=2005&sciodt=0,5).
  
  
  ---
  
  