[Beowulf] Go-playing machines

[Robert G. Brown]

On Tue, 24 Jun 2008, Vincent Diepeveen wrote:

> Go has a bigger branching factor than chess, as it starts with an empty board 
> of 19x19, versus chess a loaded board of 8x8.
>
> The first few moves in go decide the outcome of the game already, as the rest 
> is just a 'playout' of the first few moves. So what matters
> most is the first few moves in the game.

This is simply not correct.  Go is a highly nonlocal game in both space
on the game board and time.  Chess is (in contrast) relatively linear --
the restricted moves available to each piece and the ability to deduce
at least some relatively simple payoff functions make it much, much less
complex.  Sure, a "perfect chess game" is still quite complex, but its
complexity fits in its entirety in a tiny fraction of the space occupied
by Go.

> Reason why chessprograms play so well is simply money and popularity of the 
> game.

Again, no.  The reason is that the decision trees in chess are countable
by enough, big enough, fast enough, computers, and one can compute
objective functions on even a modest number of looks ahead that will
exceed what many people can do.  Go's are not.  I won't say they never
will be, but they won't be anytime soon even with help from Moore's law.
You might look at the comments here:

   http://en.wikipedia.org/wiki/Go_%28board_game%29#Computers_and_Go

Note that it is far more complex BOTH because the combinatorics are
vastly larger, where "vastly" is an understatement, and because crucial
tactical situations can be resolved by seemingly unrelated plays made
hundreds of turns earlier far away on the board.  Go also is very
difficult to tactically estimate -- one can play out seemingly balanced
tactical situations for forty or fifty plys before a tiny weakness in
one player's position -- or one of those distant pieces placed early in
the game -- causes their entire effort to "unravel" and turn into a
disaster.  That's almost twice the number of plys in an entire chess
game, and is still only the first third or so of the game.

If you or your friend disagree with this, well, feel free to edit the
wikipedia article(s) with examples that contradict it, but the
mathematics and difficulty of pruning the Go trees suggest that it
isn't.

    rgb

>
> Chess computers in the 80s and start 90s, used to export to 106 countries. I 
> remember talking about producing a dedicated chesscomputer,
> and usually 100000 of them get printed. A minimum of 20000 pieces is needed 
> to heat up the production line (Hong Kong, China).
>
> There is no go computers AFAIK, for simple reason that the only nation where 
> you can sell your product is Japan. The 3 main nations where
> go gets played is China, Korea, Japan. So only Japan you could sell some if 
> you have entrance to its very close market.
>
> In fact there is even a company that claims to have the rights on all human 
> go games.
>
> At my chat is someone, Gian-Carlo Pascutto, whose program Leela you can buy.
> It is as we speak the strongest commercial go program on planet earth that 
> you can buy.
> His engine focuses upon search, its knowlede is rather simplistic.
>
> He has a normal job just like you have one.
>
> So this is a sparetime written engine.
>
> Computerchess engines used to be fulltime work. When someone is jobless like 
> me, you again work for a few months fulltime at it.
> There is 500 chess engines to compete with or so.
>
> In go the competition is very limited, only recently more engines are there. 
> Most programmed by non-asian programmers.
> Not even from Asian decent.
>
> It's all about how much money you want to put in research. Would go have been 
> the game been played in 106 nations and chess in just 3 from which only 1 has 
> money and is a closed market, then we would be speaking now about a 
> computer-go world champion program and wondering what makes computer chess so 
> hard.
>
> In that case I would write then that if more money had been put at chess, 
> that those engines would be stronger than the go engines.
>
> Don't count at it that the big supercomputers make any chance in go, neither 
> in chess. The quality of the program is most important.
> As soon as you massively parallellize a strong engine, now *that* makes 
> sense.
>
> Vincent
>
> On Jun 24, 2008, at 6:20 PM, 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.
>> 
>> 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.
>> 
>> Peter
>> 
>> The game Go: http://en.wikipedia.org/wiki/Go_%28game%29
>> AGA (American Go Association): http://www.usgo.org
>> 
>> 
>> _______________________________________________
>> Beowulf mailing list, Beowulf at beowulf.org
>> To change your subscription (digest mode or unsubscribe) visit 
>> http://www.beowulf.org/mailman/listinfo/beowulf
>
> _______________________________________________
> Beowulf mailing list, Beowulf at beowulf.org
> To change your subscription (digest mode or unsubscribe) visit 
> http://www.beowulf.org/mailman/listinfo/beowulf

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