What is the computational complexity of "solving" chess? 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
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.