Anyone familiar with the board game? I just threw together an implementation in Java (humans only). Thinking about trying to do AI, but there are so many possible moves that I don't know if I'll even be able to get 3-ply search.
Unfortunately it's quite difficult. I have ideas, but I think it's a little beyond my meager AI studies. At the beginning of the game there are more possible moves than Go, which has confounded AI researchers for decades. I thought focusing on the endgame might help, but my efforts have yielded very little.
I remember learning how to play Go. Then I heard it was difficult to make a good idea for it, so I thought it'd make a good opponent for my inexperienced self. It completely destroyed me.
I think it'd be cool to have a Smiley themed Freecell game. You know, the card game. Have the smiley characters on the cards. Yeah, it has nothing at all to do with this topic. I just think it'd be cool. I have no idea what the hell Cathedral is anyway.
>At the beginning of the game there are more possible moves than Go
Really? Cathedral always seemed a bit simple to me. Most of the novelty was in the beautiful 3D pieces.
Also, while the beginning of the game might be open-ended, it pares down quickly once the board gets filled up. You might want to have the AI make a random best-effort early on. Hell, that's what I do.
Anyway, you should check out Blokus. It's very similar, but with a twist that makes it much more fulfilling than Cathedral.
http://www.blokus.com/
For an opening move, I suggest making a bee-line for the center.
Re: Cathedral
Never played it, but from reading the Wikipedia article, it sounds interesting. I bet an AI would be difficult though...