[Beowulf] Go-playing machines

[Robert G. Brown]

On Wed, 25 Jun 2008, Peter St. John wrote:

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

Will not!  Hypothetically, of course...;-)

    rgb

> 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
>>
>

-- 
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