[Beowulf] Go-playing machines

[Robert G. Brown]

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