Last post I mentioned that Distributed Neuron would be playing a game.  In this post, I’d like to explain a little about that game: Arimaa.

Arimaa is a unique board game in that it was created specifically to be difficult for computers to play.  It was created by Omar Syed after witnessing Deep Blue beat Kasparov at chess.  Many in the field of AI felt this “win” was not really a win for machine intelligence.  Deep Blue won not because it was more intelligent, crafty or clever.  Rather, it won through sheer bruteforce, searching through the huge tree of possible moves for the best one.

Arimaa is vaguely similar to chess.  It was designed to use the same board and even the same pieces if you don’t have custom ones.  The similarities end there.  Unlike chess, it was specifically designed to be difficult for computers to solve.  It is obvious that Kasparov and Deep Blue operated on entirely different principles.  Kasparov was making his moves through pattern recognition, an understanding of the game and intuition.  It is said most humans can only plan for 2-3 moves into the future.  And even that does not take into account all the possible moves, just the likely ones.  Deep blue had the advantage of being able to look at all moves.  While this technically allows you to win the game, it doesn’t lend much to the field of machine intelligence.

To combat this Arimaa was designed so that the search tree would be so incredibly massive that no computer could feasibly search through it all, regardless of the increases in computing power.  For instance, chess has 20 opening moves.  Due to the unique rules of Arimaa (multiple moves per turn, custom starting lineup, etc) there are from 4000-5000 opening moves.  As the game progresses, the possibilities can skyrocket as high as 40,000 moves to consider per turn.  A member of the Arimaa community has formally graphed the branching factor of Arimaa, which can be viewed here.

So why am I applying Distributed Neuron to Arimaa and not something else?  I considered a lot of possibilities.  Working on a car simulation (somewhat akin to a virtual version of the DARPA Urban Challenge) tickled my fancy for a while, as did a Go playing bot.  I really want to eventually apply DN to simulated agents living in a simulated environment but feel DN needs some work before that can happen.  So why Arimaa?  Firstly, it was designed to be difficult.  Secondly, the developer has made the game and framework incredibly developer friendly in attempts to get people to write bots.  There is a large amount of documentation and supporting software to help developers.  There is also a friendly forum full of bot developers willing to help.  And lastly, there is a prize sum of nearly $10,000.  Which I’m sure my student loans would appreciate. =)

I encourage everyone to go check out the game.  Arimaa is a lot of fun to play by itself and even more intriguing to think about in regards to bot development.  Hopefully I’ll have a working prototype of DNA (Distributed Neuron Arimaa) soon.  I just started working on the genetic algorithm / GUI client last week.  Presumably another few weeks and there will be a working prototype to tweak.

Onwards!

A lot of the critically important code in a project is often the most boring.  It is the infrastructure that keeps the cogs greased and engine purring.  Unfortunately for me, that is the body of work I’ve been working on.

A great deal of code has been added to round out the project.  It is finally starting to take shape, the end is in sight.  Perhaps a small dot on the horizon but in sight nonetheless.  Before the summer started, the project consisted of code to manage and run a brain.  It was essentially a brain in a jar with nothing attached.  Of the code I’ve written so far, this was the most fun to work on.  I was able to flesh out my theories on the mind, distilling various representations of biological neurons into simpler digital analogues.

But no brain can survive in isolation, a body is needed.  I’ve been hammering out code to add a “body” of sorts to the brain code.  And unfortunately this code is rather boring, a matter of processing inputs and outputs, directing data to various parts of the brain, etc.

Bodies, like brains, need a place to reside.  After a long, drawn out decision process I have finally picked the environment for the first tests to take place.  Instead of a traditional simulated environment seen in Artificial Life simulations (ie. a simpler version of the real world), I have chosen a boardgame.  I’ll discuss the particular boardgame and my reasons for picking it at a later date, but for now suffice to say it will be a good proving ground for my theories.  The “body” of the brain has inputs to process the gameboard and outputs to manipulate the pieces of the gameboard.  There are also inputs to watch stats like score and whose turn it is.

It should be noted that while code has been implemented to allow the machine to play the game, no rules about the game have been included.  There are no mechanisms to prevent the brain from making an illegal (or illogical) move.  If an illegal move is made, the server responds with a nasty “shame on you” message and the machine must try again.

The next step is to begin working on the genetic evolution algorithms.  Then add a mountain of plasticity-related features to the neurons.  Then implement more variables in the genetic code rather than hardcoded values.  Then the code to support distributed computation.  Then profit?  Hah.

Onwards.