[FOM] AI-completeness

[Timothy Y. Chow]

Not long ago, Joe Shipman introduced me to the imprecise but suggestive 
term "AI-complete."  I suppose different people may define this term 
differently, but in my mind, a problem is AI-complete if the methods used 
to produce an entity that solves the problem can be used to produce an 
entity that solves *any* problem requiring "intelligence."  (Notice that 
this is slightly different from the usual notion of reduction; the entity 
that solves problem 1 may not be directly usable to solve problem 2, but 
the methods used to produce the first entity should carry over to produce 
an appropriate entity for problem 2.)

It occurred to me that the concept of AI-completeness might shed some 
light on the debate about chess that took place on FOM some time ago.

But first, are there any examples of AI-complete problems?  I do not 
expect any agreement on this question, but perhaps a defensible choice 
would be:

1. Writing great novels is AI-complete.

More relevant to FOM but somewhat more controversial, because the domain 
is (seemingly) more circumscribed, would be the following claim:

2. Producing first-rate, original mathematics is AI-complete.

Let's accept 2 for the sake of argument.  In contrast, it is obviously 
false that:

3. Tic-tac-toe is AI-complete.

For we know how to create something that can solve tic-tac-toe, and the 
methods for doing so leave us with no clue how to create something that 
can produce first-rate, original mathematics.  Thus 3 is *demonstrably* 
false.  Now let us consider:

4. Chess is AI-complete.

I doubt that anyone would defend 4, but is 4 *demonstrably* false?  
Harvey Friedman has made remarks about chess that I construe as suggesting 
that 4 is not yet *demonstrably* false.  For example, he has suggested 
(paraphrasing) that a team of grandmasters playing at postal chess time 
controls can easily beat any chess computer.  He has even suggested 
(paraphrasing again) that during the next century, someone may find a 
decisive new idea in chess that will allow him or her to defeat 
systematically those not in possession of the new idea (including, 
naturally, anybody playing in 2007).  The point of these suggestions seems 
to be that chess is not yet demonstrably "solved"---or perhaps "dead" is a 
better word since we're not talking about solving chess in the strong 
sense of a practical implementation of God's algorithm, but about 
producing an entity that can match the performance of our most intelligent 
efforts at chess.

I take the point about grandmasters playing postal chess, and so I do not 
believe that chess is quite dead yet, but I do believe that it will not 
take any significant new ideas to kill it.  In particular I do not believe 
in the decisive-new-idea scenario.  I base this partly on the analogies 
between chess and Othello.  I venture to say that it is *demonstrably* 
false that:

5. Othello is AI-complete.

Since Othello strategy is not very widely known, I will say a few words 
about it.  There are certainly concepts in Othello that will allow a 
player with a mastery of those concepts to crush anyone who does not grasp 
those concepts.  Mobility is perhaps the most dramatic example.  Someone 
who has not studied Othello seriously may still quickly grasp the 
importance of seizing corners, and may fancy himself a good Othello 
player, but he probably does not understand the importance of mobility 
(i.e., ensuring that he has a lot of moves to choose from while limiting 
the number of moves that his opponent has).  As such, he is easily 
defeated by a moderately good player who understands mobility.  It 
typically takes only about 5 or 6 moves per player to obtain a totally 
winning position against someone who doesn't understand mobility.

There are several other concepts in Othello that are like mobility in this 
regard, but do we have reason to be optimistic that more such concepts 
will continue to be found in the future?  I would say no.  Computers now 
are so strong that they can easily defeat human players at any time 
control.  They have not totally exhausted the game tree yet but in some 
sense they are close.  As they got better, some phenomena emerged, in 
particular the "chaotic" nature of endgame play.  That is, closely 
contested games would often terminate in endgames in which each player had 
to walk a tightrope, and the correct move had no intelligible reason for 
being correct other than that it worked.  The chances of finding some 
concept that could "override" such combinatorially complex knife-edges is 
extremely remote.  Thus when computers got powerful enough, they needed 
only a relatively small number of conceptual ideas to surpass humans.

Chess endgame tablebases reveal chaos that is similar to that of Othello 
endgames.  Four-piece endgames are still largely intelligible, but nearly 
all six-piece endgames have now been solved and there is no prospect of 
making any sense of the more delicately balanced endgames.  Now, it's true 
that this is a long way from the 32-piece endgame that we call the 
"initial position."  But the trajectory is awfully similar to that of 
Othello and we know how that one turned out.

For those who are unconvinced and still want to side with Friedman, I 
would still recommend giving up on chess and instead arguing for:

6. Go is AI-complete.

The best computer go programs are still hopelessly bad, and it does not 
seem that the techniques that worked so well in chess will work well in 
go.  Moreover, although top go players claim to know with a fair degree of 
confidence what the "value" of a game is (i.e., how many stones Black 
should come out ahead given perfect play), I don't trust them.  
Theoretical knowledge in go is still at such a rudimentary level that the 
decisive-idea scenario is much more plausible in go than in chess.

Nevertheless, I personally don't believe that 6 is true.  In fact, I am 
tempted to go out on a limb and conjecture that:

*** No two-player strategy game that is "humanly playable" (in the
    sense that go, chess, Othello, checkers, etc., are humanly playable
    because the rules are such that the course of a game can be followed
    tolerably well by a human) is AI-complete.

This might seem surprising because ostensibly chess and go belong to 
higher computational complexity classes than theorem-proving (PSPACE and 
NP respectively, once you impose some kind of size bound).  Can someone 
disprove *** by concocting a game that is not so hard to play but that is 
hard to master---as hard as producing first-rate, original mathematics?  
Alternatively, can someone devise a "ladder" of increasingly challenging 
games, so that if and when go is "pronounced dead," AI theorists will know 
what to work on next?

Tim