2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you the you answer and references therein! On this thesis, the author seems to restrict himself to Nim with three heaps of sizes at most 7. After a sufficient training phase, this Q-learning reinforcement algorithm is able to play the optimal moves on this restricted version of the game. In a sense this is not surprising, since the number of different states is finite. $\endgroup$ – Mathieu Mari Mar 26 at 16:47
  • 1
    $\begingroup$ Well, Q-learning needs by definition those finite amount of states. To complete any configuration of Nim some changes to parameters of agent may be needed, but the fact that the algorithm may work in any configuration of Nim may not alter. It will find it when it has enough saving space to calculate the state rewards and that the tuning parameters are well selected that the convergence to optimal goes in optimal time. $\endgroup$ – mico Mar 26 at 17:30
  • 1
    $\begingroup$ I don't know if this is related but the link contains some explanation how to taggle infinite number of states. $\endgroup$ – mico Mar 26 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.