Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 tag because you can represent these games as trees, but if I'm abusing the tag please add something more appropriate

share|improve this question
3  
Questions about the complexity of chess have been rehashed in many places. The game tree has finite length, modulo the precise rules governing draws, but the game tree has very high branching factor so brute force solutions seem out of reach. To put it bluntly: the game tree has size something like $10^k$, for $k$ half-moves. I don't see a TCS question here? –  András Salamon May 13 '11 at 18:14
5  
Is it cheeky to point out that the complexity is $O(1)$ by the fifty move rule? –  Joe Fitzsimons May 13 '11 at 21:32
    
Seamus, cstheory's scope is research-level questions in tcs, please read the FAQ. You can use math.SE for non-research-level questions. –  Kaveh May 15 '11 at 7:19
    
there are some complexity-related questions in chess but as phrased this one isnt because of the finite game tree. this question is somewhat similar, can there be a perfect chess algorithm –  vzn May 9 '13 at 21:47
add comment

4 Answers

up vote 18 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Minor quibble: the maximum number of moves is more like 50 * (16 * 6 + 1) + 1. But then 16 * 6 of those are pawn moves, 16 of which are potentially drawn from 4 options, although one of those options cuts down the number of moves later... (Not to disagree with the basic point, which is sound. Curiously your estimate comes out at around 10^10^5, whereas Mathworld says that Hardy estimated it as 10^10^50. Wonder whether that's a bad transcription of his notes). –  Peter Taylor May 15 '11 at 8:01
    
@Peter My mistake, sorry. I've corrected the answer now. I'm not sure whether this was how the estimate in Mathworld was arrived at. If it simply counted legal arrangements of the board (ignoring the fifty move rule), it may have been much bigger. –  Joe Fitzsimons May 15 '11 at 19:25
    
Another quibble: you used an incorrect version of the fifty move rule. It should be "50 moves without a pawn move or a capture". The number of pieces on the board is of course monotonically decreasing during a game and the rule still allows a finite bound. Although the game is still finite without the fifty moves rule by the threefold repetition rule, which then yields a much larger bound. –  Olaf May 9 '13 at 6:52
    
Ah, yes. That increases the maximum number of moves by about a third. –  Joe Fitzsimons May 10 '13 at 6:58
    
You missed something about 50 move: after 50 move without pawn move and without any killed item, we have draw (the power of your calculation dramatically grows but still is constant). –  Saeed May 18 '13 at 9:31
show 1 more comment

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.

share|improve this answer
add comment

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

share|improve this answer
2  
Because of the rule that repeating a board configuration three times is a draw, the state of the game does not include only the current positions of the pieces, but all past board configurations as well. But whatever; a constant is a constant. –  JɛffE May 9 '13 at 5:16
    
It also needs castling rights, but it only needs the past 100 board configurations. $\hspace{.2 in}$ –  Ricky Demer May 10 '13 at 1:30
    
You seem to be sweeping a lot of the complexity into "and mark them as black win or white win". –  Joe Fitzsimons May 13 '13 at 9:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.