<div dir="ltr"><div>I made a pull request to Leela, and put some data in there. It shows the details of how Q is initialized are actually important:</div><a href="https://github.com/gcp/leela-zero/pull/238">https://github.com/gcp/leela-zero/pull/238</a><br><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2017-12-03 19:56 GMT-06:00 Álvaro Begué <span dir="ltr"><<a href="mailto:alvaro.begue@gmail.com" target="_blank">alvaro.begue@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">You are asking about the selection of the move that goes to a leaf. When the node before the move was expanded (in a previous playout), the value of Q(s,a) for that move was initialized to 0.<div><br></div><div>The UCB-style formula they use in the tree part of the playout is such that the first few visits will follow the probability distribution from the policy output of the network, and over time it converges to using primarily the moves that have best results. So the details of how Q is initialized are not very relevant.</div><div><div class="h5"><div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Dec 3, 2017 at 5:11 PM, Andy <span dir="ltr"><<a href="mailto:andy.olsen.tx@gmail.com" target="_blank">andy.olsen.tx@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Álvaro, you are quoting from "Expand and evaluate (Figure 2b)". But my question is about the section before that "Select (Figure 2a)". So the node has not been expanded+initialized. <div><br></div><div>As Brian Lee mentioned, his MuGo uses the parent's value, which assumes without further information the value should be close to the same as before.</div><div><br></div><div>LeelaZ uses 1.1 for a "first play urgency", which assumes you should prioritize getting at least one evaluation from the NN for each node.</div><div><a href="https://github.com/gcp/leela-zero/blob/master/src/UCTNode.cpp#L323" target="_blank">https://github.com/gcp/leela-z<wbr>ero/blob/master/src/UCTNode.cp<wbr>p#L323</a></div><div><br></div><div>Finally using a value of 0 would seem to place extra confidence in the policy net values.</div><div><br></div><div>I feel like MuGo's implementation makes sense, but I'm trying to get some experimental evidence showing the impact before suggesting it to Leela's author. So far my self-play tests with different settings do not show a big impact, but I am changing other variables at the same time.</div><span class="m_8761437410202889135m_-42132641091814392HOEnZb"><font color="#888888"><div><br></div><div>- Andy</div></font></span><div><div class="m_8761437410202889135m_-42132641091814392h5"><div><br></div><div><br><div class="gmail_extra"><br><div class="gmail_quote">2017-12-03 14:30 GMT-06:00 Álvaro Begué <span dir="ltr"><<a href="mailto:alvaro.begue@gmail.com" target="_blank">alvaro.begue@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">The text in the appendix has the answer, in a paragraph titled "Expand and evaluate (Fig. 2b)":<div>  "[...] The leaf node is expanded and and each edge (s_t, a) is initialized to {N(s_t, a) = 0, W(s_t, a) = 0, Q(s_t, a) = 0, P(s_t, a) = p_a}; [...]"</div><div><br></div><div><br></div></div><div class="m_8761437410202889135m_-42132641091814392m_9211197140316346587gmail-HOEnZb"><div class="m_8761437410202889135m_-42132641091814392m_9211197140316346587gmail-h5"><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Dec 3, 2017 at 11:27 AM, Andy <span dir="ltr"><<a href="mailto:andy.olsen.tx@gmail.com" target="_blank">andy.olsen.tx@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Figure 2a shows two bolded Q+U max values. The second one is going to a leaf that doesn't exist yet, i.e. not expanded yet. Where do they get that Q value from? </div><div><br></div><div>The associated text doesn't clarify the situation: "Figure 2: Monte-Carlo tree search in AlphaGo Zero. a Each simulation traverses the tree by selecting the edge with maximum action-value Q, plus an upper confidence bound U that depends on a stored prior probability P and visit count N for that edge (which is incremented once traversed). b The leaf node is expanded..."</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div></div><div class="m_8761437410202889135m_-42132641091814392m_9211197140316346587gmail-m_-8178438770251539109HOEnZb"><div class="m_8761437410202889135m_-42132641091814392m_9211197140316346587gmail-m_-8178438770251539109h5"><div class="gmail_extra"><br><div class="gmail_quote">2017-12-03 9:44 GMT-06:00 Álvaro Begué <span dir="ltr"><<a href="mailto:alvaro.begue@gmail.com" target="_blank">alvaro.begue@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>I am not sure where in the paper you think they use Q(s,a) for a node s that hasn't been expanded yet. Q(s,a) is a property of an edge of the graph. At a leaf they only use the `value' output of the neural network.<br><br></div>If this doesn't match your understanding of the paper, please point to the specific paragraph that you are having trouble with.<br><br>Álvaro.<br><br><br></div><div class="gmail_extra"><br><div class="gmail_quote"><span>On Sun, Dec 3, 2017 at 9:53 AM, Andy <span dir="ltr"><<a href="mailto:andy.olsen.tx@gmail.com" target="_blank">andy.olsen.tx@gmail.com</a>></span> wrote:<br></span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span><div dir="ltr">I don't see the AGZ paper explain what the mean action-value Q(s,a) should be for a node that hasn't been expanded yet. The equation for Q(s,a) has the term 1/N(s,a) in it because it's supposed to average over N(s,a) visits. But in this case N(s,a)=0 so that won't work.<div><br></div><div>Does anyone know how this is supposed to work? Or is it another detail AGZ didn't spell out?</div><div><br></div><div><br></div></div>
<br></span>______________________________<wbr>_________________<br>
Computer-go mailing list<br>
<a href="mailto:Computer-go@computer-go.org" target="_blank">Computer-go@computer-go.org</a><br>
<a href="http://computer-go.org/mailman/listinfo/computer-go" rel="noreferrer" target="_blank">http://computer-go.org/mailman<wbr>/listinfo/computer-go</a><br></blockquote></div><br></div>
<br>______________________________<wbr>_________________<br>
Computer-go mailing list<br>
<a href="mailto:Computer-go@computer-go.org" target="_blank">Computer-go@computer-go.org</a><br>
<a href="http://computer-go.org/mailman/listinfo/computer-go" rel="noreferrer" target="_blank">http://computer-go.org/mailman<wbr>/listinfo/computer-go</a><br></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
Computer-go mailing list<br>
<a href="mailto:Computer-go@computer-go.org" target="_blank">Computer-go@computer-go.org</a><br>
<a href="http://computer-go.org/mailman/listinfo/computer-go" rel="noreferrer" target="_blank">http://computer-go.org/mailman<wbr>/listinfo/computer-go</a><br></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
Computer-go mailing list<br>
<a href="mailto:Computer-go@computer-go.org" target="_blank">Computer-go@computer-go.org</a><br>
<a href="http://computer-go.org/mailman/listinfo/computer-go" rel="noreferrer" target="_blank">http://computer-go.org/mailman<wbr>/listinfo/computer-go</a><br></blockquote></div><br></div></div></div></div></div>
<br>______________________________<wbr>_________________<br>
Computer-go mailing list<br>
<a href="mailto:Computer-go@computer-go.org" target="_blank">Computer-go@computer-go.org</a><br>
<a href="http://computer-go.org/mailman/listinfo/computer-go" rel="noreferrer" target="_blank">http://computer-go.org/mailman<wbr>/listinfo/computer-go</a><br></blockquote></div><br></div></div></div></div>
<br>______________________________<wbr>_________________<br>
Computer-go mailing list<br>
<a href="mailto:Computer-go@computer-go.org">Computer-go@computer-go.org</a><br>
<a href="http://computer-go.org/mailman/listinfo/computer-go" rel="noreferrer" target="_blank">http://computer-go.org/<wbr>mailman/listinfo/computer-go</a><br></blockquote></div><br></div>