Best techniques for an AI of a card game

Question

I’m trying to develop an AI for a card game and I’m a bit stuck about the technique/algorithm I should use. Here are a few assumptions about the game:

• After the cards are distributed to players, there is no randomness. I mean here that every player can choose which cards he plays but no random process occurs as when distributing the cards at the beginning of the game.
• There is restriction about the cards which can be played when a card was already played.
• The player which wins the trick, plays then first. E.g. Player 1 plays a card, Player 2 plays a card and wins. Then Player 2 plays a card and then Player 1 plays.

I know a lot of hints/rules (e.g. if I know the player has cards A, B, C then I should play D) which helps me to win to the game. Thus I first wanted to use a Bayesian network to describes those rules. The problem is that I don’t know any probabilities to assign, but I could compute an heuristic using the history of played games (against a human). Second problems, it is very likely that I don’t know all rules and that there is some implicit rules which are needed by the AI to find the optimal play.

I’m unsure if this would be a good way to develop an AI for such a card game?

I am also wondering if there is others techniques which would best fit to the problem. For instance, I had a look at minimax (maybe with a pruning algorithm), but would be a good option for this problem? I’m quite unsure since the most important plays are at the beginning of the game when there is the highest unknown parameters (most of cards are not played yet).

Answer 1

Your example sounds similar to Bridge. Top Bridge-playing systems use Monte Carlo methods to select moves. At a high level:

• Determine the probabilities of each card being in a given hand. You know with certainty which cards are in your hand and which cards have been played. Determine the probability of all other cards based on cards that have been played and possibly a player's bid if there's bidding involved. To start, you could just use a naive and equal probability that a card is in some player's hand.
• Now, run through as many "virtual" games as you can. Simulate playing a card from your hand and then determine your opponents' responses using the rules of the game and your probabilities. For each virtual game, use your probabilities to assign cards to a player and then quickly simulate the game. Assume each player will play to the best of their ability. You know all the cards in your virtual game so you can make each player play perfectly.
• When you have a solid sampling (or you run out of time), pick the legal move that gave you the best outcome most often.

Once you get something working, you can add all sorts of enriched strategies. For instance, vary your probabilities based on a player's historic plays, vary probabilities based on a player's style (passive, cautious, aggressive), or even consider the effects of specific players playing together.

---

Edit per LaurentG's comment:

Ultimately, you may want to scrap the idea of perfect play for all players and substitute something more realistic. Conceptually, separate the probabilities for a card being in someone's hand (card distribution) from the probability of a player playing a given legal card during a hand (card selection).

Card selection is ripe for learning. If you track plays across games, you can learn how a given player, or players in general, tend to play based on the cards in their hand and the cards that have been played. You could even get fancy and model their assumptions about cards hidden from them.

There are also learning opportunities for card distribution. A player's past bids and card selection during a hand might reveal a "tell" about what's hidden in their hand. You could use historic data to adjust probabilities when building each virtual game.

Answer 2

A case of recent personal experience:

I've been working on a card game myself (Bisca, a 2-player Portuguese game), and I've been getting good results using Monte Carlo methods, specially using the recent Information Set Monte Carlo Tree Search algorithm (ISMCTS, described with example source code in Python at http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm).

It plays reasonably well, with the ocasional incorrect move, just with the knowledge of game rules. I'm currently trying to grok it, to be able to enhance it, as according to the information I've read about it (and its "parent" MCTS) it's possible to enhance its game play with heuristics (http://www.orangehelicopter.com/ed/papers/aiide13.pdf) and opponent card inference.

Answer 3

I think it depends on the rules of the game.

Here's what I understand from your question :

• The game is played in rounds, with each player playing one card per round
• The player who goes first can play any card he wants
• The player who goes second can only play certain cards, depending on what was played first
• The player who wins the round goes first the next round
• All the cards are distributed before the first round

Assumptions :

• With full knowledge of the other player's cards, the player going first can decide, for each of his, whether a card will win the round or not (first player can play a sure win card)
• If card A and B will both win when played first this round, playing A this round (and winning) then playing B the following round means B will win too (cards don't lose value)
• With full knowledge of the other player's cards, the player going second can decide if a card can win this round, but would lose if played first the following round (chose the worst winning card)

Example game that follows these rules :

First player plays a card. Second player has to play a card of the same suite or lose. If suites match, highest card wins.

Now, this game is decided by luck of the draw and by being able to memorize what cards have been played in order to know your opponents hand.
In this situation, I'd make the AI only partially remember what cards were played, i.e. randomly remove from the remembered list some percentage of the cards played (lower number = higher difficulty AI), but not important ones like Aces or Kings. This way, for example, the AI will know it's safe to play a Queen of Hearts because he will remember the opponent doesn't have the Ace or the King, but will have to calculate a probability if he wants to then play the 10, because he might not remember if the Jack is still in play.
This mimics human attention span.

TL;DR
Limit how much the AI knows so its decisions are not perfect, just good enough.