[FOM] AI-completeness

[James Hirschorn]

On Sunday 29 April 2007 23:40, Timothy Y. Chow wrote:
> 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. 

To the contrary, I would think that this is demonstrably not AI-complete 
(assuming the criterion is publication in a high ranking mathematics 
journal).  

In my opinion the Continuum Hypothesis is a more feasible candidate.

> 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. 

I would venture a guess that this is true but they would rather not bother 
with the tedious error checking.

The consensus seems to be that a superior game of chess is played by a human 
grandmaster assisted by a computer. Correspondence chess grandmaster Arno 
Nickel recently defeated the world's strongest chess playing program 2-0, 
using a relatively weak personal 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).  

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

> The point of these suggestions seems 
> to be that chess is not yet demonstrably "solved"---

I believe a game is normally considered "solved" once its game theoretic value 
has been (demonstrably) determined.

> 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, 

The mathematical terminology for such an algorithm is a winning or nonlosing 
strategy.

> 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:

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.

>
> 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.

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.

James Hirschorn
>
> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom