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.
My next step will be to upgrade this program to Connect 4.
On the flight from Toronto to Vancouver, there was enough room to use the Laptop. So Max and I made a tiny simple game in Processing. Max drove, I rode shotgun.
Max made a little game where your player follows the mouse and an enemy chases you until it catches you.
The game is called: Chasing.
How many Duplo aeroplanes can I make in 15 minutes? This many.
Ada made the truck. Max made the next one. I made the rest.
My daughter and I did a make it quick challenge together. I drew an eye. Zoe drew something else and put it on her blog.
It doesn’t sound like much, but I added a random computer player to the Tic-Tac-Toe game I made in an earlier MIQ. I had to refactor the entire application to be less of a monumental kludge and more object oriented. Then I could make the computer select a random move from the list of possible moves. Again, this took closer to 30 minutes than 15.
Here it is: http://jollyninja.com/Games/TicTacToe2015-06-08/
The spade made a metallic clunk as it made contact with something. Max scraped the dirt away to reveal a plain metal box. He was almost disappointed that it wasn’t an ornate treasure chest with a skull and cross bones carved into it by bloodthirsty pirates.
The only reason he found the box, was the book. He called it the book but it was more like a magic rock. A flat rectangle with pictures and symbols that changed. Sometimes they changed when he touched the surface, sometimes the images changed on their own as he travelled. Eventually he worked out that it was some kind of map, and the blinking circle was where he was on the map. The weird octopus symbol was marked on the map and he just had to work out what it was.
It had taken all night, and he was almost seen by a group of people roaming these normally deserted hills.
He started to lift the lid. A glow crept along the crack of the lid as it opened. When the lid was all the way open, he tried to work out what he was seeing.
A ring of eerie light surrounded a circle of the blackest black he had ever seen. No. Not quite black. There was a tinge of blue. Occasionally, it looked like there were sparks in the blackness.
A tight ball of dread sat in the pit of his stomach. Then he saw the tentacle; too late.
I did another 15 Minute making challenge. I had to take a break for a few hours at the 7:30 mark. But I managed to get a kludgy tic tac toe game working for two players. It only took an extra 15 minutes…