Timothy Y. Chow
tchow at alum.mit.edu
Sun Apr 29 23:40:32 EDT 2007
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
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
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*
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?
More information about the FOM