I am thinking of creating an AI for the card/board game Summoner Wars (by PlaidHat Games). It's a very nice tactical game for two players, with simple rules but quite deep.
I have considered min-max trees, Monte Carlo Tree Search (UCT), expert systems (i.e. a set of coded rules/behaviors) but I don't think any would give a good result.
Here are the facts that make creating an AI difficult:
1. The basic rules are simple, but each card has its own twist/exception on the rules. The game is of the expandable card game kind.
This makes it hard to use an expert system. Because of their cards' special rules, some factions play very differently from each other. Coding a strategy for each faction doesn't scale as the number of factions increase and simply doesn't work with custom-built decks.
Because of that, evaluating the board position without simulating what the opponent could do is very hard as well.
2. The number of possible actions is too big.
The cards are played on a 8x6 grid battlefield. During your turn you can summon new units, play events (sometimes with a choosable target), move up to 3 units, attack with up to 3 units and discard cards from your hand. Exploring all the possible ways you can do this stuff is just too expensive. You definitively have to prune your search tree (for a min-max AI).
3. It's hard to evaluate actions without thinking about the future.
It's hard to prune "bad moves" because depending on your cards (and your opponent's) some seemingly stupid or useless actions can be key to victory.
For instance, some human players kill their own units (a bad move in the short term).
Other example: the last phase of the game allows you to discard some cards from your hand to build more magic. That's key to be a good player but very hard to decide. Do I need more Magic? How much? Discarding more cards exhausts my deck faster (which is bad). And if yes: which ones? (knowing that I won't be able to play them.) And of course this is even twisted by the fact that some factions love to discard more cards because of some special effects.
Also, because the rules actually depend on the cards being played, you can't easily evaluate the position at the end of your turn. You also need to simulate your opponent's turn to see if some special abilities may ruin your position.
In my opinion, 2. and 3. make a min-max tree search unsuitable.
4. It's a game with hidden state.
There are the shuffled draw piles, your opponent hand... I don't mind if the AI "cheats" and looks at them, but it must not be obvious to the player! For instance there are some events that you can only play if you have less units on the battlefield that your opponent. It would be very annoying if the AI played aggressively all the time... and kills its own units to reduce headcount just the turn before I draw one such event!
5. It's a game with randomness.
Drawing cards of course, but I don't think this is a key factor for the strategy. Especially since most cards in the draw pile are the same. On the other hand, combat is done with dice. So if the AI decides to attack a unit, it's hard to say what the outcome will be (with which probability). Especially since many cards in play may change the actual rules regarding this (like: the number of dice rolled, change the value on some dice, remove one die roll, allow re-rolls, change the threshold value for a hit, and so on...)
MCTS was promising, but I have 2 issues with it. First how to handle the random aspects (dice rolls). Second, no paper on MCTS points it out, but I think that it only works well for games where every move brings you closer to the end of the game. Playing Summoner Wars randomly can easily result in an unending game (moving units around on the board)!
I know this is a long question, but does anyone have any idea how to write an AI for such a game? The goal is not to be a perfect player, but to provide a challenge to a human... and the game is very subtle, tactical and precise (for a human player at least).
