Tuesday, January 25, 2011

Computational Complexity of Games

At BIRS this year, the game everyone was interested in was Go.

I guess it's hard to compete with that! Aside from Go, one of the big features was NoGo. We had the first ever NoGo world tournament, both for humans and computers. After those tournaments were over, Fan Xie, the reigning human champion, battled Bob Hearn's champion NoGo-playing program. When presented with a new game like NoGo, as a computer scientist I'm always interested in the computational complexity: how hard is it to determine which player has a winning move? How long would it take a computer program to figure this out?

For some games, we have a bad (or good, depending on how you see it) answer: a lot. For Chess, for example, an algorithm that can evaluate the "winnability" of every game requires an exponential number of steps in the worst case. When I say "exponential", I mean, "exponential in the amount of information needed to describe the game board". Thus, if I look at all Chess boards that can be described using 1,000,000 bits of information, some of those require around


steps to figure out who is going to win where a is some constant greater than 1. This is not a feasible amount of time even for computers to have. As the boards get bigger, the number of steps increases by a multiplicative factor of a. We say that these problems are in the class EXPTIME because they take an exponential amount of time. (Figuring out who wins a game of Go is also one of these problems.) To be more general, we also include problems which can be solved in less time. Thus, the "complexity class" EXPTIME is the set of all problems which can be solved in an exponential amount of time (or less).

In general, if you want to figure out who wins a game by just trying all the options, this method usually takes an exponential amount of time because there are an exponential number of scenarios to reach the end of the game which must be tested.

However, for some games, the player with a winning strategy can be figured out really quickly! In the game Nim, for example, there is a fast procedure ("trick") to figure out whether the next player can win. This can be done in a polynomial amount of time, meaning there is a polynomial function that describes the number of steps needed for a computer to determine who has a winning strategy, again in terms of the size of the information needed to describe the game state. Although polynomials can have large exponents, for any one given polynomial, that exponent remains constant. We say that problems that be answered in a polynomial amount of time are in the complexity class P. Since these are both sets, and anything that can be solved in exponential time can also be solved in polynomial time, we know that P is a subset of EXP-TIME and that the two are not equal.

For some games, we don't know how long the fastest algorithm to determine winnability takes. Sometimes we describe these in terms of resources other than time. The complexity class PSPACE is the set of problems which can be solved with a polynomial amount of "space" meaning a polynomial amount of room to keep a record of important information in the algorithm. The space can be reused; erasing is allowed! Imagine that instead of restricting the amount of time you have to take a test, you are instead restricted by the amount of scrap paper you are given to do your calculations. It has been shown that P is a subset of PSPACE, which is in turn a subset of EXPTIME. It is not known whether either is equal to PSPACE (obviously both cannot be).

We can, however, say that there are some games that REQUIRE a polynomial amount of space to solve, and are thus among the hardest problems in PSPACE. These are known as PSPACE-complete. We show that a game (or any sort of computational problem) is PSPACE-complete by showing two things:
  • The game is in PSPACE
  • Any other problem in PSPACE can be efficiently rewritten as an equivalent instance of this game. (Known as hardness. Proving this means the game is PSPACE-hard.)
The notion of completeness works for any complexity class. Thus, for some class XXXXX, proving that a problem is in XXXXX and is XXXXX-hard means that the problem is XXXXX-complete. Chess, for example, is known to require and exponential amount of time because it has been shown to be EXPTIME-complete.

To show the second part (hardness) for a game, Y, means starting with any other PSPACE-complete game, X, and showing that any instance of X can be rewritten as Y where the next player wins Y exactly when the next player would win X. This is known as "finding a reduction" or "reducing X to Y". This is where the fun is! Check out this game table to see some known complexity results for games.

Why bother to show that a game is PSPACE-complete? Although we don't know whether P = PSPACE, it is likely that the two are not equal. Solutions to problems are generally considered "efficient" if there is a polynomial-time algorithm, so then PSPACE-complete problems cannot be solved "efficiently".

This post has gotten long, but I realized I should explain a bit more about computational complexity before blundering forward into some complexity results from BIRS. Next week I will talk more about that, and especially how it relates to NoGo.

I'm sure I left lots out! Please help me out in the comments!


  1. I'm curious about your entries for Go. You list Go with ko as EXPTIME-complete, and Go without ko as PSPACE-hard, in EXPTIME. It's true that the EXPTIME-completeness proof breaks without ko.

    But I think the relevant distinction is Japanese rules (no immediate ko retake), vs. rules that use superko (no recreating any previous board position), such as Chinese (sort of), or AGA. Robson's EXPTIME-completess proof assumes Japanese rules. With superko, to the best of my knowledge nobody has shown the problem is in EXPTIME. Robson speculated it could be EXPSPACE-complete -- though it could be as easy as PSPACE! I have heard that Robson now believes it is in EXPTIME, but I don't know of any proof. The idea is this: if all dynamical state is encoded in kos, as it is in Robson's EXPTIME-hardness proof, then the problem is indeed in EXPTIME, because then it's an instance of undirected vertex Geography, which is polynomial. In this case it's polynomial in the board configuration space, which is exponential in the problem size. However, to me it seems that there is no reason, in principle, that gadgets couldn't be built that used more than kos to represent state (e.g., by using captures of more than a single piece). But this is very difficult to do.

  2. Bob,

    thanks so much for checking this out! I am definitely a bit confused as to the different Go variants and how they are played. This kind of information is excellent!

    How would you describe the most common variants? Are these Japanese/ko, Chinese and AGA? If so, am I correct in understanding that the complexity when using ko is known to be EXPTIME-complete? It sounds like the other two have not been completely nailed down. Do these both use the superko rule? Are these at least known to be PSPACE-hard?

    If the two superko rule sets are different, which one is Robson specifically commenting about?

    Thanks for looking closely at this and alerting me to this inconsistency, Bob! I really hate making these kinds of mistakes and definitely want to improve the table!

  3. All Go variants have a ko rule, forbidding immediately recreating the previous board position. Some rulesets also have a "superko" rule, forbidding recreating *any* previous board position. See http://www.britgo.org/rules/compare.html#rept, and http://senseis.xmp.net/?Ko.

    Robson's EXPTIME-completeness result only applies to Japanese rules; the gadgets break if a superko rule is used. There are a few different types of superko rule, but likely it would not matter which was used, from a complexity perspective. (Whether Chinese rules count as using superko is actually a bit of a matter of some debate.)

    All rulesets of Go are PSPACE-hard and EXPSPACE-easy. Beyond that, all that is known is Robson's result for Japanese rules.

  4. ... actually, Olivier Teytaud speculates that a different decision question (can one side with with probability greater than a specified rational), for phantom-Go (go played blindfold), could be 3EXPTIME-complete.

    And I have conjectured that the standard decision question (does one side have a guaranteed win) for Rengo Kriegspiel (team blindfold Go) is undecidable.

  5. Super helpful! Thank you, Bob!

    I have updated the table (not including the blindfold versions, sorry... does this even count as combinatorial?). Let me know if there's anything that continues to irk you!

    I'm surprised that some places list Chinese as a type of rules, while other don't. Thanks for the excellent links!