AI for Tic-Tac-Toe (Part 1)

TicTacToe0

Neural Network is a subject which interests me. Nevertheless, I was never idea about an application of the artificial intelligence. Recently, I remembered an old application I have created: a simple Tic-Tac-Toe. This game is easy, an "expert" can avoid traps and never lose. I have implemented a false intelligence in this game which was unbeatable. When you play, you have not thousand of combinations. First point, you can rotate the board and use symmetry to reduce the number of possible combinations. Second point, when the opponent have filled two cells in a line, you will fill the last one to avoid the opponent to win.

So, my question: is a neural network able to tend toward an unbeatable intelligence? Fortunately, a lot of people use Tic-Tac-Toe to explain Neural Network. I have found an interesting website (Neural network with learning by backward error propagation).

In the first step, I won't present Neural Network, but methods to create a bot to play to Tic-Tac-Toe. Even if I think this is an easy game, the aim is the understanding of the game. These bot could be used as reference to compare the performance of the Neural Network.

1st competitor: 'Full Random'

Before to talk about this AI, I present other competitors. The first of them is 'Full Random' and it plays randomly. If this player plays again itself the result is uncertain.

Battle #1: 'Full Random' vs 'Full Random'

The next chart shows the percentage of victories of this simple player. The first player has an important advantage.

2nd competitor: 'Partial Random'

The next competitor named 'Partial Random' use a random choice except if it can align three cells or if the opponent align two cells. This competitor is better than the first, but many traps exists.

The 'Partial Random' can align 3 cells and avoid that the opponent align cells (except the cases where there are traps)
The 'Partial Random' can align 3 cells and avoid that the opponent align cells (except the cases where there are traps)
Battle #2: 'Partial Random' vs 'Full Random'

This is the result if 'Partial Random' is the first to play.

Battle #3: 'Full Random' vs 'Partial Random'

This is the result if 'Partial Random' is the second player.

Battle #4: 'Partial Random' vs 'Partial Random'

Conclusion

This first article shows two competitors. One which play randomly and the second which prefers to align cells.

The battle #1 presents the real proportion of the different cases: 10% of Ties, 60% for 1st player and 30% for 2nd player.

The battle #4 shows the proportion of traps. So half of cases are traps: 30% for 1st player and 15% for second player.

Next time, I'll present you the third competitor. The unbeatable player.