26

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

  • 1
    Great question! Don't have a complete answer. I'd just like to add my 2c: if you know all the possible states your game can be in, then Minimax would theoretically be a good way to traverse that game-states tree. Could get into performance issues if that game states tree is too large... – Shivan Dragon Oct 9 '13 at 11:45
  • 1
    What is the goal of the game? Who wins? Could it be possible for a player to approximate his/her chances of winning the game at any given time? – COME FROM Oct 9 '13 at 13:08
  • I can't explain in details the game. To win one have to get the highest number of points (more than the other player). At the beginning, it is hard/impossible to say if we are going to win. At the end, we can be sure that to win if one has already enough point (the other player cannot win enough points anymore to win). – LaurentG Oct 9 '13 at 13:12
  • 1
    Is the game HeartStone ? :) – Lescai Ionel Oct 9 '13 at 13:59
  • 1
    It looks like I'm in a very similar situation to you, also card game, also local one (not Switzerland though) and I'm also trying to understand where I start. One thing that I found interesting is an evolver, where you assign DNAs to virtual players, and then pit them against each other. You kill the loosers and you breed the winners. The result could be quite decent AI bots. I have not figured out how adapt this tropiceuro.com/puerto-rico-evolver for my card game but I think this is possible. – Andrew Savinykh Dec 5 '13 at 23:44
11

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.

  • Thank you for your interesting answer. You are right, the game shares a few rules with Bridge. As I understand, your AI will not be better that what you coded. Is there a way to use a Monte Carlo method and make the AI learns? Would it be possible to assign the probabilities for each card using the past events (of all previous games)? – LaurentG Oct 9 '13 at 13:59
  • You can definitely make the AI learn. The trick would be to separate probabilities for a card being in a particular hand from the probability of a player playing a given legal card once it's in their hand. I'll elaborate above. – Corbin March Oct 9 '13 at 14:31
6

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.

  • 1
    this post is rather hard to read (wall of text). Would you mind editing it into a better shape? – gnat Jan 14 '14 at 18:48
  • thanks for the answer from someone with real experience on the problem. great links! – luben May 15 '14 at 16:40
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.

  • Thanks for your answer. But as said in the question, there is no luck / no randomness after the cards are distributed. And a player doesn't know the cards of other players. He must make assumptions using the already played cards and some "rules". – LaurentG Oct 9 '13 at 12:54
  • 1
    Like the idea of randomly removing memorized cards. This gives a hint on development of levels like easy, medium and hard. – superM Oct 9 '13 at 13:06

protected by gnat May 25 '16 at 8:21

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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