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.

Here at Sifteo, we’ve been enjoying the first couple weeks of the New Year.

The pace has slowed enough for us to catch our breath after the busy holiday season, San Francisco weather has been unseasonably warm, and we’ve just outfitted the lobby with some brand new bike racks.

With a few sun-coated, blissed-out January moments, the engineers tinker. The game designers doodle. Our minds wander and we often find ourselves wondering about the Sifteo customers we’ve connected with over the past several weeks. How did they spend the holidays? What’s new for them in 2012? Do they like their Sifteo cubes? Are they out there somewhere playing a Sifteo game right now, at this very minute?? Trippy.

Every so often, a few answers come to us from out of the blue—an event that causes all respective thought bubbles to burst and all activities to cease. We become very excited!

That’s what happened yesterday when we received the following note and photos from a Sifteo customer. We thought we’d share them here for posterity:

“Cool Uncle Matt gave Sifteo cubes to my kids for Christmas this year. The photo is from New Year’s Eve as my kids were showing their friends all of the games on Sifteo.  My kids are 10, 7 and 4 years old and each found a favorite way to play with the cubes, whether it was code-breaking in Peano’s Vault, competing in math quizzes using Mount Brainiac, or solving puzzles in Chroma.  The favorite app for all the kids was Mount Brainiac, because regardless of difficulty level, the kids could try and beat their own high score, or compete against their friends.   The Sifteo cubes are intuitive (no parenting necessary other than the initial set-up), addicting and fun.  Congrats on creating a very unique and engaging game.” – P.C.

Thanks for the kind words, P.C.! We couldn’t be happier to hear them. Hoping you and yours continue to enjoy Sifteo and have a terrific new year.

A lot of brainpower goes into the development of any single Sifteo game. In fact, we generally believe the more brains the better, and try to welcome as much collaboration as possible. Since many of our users have great ideas about what games they’d like to play and how our system can better suit their imaginations, we like to reach out and connect with them, too.

But most people don’t realize that many of the minds at work on our games are very young. And I’m not talking start-up, Silicon Valley young, but like, elementary school young. At Sifteo, kids are taken very seriously as critics of our work. After all, they’re usually the most enthusiastic and active game players out there!

Some of us are lucky enough to have nieces, nephews, or kids of our own who are eager to test out the latest Sifteo games in development. But most of the very young people we work with hang out at the Innovation Lab of the Children’s Creativity Museum, where children get a hands-on experience with new technology, talk with tech professionals about their jobs, and experiment with the latest innovations.

We really appreciate this opportunity to work with Sifteo’s biggest fans. With the right kind of exposure to technology, we’ve seen students become inspired to pursue a curriculum that could eventually lead to a career in computer science or engineering. And of course, the insights of children at play in the Innovation Lab are tremendously helpful to our game developers, who are in turn inspired by the imaginations of even our youngest users.

“I didn’t intend for Matchination to be playable with 2 cubes; I thought it’d be too simple,” Sifteo Game Developer, Eric Liao, explains. “But I’d forgotten to restrict the game to 3 cubes or more, and then noted that a lot of our younger play testers at the Children’s Creativity Museum were having a blast with 2 cubes. Their engagement really helped me understand what works for different age levels. I immediately made 2-cube play one of the options in Matchination.”

Another Developer, Josh Lee, describes group dynamics in Sifteo game play. “During one of our earliest play tests, I put a set of three cubes down on a table in front of three girls. Each girl took a cube and claimed it as her own. I thought this would make the games unplayable—they were designed with a single player in mind! But the girls naturally cooperated and brought their cubes together to play Chroma Shuffle and Mount Brainiac like a boss (a three-headed, six-handed boss). It really opened my eyes to different forms of collaborative play.”

On the games development team, we’re excited by this congruity of values in our work and play—we have more success and more fun when we work together.

If you live in the San Francisco Bay Area and are interested in having your children participate in the Sifteo PlayLab, please fill out our survey or contact emily@sifteo.com. In the meantime, feel check out ABC 7’s coverage of play time in the Children’s Creativity Museum!

Thanks for the shout out We think you’re pretty great, too!

We’re sorry! Our pop-up store location has changed. If you are in the Bay Area and were planning to come by Mint Plaza to check out our store, please reroute to 2475 3rd St. #252. We’re still doing demos, selling Sifteo cubes, and giving away freet-shirts and gift wrapping.

Also, thanks so much to everyone who visited us in Mint Plaza! We had a great time playing games and getting to know you a bit. Please feel free to stay in touch with us on Facebook and Twitter–we’d love to hear from you!

10 hours of shooting in the Sifteo office and out and about San Francisco paid off! This video by Good.is featuring Sifteo co-founder David Merrill does a beautiful job of telling the Sifteo story.

“Sifteo co-founder David Merrill believes in the power of hands-on thinking. Using digital cubes, he explores how intelligent play and physical exploration with our hands stimulates cognitive learning. Defying the idea that technology creates a passive experience, Sifteo cubes engage users with games and encourage them to play and think nimbly with exploration-oriented problem solving.” See the full article on Good.is

Sifteo is a finalist for “Best New Gadget” in the 5th annual Mashable Awards!!! We’re up against some tough competition. Sifteo founders David Merrill and Jeevan Kalanithi discuss the reasons you should vote for Sifteo.

Vote today (and every day for the next 10 days)!

Note the voting button in the right column >>>>

10.) You like cracking puzzles more than you like re-watching The Nutcracker, and Sifteo cubes are perfect for that. With over 16 unique games with a wide range of difficulty levels, you’ll stay occupied for hours in your holiday downtime.

9.) Awkward (but awesome) family time: we all know how it goes. You love these guys, but you have to insist—again—that you won’t be joining Uncle Hurnold in his Slanket on the La-Z-Boy and if you have to play one more game of Yahtzee with Aunt June you’ll be seeing dice in your sleep. With so many fun, hands-on, and multi-player games, Sifteo offers more quality time, less awkward time. (And yes—less Yahtzee time.)

8.) The will to give gifts that people actually keep. The lines to return crappy gifts are practically as long as the lines to buy them. Order Sifteo cubes online and have more time for doing fun stuff.

7.) You’re way too indie for Apple…or at least that’s what you say when people wonder why you’re still using a Samsung flip phone that folds open like a book. No, not a Google Book, a straight up book. But Sifteo brings you gadgetry that rivals Apple’s awesomeness while allowing you to remain a persistent advocate of lifestyle alternatives. After all, Sifteo is a small, San Francisco-based start-up, and supporting the underdog is undeniably cooler than buying mainstream merchandise at any time of the year.

6.)    Drinking games, which you can make using Sifteo’s Creativity Kit. Trust us, this is easy. And amazing. Do not add eggnog. (Or do, and let us know how it goes…)

5.) Holiday nostalgia. It’s unavoidable: at some point this December, somebody’s going to pull out that photo album and pass around the pic of your mullet from 1984. Your relatives can laugh their well-groomed heads off—but hey, wasn’t that also the year Tetris came out? And doesn’t Tetris probably still rank in the Top 5 Gifts you’ve ever received, and didn’t it usher in a personal Golden Age during which you vanquished all contenders in your sibling rivalry? Sifteo offers classic play patterns and amps them up with the coolest technology available today (see reason #4).

4.) You wish to bamboozle your brother, to flummox your Luddite cousin. With the latest and most exciting technology, it’s easy to amaze even spaced out, sugar-overloaded and food-comatose friends and family with Sifteo cubes, which have been called “magical” as well as “the world’s smallest computer.” We find that the combination of LCD screens, wireless play, accelerometers, and proximity sensors tends to have that effect.

3.) Gene Autry, Jingle Dogs, Wham!’s “Last Christmas” (something from 1984 we really do wish could be forgotten), and every single existent version of “I Saw Mommy Kissing Santa Claus.” Of course, we love holiday jams, too—but selectively, and in moderation. For sanity’s sake, we think it’s acceptable to tune out on occasion. Sifteo currently has two games, LoopLoop and Planet of Tune, which allow you to make your own music. Enjoy.

2.) Blizzards. Like I said, we’re Californians. But we’ve heard that it snows in other parts of the world and we’ve even watched the plows exhume your residential roads on the evening news. We sympathize, so Sifteo’s proposal is this: put down the shovels, make some hot cocoa, and play with Sifteo cubes to beat your cabin fever, where ever you may be.

1.) You want to keep the kids happy, no matter what the holidays bring. It’s not like you’re a softy or anything, but you love to see their faces light up—and not just in the blue glow of the television, but with true, beautiful wonder and excitement. Sifteo does just that, period.