NIM/Order Invariant Games

[Harvey Friedman]

I questioned whether the new technologies can play perfect NIM like
humans can. See
https://cs.nyu.edu/pipermail/fom/2022-February/023159.html

Here we define a very natural collection of NIM like games and ask how
humans do against computers.

First of all, coming back to NIM, I was tacitly assuming that humans
can play perfect NIM with a large number of large piles - as long
sequences of integers - even if the game tree is far far far too large
to build. That much seems clear.

So then for such sizes, it is a fair question as to whether any
technology can learn "just from the rules of NIM" how to play
perfectly. From some off line discussions it appears that experts
think they can but it hasn't been established.

GENERALIZED NIM

We can think of NIM in this way. We have a dimension k, and a binary
relation R on Z+^k, where x R y implies x is not y and for all i, x_i
>= y_i.

The game is played as follows. First we pick u in Z+^k. The game is
written (R,u).

Alice plays an R successor of u. Bob plays an R successor of Alice's
previous play. Alice plays an R successor of Bob's previous play. And
so forth. If a player cannot move, then that player loses.

The condition that we place on the binary relation R on Z+^k is that R
be order invariant. I.e., order invariant as a subset of Z+^2k.

RECALL: S contained in Z+^r is order invariant if and only if whenever
x,y in Z+^r are order equivalent, x is in S iff y is in S. x,y are
order equivalent if and only if for all i,j, x_i < x_j iff y_i < y_j.

Is there an efficient algorithm for determining who wins game (R,u) or
perfectly playing game (R,u)? There is a very efficient algorithm for
the special case of NIM.

When k is even rather small, order invariant relations on Z+^k can
have necessarily long descriptions unlike what is needed to state NIM.
So one would naturally impose structure on the order invariant
relations which can be done in various natural ways.

But in tiny dimensions, looking at all order invariant relations is
reasonable. In particular, consider the case k = 2. Here the theory
should be pretty interesting as well as the computer challenges. Of
course NIM for k = 2 is trivial to play perfectly. There are just two
piles. But there are a lot of order invariant subsets of Z+^4 to
consider and what can be prove about the resulting games? And what can
be found by pure technology?

For this, three piles (k = 3) is a whole new level of challenges..

In higher dimensions we have to be more careful to frame the right
questions and challenges.

Harvey Friedman