Teaching a computer how to play Tic Tac Toe — A Trip Report
From classic algorithms to Reinforcement learning with Neural Networks
In this series of articles and Jupyter notebooks we will explore a number of different approaches, from the Min Max algorithm to Neural Networks, with the aim of teaching / training a computer how to play the well known board game Tic Tac Toe.
This is not a set of tutorials by an expert in the field who is sharing his knowledge with the world. This is more of a trip report by someone who is trying to learn some new skills, namely Reinforcement Learning and Neural Networks.
Not everything we will try in this series will work very well; and often the reasons why something worked or didn’t work ultimately will remain unclear. I still hope the articles are informative, may provide some insights, and in the end will help you with getting a deeper understanding of Reinforcement Learning and Neural Networks — how to use them as well as the challenges you may encounter when trying to do so.
Most people will be familiar with Tic Tac Toe and more than likely you will have played it at some stage of your life.
The game is rather simple. With respect to its rules as well as its strategy. In fact, it can be played by young children and Tic Tac Toe boards can often be found at playgrounds:
If you have played Tic Tac Toe a couple of times you will have quickly realised that it is quite easy to master. You will most likely also have discovered that when both players play good moves, the game will always end in a draw.
In the following, we will use the example of Tic Tac Toe to look at various approaches which can be used to teach or train a computer to play this game. Not because Tic Tac Toe is particularly challenging, but because it gives us a consistent, easy to understand target.
We will look at the classic Min Max algorithm, a Tabular Reinforcement Learning approach as well as a couple of Neural Network based Reinforcement Learning approaches:
- Part 1 — Computer Tic Tac Toe Basics
- Part 2 — The Min Max Algorithm
- Part 3 — Tabular Q-Learning
- Part 4 — Neural Network Q-Learning
- Part 5 — Q Network review and becoming less greedy
- Part 6 — Double Duelling Q Network with Experience Replay
- Part 7 — This is deep. In a convoluted way
- Part 8 — Tic Tac Toe with Policy Gradient Descent
The source code and Jupyter notebooks for this series are available at GitHub.
If you don’t want to install Jupyter or Python on your computer, you can run the Jupyter notebooks online in Binder:
To get the most out of these articles you should have some basic understanding of programming in Python, and for the later parts, ideally, a basic idea what Neural Networks and the TensorFlow library are.