Arimaa -- difficult game for computer to play

When I was playing a game of chess with asmael, I noticed a reference in his blog to Arimaa. Arimaa is a game that was created by a computer scientist and by design it is difficult for computers to play well. Arimaa has a high branching factor (makes brute force search difficult) , has a randomized setup (makes opening book less effective), and games have relatively few captures (makes endgame tables less relevant). I've not played Arimaa yet, but I love the theory behind it. Incidentally it's playable with a standard chess board/set.

 Here's a pointer to the wikipedia entry:
http://en.wikipedia.org/wiki/Arimaa

 The official website has some cool papers if you want to study the theory:
http://arimaa.com/arimaa/

 Kudos to asmael for pointing this out.... he's gone now (banned for spamming(!)) so I'm trying to keep the fire alive for arimaa.