[FOM] AI Challenge

[Harvey Friedman]

Around March 1, 2017, I formulated a challenge to the AI community in
light of the recent breakthroughs in and around "deep learning".

But replace mathematicians?

Here is my AI Challenge.

In order to not get horribly slaughtered by humans in the game of NIM,
the computer is going to have to play NIM perfectly -- since humans
have figured out a nice winning strategy for the two person zero sum
NIM.

Can a computer figure out how to play NIM perfectly? Of course, it is
not being given the winning strategy for NIM.

So there is the question of just what information we want to give the
computer before we ask it to play NIM.

I would say that there is some basic infrastructure of game theory
that it should be given - i.e., where it knows about game trees.

To behave like a real mathematician discovering the winning strategy
for NIM, we can't really give the computer an enormous number of games
where one side is playing perfectly and the other side putting up a
lot of resistance - (not clear what that should mean for NIM, an
interesting question maybe). HOWEVER, maybe we should explore what
happens when the computer is given such a huge database of games. It
will of course on its own generate its own games, but not with one
player playing perfectly (until of course it figures out what is
really going on, which is the issue).

OK, let's do some toy examples. Let's look at some really trivial games.

1. NIM with exactly two rows only. I assume the technology is more
than adequate to get the computer to play this perfectly, where it
generates its own game trees from scratch. It might be interesting to
develop some nice theory about how to discover the winning strategy by
computer here.

2. Another trivial game where I think the computer should not have
much of a problem given very little information is NIM with one row,
but where players are only allowed to take 1 or 2 stones away. Again,
would be interesting, probably, to have a clean theory of how the
winning strategy is discovered easily by computer.

Of course, we can really jump the shark by asking AI to find proofs of, e.g.,

A. n^2 = 2m^2 has no solution in integers.
B. For all integers n there is a prime > n.

It seems like AI is progressing no nicely because it finds ways of
doing things that are apparently not the way we do them. (This can be
argued - perhaps according to some the deep learning is in some
important ways a kind of primitive imitation of some important ways we
do things). So the natural question is: what kind of things force AI
to do the way we do them? It apparently has found different ways to
play checkers, chess, go, and these different ways are better than the
ways we play them.

So you may be able to clean the inside of my house, paint the outside
of my house, go get the items on my shopping list, come back and cook
the food perfectly at my house according to my tastes, and so forth,
but can you do my math?

Harvey