Board Game AI (Cathedral)

ID:151783
 
Apr 15 2009, 8:35 am
I'm looking around for AI approaches for the board game Cathedral. I've got a few ideas but nothing concrete yet.

Does anyone have suggestions for the type of AI approach that might work best?

I'm thinking about using 'Influence Mapping' but I'm not sure if it's the right solution for Cathedral.

I'm not even sure if it's feasable to make a decent AI for this board game.

If you have experience at playing this game, I'd like to get your insight on game play. What kinds of human 'trickery' is involved to win a game?

ts





Apr 15 2009, 9:49 pm
Sounds like Go. You have 100 possible moves on the first turn, if I'm reading the Wiki description correctly, which suggests a minimax-based approach is inappropriate due to combinatorial explosion - that is, unless a whole bunch of those moves can be dismissed by a simple heuristic.

I'd suggest looking up how AI for the game Go is written. Similar approaches would probably be required.
Apr 16 2009, 8:20 am
In response to Jp
Thanks for the pointer, I'll take a look at lunch today.

ts
May 31 2009, 6:41 pm
In response to Jp
Jp wrote:

I'd suggest looking up how AI for the game Go is written. Similar approaches would probably be required.

I've heard that they can't figure out how to write an AI for it. They've asked expert players why certain moves were "god" or "bad", and they said they just fwlt they were. So, yeah...
May 31 2009, 9:23 pm
In response to Guy Hendricks
Given that there are AI Go players, you're wrong.

The problem is that Go is not terribly amenable to modern AI methods. The statespace is absolutely huge, so minimax is basically worthless - there's a large number of legal moves each turn. Additionally, a number of Go rules require solving NP-hard problems.

The current crop of AI Go players can beat amateurs. With a handicap going its way, they can beat relatively low-ranked professionals. They don't have a hope against really good players, though, even with massive handicaps their way.

But this 'cathedral' game sounds much simpler than Go, so the same techniques will likely apply with better results (Because of the smaller statespace and less NP-hard stuff).