Reinforcement Learning

Can you create an unbeatable opponent?

Artificial Intelligence has increased in both popularity and application in the workforce. While there are many techniques and branches that all could fall under the term ‘Artificial Intelligence’, I wanted to explore a specific subcategory called reinforcement learning. What makes reinforcement learning different from other branches of AI is that it ‘learns’ from exploring and receiving certain rewards or punishments from it’s actions, it never has the ‘correct’ answer in front of it. Instead, it is able to explore in it’s environment and learn the behavior that maximizes it’s reward. It is for that reason that reinforcement learning is great for tasks that have a learning curve, such as playing games or the behavior of autonomous robots.

I briefly describe the game below, but it actually was inspired by one of my favorite Cyberchase episodes, my favorite TV show as a kid. Watch Here

Project Overview

Identify A Game For The Agent To Learn On
For this project, I decided to keep it simple and develop an agent to play the game ’21.’ In this game, there are 21 tokens, and two players. Each player may take 1, 2, or 3 tokens from the board. While alternating turns, the players goal is to force the opponent to take the last token. Or in other words, you lose if you must take the last token.
Whiteboard Out The Classes Of Environment, Agent, and Human
During the project I made three different classes: Agent, Environment, and Human. In typical reinforcement learning theory, the simulation is set up in two pieces of the agent, which interacts with the environment. The human class is just a subclass of the agent, but it’s difference being the fact that it is controlled by a human rather than it’s own knowledge.
Code The Game
While the project took me about 10 hours to perfect, most of the work came in updating each state value for the agents. In other words, every time the agent would play the game, it would value and grade it’s performance of each move. If it had lost, it would then correlate the moves it had made with losing, allowing it to ‘learn’ from past trials.
Train The Agent
This is the fun part. Once everything was built, the only thing left was to have the computer be trained to play the game. To do this, I essentially created two different agents where the the computer would play against itself for 100,000 times. This took about 45 seconds, but I’m sure it could be trimmed down with optimization.
Play Against The Computer
The results? An unbeatable opponent. After 100,000 games, the computer had quickly mastered which moves were best, and how many tokens should be left to condemn your opponent to lose early on in the game. In fact, I chose this game because I suspected with such simple rules, there would be a pattern to emerge, and I was right. The computer would always make the moves necessary to force the opponent to be left with 5, 9, 13, or 17 tokens. At these numbers, if played right, the computer could guarantee that the opponent would have to take the last token.

Value States Over Time

In reinforcement learning, for every state there exists a ‘value’ which measures how good it is to be in said state. In the case of this game, there was an initial value of ‘0’ for each state except for the state where there was one token remaining. In this case, the value of the state was -10, as it indicates that the player has lost the game. In the video below we see that as the agent plays each game, (an epoch) the values quickly converge to approximate their true values. This is behavior that can be defined as the agent ‘learning’ how to play the game.

Running The Code

Recording of the completed code. While building a reinforcement learning agent from scratch was pretty hard, it really helped me understand the math going on behind the scenes, especially the Bellman equation. Notice in the first game it wins handily. But in the second, a poorly timed exploration move causes it to lose. I should have decreased the learning rate over time, but I had to give us poor humans a chance somehow right?