That go is "vastly" more complex is a matter of degree; but there are bounds on e.g. the number of possible games, and if chess is googleplex times 2, go is up-arrow-googleplex. That's not my official mathematician estimage :-) but yeah go is horribly complex, and more horribly than chess, but still tractable to folks who think as we do.<br>
<br>Go programs can beat even masters, now, on the 9x9 board, and I think recently they play well enough to beat a master on the full 19x19, *occasionally*, at *fast time controls*, and with handicaps. When I played Many Faces of Go several years ago I could beat it at 13 stone handicap, but it could beat me at 17 (Edward Lasker said that 3 stones was like knight odds in chess). But now, if I play a "bot" on KGS, I have difficulty giving it a 6 stone handicap. That's a huge improvement (to me). There is still a lone way to go.<br>
<br>On a finite board, the game eventually becomes local; in fact "contact plays" are common after about the first dozen moves, but they are inescapable later. But the possibilities are horrible, the numbers are huge, for tree-searching. The new thing is monte carlo; to consider a move, the machine actually plays that position against itself a few hundred times (with a trivial, not recursive, algorithm) and weighs the move by the percentage of outcomes. It's weird, to me.<br>
<br>Peter<br><br><div class="gmail_quote">On Tue, Jun 24, 2008 at 9:22 PM, Robert G. Brown <<a href="mailto:rgb@phy.duke.edu">rgb@phy.duke.edu</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">On Tue, 24 Jun 2008, Peter St. John wrote:<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Programming a computer to play Go (an Asian strategy boardgame) has been<br>
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>
</blockquote>
<br></div>
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.<div class="Ih2E3d"><br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
This article:<br>
<a 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>
</blockquote>
<br></div>
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<div><div></div><div class="Wj3C7c"><br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
Peter<br>
<br>
The game Go: <a 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 href="http://www.usgo.org" target="_blank">http://www.usgo.org</a><br>
<br>
</blockquote>
<br></div></div><font color="#888888">
-- <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 href="http://www.phy.duke.edu/%7Ergb" target="_blank">http://www.phy.duke.edu/~rgb</a><br>
Book of Lilith Website: <a href="http://www.phy.duke.edu/%7Ergb/Lilith/Lilith.php" target="_blank">http://www.phy.duke.edu/~rgb/Lilith/Lilith.php</a><br>
Lulu Bookstore: <a href="http://stores.lulu.com/store.php?fAcctID=877977" target="_blank">http://stores.lulu.com/store.php?fAcctID=877977</a><br>
</font></blockquote></div><br>