Trading Card Game AI

With a card game, the uncertainty factor introduced by not knowing what cards the other person will be able to play makes a basic search algorithm like minimax pretty difficult to do well, I''d expect. Therefore truly looking at every possibility would be next to impossible.

If, as in Magic the Gathering, there are generally not all that many things you can choose to do in a certain turn, it may be possible to simply consider each possible option in the current situation and evaluate it according to a few heuristics. You may have to start getting into probabilities if you need some sort of look-ahead, to take into account that you may not know what card will be drawn.

But as I said in another thread recently, it''s hard to give any kind of advice without knowing the rules in more detail because there is no "one size fits all" AI algorithm, unless "find the best choice and execute it" counts. As always, your main issue is to find a meaningful representation of the game state, and from there look at ways in which to change the state for the better. To do this usually requires domain-specific knowledge, which in this case might be the value of different cards, the victory conditions, etc.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

I suspect the current trading card games (especially in the
case of the recent Yu-Gi-Oh games) do not go about this problem
from the "academic" angle.

What I mean is, they didn''t program the AI to strictly look at
its own hands and decide what to do next. Probably, they
let the AI "cheat" a little and use the human player''s hand,
even snooping at the undrawn card deck.

A game tree can thus be made of all the possible outcomes.
Then it''s just a matter of choose the "best" course of action
using some game-specific heuristics.

To offer different levels of difficulty, the AI can stop
evaluating the game tree at a certain depth. Obviously, the
deeper it looks, the "better" an opponent it''d be.

Oh yeah, this looks like traditional chess AI, doesn''t it?

Sure, sure, you call this cheating. But since we''re just
making a game to entertain people. It''s no big deal. Making
the game appear to have intelligence is more important
than have "true intelligence".

---

Kami no Itte ga ore ni zettai naru!

tangentz raises a reasonable point... do you want to create an AI that plays with the same/similar information that the human player receives, or do you want to permit it to cheat.

On a philosophical level, I HATE games that cheat. If it isn't smart enough to beat me with the information that I get, then it's a waste of my time and money... this is why I tend to play multiplayer games these days... game AIs are just too boring.

A player faced with a cheating AI in a card game would become very frustrated very quickly. However, it's probably a good place to start your AI from... give it as much information as it needs to be able to play perfectly and then decrease the information to degrade its performance.

Alternatively, take a look at the Bayesian Poker Player designed by Kevin Korb. You can get some info from his website at Monash Uni. Alternatively, the Univ. of Alberta Games Research group also have an excellent automated poker player. Now, I know Poker isn't MTG or the like, however the problems faced are the same: how to make decisions under uncertainty, how to evaluate the 'goodness' of a hand, etc., etc.

Good luck in your endeavour.

Timkin

[edited by - Timkin on January 19, 2004 10:00:44 PM]