[FOM] AI-completeness

[Timothy Y. Chow]

On Fri, 4 May 2007, James Hirschorn wrote:
> In my opinion the Continuum Hypothesis is a more feasible candidate.

What exactly is the problem here?  To determine the truth value of the 
continuum hypothesis?  Or what?

> Bobby Fischer concluded a long time ago that chess had been "played out" 
> in a sense that would preclude this.

It's not clear how much stock one should place in such pronouncements.  
Capablanca spoke of the "drawing death" of chess long before Fischer.  
They might be right, but just because they say so doesn't make it so.

> Checkers might make a better example. Its considered much easier to 
> solve than Othello even though it is a more complicated game (I don't 
> know why this is so), with some AI experts predicting a solution in the 
> near future.

It's possible that checkers makes a better parallel to chess, but I didn't 
want to talk about it because I personally don't know as much about 
checkers.  I know the Chinook-Tinsley story but I don't play checkers 
myself and hence have little intuition about it.

Checkers may be easier to solve than Othello simply because it is played 
on only 32 squares while Othello is played on 64 squares.  It may also be 
because checkers is more "dead drawn" than Othello is.  By "dead drawn" I 
mean roughly that not only is it drawn but that it's "easy" to draw, i.e., 
there are lots of ways to draw.  That makes it easier to prune the game 
tree.  In contrast, 8x8 Othello is probably drawn, but you have to be very 
careful to make sure that, for example, your allegedly drawn position is 
not actually a very narrow 31-33 victory for White.  The draw is more 
"delicate" than in checkers, it seems.  In fact, the very fact that 8x8 
Othello is probably a draw makes it harder to solve; if 8x8 Othello were, 
say, a win for White (as 6x6 Othello is) and all you cared about was 
whether it was a win for White and not what the actual score was (i.e., 
how many discs White could secure), then it would probably be easier to 
solve.

On the other hand, in Othello the board fills up as you play; this makes 
exhausting the endgame game tree easier.  So, a priori I wouldn't have 
been confident where to place my bet.

> I don't think end game play in chess is so chaotic as you described for 
> Othello. There is a whole end game theory for chess, and "knife-edge" 
> endings, like having checkmate in (no less than) 200 moves when there 
> are 2 queens and 1 pawn left, are I think more exceptional than the 
> rule.

I do not believe that this is true if you study the endgame tablebases.  
People had developed endgame theory prior to the large-scale computation 
of tablebases, but a significant amount of this theory was shown to be 
incorrect.  For example, K+Q vs. K+B+B (or K+N+N) was thought to be often 
drawn, whereas now we know that it is almost always a win for K+Q.  If you 
don't believe in the knife edge, you should look at K+R+R vs. K+R+N or 
K+Q+N vs. K+R+B+N.  There are many positions which are, for example, a win 
for the stronger side, but only after perfect play for several hundred 
moves, and on almost every move the slightest misstep by the stronger side 
leads to a draw and the slightest misstep by the weaker side shortens the 
win significantly.  The "reasons" for why the unique best move works and 
the others don't are completely inscrutable.  I would say that this is in 
fact typical, and not exceptional, for endgames where there is a small 
material imbalance between the two sides.

Even in cases where the endgame theory was worked out before computers 
(and was not later overturned), it wasn't easy to master.  Anyone who has 
made a serious effort to master K+R+P vs. K+R knows that very delicate 
positions can arise in practice, that can be handled perfectly only if 
you've memorized a lot of special positions and variations.

Having said that, I grant that it's possible that the initial position in 
chess is so "dead drawn" that these knife edges never arise and don't 
matter, if all you care about is the value of the game starting from the 
initial position.  So maybe, as you suggest, checkers is a better analogue 
to chess than Othello is.

Tim