Any good card game AI strategies?

Question

What would be strategies for writing a good computer opponent for a card game? Most card games are games of incomplete information, so simply mapping out and traversing the game tree as one could do with a board game does not seem too promising.

Maybe one could track what open cards are in the game (as soon as they are revealed) and assign probabilities to certain events (e.g. opponent still has 2 cards of clubs).

Does anyone have experience with this? Links and directions greatly appreciated.

Answer 1

What you describe using probabilities is basically how poker AI (or a human poker expert) works. There's been an ongoing series on Coding the Wheel about creating a Poker Bot that you might be interested in reading.

Answer 2

If you are fine not having the most efficient bot out there I would use some logical language. And it get slower and slower the more generic you make the language, but could be a start.

The key element is to define strategies that you are interested and model this strategies in your logical language.

If you are thinking in a guessing game, for example, you could have two strategies:

strategy-1 guess the card you think is the most likely; or 

strategy-2 among the cards that are the most likely, guess the card that 

my opponent believes to be the most likely. 

Now your problem is to define the strategies in a formal language which you can interpret (you need a sound language).

Usually a language for such logic should be able to express basic probabilities, at least. For example a language given by the following form:

A = c | -A | A v A | A -> A | P(A) >= r | P(A) >= P(A) | \forall c . A(c)

for r a rational between 0 and 1. Read P(c) >= r to be 'the player believes that the opponent have the card c with probability at least r.'

For instance, strategy-1 looks like

Guess card C only if holds that 
\forall C'. P(C) >= P(C') . 

strategy-2 looks like

Guess card C only if holds that 
[\forall C'. P(C) >= P(C')] ^ [-\forall C''. P'(C'') > P'(C)]

(P'(c) is the probability assigned by my opponent).

If your strategy is given by the formula STRATEGY your function for action would be simply asking for a possible card that satisfies the strategy:

act gameState = take 1 [c : c |= STRATEGY]

This language that I gave as example is not expressive enough for expressing problems of hiding your type (strategies extremely important in games like Poker or HearthStone, for example). For strategies with that some extension would be needed.

Another common extension would be for Dynamical operators so you could express strategies like 'after the strongest card is defeated I hold the board.'

On your comment about 'track which cards are open,' it is limited in the sense that you do not consider what your opponent is thinking given your actions. Strategy-2 is an example of how to improve the computer with higher-order beliefs.

For a guessing game I suggest the paper called Logic of Pit from Ditmarsch. (http://link.springer.com/article/10.1007/s11229-005-4331-5) (it does not implement an AI, just express the game called PIT. I do not think it worth to pay for it. If you can get for free it worth it. Maybe you can look for his thesis, instead if it's free.)

I would love to write a paper on HearthStone but I never find the time :(

Answer 3

Another good read is the http://aigamedev.com/ site. It's very detailed and goes into code examples where it applies.

Answer 4

Again it's a blog, but an interesting one in this area is Computer Programming and Magic: The Gathering. If nothing else it's notable because of the very complicated programming, MTG has a sea of rules for the cards and because the author actually completed his first version of the program three years ago. Tons of game projects get no further than the planning stage.

The project he describes in his blog is open source so you can see if there's anything interesting to you there and he's very prolific about posting to his blog.

Answer 5

a concrete answer: implement the min-max algorithm with random events like drawing of cards containing propabilities instead of hard decisions.

Answer 6

You're right that traversing 'the' game tree won't work because you don't have enough information but if you generate several potential game trees and look at what options are more likely to result in better outcomes then you'll have an AI.

If you have the time you can do it exhaustively and generate every possible scenario but in reality you don't have 10mins to play a card so just do a small portion of the whole space.

I wrote a poker bot that did this and it played an ok game but I lost interest in it before I got around to handling positional implications so it was never strong.