Can an artificial intelligence be unbeatable at simple games?

Question

There are (two-players, perfect information) combinatorial games for which, at any configuration of the game, a winning move (if there is one) can be quickly computed by a short program. This is the case of the following game that starts with a bunch of matches and each player alternatively removes 1,2 or 3 matches, until the player that removes the last one wins. This is also the case of the Nim game.

On the other hand, understanding the winning strategy of games like Go or chess seems hopeless. However, some machine-learning based programs like alphaGo zero are able "learn the strategy" of complex games, using as input data only the rules of the game. I don't really know how these algorithms work but here is my vague question:

For simple game like Nim, can such an algorithm be able to actually find a winning move in any winning configuration of the game ?

The number of configurations of Nim is infinite, but the algorithm will consider during its "training" only a finite number of configurations. It seems imaginable that if this training phase is long enough, then the program will be able to capture the winning strategy, like a human would do.

Answer 1

There is actually a github project about 'solving' Nim that implements certain type of Q-learning reinforcement algorithm (described in undergraduate thesis of Erik Jarleberg (Royal Institute of Technology) entitled "Reinforcement learning on the combinatorial game of Nim") that supposedly finds that optimal strategy lying down there inside in the game that also human can find out.

The project uses a code in Python, which is 'only' 114 lines of code, so it can be run on your own machine if you got interested and want to test it. Github page tells also:

There is a known optimal strategy for the game which is credited to Charles L. Bouton of Harvard which can serve as a benchmark for evaluating the performance on our Q-learning agent.

(That is the quote I refer for it getting enough good / optimal results).

Q-learning is part of the reinforcement learning algorithm family where the so called agent learns how to play the game by getting rewards from its actions and it tries to maximize the amount of total reward with following strategy:

The goal of the agent is to maximize its total reward. It does this by adding the maximum reward attainable from future states to the reward for achieving its current state, effectively influencing the current action by the potential future reward. This potential reward is a weighted sum of the expected values of the rewards of all future steps starting from the current state.

Quote and more information in Q-learning Wikipedia-page.

For further interest on easy games tackled with Reinforcement Learning, please have a look on following paper: Playing Atari with Deep Reinforcement Learning. There is also an Udemy class on that paper and its findings.