[Beowulf] Go-playing machines

[Peter St. John]

RGB,
My hypothetical future Recursive Genetic Algorithm Go Player will crush your
Hypothetical Future NeuralNet Go Player!
Peter

On 6/24/08, Robert G. Brown <rgb at phy.duke.edu> wrote:
>
> On Tue, 24 Jun 2008, Peter St. John wrote:
>
> 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.
>>
>
> It makes sense to me.  It's in some sense more like humans play.  In
> fact, if one can come up with any (even very simple) "local" rules to
> semi-prune the tree, you can imagine an importance-sampling monte carlo
> algorithm.
>
> However, if I were going to try, it would be genetic algorithm all the
> way.  Don't explore trees exhaustively; too many of them.  Don't sample
> them (especially if you can't create a canonical weight to do importance
> sampling); too many of them.  Breed them.  There are still too many, but
> again, if one can generate ANY sort of fitness function, maybe one can
> get the N^3 and exponential growth of favorable possibilities that are
> like "making a decision".
>
> Fortunately, I'm not going to try.  Neural nets are much more fun.  And
> MIGHT be able to manage the complexity -- especially one built with a
> GA...;-)
>
>   rgb
>
>
>> 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
>>>
>>>
>>
> --
> 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
> Book of Lilith Website: http://www.phy.duke.edu/~rgb/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/20080625/94251d73/attachment.html>