Sign in to follow this  
Navyman

Creating an AI for a CCG

Recommended Posts

Navyman    9781

I have read a few posts about using a Monte Carlo Tree Search. While I understand the basics I am at odds on how to put the idea into motion.

 

If there is anyone that could shed some light on the possible options / methods it would be most helpful.

 

Thank you in advance.

Share this post


Link to post
Share on other sites
jefferytitan    2523

What aspects are giving you trouble? I am not an expert, but to get started I would say:

  1. Create a system for generating all valid moves for a node.
  2. Start exploring from the root node.
  3. Use some weighted random function to select a leave node to expand. In general I would say favour winning nodes (for whichever player you are simulating).
  4. Whenever you reach a win/lose state, propagate the win/loss statistics back up the tree.
  5. When you choose to stop the search (time limit? number of nodes explored?) choose the move with the best win/loss score.

Check wikipedia for much more in depth analysis.

Share this post


Link to post
Share on other sites
alvaro    21246
Most card games have the added wrinkle that you can't see what cards your opponents have. I would start by writing an AI for a version of the game in which all information is public (everyone plays with their hand open). You can implement Monte Carlo search without the "tree" part, because it's easier and because the tree part is nearly useless for the full game (with hidden information).

One way to handle hidden information that is theoretically sound consists on generating random card distributions that are consistent with what has happened in the game so far (trying to not introduce biases) and using Bayes's formula to compute their likelihood, given a probabilistic model of how players pick moves (you can start with a model that gives all moves equal probability, but your program won't be very good at guessing the opponents' hands). Play the rest of the game normally (as you were doing in the previous paragraph) until you reach a terminal state and update the statistics for your first move, using a weight that is the likelihood of the card distribution.

Share this post


Link to post
Share on other sites
Navyman    9781

@ Alvaro Okay the hidden information was that part that was upsetting my mental design for the AI. However, if you are able to play multiple cards in a turn would this still require the tree to be formed to allow the AI to decide which order to play?

Share this post


Link to post
Share on other sites
alvaro    21246
If you play multiple cards in a turn, you can think about it as taking multiple turns in a row, and it would make perfect sense to use a technique like UCT to build a tree in that case. Once it's someone else's turn, keeping a tree becomes hard because you have a different card distribution each time.

Share this post


Link to post
Share on other sites
LorenzoGatti    4442

Typically, a "turn" in a CCG isn't a "turn" in the traditional game tree usage of the word, but a sequence of many AI turns of different types.

Taking Magic: the Gathering as a reference, every time a player passes priority to the opponent to answer his move it is one turn in the game tree, even if the other player's move is doing nothing (which in many cases is the optimal choice). Some of these turns are special actions (e.g. declaring attacking and blocking creatures), some are game state changes without player decisions (e.g. resolving spells and abilities, combat damage steps, state based actions) and some consist of composite moves (e.g. playing mana abilities as you play a spell or ability, or stacking several spells and abilities without passing priority).

Edited by LorenzoGatti

Share this post


Link to post
Share on other sites
Orymus3    18821

Is the opponent's deck 'fixed'? If so, there are a few ways you can cheat at this.

Also, are there complex interactions? (cards that strengthen others) or are most cards single-use/consumable effects or permanent 'lone wolves'?

Share this post


Link to post
Share on other sites
Navyman    9781

 

 

Is the opponent's deck 'fixed'?

 

I have not decided to set the deck and card order or allow it to be random card order. Writing the AI for a fixed card order would be much easier, because it would only require a few sets of switch gates to handle the card play order.

Share this post


Link to post
Share on other sites
Orymus3    18821


Writing the AI for a fixed card order

 

I meant, is the deck content fixed? Or are the possibilities finite? CCG implies your enemy could have pretty much any kind of deck, so I'm assuming you want to have an AI that can handle all possible outcomes and weigh their relative values, but if you build opponent decks as with a single player linear progression, you could nudge your AI in the right direction with every level by making it understand the core concept of how to play the deck (somewhat hard-coded) and limit your efforts with actual AI (instead of creating an AI that has to know and master every subtlety and synergy of the entire card library).

Share this post


Link to post
Share on other sites
Navyman    9781

I have redefined the method by which the Battlefield data is handled and now the AI has better access to the information. This hopefully make it easier to make the AI to select the better actions.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this