Answers.Body: <p>There are a few things you can do to address this</p>
  <p>(1) Setting Q correctly on unexplored nodes</p>
  <blockquote>
  <p>With some debugging I figured that after the first simulation, the last visited child would have a Q value which is on average 0.5, and all the rest of the children would have 0 for their Q values</p>
  </blockquote>
  <p>This already points out a bug, as the rest of the children should start with the &quot;average Q-value&quot;. Remember that Q is just our guess for the EV of an action. Your comment says that you set it to &quot;0.5&quot;, but this still isn't quite right. You'll want to modify this by initializing it to the &quot;average value&quot; of a &quot;random move&quot; in that position.</p>
  <p>For Chess and Go, this is quite close to 0 from most positions, since most valid moves are terrible. For your game, it's possible that this value is higher, if most moves are &quot;reasonable&quot;. But, it should still be set to the &quot;Average value of a random move in that particular position&quot;, not simply 0.5.</p>
  <p>When your network is very weak, its choice will have a value of approximately &quot;the average value of a random move&quot;, so by setting the initial Q correctly, it will cause the difference in Q between two different moves to be very small, letting the &quot;U&quot; term dominate initial exploration. To be precise, the difference in Q will tell you <em>How much better you current path is, over just picking some other random move</em>, which is exactly what you want the difference in Q to be.</p>
  <p>See Lc0's &quot;FPU / First Play Urgency&quot; configuration, which sets unvisited node's initial value to be 0.44 less than the parents' evaluation.</p>
  <ul>
  <li>Theoretically, if you have high confidence in your NN, you can lower FPU for increased efficiency.</li>
  </ul>
  <p>(2) Increase <span class="math-container">$C_{puct}$</span> with respect to the number of paths down that edge.</p>
  <p>In the face of extreme depth down a particular path, <span class="math-container">$C_{puct}$</span> should begin to increase to at least &quot;double-check&quot; the moves we've been ignoring thusfar. AlphaZero already does this:</p>
  <hr />
  <p><a href="https://i.sstatic.net/jnLST.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/jnLST.png" alt="enter image description here" /></a></p>
  <hr />
  <p>With their numbers, <span class="math-container">$C_{puct}$</span> starts at 2.5, but rises to 2.8 when Depth = 20k, and 2.97 when Depth = 40k. (<span class="math-container">$2.5 + \log(2)$</span>, and <span class="math-container">$2.5 + \log(3)$</span>, respectively). You'll have to adjust this manually, often in relation to your simulations-per-move.</p>
  <p>(3) Increase Dirichlet Noise</p>
  <p>I'm not sure what <span class="math-container">$\alpha$</span> you used, but based on AlphaZero, <span class="math-container">$\alpha = 10/60000 =$</span> 1.66e-4 is what you should be aiming for, if you want to match AlphaZero's configuration of 10/AverageValidMoves.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-09T02:28:52.507Z
Answers.Text: Thanks for the detailed answer. Regarding this statement: "For Chess and Go, this is quite close to 0 from most positions, since most valid moves are terrible." - In this does the 0 represent a loss or draw? Because in many sources the range of Q is [-1, 1]  than [0, 1]. It just happens that in my implementation I used [0, 1] from the value head. If I initialise Q to 0 or close to 0 it is almost saying an unexplored move is estimated to be a loss, and this will give significant weightings to the explored moves during selection when the network is still very weak.
Answers.UserDisplayName: javaPhobic
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-09T02:41:12.367Z
Answers.Text: @javaPhobic It would represent a loss. The LeelaZero team generally found that your odds of winning drops about 44% when you make a random move. So 50/50 game goes to 6%/94%. And a 94% chance of winning drops to a 50% chance of winning.
Answers.UserDisplayName: Nicholas Pipitone
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-09T03:27:14.273Z
Answers.Text: It is important that for LeelaChess, FPU is still > 50%, when you start off with a 98% chance of winning. You don't want to blindly set it, you want it to be relative to the parent EV. For Chess/Go, it's still harsh though. But for 60,000 moves, it's likely the case that a lot of them are reasonable, if your NN has to pick the "one magic move" out of 60k, it'll take a lot of Dirichlet noise to figure that out lol. This is definitely a "hyperparameter" you'll want to tune a lot, lower FPU values will more aggressively use the NN.
Answers.UserDisplayName: Nicholas Pipitone
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-09T03:33:51.783Z
Answers.Text: For Go, this was set to "0" for all positions, since in Go, even if you have a 90% chance of winning, most random moves are terrible. Only a small set of the dozens upon dozens of valid moves are reasonable.
Answers.UserDisplayName: Nicholas Pipitone
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-08T13:01:06.270Z
Answers.LastActivityDate: 2022-02-08T13:34:46.407Z
Answers.LastEditDate: 2022-02-08T13:34:46.407Z
Answers.UserDisplayName: Nicholas Pipitone
Body: <p>I have a problem with applying alpha zero self-play to a game (Connect 6) with a huge branching factor (30,000 on average).</p>
  <p>I have implemented the MCTS as described but I found that during the MCTS simulations for the first move, because <strong>P(s, a)</strong> is so much smaller than <strong>Q(s, a)</strong>, the MCTS search tree is extremely narrow (in fact, it only had 1 branch per level, and later I have added dirichlet noise and it changed the tree to have 2 child branches instead of 1, per level).</p>
  <p>With some debugging I figured that after the first simulation, the last visited child would have a <strong>Q</strong> value which is on average 0.5, and all the rest of the children would have 0 for their <strong>Q</strong> values (because they haven't been explored) while their <strong>U</strong> are way smaller, about 1/60000 on average. So comparing all the <strong>Q + U</strong> on the 2nd and subsequent simulations would result in selecting the same node over and over again, building this narrow tree.</p>
  <p>To make matter worse, because the first simulation built a very narrow tree, and we don't clear the statistics on the subsequent simulations for the next move, the end result is the simulations for the first move dictated the whole self-play for the next <em>X</em> moves or so (where <em>X</em> is number of simulations per move) - this is because the N values on this path is accumulated from the previous simulations from the prior moves. Imagine I run 800 simulations per move but the <strong>N</strong> value on the only child inherited from previous simulations is &gt; 800 when I started the simulation for the 3rd move in the game.</p>
  <p>This is a basically related to question 2 raised in this thread:</p>
  <p><a href="https://ai.stackexchange.com/questions/24966/alphago-zero-does-qs-t-a-dominate-us-t-a-in-difficult-game-states">AlphaGo Zero: does $Q(s_t, a)$ dominate $U(s_t, a)$ in difficult game states?</a></p>
  <p>I don't think the answer addressed the problem I am having here. Surely we are not comparing Q and U but when Q dominates U then we ended up building a narrow and deep tree and the accumulated N values are set on this single path, preventing the self-play to explore meaningful moves.</p>
  <p>At the end of the game these <strong>N</strong> values on the root nodes of moves played ended up training the policy network, reinforcing these even more on the next episode of training.</p>
  <p>What am I doing wrong here? Or is AlphaZero algorithm not well suited for games with branching factor in this order?</p>
  <p><em>Note: as an experiment I have tried to use a variable <strong>C PUCT</strong> value, which is proportional to the number of legal moves on each game state. However this doesn't seem to help either.</em></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-26T16:24:41.540Z
Comments.Text: Hello. Welcome to AI SE. I want to let you know that you can use latex/mathjax on this site, so I suggest that [you edit your post to format the math symbols properly with them](https://ai.stackexchange.com/posts/25939/edit).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-15T12:19:36.107Z
Comments.Text: I don't know if my experience can be of any help to anyone, but I got this exact scenario because I unintentionally initialize v (or q?) != 0 for newly encountered state when building the Monte-Carlo tree. Basically then the search never considers certain states/branches ever again because the agent thinks it can get better results in the other branches.
Comments.UserDisplayName: Nuclear241
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-01T01:17:10.020Z
Comments.Text: Yes @Nuclear03020704 I believe this is what I ran into. In my case I was initialising Q as 0 but I need it set as 0.5 rather, because my value head has an activation function that returns [0, 1] than [-1, 1]. So it depends on what your representation is for a draw game evaluation :)
Comments.UserDisplayName: javaPhobic
Tags: <machine-learning><deep-learning><monte-carlo-tree-search><alphazero>
Title: Alpha Zero does not converge for Connect 6, a game with huge branching factor - why?
UserDisplayName: javaPhobic
ThreadText: # Alpha Zero does not converge for Connect 6, a game with huge branching factor - why?
  
  (Asked by: username_0 on 2021-01-23)
  
  I have a problem with applying alpha zero self-play to a game (Connect 6) with a huge branching factor (30,000 on average).
  
  I have implemented the MCTS as described but I found that during the MCTS simulations for the first move, because **P(s, a)** is so much smaller than **Q(s, a)**, the MCTS search tree is extremely narrow (in fact, it only had 1 branch per level, and later I have added dirichlet noise and it changed the tree to have 2 child branches instead of 1, per level).
  
  With some debugging I figured that after the first simulation, the last visited child would have a **Q** value which is on average 0.5, and all the rest of the children would have 0 for their **Q** values (because they haven't been explored) while their **U** are way smaller, about 1/60000 on average. So comparing all the **Q + U** on the 2nd and subsequent simulations would result in selecting the same node over and over again, building this narrow tree.
  
  To make matter worse, because the first simulation built a very narrow tree, and we don't clear the statistics on the subsequent simulations for the next move, the end result is the simulations for the first move dictated the whole self-play for the next *X* moves or so (where *X* is number of simulations per move) - this is because the N values on this path is accumulated from the previous simulations from the prior moves. Imagine I run 800 simulations per move but the **N** value on the only child inherited from previous simulations is > 800 when I started the simulation for the 3rd move in the game.
  
  This is a basically related to question 2 raised in this thread:
  
  [AlphaGo Zero: does $Q(s\_t, a)$ dominate $U(s\_t, a)$ in difficult game states?](https://ai.stackexchange.com/questions/24966/alphago-zero-does-qs-t-a-dominate-us-t-a-in-difficult-game-states)
  
  I don't think the answer addressed the problem I am having here. Surely we are not comparing Q and U but when Q dominates U then we ended up building a narrow and deep tree and the accumulated N values are set on this single path, preventing the self-play to explore meaningful moves.
  
  At the end of the game these **N** values on the root nodes of moves played ended up training the policy network, reinforcing these even more on the next episode of training.
  
  What am I doing wrong here? Or is AlphaZero algorithm not well suited for games with branching factor in this order?
  
  *Note: as an experiment I have tried to use a variable **C PUCT** value, which is proportional to the number of legal moves on each game state. However this doesn't seem to help either.*
  
  **Tags:** machine-learning, deep-learning, monte-carlo-tree-search, alphazero
  > **Comments:**
  > **username_1**: Hello. Welcome to AI SE. I want to let you know that you can use latex/mathjax on this site, so I suggest that [you edit your post to format the math symbols properly with them](https://ai.stackexchange.com/posts/25939/edit).  
  > **username_2**: I don't know if my experience can be of any help to anyone, but I got this exact scenario because I unintentionally initialize v (or q?) != 0 for newly encountered state when building the Monte-Carlo tree. Basically then the search never considers certain states/branches ever again because the agent thinks it can get better results in the other branches.  
  > **username_0**: Yes @Nuclear03020704 I believe this is what I ran into. In my case I was initialising Q as 0 but I need it set as 0.5 rather, because my value head has an activation function that returns [0, 1] than [-1, 1]. So it depends on what your representation is for a draw game evaluation :)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2022-02-08. Score: 1 | Accepted answer
  
  There are a few things you can do to address this
  
  (1) Setting Q correctly on unexplored nodes
  
  > With some debugging I figured that after the first simulation, the last visited child would have a Q value which is on average 0.5, and all the rest of the children would have 0 for their Q values
  
  This already points out a bug, as the rest of the children should start with the "average Q-value". Remember that Q is just our guess for the EV of an action. Your comment says that you set it to "0.5", but this still isn't quite right. You'll want to modify this by initializing it to the "average value" of a "random move" in that position.
  
  For Chess and Go, this is quite close to 0 from most positions, since most valid moves are terrible. For your game, it's possible that this value is higher, if most moves are "reasonable". But, it should still be set to the "Average value of a random move in that particular position", not simply 0.5.
  
  When your network is very weak, its choice will have a value of approximately "the average value of a random move", so by setting the initial Q correctly, it will cause the difference in Q between two different moves to be very small, letting the "U" term dominate initial exploration. To be precise, the difference in Q will tell you *How much better you current path is, over just picking some other random move*, which is exactly what you want the difference in Q to be.
  
  See Lc0's "FPU / First Play Urgency" configuration, which sets unvisited node's initial value to be 0.44 less than the parents' evaluation.
  
  * Theoretically, if you have high confidence in your NN, you can lower FPU for increased efficiency.
  
  (2) Increase $C\_{puct}$ with respect to the number of paths down that edge.
  
  In the face of extreme depth down a particular path, $C\_{puct}$ should begin to increase to at least "double-check" the moves we've been ignoring thusfar. AlphaZero already does this:
  
  ---
  
  [![enter image description here](https://i.sstatic.net/jnLST.png)](https://i.sstatic.net/jnLST.png)
  
  ---
  
  With their numbers, $C\_{puct}$ starts at 2.5, but rises to 2.8 when Depth = 20k, and 2.97 when Depth = 40k. ($2.5 + \log(2)$, and $2.5 + \log(3)$, respectively). You'll have to adjust this manually, often in relation to your simulations-per-move.
  
  (3) Increase Dirichlet Noise
  
  I'm not sure what $\alpha$ you used, but based on AlphaZero, $\alpha = 10/60000 =$ 1.66e-4 is what you should be aiming for, if you want to match AlphaZero's configuration of 10/AverageValidMoves.
  
  > **Comments:**
  > **username_0**: Thanks for the detailed answer. Regarding this statement: "For Chess and Go, this is quite close to 0 from most positions, since most valid moves are terrible." - In this does the 0 represent a loss or draw? Because in many sources the range of Q is [-1, 1]  than [0, 1]. It just happens that in my implementation I used [0, 1] from the value head. If I initialise Q to 0 or close to 0 it is almost saying an unexplored move is estimated to be a loss, and this will give significant weightings to the explored moves during selection when the network is still very weak.  
  > **username_3**: @javaPhobic It would represent a loss. The LeelaZero team generally found that your odds of winning drops about 44% when you make a random move. So 50/50 game goes to 6%/94%. And a 94% chance of winning drops to a 50% chance of winning.  
  > **username_3**: It is important that for LeelaChess, FPU is still > 50%, when you start off with a 98% chance of winning. You don't want to blindly set it, you want it to be relative to the parent EV. For Chess/Go, it's still harsh though. But for 60,000 moves, it's likely the case that a lot of them are reasonable, if your NN has to pick the "one magic move" out of 60k, it'll take a lot of Dirichlet noise to figure that out lol. This is definitely a "hyperparameter" you'll want to tune a lot, lower FPU values will more aggressively use the NN.  
  > **username_3**: For Go, this was set to "0" for all positions, since in Go, even if you have a 90% chance of winning, most random moves are terrible. Only a small set of the dozens upon dozens of valid moves are reasonable.  
  
  ---
  
  