Incomplete information card game

Question

I would like to develop a trick taking card game. The game is between four players, one of which is a human and the other three hands are played by the computer.

Where can I read up about developing the AI for such games?

Answer 1

Artificial Intelligence: A Modern Approach (2nd Edition).

@binil See the table of contents. There is a whole chapter on topics such as Problem Solving and Uncertain Knowledge and Reasoning. In general, I think you can benefit from understanding the basic structure of modern AI: AI as an agent approach.

Answer 2

AI is just one of those terms that seems to be different between what it originally was and what the media (even computer game media) portray it to be.

Are we talking about making a genetic learning algorithm that you run a million times to develop its intelligence?

Usually with card games having simple rules, you can hard-code the "smarts" yourself and get the computer players to make a decision based on the state of the game. Not really AI but a NPC (non player character).

Answer 3

@Mark Galorie: You are right, my current aim does not involve any machine learning. The game invloves an initial "bidding" where the "mood" of the current set of players and overall score has to be taken into account. I am hoping that some reinforcement learning techniques can help there. But at this point, that is far out into the future.

Nonetheless, from my limited understanding of the term, I think it is still fair to call this "AI". A player does not know what cards are held by other players. There are heuristics which help guess what cards might be held by others based on past tricks - these can be expressed as probabilities. Based on these probabilities, a player decides what card to play next. This is approximately how humans play the game - I want to automate this process. Heuristics used by humans might be more involved than what can be programmed, but I am hoping that that will be offset by the perfect memory programs have. My question was if anyone is aware of example code, papers or books tackling such a situation.

Answer 4

You could try to just let the computer player to randomly pick out any valid move. Test that it actually does play validly (but somewhat halfwittedly). After that you could build on top with more complex rules and moods.

Answer 5

I'm currently writing two board/card games that have (or will have) AI opponents. I don't have any algorithms for you to reuse, but I can strongly recommend the Strategy pattern, which as Wikipedia explains can be used in many programming languages. This will make your AIs pluggable, so that you can write a dumb one initially, just to get your program working, then write more capable ones as time permits. If you publish your strategy API, you can even invite other fans of the game in question (easily found via fan sites like www.boardgamegeek.com) to contribute their own AIs. I hope this isn't teaching you how to suck eggs.

Also check out the AI page at GameDev.net.

Answer 6

An additional answer in the spirit of the question you asked:

Read up on game theory if you haven't already. This is what you will find some good answer on how to implement any sort of incomplete information algorithm. Your probably going to end up making a big branching tree and assigning expected values to different outcomes.

And to make things more interesting, if your tree of possible outcomes is big enough and your CPU limited enough you will want to read up on algorithms to stop evaluating branches earlier (or use some sort of A* type of evaluation to decide which branches to pursue first)

At the star tof the game these trees might be prohibitively large, for these cases a simple rule of thumb expert strategy will probably work well, based on an estimated value of cards in hand high-low spread or whatever you find appropriate.

Answer 7

You might be interested in the techniques used to create GIB, a bridge playing program. The game of bridge is played by four players, has a bidding stage followed by a trick taking playing stage and might be similar to what you need.

Here is an article: GIB: Steps Toward an Expert-Level Bridge-Playing Program

At the end in the references, lookup Partition Search authored by the same author. Link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.9799