Make it Slower #7 – Random Tree Search for Tic Tac Toe

The Air Canada flight from Toronto to Vancouver had more room for a laptop, so I decided to try out an algorithm for game AI, I’ve read about. It’s called Random Tree Search. It’s a bit like Monte-Carlo Analysis for games. Essentially, the computer randomly plays lots and lots of games and counts how many wins, losses, and draws happen on each possible next move. Then the move with the best results is chosen.

I decided to try this on a small scale with Tic Tac Toe, since this is a very simple game that humans can easily play optimally.

I built upon a previous “Make it Quick” effort. And added a simple algorithm to randomly play games, counting the wins.

When I simply used total wins as the criteria, the computer quite often made dumb mistakes. When I changed the criteria to wins – losses. The computer was smarter.

Here is the game. It’s not optimal, but it isn’t completely stupid either.

TicTacToeRTS

My next step will be to upgrade this program to Connect 4.