Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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.

  • You cannot reply to this topic
9 replies to this topic

#1 Navyman   Crossbones+   -  Reputation: 4049

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.

 

Thank you in advance.


Developer with a bit of Kickstarter and business experience.

34410.png

Sponsor:

#2 jefferytitan   Crossbones+   -  Reputation: 2220

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   Crossbones+   -  Reputation: 13645

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.

#4 Navyman   Crossbones+   -  Reputation: 4049

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.

34410.png

#5 Álvaro   Crossbones+   -  Reputation: 13645

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.

#6 LorenzoGatti   Crossbones+   -  Reputation: 2734

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.

Produci, consuma, crepa

#7 Orymus3   Crossbones+   -  Reputation: 9938

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



#8 Navyman   Crossbones+   -  Reputation: 4049

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.

34410.png

#9 Orymus3   Crossbones+   -  Reputation: 9938

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



#10 Navyman   Crossbones+   -  Reputation: 4049

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.

34410.png




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.



PARTNERS