Complexity of Go

    Keywords: Theory

On the mathematical complexity of Go:

As of October 2007, Feng-Hsiung Hsu wrote of his thoughts on [ext] Cracking Go through a combination of "recursive null-move pruning", alpha-beta pruning, "method of analogy" and hardware improvements compared to the hardware used in Deep Blue. He estimates that "recursive null-move pruning" and alpha-beta pruning will reduce the branching factor to about the fourth root of the of the number of move choices.

See Also: [ext] Computer Go Bibliography


HarryWang OK, I cannot help it to notice there are no page in sensei here to discuss the mathematical nature of GO.

I copied this following part from [ext] http://en.wikipedia.org/wiki/Go_(board_game). I have no clue where they come up with these numbers. I hope someone can actually illustrate various math natures of Go on this page.

personally, I know that a un-pruned GO game tree is 361! = xxx × 10 ^ 71. Most GO games seems to end with less than 300 moves. so I guess the average GO game tree is 300! But how to prune the GA grame tree. I am facinated to know

from wiki: "It is commonly said that no game has ever been played twice. This may be true: On a 19×19 board, there are about 3^361×0.012 = 2.1×10^170 possible positions, most of which are the end result of about (120!)^2 = 4.5×10^397 different (no-capture) games, for a total of about 9.3×10^567 games. Allowing captures gives as many as 10^(7.49×10^48) possible games, most of which last for over 1.6×10^49 moves! (By contrast, the number of legal positions in chess is estimated to be between 10^43 and 10^50, and physicists estimate that there are not more than 10^90 protons in the entire universe.)"

HandOfPaper: An unpruned Go game tree could have more than 361! branches, since moves (but not boardstates) can be repeated: for example, in ko fights, or, more generally, after a capture of a group. Also, one fact which would automatically prune a Go tree is the existence of illegal moves, such as immediate ko recapture or group suicide. Finally, there are situations, like multiple ko, eternal ko, and eternal life, where optimal play goes on forever unless you use a superko rule.

Also, it is possible to exhibit more than (120!)^2 distinct no-capture games: Here I will refer to points as (m,n), where m and n are integers from 1 to 19. Suppose that White and Black agree beforehand that White will always place on points (m,n) where m>n and Black will always place on points where m<n (both players agree to abstain from points where m=n). Then each player gets (19^2-19)/2=171 points on which to place stones. In the first 6 moves, White and Black each make, in their respective corners, 6-stone live configurations. Suppose you fix the way this happens, so that we have only possibility for how the game gets to this point. Also, we assume that both players are not being stupid and not filling in the initial eyes of their 2-eyed groups. These groups take up (6 stones)+(2 eyes)=8 points on the board, so each player is left with 171-8=163 possible places for stones. If gameplay continues until each player has filled in all points of the portion of the board they originally agreed to (except for the 2 eyes of the initial group), then we get (163!)^2 possible no-capture games in this scenario, and this is significantly larger than (120!)^2 (of course, most of these involve horrible massive eye-filling and would characterize anyone actually carrying them out as far below 30 kyu...).


unkx80: Since the page title is also a common term in computer science, I shall also mention something about the computational power required for perfect computer Go players.

The game of Go on a general n by n board is a computationally difficult problem. It is known to be an EXPTIME-complete[1] problem, which means that it is very computationally expensive for a computer to solve any position perfectly. In fact, Go endgames is already known to be PSPACE-hard.

The implication is that there is are some go problems which are completely infeasible for computer Go programs to solve perfectly, particularly by using brute force searching.[2] Hence, programs for Go have to rely on heuristics, which gives imperfect answers to problems.

Even on the normal 19 by 19 board, which has 361 points, current computer Go players are still very weak compared to current computer chess (both Chinese and International) players. While International chess programs like X3D Fritz can draw with grandmasters like Garry Kasparov, current Go programs are probably not even amateur Dan strength.

HandOfPaper: Solving arbitrary Go positions is EXPTIME-complete. However, that does not immediately imply that a perfect, fast (in the polynomial time sense) computer Go player that works on arbitrary boards cannot exist. It may be possible that there exists a property C such that solving Go positions having property C is doable in polynomial time and that optimal play by at least one player from the empty initial position always results in positions with property C. I am not saying this is likely, but if someone wants to say that fast optimal computer Go is impossible because of the EXPTIME-completeness result, I would like to say that such reasoning has this gap in it, as far as I can see. If someone knows of an attempt to fill this gap, then I'd be interested in hearing it. It is not known whether PSPACE=P, so there may be a PSPACE-hard problem that is solvable in polynomial time. I am not saying this is likely either, but I am merely pointing out the difference between likely and proven.

BobHearn: Actually the mentioned EXPTIME-completeness result only applies for Japanese Rules. With the addition of the superko rule, as used e.g. in China and the US, not only does the EXPTIME-hardness result (lower bound) no longer hold, but the game might not even be solvable in exponential time at all (upper bound)! The only thing definitely known is that go with superko is at least PSPACE-hard. But it could be as hard as EXPSPACE-complete. That is, it might require an exponential amount of space (memory) to determine optimal play from a given position, rather than "merely" an exponential amount of time. See the Robson papers referenced [ext] here. Note that this problem (the complexity of go with superko) has been open for more than 20 years, and seems very difficult to resolve. There is some more discussion of this issue in my Ph.D. thesis, [ext] Games, Puzzles, and Computation.


[1] It is EXPTIME-complete under the simple ko rule. Deciding if a ladder works is PSPACE-hard. -- Rafael Caetano

[2] Rafael: Those complexity classes are about worst-case complexity. The complexity of the general problem is as high as the complexity of its worse specific instance. For example, the kind of ladder problems which require lots of time and space to solve are highly artificial, and probably a tiny fraction of all possible ladder problems. Still they are ladder problems, so the complexity of the general ladder problem is said to require lots of time and space.


See also:


Complexity of Go last edited by tromp on April 20, 2019 - 19:16
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library