<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
span.EmailStyle17
        {mso-style-type:personal-reply;
        font-family:"Calibri",sans-serif;
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;
        font-family:"Calibri",sans-serif;}
@page WordSection1
        {size:8.5in 11.0in;
        margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
        {page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>OK, so let’s talk theory vs practice.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>In theory, TD learning approaches asymptotic optimality when used with a full state space. That is, if your RL model has one parameter for each state, then TD will converge those parameters to the game theoretic values. There are some pre-conditions, but this is true with remarkable generality. In particular, there is nothing about stochastic vs deterministic in the theory.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>So yes, the published experiments for Chess were failures. That is, using a very shallow search and relatively simple evaluation function does not work for chess like it did for Tesauro’s experiments in backgammon. But the conclusion that this is because of stochastic/deterministic is incorrect. Consider Go, for example, where static move generators can play at 1 dan level, and probably quite a bit higher.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>An inference that is compatible with theory is that to conquer chess you will need a deeper, wider network, or better inputs, or a better search engine. Or all of those. You could imagine measuring the skill of a variety of architectures, and map out the path of steepest ascent.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>In retrospect, I view Schradolph’s paper as evidence that neural networks have always been surprisingly successful at Go. Like Brugmann’s paper about Monte Carlo, which was underestimated for a long time. Sigh.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Best,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Brian<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> Minjae Kim [mailto:xiver77@gmail.com] <br><b>Sent:</b> Friday, February 24, 2017 11:56 AM<br><b>To:</b> Brian Sheppard <sheppardco@aol.com>; computer-go@computer-go.org<br><b>Subject:</b> Re: [Computer-go] dealing with multiple local optima<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>TD-gammon is regarded as a special case from the stochastic characteristics of the backgammon game; it smoothens the search space for the value function and the value function itself to a great degree compared to those 'static' games such as go. Experiments of applying TD learning to chess and go was done after the success of TD-gammon, and the result was not good. I also did a small experiment a while ago applying TD learning to go using a similar network structure to that of TD-gammon. The network gets 'stuck' really fast. You can see similar comments to my experience here (<a href="https://chessprogramming.wikispaces.com/Temporal+Difference+Learning">https://chessprogramming.wikispaces.com/Temporal+Difference+Learning</a>). You can make the network more 'actively' trained by doing stochastic move selection rather than simply selecting the move with highest value, but this doesn't work well enough to my experience, where I applied softmax. Schradolph experimented with TD for go in his 1994 paper, where he applied Gibbs sampling for stochastic move selection, although it wasn't a success for building a strong go bot.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>On Fri, Feb 24, 2017 at 11:03 PM, Brian Sheppard via Computer-go <<a href="mailto:computer-go@computer-go.org" target="_blank">computer-go@computer-go.org</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Neural networks always have a lot of local optima. Simply because they have a high degree of internal symmetry. That is, you can “permute” sets of coefficients and get the same function.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Don’t think of starting with expert training as a way to avoid local optima. It is a way to start training with some good examples so that learning can start at a higher level. But then you should continue with self-play.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Backgammon was trained to expert level based on self-play games that were initially random. Google “Tesauro backgammon” and you should be able to find a paper.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>I don’t know NEAT and HyperNEAT; I will look them up. Thank you for the reference.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Best,</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Brian</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> Computer-go [mailto:<a href="mailto:computer-go-bounces@computer-go.org" target="_blank">computer-go-bounces@computer-go.org</a>] <b>On Behalf Of </b>Minjae Kim<br><b>Sent:</b> Friday, February 24, 2017 3:39 AM<br><b>To:</b> <a href="mailto:computer-go@computer-go.org" target="_blank">computer-go@computer-go.org</a><br><b>Subject:</b> [Computer-go] dealing with multiple local optima</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>I've recently viewed the paper of AlphaGo, which has done gradient-based reinforcement learning to get stronger. The learning was successful enough to beat a human master, but in this case, supervised learning with a large database of master level human games was preceded the reinforcement learning. For a complex enough game as go, one can expect that the search space for the policy function would not be smooth at all. So supposedly supervised learning was necessary to guide the policy function to a good starting point before reinforcement. Without such, applying reinforcement learning directly to a random policy can easily make the policy stuck at a bad local optimum. I could have a miunderstanding at this point; correct me if so, but to continue on: if it is hard to have "the good starting point" such as a trained policy from human expert game records, what is a way to devise one. I've had a look on NEAT and HyperNEAT, which are evolutionary methods. Do these evolutionary algorithms scale well on complex strategic decision processes and not just on simple linear decisions such as food gathering and danger avoidance? In case not, what alternatives are known? Is there any success case of a chess, go, or any kind of complex strategic game playing algorithm, where it gained expert strength without domain knowledge such as expert game examples?<o:p></o:p></p></div></div></div><p class=MsoNormal><br>_______________________________________________<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" target="_blank">http://computer-go.org/mailman/listinfo/computer-go</a><o:p></o:p></p></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></body></html>