[FOM] NIM/AI challenges

[Harvey Friedman]

FROM JOHN SCHULMAN
October 15, 2017

I think it the result would be most interesting if
1. you could not only solve nim, but also other nim-like games (like
the ones Harvey mentioned on the mailing list)
2. after training the network with small example, it generalizes to
larger examples, suggesting that it's identified the correct rule

On the other hand, the question of "how to learn a simple mathematical
rule that generalizes to larger examples" is easier to study in the
supervised learning setting, e.g. learning how to do arithmetic,
sorting algorithms, etc. And it's still not really solved there, yet.
So it might be premature to study this problem in the game setting,
where the two-player aspect makes it more complicated.

Anyway, I'll ponder it a bit more, and maybe try the self-play
training if I get a chance.

John

FRIEDMAN REPLES

I have been thinking a little bit about a persistent issue that arises
with regard to the nature of the AI challenges posed by NIM. Namely,
how do we want to present NIM to the machine?

I want to present a systematic way of presenting NIM which I think has
some independent interest from an f.o.m., math logic, cs, and game
theoretic viewpoints.

There are some fundamentally important classes of relations on N = set
of all nonnegative integers, starting with my favorite (smile, because
of emulation theory). Let's first take relations on N to simply mean a
subset of N^k, for some k >= 1.

One way to organize these is to consider some basic structures with
domain N, that include at least <, and take the

i. Quantifier definable relations without parameters.
ii. Quantifier definable relations with parameters.
iii. First order definable relations without parameters.
iv. First order definable relations with parameters.

Here are some structures to consider. For my favorite - order
invariant - we simply use (N,<) with i above.

(N,<), (N,<,0), (N,<,+1), (N,<,+1,0), (N,<,+), (N,<,+,1).

So we are talking about Presburger sets (first order over (N,<,+) or
(N,<,+,1) with or without parameters), and some natural fragments
thereof.

Now let's come to NIM. Let's define k-NIM as NIM with k rows. The game
k-NIM has a canonical presentation as an ORDER INVARIANT GAME in the
following sense.

The players "play" an element of N^k. The GAME RELATION is simply that
x,y are related if and only if x,y in N^k, and a big Boolean formula
holds that simply says that x,y agree at every coordinate i except
one, and at that one coordinate i, we have y_i < x_i. The winner of
the game is the player that after their turn, leaves all 0's.

So in k-NIM, the GAME RELATION is order invariant. In fact, a
particularly simple one This leads to two issues.

1. Can we obtain a winning strategy for all such order invariant
games? We can also allow some flexibility in determining who the
winner is, but at first I think it best to stick with all 0's. You can
see why we should also consider (N,<,+1), because, for example, there
is a baby version of NIM, a little different, with only one row, where
players are allowed to remove one or two stones, and this won't be
order invariant - although it would fall into being definable over
(N,<), an important class.

2. There is of course NIM which is the "union" of k-NIM, over k. We
can of course ignore this issue by talking only about 100-NIM, and if
we want to simplify matters for the computer, note that starting
positions may be required to have a lot of coordinates set to 0. So
this is not so crucial. HOWEVER, theoretically, we would like to take
about such things as order invariant binary relations on N*, where N*
is the set of all finite sequences from N. There are some issues about
how we want to set up all of these myriad numbers of natural classes
of relations above when we move to N*.

Note that in this setup, we have given the computer NO HINT of fooling
around with base 2 representations.

Harvey Friedman