<div>RGB,</div>
<div>My hypothetical future Recursive Genetic Algorithm Go Player will crush your Hypothetical Future NeuralNet Go Player!<br>Peter<br> </div>
<div><span class="gmail_quote">On 6/24/08, <b class="gmail_sendername">Robert G. Brown</b> <<a href="mailto:rgb@phy.duke.edu">rgb@phy.duke.edu</a>> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid"><span class="q">On Tue, 24 Jun 2008, Peter St. John wrote:<br><br></span><span class="q">
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">On a finite board, the game eventually becomes local; in fact "contact<br>plays" are common after about the first dozen moves, but they are<br>
inescapable later. But the possibilities are horrible, the numbers are huge,<br>for tree-searching. The new thing is monte carlo; to consider a move, the<br>machine actually plays that position against itself a few hundred times<br>
(with a trivial, not recursive, algorithm) and weighs the move by the<br>percentage of outcomes. It's weird, to me.<br></blockquote><br></span>It makes sense to me.  It's in some sense more like humans play.  In<br>
fact, if one can come up with any (even very simple) "local" rules to<br>semi-prune the tree, you can imagine an importance-sampling monte carlo<br>algorithm.<br><br>However, if I were going to try, it would be genetic algorithm all the<br>
way.  Don't explore trees exhaustively; too many of them.  Don't sample<br>them (especially if you can't create a canonical weight to do importance<br>sampling); too many of them.  Breed them.  There are still too many, but<br>
again, if one can generate ANY sort of fitness function, maybe one can<br>get the N^3 and exponential growth of favorable possibilities that are<br>like "making a decision".<br><br>Fortunately, I'm not going to try.  Neural nets are much more fun.  And<br>
MIGHT be able to manage the complexity -- especially one built with a<br>GA...;-)<br><br>  rgb<br><br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">
<div><span class="e" id="q_11abdb9b15ee30fb_3"><br>Peter<br><br>On Tue, Jun 24, 2008 at 9:22 PM, Robert G. Brown <<a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:rgb@phy.duke.edu" target="_blank">rgb@phy.duke.edu</a>> wrote:<br>
<br></span></div>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">
<div><span class="e" id="q_11abdb9b15ee30fb_5">On Tue, 24 Jun 2008, Peter St. John wrote:<br><br> Programming a computer to play Go (an Asian strategy boardgame) has been<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">difficult; some people say it's proof that Go is better or harder than<br>chess, since computers can beat masters at chess but struggle at Go. (I<br>
think that statistically a game of go is about equivalent to a two-game<br>match of chess; both games empty your brain quickly of course). My view is<br>that while go may be somewhat harder to reduce to tree-searching, the main<br>
advantage of computer chess was an early start, e.g. von Neumann.<br><br></blockquote><br>I thought that Go was combinatorially vastly, vastly more difficult than<br>chess.  Both because of the extremely large number of move permutations<br>
that make it very difficult to follow trees and because Go is a<br>fundamentally nonlocal game -- one can imagine a "perfect" Go strategy<br>in which pieces are never played close to each other as the board<br>gradually fills in with higher and higher still disconnected density,<br>
culminating in the winner completely unravelling the loser or<br>precipitating out to win by a single small amount.  Yet nobody can even<br>come close to playing that way -- most games start out that way for a<br>while and then transform into local dogfights that are STILL often<br>
resolved by long range connections.<br><br> This article:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid"><a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.usgo.org/resources/downloads/CogApdx%20II-2.pdf" target="_blank">http://www.usgo.org/resources/downloads/CogApdx%20II-2.pdf</a><br>
describes recent trends in computer Go and mentions a 32-node cluster, 8<br>cores per node. Apparently MPI parallelization is recent for them and they<br>are making good progress.<br><br></blockquote><br>Interesting.  I'll have to look.  Last time I read up on this (in the<br>
context of a conversation with you, IIRC:-) nobody could make a computer<br>go player that could beat even a very bad human player, where computers<br>back to maybe 386's have been able to play chess well enough to win at<br>
least sometimes against weak humans (and win "often" against weak human<br>players by now).  I suck at chess (but can still beat a lot of the<br>people I -- rarely -- play) and modern computers can beat me pretty<br>
easily.  I suck at Go, too -- but I can't even find a BAD go player to<br>run on a PC to try to get better.<br><br> rgb<br><br><br><br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">Peter<br><br>The game Go: <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://en.wikipedia.org/wiki/Go_%28game%29" target="_blank">http://en.wikipedia.org/wiki/Go_%28game%29</a><br>
AGA (American Go Association): <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.usgo.org/" target="_blank">http://www.usgo.org</a><br><br><br></blockquote>--<br>Robert G. Brown                            Phone(cell): 1-919-280-8443<br>
Duke University Physics Dept, Box 90305<br>Durham, N.C. 27708-0305<br></span></div>Web: <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.phy.duke.edu/~rgb" target="_blank">http://www.phy.duke.edu/~rgb</a> <<a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.phy.duke.edu/%7Ergb" target="_blank">http://www.phy.duke.edu/%7Ergb</a>><br>
Book of Lilith Website: <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.phy.duke.edu/~rgb/Lilith/Lilith.php" target="_blank">http://www.phy.duke.edu/~rgb/Lilith/Lilith.php</a><<a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.phy.duke.edu/%7Ergb/Lilith/Lilith.php" target="_blank">http://www.phy.duke.edu/%7Ergb/Lilith/Lilith.php</a>><span class="q"><br>
Lulu Bookstore: <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://stores.lulu.com/store.php?fAcctID=877977" target="_blank">http://stores.lulu.com/store.php?fAcctID=877977</a><br><br></span></blockquote>
<br></blockquote>
<div><span class="e" id="q_11abdb9b15ee30fb_9"><br>-- <br>Robert G. Brown                            Phone(cell): 1-919-280-8443<br>Duke University Physics Dept, Box 90305<br>Durham, N.C. 27708-0305<br>Web: <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.phy.duke.edu/~rgb" target="_blank">http://www.phy.duke.edu/~rgb</a><br>
Book of Lilith Website: <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.phy.duke.edu/~rgb/Lilith/Lilith.php" target="_blank">http://www.phy.duke.edu/~rgb/Lilith/Lilith.php</a><br>Lulu Bookstore: <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://stores.lulu.com/store.php?fAcctID=877977" target="_blank">http://stores.lulu.com/store.php?fAcctID=877977</a><br>
</span></div></blockquote></div><br>