928: Order Invariant Games/2

[Harvey Friedman]

I want to expand a bit on the previous posting
https://cs.nyu.edu/pipermail/fom/2022-March/023168.html

First of all, as Tim Chow has pointed out, I had brought up NIM before on FOM:

https://cs.nyu.edu/pipermail/fom/2017-September/020612.html
https://cs.nyu.edu/pipermail/fom/2017-October/020642.html

In particular, the second one above contains reports by John Schulman,
October 15, 2017.

I find a casual reading of all the things I have seen written about
learning NIM as unsatisfactory. I think this is partly due to the
result of some lack of proper focus in the way that I present this AI
Challenge.

I am trying to use NIM and NIM like games as real AI challenges and on
a superficial reading of what I  have seen, somehow I do not think
that this is being addressed.

The great success with chess playing technology is based on
mathematical refinements of brute force search on top of humans using
their chess knowledge in two main ways. The brute force approximates
the game tree going forward, and also uses the perfect retrograde
analysis for small size endings. The human component uses what is
called the opening book, the result of centuries of human analysis
from the starting position. The other is the human created evaluation
of chess positions.

Still there is the residual feeling that this isn't "real AI". And
that "real AI" has not really gotten of the ground.

What is not clear is what is really meant by "real AI" and whether the
distinction between "real AI" and what we have been able to do with
fantastically intensive computer power is genuine.

What was so exciting about the new Deep Learning was that it appears
to be more powerful or at least not subsumed by the methods previously
used in Chess and Go. On the other hand, comparison in Chess seems to
be rather controversial, and in particular the comparison between
Alpha Zero and Stockfish. Issues have been raised about the ground
rules. But my understanding is that with Go the new Deep Learning is
much better than previous brute force Go. This advantage of Deep
Learning seems to depend at least partly on the shape of the game
trees.

I picked NIM (back in 2017) as a good setting for talking about "real
AI". But I am not sure this is being looked at the proper way.

The relevant issue is how Deep Learning Nim compares with standard
methods for searching game tress. For Nim with fairly small initial
configuration, the game tree is not too large for exhaustive search.
So for fairly small initial configurations, using Deep Learning is not
going to be, prima facie, interesting.

Computer Nim really starts to get interesting when the game trees
start to get enormous, particularly when they start to get
unsearchable.

IMPORTANT DISTINCTION: We MUST make a distinction between ordinary NIM
and digital NIM. In ordinary NIM we actually have many piles of many
stones in physical reality. In digital NIM we have a finite sequence
of nonnegative integers in base 2 (or base 10).

With digital NIM, the game trees quickly get absurdly large. For
instance, we may consider 20 piles each one containing a randomly
chosen 50 digit number. That's only at most 1000 bits for the starting
position and every position thereafter..

QUESTION. How many moves does it take to win this sized digital NIM
against an arbitrary opponent? What about against an opponent playing
randomly?

Note that we can actually play digital NIM - but maybe the number of
moves gets out of hand? When the losing opponent plays randomly or
plays with certain restrictions?

So it does not appear that any kind of brute force AI is going to get
anywhere with a situation like this. And we know that humans play
perfectly. So what do the newer AI methods do here? We really need to
compare apples to apples here.

So returning to Chow's inquiry as to why I brought this up again on
FOM. There was a partly subconscious feeling that somehow the issue
may not have been joined properly. And that feeling is being brought
out here with the distinction between ordinary NIM and digital NIM and
fair comparisons between brute force methods and new AI methods. This
does lead to some mathematical investigations into digitized NIM.

Another reason I brought this up is that I was looking for a perhaps
new way to look at NIM generalizations. So I came up with order
invariant games. See

Order invariance plays a crucial role in the new Tangible
Incompleteness, maybe for 50 years. See

https://cs.nyu.edu/pipermail/fom/2021-December/023034.html
https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2021/09/IncompChinese090821.pdf
page 19

So I began to look at NIM as an order invariant game in

https://cs.nyu.edu/pipermail/fom/2022-March/023168.html

But that formulation doesn't take into account the crucial difference
between ordinary NIM and digital NIM when one wants to bring in
quantitative aspects.

I am also looking at some theorems about partial winning strategies in
order invariant games that require large cardinals to prove. These are
not ready for discussion.

Recall the following closing section from
https://cs.nyu.edu/pipermail/fom/2022-March/023168.html

MUCH MORE AMBITIOUS

Use larger classes of binary R on the N^k. The most ambitious of this
character would be the Presburger relations. These are first order
defined over (N,+). But there are many interesting and important
fragments.

added now: A particularly interesting larger class of binary R on the
N^k (larger than order invariant) is quantifier free definable over
(N,<,+1). This supports some very natural game rules going beyond NIM.

Also tangentially relevant is
https://cs.nyu.edu/pipermail/fom/2022-January/023084.html

##########################################

My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 928th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-899 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

900: Ultra Convergence/2  10/3/21 12:35AM
901: Remarks on Reverse Mathematics/6  10/4/21 5:55AM
902: Mathematical L and OD/RM  10/7/21  5:13AM
903: Foundations of Large Cardinals/1  10/12/21 12:58AM
904: Foundations of Large Cardinals/2  10/13/21 3:17PM
905: Foundations of Large Cardinals/3  10/13/21 3:17PM
906: Foundations of Large Cardinals/4  10/13/21  3:17PM
907: Base Theory Proposals for Third Order RM/1  10/13/21 10:22PM
908: Base Theory Proposals for Third Order RM/2  10/17/21 3:15PM
909: Base Theory Proposals for Third Order RM/3  10/17/21 3:25PM
910: Base Theory Proposals for Third Order RM/4  10/17/21 3:36PM
911: Ultra Convergence/3  1017/21  4:33PM
912: Base Theory Proposals for Third Order RM/5  10/18/21 7:22PM
913: Base Theory Proposals for Third Order RM/6  10/18/21 7:23PM
914: Base Theory Proposals for Third Order RM/7  10/20/21 12:39PM
915: Base Theory Proposals for Third Order RM/8  10/20/21 7:48PM
916: Tangible Incompleteness and Clique Construction/1  12/8/21   7:25PM
917: Proof Theory of Arithmetic/1  12/8/21  7:43PM
918: Tangible Incompleteness and Clique Construction/1  12/11/21  10:15PM
919: Proof Theory of Arithmetic/2  12/11/21  10:17PM
920: Polynomials and PA  1/7/22  4:35PM
921: Polynomials and PA/2  1/9/22  6:57 PM
922: WQO Games  1/10/22 5:32AM
923: Polynomials and PA/3  1/11/22  10:30 PM
924: Polynomials and PA/4  1/13/22  2:02 AM
925: Polynomials and PA/5  2/1/22  9::04PM
926: Polynomials and PA/6  2/1/22 11:20AM
927: Order Invariant Games/1  03/04/22  9:11AM

Harvey Friedman