Google's AlphaGo. We implemented something similar. We realised that existing tic tac toe AIs you can find on the web are not that good, especially for custom tic tac toe games with boards larger than 3x3. The number of states in such a game increase exponentially exceeding the number of atoms in our galaxy for a table of 7x7.
What it does
It uses a deep neural network with more than 300 neurons to do reinforcement learning. The neural networks learns how to play tic tac toe.
How we built it
The neural networks learns by playing against a random agent and tries to learn a policy function which tells it what actions bring maximum reward. At the beginning, the neural network has no notion of the game. It does not even know the rules but after playing a couple of hundreds of thousands of games it beats the random agent more than 85% of the times. The neural network has 3 hidden layers, fully connected, each of 100 perceptrons. In average, 100000 games are needed in order for the neural network to learn the game.
Challenges we ran into
We didn't manage to get access to AWS and an EC2 instance. For large boards, we would have needed an EC2 instance with a powerful GPU in order to process games with very big number of states. Unfortunately that wasn't possible. Also, we had the challenge of finding the right learning rate for many reasons, but we came up with a clever algorithm for that.
Accomplishments that we're proud of
The Neural Networks plays very well (perfectly) for small boards of 3x3 or 4x4 because we managed to do lots of training only on our laptop's CPU. We also did everything from scratch and we used no data. The Neural Network learns only from experience. We also have a python server on which the Neural Network runs and a user interface you can use to play against the computer.
What we learned
What's next for DeepTacToe
Learning on powerful GPUs. I am also planning to train it by making it play against itself.
We have the Eight of Clubs.