[Beowulf] Go-playing machines
Vincent Diepeveen
diep at xs4all.nl
Tue Jun 24 21:10:21 PDT 2008
On Jun 25, 2008, at 4:15 AM, Robert G. Brown wrote:
> 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.
>
In fact it is the opposite: Go has more local effects than Chess.
This is empirically provable by the fact that you can safely prune in
a hard manner in search moves in Go - the same is not possible in
chess at all.
In fact some of the top programs just below the level of Leela even
today still prune in computer go already at the root. The same in
computer chess
would result in a player that is *real* weak. In fact weaker than the
go programs in question doing it.
Historically Go software (think of the old handtalk) consisted out of
a global search and a fast assembler local search.
In computerchess this idea was abandonned around end of 70s and
exchanged for a global search.
If you think about it, it makes sense. Just do a full factorization -
GCD of {Chess,GO}, then it factors out that the nonshared factor is
that in
chess all pieces can move, whereas in Go once you make a move
somewhere, it will keep there large areas. So for the only thing that
really
matters in computer go - the dead and alive evaluation - you can
nearly local figure this out. That's exactly what software used to do.
>> 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:
>
A few years ago a few chessprogrammers switched to computer-go.
See what has been achieved last few years. A huge increase in
playstrength.
When i spoke to some computer-go authors a few years ago,
they all made real fundamental mistakes in search.
> 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
What matters for progress is how many brilliant guys are interested
in building a competing software engine, and put fulltime work in it,
*that* progresses a field.
In computer-go this incentive is not there simply. The huge easy
money that was there to win in the 80s and 90s in computer-chess,
has caused a big number of real brilliant minds to be busy with the
problem. That amount gets less and less now, which is sad in itself.
If we consider that all ideas in computer go now get completely
dominated by remnants left over from computer chess,
in fact ex-computer chess authors, not a single algorithm been
invented in China, Japan nor Korea that kicks butt for computer-go,
then obviously the point is easy to prove.
What i foresee in computer-go is that the field will keep get
dominated for the coming years by authors from Western Europe and USA.
If you realize how many people live in those countries, Japan, China
and Korea, that is in itself an interesting observation.
End this year there is a computer-olympiads, so both world
championship computer chess and go in China, Beijing.
It is very easy in such events, which yearly happen, to speak to the
different authors.
It is very difficult to motivate someone to start writing a go engine
if he doesn't even know how to make a ton of money with it.
Out of respect for authors i won't quote you the number of copies of
computer-go programs sold, but if you compare that with just
2 chess interfaces that sold each millions and millions of copies
(just chessmaster already 4 million copies), and that this was
already long after the decline of income from dedicated
chesscomputers (as you can't copy those easily!) which were exported
to 106 nations and manufacturers made hundreds of millions a year,
just on a game that in itself has very few fanatic practioners,
and a potential of "only" 200 million people when the Chinese get not
counted (as chess is so similar in itself to chinese chess,
and the huge step they make there now to play chess means that
another half billion people will know the chess rules by now);
compare that with computer-go which never sold really well.
If there is 1 product on a console that sold a 100k copies one day
that is already *really* a lot, and this only and only in Japan,
whereas the current top programs *hardly* sell a copy to Japan.
Economy gets driven by sales; if economy demands a better product, it
will be there.
I'd argue that the top go programs would be professional dan level by
now when authors would be able to fulltime work on those programs
and have a lot of competition. AFAIK not a single computer-go author
works fulltime on his engine as of now (not to confuse with GUI that
sells).
> 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
>
If you realize how much effort has been put in chess to make kick
butt evaluation functions,
and slowly by now people learn how to do it. None of those techniques
has been applied yet to
computer go. All that happens very slowly now. Of course within 10
years usually things leak
from computer chess to computer go. That's how things happen.
> tactical situations for forty or fifty plys before a tiny weakness in
There are clear estimates on the tactical depth of chess and go.
In computer-chess the average depth for a trick is about 12 ply for
'advanced' level.
Say 'national master level' in USA.
Tricks at my level usually are within that depth also, and the more
advanced tricks
are usually less than 20 ply.
About a ply or 8 you get 'for free', as simple extensions can extend
you that line.
So todays chess software with their ultimate thin searches, see those
tricks at around 16 ply.
In computer-go, the deepest tactics is about 30 ply. About 20 ply out
of that is totally forced moves.
Right now the thin searches in computer-go are a 1 to 1 match nearly
with computerchess.
That's weird in itself. How to extend they slowly figure out, because
the authors in question are real weak in computer-go.
Compare with chess where even PHD's have been achieved by persons
just on "how to extend?".
None of all that in computer-go.
I'd argue that if you get selectively about 20 ply deep in computer-
go, that a good evaluation function and good computer-go
driven extensions will get the engine in itself to the same level
like in computerchess; as soon as you remove the openingsbook of
todays top chess programs, they still look like beginners in the eye
of titled chessplayers.
Go has a huge historic disadvantage there; go games hardly ever get
written down on paper.
Chess has a 100 years advantage in the opening there. Or some
trainers will argue 50 years advantage,
as honor, glory and not being creative, and dying just for not
admitting you were wrong,
was before world war 2 real normal in chess; short after world war 2
that all changed.
Go is such a local Asian game, as a result it is totally impossible
if you do not speak Mandarin nor one of the Japanese languages,
to get access to go knowledge ready to implement in your go program.
In chess this has all been much
easier for authors. This problem will keep there.
Working indirectly via translation using a go player is tough too;
not so long ago i had asked a Polish girl to translate a small text
where a Polish
chess author wrote down some algorithmic ideas he had. I lost big
time there again as it made zero sense the pseudo-C code
versus the translated text. The Polish programmer posted a day later
the pseudo-C code into an English forum and it appeared
the translation was total wrong. Not even a little, just completely.
That confusion is there still in the go world.
The culture of China and Japan and Korea causes Go to be at the state
of where Chess was before world war 2.
Like here i have a book from a 9-dan go. The idea being: "attack your
enemy where he is strongest".
Just to be sure i contacted a few strong go players whether this is
true. They confirmed my feeling that this lemma is total wrong.
Punished bigtime also in world war 1. In English there is this
saying: "over the top" derived from that type of warfare. (getting
over the
top out of a trench straight into the machine guns).
Basically that is not helping computer go much either.
When busy with a go program end of 90s, I concluded that only with a
good go player next to me, i would make a chance of
writing a good go program, as the start of the game where in Go
having a book doesn't help much, is requiring some positional knowledge.
In computerchess we cover up for idiocy of programs there by a book,
something that is hard in go.
All that makes it of course extra surprising that there is no strong
Chinese/Korean/Japanese go programs at this moment that make
any chance against programs from here. If i draw a circle from here
with a 300 miles radius, i have a big number of world top go engines,
under which the number 1 and number 2. Perhaps even the top 3.
> 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.
>
See above for correct calculation.
> 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.
>
See above for disproof of that.
Vincent
> 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
>
More information about the Beowulf
mailing list