Robotics Reference
In-Depth Information
high level. The reasons relate mainly to the enormous size of the game
tree. The normal Go board has 19x19 lines,
27
with play taking place on
the intersections, so at the the start of the game there are 361 possible
moves that can be made by the first player, compared to 20 at Chess.
Why Is Programming Go So Difficult?
By comparing Chess and Go we can see how immense the Go tree be-
comes after only a few half-moves. In Chess, with an average of approx-
imately 37 moves to consider, the number of leaf positions on a tree of
depth 20 is approximately 2.8 x 10
31
. In Go, with an average of approx-
imately 240 moves to consider in a position, the tree for a 20-ply search
would encompass approximately 4 x 10
47
leaf positions. In other words,
a Go tree of depth 20 will have approximately 14,000,000,000,000,000
times as many leaf positions as a Chess tree of the same depth.
28
Further-
more, a winning strategy in the game of Go requires a more long-range
insight than a successful strategy in Chess, and it is therefore most un-
likely that even if a Go program could search to 20-ply, it would be able
to play the game at the level of the strongest human players.
40 Years of Computer Go—How Much Progress?
The first writings on programming the game of Go appeared in the early-
to-mid 1960s, but because the game is so much more difficult than Chess
to program, it did not attract much serious interest from programmers
until 1984, when a program called Nemesis took part in the Eastern
U.S.A. Go Championships (for humans) and was rated at 20-Kyu.
29
27
Beginners can learn the basics on a 9 x 9 board, a format that has been gaining in popularity in
recent years as a game in its own right.
28
Another way to put the size of the Go programming problem into perspective is to compare the
number of possible Go positions, estimated at 10
170
, with the number of possible Chess positions,
estimated at 10
44
, and that for Checkers (10
20
).WhilesolvingthegameofCheckersmaywellbe
possible in the first decade of the twenty-first century, through the creation of a database containing
every possible Checkers position, to do the same for Chess would require the power and memory
sizes of today's computers to increase by a factor of 1,000,000,000,000,000,000,000,000, even with-
out allowing for the fact that more memory is required to store a Chess position than a Checkers
one. And for the next jump, from a complete database for Chess to one for Go, add another 126
zeros to appreciate the magnitude of the problem.
29
The Go ranking system requires some explanation, to say the least, and this explanation is
subject to variations between some countries. The ranks start at about 30-Kyu (a complete beginner)
and go down to 1-Kyu as a player gets stronger. After 1-Kyu, a player becomes 1-Dan, and from there
the ranks ascend to 9-Dan. A few Asian countries (China, Japan, Korea, Taiwan) have professional
ranks as well as amateur ranks. The professional ranks in Japan and Korea start at 1-Dan and go up
to 9-Dan. But these ranks are not on the same scale as the amateur Dans. A 1-Dan professional is
roughly the same strength as a 7-Dan amateur.
