What is the computational complexity of "solving" chess?

Question

The basic idea of backwards induction is to start with all the possible final positions of a game in which player X wins. So for chess, look at all the ways White can checkmate Black. Now work backwards to all the possible moves/positions that would allow White to move in to one of those positions. If White ever found herself in such a position she could win by moving to the relevant checkmating move. Now we work backwards another step and so on. Eventually we get back to all the possible first moves White could make. The point is, once we've done this, we know that we have White's best response to any move Black makes.

Recently (last five years or so) Checkers was "solved" in this way. Obviously Noughts and Crosses (what the colonials might call "Tic-Tac-Toe") has been solved for ages. At the very least since this xkcd but presumably long before.

So the question is: what factors does this sort of procedure depend on? The number of possible legal positions, presumably. But also perhaps the number of legal moves at any given node... And given this, how complex is this sort of problem?

Bonus question: how long before a $2000 PC can solve checkers in a day? Chess? Go? (Of course for this you also have to take into account increasing speed of home computers...)

I've added the graph-algorithms tag because you can represent these games as trees, but if I'm abusing the tag please add something more appropriate

Answer 1

As @Joe points out, chess is trivial to solve in $O(1)$ time using a lookup table. (An actual implementation of this algorithm would require a universe significantly larger than the one we live in, but this is a site for theoretical computer science. The size of the constant is irrelevant.)

There is obviously no canonical $n\times n$ generalization of chess, but several variants have been considered; their complexity depends on how the rules about moves without captures and repeating positions are generalized.

If a draw is declared after a polynomial number of capture-free moves, or after any position repeats a polynomial number of times, then any $n\times n$ chess game ends after a polynomial number of moves, so the problem is clearly in PSPACE. Storer proved that this variant is PSPACE-hard.

For the variant with no limits on repeated positions or capture-free moves, the number of legal $n\times n$ chess positions is exponential in $n$, so the problem is clearly in EXPTIME. Fraenkel and Lichtenstein proved that this variant is EXPTIME-hard.

Answer 2

This probably isn't a terribly useful answer, but I think it is worth pointing out that chess has a maximum number of moves, and hence there is a finite number of possible games. The fifty move rule allows either player to claim a draw if 50 or more moves take place without movement of a pawn. We can reasonably assume that this is always used, since if there is any objective measure of the strength of each players positions then the weaker one will claim the draw. Further, the rules of chess require that whenever a pawn is moved it advances one square towards the opponents side of the board (whether moving directly forward, or taking diagonally), and hence each pawn can move at most 6 times. As there are 16 pawns in total, this puts the maximum number of moves at $50\times (16 \times6 + 1) + 1 = 4851$. In each move, the player moves one of at most 16 pieces. For a pawn there are at most 3 moves, 14 for a rook, 8 for a knight, 14 for a bishop, 28 for a queen and 8 for a king, for a total of 132 possible moves. This gives an upper bound of $132^{4851}$ on the total number of chess games. So, while this is a truely enormous number (approx $2^{34172}$), it does mean that the complexity is trivially $O(1)$. On the other hand, with such a naive approach would take approximately fifty thousand years for the problem to become tractable, assuming Moore's law continued indefinitely.

Answer 3

There are actually a couple of different questions here: (a) how much computing power does it take to do tree search for games, and (b) what's the computational complexity of these problems? The best all-purpose resource for this sort of thing is probably the Wikipedia page on Game Complexity, but to go into a bit more detail:

For (a), there are a lot of different practical algorithms that come into play, but they all boil down to some form of the tree search you noted; the biggest optimization that's generally used for the tree search itself is known as Alpha-Beta, which prunes branches of the tree once it's known that they can't be better than the best option already discovered. This is useful for evaluating positions 'on the fly' for chess (particularly with smart heuristics for ordering moves), because there are good estimates of the 'value' of a position; it generally gets a lot worse when having to compute a precise result for a position just because those heuristics don't hold. In general, if the tree has depth $d$ and a branching factor of $b$, then alpha-beta pruning cuts the number of nodes that need to be examined to roughly $b^{d/2}$ (from the naive value of $b^d$) - but even with this optimization, that's obviously a huge factor; consider that for the opening position of chess, $d$ is on the order of 60-100, and the branching factor $b$ is estimated to be in the range of 30-40.

In practice, pure tree search is supplemented by a bottom-up dictionary; for instance, the results of all 6-piece chess endgames are known, and many 7-piece endgames have been analyzed (see http://en.wikipedia.org/wiki/Endgame_tablebase), so the result of a game branch can be looked up in the 'dictionary' (a huge database of positions) once the position has been reduced to few enough pieces, shortcutting a lot of extra tree search that would otherwise be needed. This is what was done with checkers - databases were built up of all endgames with sufficiently few pieces, then extended to add more pieces and more, until the results of all 10-piece endgames were known; then tree search was used from the initial position, and essentially the two met in the middle.

Beyond these practical approaches, though, there's the (b) side of the question: what is the computational complexity of these sorts of problems? Abstractly, most problems of this ilk tend to fall into a couple of categories; they're either PSPACE-complete - which roughly means 'if you can solve this, you can solve any problem that takes polynomially much space' - or EXPTIME-complete (which roughly means 'if you can solve this, you can solve any problem that takes exponentially much time'), depending on how long the game can last; again, the Wikipedia page on EXPTIME-completeness has a pretty good discussion of the issues involved and what differentiates different games on this front.

Answer 4

These estimates are way too high.

You're focused on branching based on legal moves. This makes lots of sense if you are trying to make a fast chess computer, but it's not how you would write a program to "solve" chess.

There <<<<< 13^64 possible game states in chess. Each square can only contain one of the chess pieces or nothing. You can iterate though them all and mark them as black win or white win in no more than 2^256 or so operations.

A more realistic guess of the number of reasonably achievable game states is around 2^100