[FOM] AI-completeness
joeshipman@aol.com
joeshipman at aol.com
Mon Apr 30 16:37:11 EDT 2007
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.
More information about the FOM
mailing list