We get a lot of questions about how the Artificial Intelligence (AI) in Blok 9 works, so today we got the game’s creator to spill a few of his secrets and give a heady explanation of the magic (or mathematics) at work.

First meet Eric:

Name: Eric

Age: 32

Sifteo job title: Game Designer/Developer

Fun fact: I am an expert at opening fruit with my bare hands. Once I opened a pineapple.

Favorite food: pigs’ feet

…and now meet his AI and formidable opponent, The Void:

Name: The Void

Age: 11 months

Sifteo job title: Office Security

Fun fact: I can recite pi in iambic pentameter.  It is beautiful.

Favorite food: Slim Jims

When designing Blok 9, I first had to consider what the goals for the AI were. Obviously, the main goal is to have it be able to play the game. But at what level? It’s surprising to some that the goal of game AI is usually not to be as good as possible. If you’ve ever played a game against an opponent who crushes you every time, you know that’s no fun. In order to result in a fun experience, it must be challenging but seem beatable by the player.

At this early stage of development, I realized that I wouldn’t be able to lay down rules and strategy for how the AI behaved, as I myself didn’t understand what good Blok 9 strategy was (one sign of an interesting game: the designer can’t fully solve the game immediately). So I began to survey my options.

One of the chief ways AIs for board games like chess and Othello work is by using an algorithm called minimax. In this algorithm, the AI will create a branching tree that explores each possible move n turns into the future. It predicts the future by having each player pick the best move possible for that player. Since there are so many branches, the tree becomes too large to compute, and one must rely on a heuristic, or special rule, to decide which parts of the tree to explore. For example, in chess, you could have a heuristic that ignores all moves that involve moving anything but pawns. (Note: That is probably not a good chess heuristic!)

That sounded like a good start, except that Blok 9 has one fundamental difference from those games: it is non-deterministic. What this means is that there is some element of chance involved. Each turn, a player gets one of two pieces randomly; as a result, there’s no way to predict what moves are optimal in the future.

I decided I had enough research under my belt and I wanted to start experimenting. At first, I was curious how an AI would perform if it wasn’t able to look ahead at each move’s outcome, so I programmed it to simply pick the move that gave it the most pieces. This is known as a greedy algorithm. Check it out here:

As someone who grew up in the 80s, this was a real War Games moment for me. It tickled me to no end. But how well did the greedy AI play?

As you might expect, the greedy algorithm doesn’t fare too well. It’s too easy for the human player to trick the AI into making a move that’s only good in the short term, and then steal all the AI’s pieces back and win the game.

So what next? I began looking into what’s called the Monte Carlo method.

The Monte Carlo method

The Monte Carlo method involves simulating many possible games from the current point forward, choosing moves randomly, and choosing the move which results in the most wins.

For example, let’s say the AI has 3 moves available. We could simulate a bunch of games from those 3 moves and look at the results:

Results for 1000 games

Since Move 1 has the most resulting wins, we choose it. Simple, right? Since we are simulating the full games, it takes into account the randomness of the game. I didn’t have to tell it anything about strategy, and if the game changed, the AI would continue to work. It sounded good to me!

And indeed it was—the Monte Carlo AI beating the greedy AI about 70% of the time. Simulating 1000 games is time consuming, however—even for a computer! Each turn took about a minute and a half, which is way too long. I needed a method that would take the AI less than 5 seconds each turn to complete.

It’s easy to think, then, that the solution could be to simulate games for 5 seconds only, right? But one thing about the Monte Carlo method is that it works much better with more data. If your sample size is too small, you might be just hitting a random run. For example, if you flip a coin 1000 times, you’re likely to get very close to 50% heads and 50% tails. But flip it 10 times, you might get something very unbalanced. My computer could simulate only about 50 games in 5 seconds. That was not enough.

Since it was clear that the more games simulated, the better, I worked on speeding up the AI so it could simulate a few hundred games in 5 seconds. That helped, but what helped even more was being smarter about which games to simulate.

Look above at the chart of 1000 games. Move 2 looks like a clear loser. Do we really need to simulate 333 games that follow from Move 2 just to see that it loses 288 times? No. A simple change to prioritize winning moves gave the AI the magic it needed to begin consistently beating me.

And that’s how The Void came to be.

I’m glossing over plenty of details here, but if you’re interested in learning more about the AI concepts mentioned in this post, check out:

• wikipedia entry on minimax: http://en.wikipedia.org/wiki/Minimax
• a cool blog post about Monte Carlo, with a playable Connect Four app that shows you the algorithm working: http://beej.us/blog/2010/01/monte-carlo-method-for-game-ai/

So now that you know the Void’s tricks, can you beat it? Try and find out!

Any questions or comments about the Blok 9 AI? You’re welcome to add your comments below or to email me: eric@sifteo.com.

The secret to beating No Evil Monkeys…

DID YOU KNOW… Unscrambling the pictures in No Evil Monkeys can seem really hard at times. Like, REALLY hard. But there’s a simple rule that will give you a big advantage over those sneaky monkeys: before you shuffle the tiles, memorize which monkey is on which cube. Then focus on putting the monkeys back in their original positions. As long as you can remember which piece goes where and don’t let yourself get turned around, you’ll be juggling monkeys in no time.

Planet of Tune

Imagine this: you’re listening to a piece of music and you want to shake things up a bit. But instead of skipping to the next track, you reach out and grasp pieces of the music you hear, shaping them with your hands to create an entirely different sound. A sound that’s all yours and very literally shaken up!

Here at Sifteo, Game Designer Chris March imagined exactly that—and made it a reality on your Sifteo cubes. In our latest application, Planet of Tune, we combined our love of music with the technology that makes this kind of musical interaction possible.

With Planet of Tune, each Sifteo cube becomes a home for one of 14 different, crazy creatures playing a unique instrumental sound. The creatures prowl through 7 wild terrains on the Planet of Tune and, with each step, play a note on their instruments. You can tilt or shake your cubes to guide them to walk on your favorite notes. With one-button recording and looping playback, Planet of Tune offers a whole new world of music to explore and original compositions to create!

A couple days ago, Sifteo gave a sneak preview with a video that featured the first of the 7 planetary terrains. Each terrain has a distinctive mood and style, so we’d like to give you another glimpse (and listen!) into life on the Planet of Tune: