[Beowulf] Go-playing machines

[Robert G. Brown]

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
Book of Lilith Website: http://www.phy.duke.edu/~rgb/Lilith/Lilith.php
Lulu Bookstore: http://stores.lulu.com/store.php?fAcctID=877977