Solving Checkers and EXPTIME? In Lance Fortnow's book, The Golden Ticket: P, NP, and the Search for the Impossible, he writes "Computer scientists generally believe that chess, checkers, Othello, and Go are all much harder than any NP problem" (64).

I understand that checkers (as well as the others) are all EXPTIME-Complete, and thus "harder" than an NP-Complete problem, but I don't understand exactly what he means by "harder". 

I would assume he means harder to solve, but checkers is a solved game (to force a draw). Am I just not understanding why checkers is categorized as an EXPTIME-Complete game?

In Robson's paper, "N x N Checkers is Exptime Complete", he writes in the Abstract: "The game of Checkers can easily be generalized to be played on an N by N board and the complexity of deciding questions about positions regarded as a function of N. This paper considers mainly the question of whether a particular player can force a win from a given position and also the question of what is the best move in a given position. Each of these problems is shown to be complete in exponential time". 

Does that mean that the problem of evaluating a given move in checkers is EXPTIME-Complete, but not the problem of "solving" the game?
The solution of checkers by Schaeffer and his colleagues is for the $8\times 8$ version of the game.  Robson and Fortnow refer to a family of games played by the same rules on $N \times N$ boards with different values of $N$.

An $N \times N$ board can be populated by men and kings in $5^{N^2/2}$ different ways.  This is because there are $N^2/2$ squares where pieces may be placed.  Each of these squares may be in one of five states.)  If we add one bit of state to track which player plays next, we have $2\cdot5^{N^2/2}$ configurations, which for $N=8$ amounts to $46566128730773925781250$.  

Many of these configurations are not reachable from the initial configuration, but that's not important.  One can, in principle, draw a graph with a vertex for each configuration, join two vertices with a directed edge if there is a legal move that turns the source configuration into the destination and analyze this graph for a strategy.  

Starting from the configurations in which one player has won the game, one can work backwards and identify all other positions from which that player can force a visit of one of its winning positions.  The process can be carried out in time polynomial in the size of the graph.  Once this is done for both players, each configuration is winning for black, winning for white, or drawn.  This is what Robson alludes to with "the proof that the language is in Exptime is simple and is omitted."

While one should not discount the practical difficulty of analyzing the $8 \times 8$ version of the game in a reasonable amount of time, the conclusion that perfect play by both players from the initial position leads to a draw applies to that board size.  In that light, $N \times N$ checkers is not a solved game.  Yes, we have an algorithm that would give us the answer, but it takes impractically long for $N &gt; 8$.

Contrast this situation with the game of nim or with a game I take from Honsberger's More Mathematical Morsels, p. 6.


  From a row of $n \geq 12$ consecutive positive integers, two players, first $A$ and then $B$, take turns crossing out the integer of their choice until there are just two numbers left, $a$, and $b$.  $A$ wins if $a$ and $b$ are relatively prime, and $B$ otherwise.  If $n$ is odd, would you choose to play first or second?  What if $n$ is even?


It turns out that it's easy to analyze the initial configuration to decide which player has a winning strategy and the strategies are simply described.    The amount of work required to analyze an initial position is polynomial in $n$.  (For nim, let $n$ be the total number of counters; it's easy to analyze any position.)

We could, in principle, draw a graph with all possible configurations as vertices and follow the same approach as in $N \times N$ checkers.  For the game from Honsberger's book, a configuration would be a subset of the given set of integers with at least two elements, and a turn value.  However, there are much faster methods, while Robson's proof implies that there is no deterministic polynomial time algorithm to decide whether an arbitrary position of $N \times N$ checkers is winning for a player and we don't know of a fast way to assess the initial position.
The solution of checkers by Schaeffer and his colleagues is for the $8\times 8$ version of the game.  Robson and Fortnow refer to a family of games played by the same rules on $N \times N$ boards with different values of $N$.

An $N \times N$ board can be populated by men and kings in $5^{N^2/2}$ different ways.  This is because there are $N^2/2$ squares where pieces may be placed.  Each of these squares may be in one of five states.)  If we add one bit of state to track which player plays next, we have $2\cdot5^{N^2/2}$ configurations, which for $N=8$ amounts to $46566128730773925781250$.  

Many of these configurations are not reachable from the initial configuration, but that's not important.  One can, in principle, draw a graph with a vertex for each configuration, join two vertices with a directed edge if there is a legal move that turns the source configuration into the destination and analyze this graph for a strategy.  

Starting from the configurations in which one player has won the game, one can work backwards and identify all other positions from which that player can force a visit of one of its winning positions.  The process can be carried out in time polynomial in the size of the graph.  Once this is done for both players, each configuration is winning for black, winning for white, or drawn.  This is what Robson alludes to with "the proof that the language is in Exptime is simple and is omitted."

While one should not discount the practical difficulty of analyzing the $8 \times 8$ version of the game in a reasonable amount of time, the conclusion that perfect play by both players from the initial position leads to a draw applies to that board size.  In that light, $N \times N$ checkers is not a solved game.  Yes, we have an algorithm that would give us the answer, but it takes impractically long for $N &gt; 8$.

Contrast this situation with the game of nim or with a game I take from Honsberger's More Mathematical Morsels, p. 6.


  From a row of $n \geq 12$ consecutive positive integers, two players, first $A$ and then $B$, take turns crossing out the integer of their choice until there are just two numbers left, $a$, and $b$.  $A$ wins if $a$ and $b$ are relatively prime, and $B$ otherwise.  If $n$ is odd, would you choose to play first or second?  What if $n$ is even?


It turns out that it's easy to analyze the initial configuration to decide which player has a winning strategy and the strategies are simply described.    The amount of work required to analyze an initial position is polynomial in $n$.  (For nim, let $n$ be the total number of counters; it's easy to analyze any position.)

We could, in principle, draw a graph with all possible configurations as vertices and follow the same approach as in $N \times N$ checkers.  For the game from Honsberger's book, a configuration would be a subset of the given set of integers with at least two elements, and a turn value.  However, there are much faster methods, while Robson's proof implies that there is no deterministic polynomial time algorithm to decide whether an arbitrary position of $N \times N$ checkers is winning for a player and we don't know of a fast way to assess the initial position.