Understanding Q-learning algorithm through Nim game

For the past 3 years, there was so much buzz on AI and I could see that AI has become pivotal in our lives. Today, we rely on AI assistants rather than a search engine for all questions. Thus, I became curious to know how an agent can understand different languages and answer all our questions.

In pursuit of knowing AI, I took Harvard’s CS50 Intro to AI which gave me a glimpse of various fields in AI. As part of the course, I had to complete a coding assignment to build an agent which has to play a Nim game against a human. While testing the code, I observed that AI behaved differently for different parameters and it motivated me to run a simulation to understand the behavior. In this blog, I would briefly explain how AI learns to play the Nim game and how its intelligence changes based on the training and other parameters.

Nim is a strategy game where two players take turns to remove stones from a distinct pile. The player who removes the last stone, loses the game. Let’s consider a heap of stones [1, 3, 5] where the third pile has 5 stones, 2nd pile has 3 stones and 1st pile has 1 stone. The following sequence of moves results in a win for Player 1:

• Player 1 takes 1 stone from 1st pile
• Player 2 takes 5 stones from 3rd pile
• Player 1 takes 2 stones from 2rd pile
• Player 2 takes 1 stone from 2rd pile and loses the game.

In the assignment, AI plays the Nim game using the Q-learning algorithm. Q-learning is a reinforcement learning algorithm which helps an agent to pick the best possible action for a given state. In layman terms, AI keeps score of every action it takes and this score is called q-value. AI will reward less points for an action which leads to loses and more points for the ones that lead to wins. Over time, AI chooses an action with maximum q-value. Q-value is computed whenever an agent moves from one state S to another S’ through an action A and it is best expressed by the following expression

*Q(S, A) = Q(S, A) + 𝛂 (immediate reward + max Q(S′,A′) — Q(S, A)) where

• S represents the current state
• A represents an action taken by AI
• 𝛂 represents the learning rate
• Immediate rewards represent rewards for transitioning from S to S’ through an action A
• max Q(S′,A′) represent best possible long-time value that can be gained at state S’

One of the drawbacks of the Q-learning algorithm is that it can end up learning a sub-optimal strategy. To avoid this, we introduce an exploration factor called 𝛆 (epsilon) which allows AI to explore other strategies randomly. As a result, Nim game will follow Q-learning algorithm for a probability of 1- 𝛆 while with probability of 𝛆 it selects actions randomly. If 𝛆=0.1 then the AI agent will explore the unknown path only 10% of the time and 90% of the time, it keeps exploiting the known path. Thus, depending upon the number of training and learning rate, the AI might either be completely unaware or aware of the optimal strategies.

The domain model for the Nim game is expressed as follows

• Current state of the pile represents a state
• Moving x stones from the nth pile represents an action. For example, removing 2 stones from 3rd pile represents an action (2,3)
• Immediate reward of +1 is assigned when the agent wins the game, -1 when it loses the game and 0 for states where the game is still in progress

During the training, AI plays the role of both players and it uses a Q-learning algorithm 1-𝛆 % of the time to choose an action. In real-world applications, however, AI can also be trained by observing games played by human players or through similar self-play approaches. In the Nim game, whenever a player removes ‘x’ stones from a pile, their corresponding q-value is updated. Actions that contribute to winning the game receive higher Q-values while actions that contribute to losing the game receive lower Q-values. For non-terminal states, the Q-value is adjusted based on the estimated value of future moves. At the end of the game, AI has some data which helps it to pick the best move in the next game.

The above image shows q-value for each possible actions in the state [1,0,5] at different training games

After the training, I ran an experiment to understand how intelligence of an AI varies based on varying the number of training session, learning rate (𝛂) and exploration rate (𝛆). In order to measure intelligence, the win rate and number of steps taken to win were tracked for every trial. Additionally, to avoid manual efforts to play the game against AI, I simulated an average human player who chooses to remove the maximum number of stones from a pile 60% of the time.

The above graphs shows how the win rate and the number of turns required to win vary with the number of training sessions, exploration rate (𝛆), and learning rate (𝛂).

From the above graph, we can observe the following things

• The win rate increases as we increase the number of training sessions and it is true irrespective of the learning rate (aka alpha). This implies that more training gives sufficient opportunities to explore and reinforce effective strategies.
• For fewer training games, the win rate increases as we increase the epsilon winrate(epsilon=0.1) < winrate(epsilon=0.3) < winrate(epsilon=0.7). This implies epsilon helps the AI to win by allowing it to explore better strategies despite limited training.
• Interestingly, the win rate is quite unstable for different values of alpha under the same epsilon and training session.
• Epsilon might help the AI to win the game in fewer turns. However, this observation can vary depending on the intelligence of the opponent

One could relate the AI behavior to the following analogy. Assume that a student is preparing for an exam on linear algebra. The student may adopt different learning strategies like watching a video, reading a text book, working out the problems, seeking out a tutor’s help. In this case, epsilon represents willingness to explore different learning strategies while alpha represents how strongly the student adopts the learning strategy based on outcome. The chances of clearing an exam depends on the difficulty of the examination and the appropriate learning strategy adopted by the student. For example: an exam primarily consists of questions asked in previous years, then the student may succeed by memorizing patterns and repeatedly practicing those questions without deeply understanding the underlying mathematical concept. However, this strategy will not work if the final assessment requires the student to apply linear algebra concepts creatively, such as presenting a white paper on real-world applications of linear algebra in astronomy. In this case, the student must adopt learning strategies like thinking aloud while working on problems, teaching a concept, reading a book, etc., to gain deeper understanding than memorizing the patterns.

In conclusion, frequent training sessions help AI to win the game while the epsilon might help the AI to win the game in fewer steps. Interestingly, depending upon the randomness, the learning rate may have a negative impact on AI’s performance if it was not trained enough.