Answers.Body: <p>There is actually <a href="https://github.com/abelmariam/nimPy" rel="nofollow noreferrer">a github project about 'solving' Nim</a> that implements certain type of <code>Q-learning reinforcement algorithm</code> (<em>described in undergraduate thesis of Erik Jarleberg (Royal Institute of Technology) entitled "Reinforcement learning on the combinatorial game of Nim"</em>) that supposedly finds that optimal strategy lying down there inside in the game that also human can find out.</p>
  
  <p>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:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p><em>(That is the quote I refer for it getting enough good / optimal results).</em></p>
  
  <p><code>Q-learning</code> is part of the reinforcement learning algorithm family where the so called <code>agent</code> learns how to play the game by getting <code>rewards</code> from its actions and it tries to maximize the amount of <code>total reward</code> with following strategy:</p>
  
  <blockquote>
    <p>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. </p>
  </blockquote>
  
  <p>Quote and more information in <a href="https://en.wikipedia.org/wiki/Q-learning" rel="nofollow noreferrer">Q-learning Wikipedia-page</a>.</p>
  
  <p>For further interest on easy games tackled with Reinforcement Learning, please have a look on following paper: <a href="https://deepmind.com/research/publications/playing-atari-deep-reinforcement-learning" rel="nofollow noreferrer">Playing Atari with Deep Reinforcement Learning</a>. There is also <a href="https://www.udemy.com/course/reinforcement-learning-with-pytorch/" rel="nofollow noreferrer">an Udemy class on that paper and its findings</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-26T16:47:00.633Z
Answers.Text: 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.
Answers.UserDisplayName: Mathieu Mari
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-26T17:30:45.990Z
Answers.Text: 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.
Answers.UserDisplayName: mico
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-26T17:32:06.213Z
Answers.Text: I don't know if [this is related](https://www.quora.com/Can-reinforcement-learning-still-be-used-if-there-are-infinite-number-of-actions-per-state) but the link contains some explanation how to taggle infinite number of states.
Answers.UserDisplayName: mico
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-25T20:24:28.710Z
Answers.LastActivityDate: 2020-03-25T20:41:18.533Z
Answers.LastEditDate: 2020-03-25T20:41:18.533Z
Answers.UserDisplayName: mico
Body: <p>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 <a href="https://en.wikipedia.org/wiki/Nim" rel="nofollow noreferrer">Nim game</a>. </p>
  
  <p>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:</p>
  
  <p><em>For simple game like Nim, can such an algorithm be able to actually find a winning move in any winning configuration of the game ?</em></p>
  
  <p>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.</p>
  
Tags: <machine-learning><combinatorial-games>
Title: Can an artificial intelligence be unbeatable at simple games?
UserDisplayName: Mathieu Mari
ThreadText: # Can an artificial intelligence be unbeatable at simple games?
  
  (Asked by: username_0 on 2020-03-25)
  
  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](https://en.wikipedia.org/wiki/Nim).
  
  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.
  
  **Tags:** machine-learning, combinatorial-games
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-03-25. Score: 2
  
  There is actually [a github project about 'solving' Nim](https://github.com/abelmariam/nimPy) 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](https://en.wikipedia.org/wiki/Q-learning).
  
  For further interest on easy games tackled with Reinforcement Learning, please have a look on following paper: [Playing Atari with Deep Reinforcement Learning](https://deepmind.com/research/publications/playing-atari-deep-reinforcement-learning). There is also [an Udemy class on that paper and its findings](https://www.udemy.com/course/reinforcement-learning-with-pytorch/).
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: 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.  
  > **username_1**: I don't know if [this is related](https://www.quora.com/Can-reinforcement-learning-still-be-used-if-there-are-infinite-number-of-actions-per-state) but the link contains some explanation how to taggle infinite number of states.  
  
  ---
  
  