[FOM] AI-completeness

[joeshipman@aol.com]

Tim,

Excellent post. I think that if any formally specified currently 
existing game is AI-complete, then Go is, and I agree with your 
intuition that games are not as hard as writing great novels.

However, "writing great novels" cannot be precisely defined either 
formally or informally. "Writing bestselling novels", however, *CAN* be 
given an informal but clear definition, and I suspect it is also 
AI-complete (because it is very hard even for humans to do).

In between Go and "writing bestselling novels", we can create some 
games which are not formally specified as Go is, but which are clear 
informally:

1) the Imitation Game on which Turing based his famous "Test" (This 
game is practically the definition of AI-complete!)

2) the Language Translation game: given a text in English, produce a 
corresponding Chinese text which is graded for accuracy and quality by 
a panel of humans who are erudite and fluent in both languages. Any 
computer which can score as well as a top-rank human translator at this 
on arbitrary texts has probably achieved AI-completeness.

3) The Alphabet Recognition game: given a picture that is supposed to 
represent a written text in the Roman alphabet, reconstruct the text 
(which may be gibberish, the point is to recognize the essence of 
individual letters amidst the infinite variety of possible fonts 
without semantic cues). Douglas Hofstadter has argued that this task is 
arbitrarily hard.

Note that the last two of these are really tasks, not games, which 
become games when the object is to outscore an opponent -- they are a 
restricted type of game though because the opponent's "moves" do not 
have any effect on one's own.

Now here is a candidate for a completely formally specified 2-player 
game which is AI-complete:

4) The Busy Beaver game: Construct a Turing machine of a specified size 
which runs the longest (compared with the other players' TMs) before 
halting, but which you can prove halts (the proof can be longer than 
the size of the TM, but it's part of the game to make the proof too so 
it will have to be a feasible-size proof).

The only problem here is that it is arbitrarily hard to decide who has 
won the game -- even though proofs that TM_1 and TM_2 eventually halt 
can be verified quickly, there may not be a feasible proof settling 
which of the two runs for longer before halting.

Here is another candidate which was actually popular in the Middle 
Ages, that is playable and easily umpired:

5) The equation-solving game: Each player constructs an equation with a 
feasible size solution, and whoever solves the other player's equation 
first wins. Both players should be given access to equivalent 
computational resources for this to be fair. I have not specified what 
kind of equation to use but multivariable diophantine equations ought 
to work (in the Middle Ages mathematicians challenged each other to 
find solutions expressible in radicals of single-variable polynomial 
equations with rational coefficients, but Galois showed that that is 
not AI-complete, and Susan Landau and Gary L. Miller found a polynomial 
time algorithm in 1983.)

If P is not equal to NP then it is conceivable that this game will 
always be drawn when experts play, because they won't be able to solve 
each others' equations in feasible time; can anyone modify this game to 
avoid this problem, or give an argument that it is unavoidable?

-- JS

________________________________________________________________________
AOL now offers free email to everyone.  Find out more about what's free 
from AOL at AOL.com.