1
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Do you have a license from PlaidHat Games to use their intellectual property? \$\endgroup\$ – Philipp Oct 26 '14 at 0:58
  • \$\begingroup\$ possible duplicate of How would one approach developing an AI for a trading card game \$\endgroup\$ – Philipp Oct 26 '14 at 1:00
  • \$\begingroup\$ @Philipp I have looked at this question (and others) before but I don't think the answer is really applicable here. In a TCG like Magic the number of possible actions in your turn is relatively low, so you can go with min-max. The 8x6 battefield in this game makes this a lot more difficult here because it increases the possible moves a lot. \$\endgroup\$ – jods Oct 26 '14 at 10:10
  • \$\begingroup\$ @Philipp as a specific example: in Magic you can try to play a wall card from your hand or not. -> 1 action. In Summoner Wars, if I choose to play a wall I have to decide where I put it, which is approx. 20 possible moves! And this choice has very important consequences for many aspects of the game. A good AI would have to pick the location very carefully. \$\endgroup\$ – jods Oct 26 '14 at 10:13
1
\$\begingroup\$

MCTS can work very well for this kind of game; the principle advantage is that all you have to do is implement the rules, and all the behavior that depends on their complexity is automatically included. MCTS is not troubled by randomness, hidden information, or a large decision space. My AI for "Euphoria" at Boardspace.net, plays as well as most human players.

Randomness (dice rolls, card draws etc.) and hidden information (opponent choices you do not know the value of) are handled by re-randomizing at the top of the move tree before each random game.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. As I wrote in my question I considered MCTS, which looked very promising (especially the "rule-independent" part). It is my understanding that you have to simulate the game to its end with MCTS... How would you do that with a game whose most important component is a tactical combat on a 8x6 grid? Also, what do you mean by re-randomizing? How do you handle an unknown combat outcome based on dice rolls? \$\endgroup\$ – jods Oct 27 '14 at 20:24
  • \$\begingroup\$ Replace all the cards which you don't know the value of with another card from the set of possible values. Change the seed of the random number sequence so you get a new and different sequence of rolls on each simulated game. You do not need to simulate all the way to the end, just to a point where you want to stop, and use any reasonable proxy for "winner" at that point. \$\endgroup\$ – ddyer Oct 27 '14 at 20:30
  • \$\begingroup\$ OK. Yes simulating just a few turns and evaluating the board at that point is totally doable in my case. How would you simulate though? From what I read you should play 'randomly' but I think that in a very tactical game doing random moves is not going to be very helpful? \$\endgroup\$ – jods Oct 27 '14 at 20:34
  • \$\begingroup\$ Read up on MCTS. Do play randomly, but 100,000 random games will give a pretty good idea what the best move is. \$\endgroup\$ – ddyer Oct 27 '14 at 21:17
  • \$\begingroup\$ So I did implement MCTS on the basics of the game. There are several tricky issues but the main one is that one AI turn is just too many combinations (even with RAVE optimisations) to be efficiently explored and find out a good sequence of moves. I'm doing 100,000 games, it's not fast and the result is not a strong AI player. I think the approach could work but it would need a lot more games, which wouldn't be 'playable' given the required processing time. \$\endgroup\$ – jods Feb 28 '15 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.