[FOM] NIM Challenges

[Harvey Friedman]

On Thu, Sep 28, 2017 at 5:46 PM, Walt Read <walt.read at gmail.com> wrote:
> Harvey:
>
> Challenges can be fun for the thought and discussion they generate.
> But this challenge seems to have too many under-defined ideas as
> posed. In particular, "behave like a real mathematician", "not the way
> we do them" and maybe especially "strategy". It's not clear just what
> I would have to come up with to meet the challenge. Would I have to
> demonstrate somehow that the "computer" had (implicitly? explicitly?)
> used the "mathematical theory" as described by Wikipedia?

That is the challenge - to come up with something interesting to sort
the relatively clear informal ideas I discussed
http://www.cs.nyu.edu/pipermail/fom/2017-September/020612.html and put
them into precise frameworks and formulate detailed research
proposals.

I certainly can go a certain distance along these lines of
formalization myself, and in fact did do a little bit of it in the
original posting.

> But before we can get to that question, we have to ask how the game is
> going to be defined to the computer.

Of course at the semiformal level, we have plenty of experience with
this. E.g., we have presented chess, checkers, go, etcetera as games
to computers who have done better than humans now by a big margin,
with these. Now the question is whether they can get close to how good
we are at NIM and watered down NIM - under various modes of
presentation and various AI methodologies.

Here we have an easier time gauging their progress, since we have a
perfect strategy for NIM.

> 1. Will it be given a large number of examples (training set) with
> criteria for success and be expected to perform successfully on new
> examples (test set)? You suggest that that's not like a real
> mathematician (but using at least some examples is important even to
> real mathematicians) though you allow it as a possibility later. It's
> also what most people do most of the time to learn and have been doing
> throughout human history. (I recently spent a week playing samba
> reggae and maracatu at California Brazil Camp and the music directors
> routinely "taught" by playing examples until we were able to copy
> them.)

For you and other investigators to work out. One idea of many is of
course to define some general search for patterns that makes sense for
a defined category of games, and see whether it takes only feasible
time for the algorithm based on no external examples to come up with
the winning strategy. Other ideas are to provide massive numbers of
examples of various kinds, etcetera. For you and other investigators
to work out.

An interesting thing about Chess AI is that over the years tremendous
use was made in Chess Programs of the humanly created Opening Books,
developed by the greatest players. But probably by now, and I will
check this out, if the opening books are turned off, then the
computers are now still able to destroy the top players. I.e., to what
extent can computers destroy humans at chess starting from scratch -
under various notions of "starting from scratch"?

This suggests the research investigation of defining starting from
scratch, and seeing what our 21st century computers can do for a
number of games including NIM. I have some ideas for how to get a nice
rigorous model of this, but I wouldn't be surprised if you do also.

I.e. we need a better development of a corner of FOAI = foundations of
artificial intelligence.
>
> 2. Will it be given a set of rules and be allowed to explore
> possibilities through, perhaps, exhaustive search? And perhaps with
> some obvious heuristics?  Any constraints (time, depth) on the search?
> Bounded search is probably how most games are played most of the time
> and probably how this was originally played.

For you and other investigators to work out.
>
> 3. Will it be given either rules or criteria for success and a set of
> definitions/basic strategies/whatever as heuristics (and maybe a few
> examples?) and be expected to mutate these into better heuristics?
> Maybe basic definitions as in AM or extremely general heuristics as in
> GA-type classifier systems? This sounds the closest to what you have
> in mind.

For you and other investigators to work out.
>
> Maybe it could be given whatever heuristics people used (the game
> seems to be ancient) before the mathematical theory was discovered and
> asked to take the further steps. That would seem to be close to what
> real mathematicians do.

Least clear to me, but for you and other investigators to work out.
>
> To succeed by any of these means, will it have to describe the
> calculation as we would? Getting the computer to use the standard
> "winning strategy" that we're familiar with is almost certainly a lot
> easier than getting it to explain how it solved the problem or to
> write out a human-oriented rule that would allow other people to
> implement the strategy in their own wetware. For it to reproduce, say,
> the description in the Wikipedia article, it's going to have to have a
> basic set of words and rules for combining them. But it could be
> implicitly using the same rule implemented as connections in a neural
> net or as heuristics in a classifier system. And that might be our
> wetware version of your math.

For you and other investigators to work out.

Some of the things you suggest resonate with me as promising lines of
investigation, and others do not.

So we have the NIM situation, which differs greatly from Chess and go
in that we play NIM perfectly. However, I think it interesting to
consider also not only NIM variants that are various levels of easier
than NIM, but also some variants of NIM that are harder and that we
have no idea how to play perfectly. What is not clear to me is whether
or not the AI methods that have been so hugely successful, and
different ones, by the way, for chess and go, would work for NIM and
NIM variants. Or are games like NIM somehow "different"?

SEVERAL INTERESTING NIM VARIANTS

1. Players are allowed to take one or more stones from either one row
or two rows. As usual, the last person take any stones wins. (And the
variant where the last person take any stones loses).
2. Stones are originally placed on an n x n chessboard. Players are to
take one or more stones from either a row or a column.
3. Same as 2 except rows, columns, diagonals.

Harvey Friedman