... .  .    .       .joeberkovitz.com

Not-So-Deep Blue: A Flex2 app that plays Connect Four

April 8, 2006 on 2:15 am | In Flex | 7 Comments

About a month ago I was curious as to how fast the new AS3 virtual machine was, and I was also playing a lot of Connect Four with my girlfriend’s kids — and losing. I’m pretty terrible at visual games. I decided it would be fun and instructive to hack up a Flex 2 app that played Connect Four really, really well. It would also be my revenge on the kids :)

And so I did. Play the game or check out the source. It’s not easy to beat — the program considers thousands of positions per second! There are also some fun graphics and sound effects. You can ratchet the strength of the computer player up and down and look at a visual representation of the game analysis, too. You’ll need Flash Player 8.5 Beta 3, downloadable from Adobe Labs.

Here’s a screenshot:

I wound up doing a bit of research on game theory…. There’s a lot out there, but an article in the Stanford Encyclopedia of Philosophy helped me out quite a lot. There’s a lot to think about, but here are some highlights.

Connect Four is an example of a so-called zero-sum game, in which any player’s advantage is the other player’s disadvantage. In these games, a concept known as Nash Equilibrium is sufficient to determine the best course of action for a player in any particular game state. (Yes, it’s the same Nash as in “A Beautiful Mind”, which I have never seen.) Roughly speaking, a Nash equilibrium for some game is some strategy for which any change by a player makes their situation worse. To find this strategy for a zero-sum game is straightforward: one can recursively build out a tree of possible states, assigning a score to each one from the vantage point of the player who made the move that led to that state. The score at any state is the inverse of the best possible score that an opponent could make in any of the possible subsequent moves, assuming that each player does their best.

In a world of infinitely fast CPUs, one would recursively score a game tree all the way to its leaves — the point at which someone wins. In reality, you stop after recursing some number of levels and apply a heuristic to determine a “positional score”. My positional scoring algorithm simply totes up the number of sequences of consecutive tokens, anywhere on the board, using some simple weights so that longer runs count for much more than shorter ones.

In ActionScript3, I used a bunch of tricky bit-field operations to represent game states very efficiently for scoring purposes. As a result (and also due to the impressive gains in speed in AS3 over prior Flash players) the computation really screams.

But, best of all, and a bit unexpectedly, I’ve become a much better Connect Four player, unaided by any machine. That might be the best revenge of all.

Random notes:

- Don’t bother setting the strength higher than around 6 (you’ll probably run out of heap space). Even with the strength at 2 or 3, the program plays pretty well.

- The app doesn’t know when a draw has been reached.

7 Comments