• Create Account

## Creating an AI for a CCG

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

9 replies to this topic

### #1Navyman  GDNet+

7020
Like
0Likes
Like

Posted 30 July 2014 - 04:10 PM

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.

Developer with a bit of Kickstarter and business experience.

### #2jefferytitan  Members

2508
Like
3Likes
Like

Posted 30 July 2014 - 05:49 PM

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.

### #3Álvaro  Members

20268
Like
2Likes
Like

Posted 30 July 2014 - 07:23 PM

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.

### #4Navyman  GDNet+

7020
Like
0Likes
Like

Posted 31 July 2014 - 04:48 AM

@ 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?

Developer with a bit of Kickstarter and business experience.

### #5Álvaro  Members

20268
Like
1Likes
Like

Posted 31 July 2014 - 05:10 AM

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.

### #6LorenzoGatti  Members

4089
Like
0Likes
Like

Posted 01 August 2014 - 01:37 AM

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, 03 August 2014 - 11:48 AM.

Omae Wa Mou Shindeiru

### #7Orymus3  Members

18543
Like
1Likes
Like

Posted 01 August 2014 - 05:50 AM

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'?

-=- My Articles -=-
Getting Games Done - Method and tools on how to start a hobby project and get it Done!

The Art of Enemy Design in Zelda: A Link to the Past - Reverse-engineering functional enemy design from applied example.

Retro Mortis - "RTS" - Article Series (4 Parts) on the history of RTS development (4th part finally released!!!)

### #8Navyman  GDNet+

7020
Like
0Likes
Like

Posted 01 August 2014 - 06:18 AM

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.

Developer with a bit of Kickstarter and business experience.

### #9Orymus3  Members

18543
Like
1Likes
Like

Posted 02 August 2014 - 08:56 PM

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

-=- My Articles -=-
Getting Games Done - Method and tools on how to start a hobby project and get it Done!

The Art of Enemy Design in Zelda: A Link to the Past - Reverse-engineering functional enemy design from applied example.

Retro Mortis - "RTS" - Article Series (4 Parts) on the history of RTS development (4th part finally released!!!)

### #10Navyman  GDNet+

7020
Like
0Likes
Like

Posted 13 August 2014 - 01:40 PM

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.

Developer with a bit of Kickstarter and business experience.