[Beowulf] Go-playing machines

[Peter St. John]

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.

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.

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.

Peter

On Tue, Jun 24, 2008 at 9:22 PM, Robert G. Brown <rgb at phy.duke.edu> wrote:

> On Tue, 24 Jun 2008, Peter St. John wrote:
>
>  Programming a computer to play Go (an Asian strategy boardgame) has been
>> difficult; some people say it's proof that Go is better or harder than
>> chess, since computers can beat masters at chess but struggle at Go. (I
>> think that statistically a game of go is about equivalent to a two-game
>> match of chess; both games empty your brain quickly of course). My view is
>> that while go may be somewhat harder to reduce to tree-searching, the main
>> advantage of computer chess was an early start, e.g. von Neumann.
>>
>
> I thought that Go was combinatorially vastly, vastly more difficult than
> chess.  Both because of the extremely large number of move permutations
> that make it very difficult to follow trees and because Go is a
> fundamentally nonlocal game -- one can imagine a "perfect" Go strategy
> in which pieces are never played close to each other as the board
> gradually fills in with higher and higher still disconnected density,
> culminating in the winner completely unravelling the loser or
> precipitating out to win by a single small amount.  Yet nobody can even
> come close to playing that way -- most games start out that way for a
> while and then transform into local dogfights that are STILL often
> resolved by long range connections.
>
>  This article:
>> http://www.usgo.org/resources/downloads/CogApdx%20II-2.pdf
>> describes recent trends in computer Go and mentions a 32-node cluster, 8
>> cores per node. Apparently MPI parallelization is recent for them and they
>> are making good progress.
>>
>
> Interesting.  I'll have to look.  Last time I read up on this (in the
> context of a conversation with you, IIRC:-) nobody could make a computer
> go player that could beat even a very bad human player, where computers
> back to maybe 386's have been able to play chess well enough to win at
> least sometimes against weak humans (and win "often" against weak human
> players by now).  I suck at chess (but can still beat a lot of the
> people I -- rarely -- play) and modern computers can beat me pretty
> easily.  I suck at Go, too -- but I can't even find a BAD go player to
> run on a PC to try to get better.
>
>   rgb
>
>
>
>> Peter
>>
>> The game Go: http://en.wikipedia.org/wiki/Go_%28game%29
>> AGA (American Go Association): http://www.usgo.org
>>
>>
> --
> Robert G. Brown                            Phone(cell): 1-919-280-8443
> Duke University Physics Dept, Box 90305
> Durham, N.C. 27708-0305
> Web: http://www.phy.duke.edu/~rgb <http://www.phy.duke.edu/%7Ergb>
> Book of Lilith Website: http://www.phy.duke.edu/~rgb/Lilith/Lilith.php<http://www.phy.duke.edu/%7Ergb/Lilith/Lilith.php>
> Lulu Bookstore: http://stores.lulu.com/store.php?fAcctID=877977
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.beowulf.org/pipermail/beowulf/attachments/20080624/f89752a9/attachment.html>