I'm a game designer working with a set of coders trying to create a card game. Currently we're trying to implement a drawing mechanic in which you choose which card you draw, but the Adversarial Search AI can't keep up with that many choices and can only look two turns ahead without this new mechanic. I'm pretty set on finding a way to make this work, does anyone have and alternatives to fixing this problem?

I've tried reducing the space down to having only a few choices out of the deck, but the problems comes from the AI having to see what the player is going to draw. I'm pulling my hair over this problem, any thoughts?


It seems you're using the Minimax algorithm, is that correct? If you already didn't, you should at least implement Alpha-Beta pruning in order to reduce the number of explored branches of your game tree. If it is not enough, the task at hand may be more suited to MCTS, which is used in Go due to the large branching factor, just like the one you describe.

  • \$\begingroup\$ As far as I'm aware, our AI guy was talking to us about all the things you mentioned. Apparently this game we're making has a higher branching factor as currently it can only look two moves ahead. With the ability to have a deck and draw from it he said that we would be able to look one move ahead. \$\endgroup\$ – user5262541 Mar 6 '16 at 0:55
  • \$\begingroup\$ How many cards in the deck? \$\endgroup\$ – rcpinto Mar 6 '16 at 4:55
  • \$\begingroup\$ we're playing around with 10-20, but it varies since the deck size is dependent on how valuable the cards are rather than each card. The main problem (which i'm correcting now) is that the game works by allowing the player to play one free card at the start of their turn, and not having a deck. All cards are available from the start. I tried to convince our AI coder that having a deck would be better, but the other problem to that is we are implementing a system that allows you to choose what cards you draw if we implemented a deck. We're trying to make it less random. \$\endgroup\$ – user5262541 Mar 9 '16 at 7:40
  • \$\begingroup\$ 20 is a small number for minimax (it is similar to chess, so the same techiniques apply in general). The "Magic Duels" game has potentially much more options per turn and yet they use minimax. The search is very shallow, but they compensate on the heuristics. Search and heuristics are complementary, if one is very good, the other does not need to be great. PS: sorry, I could not find the article where they explain the AI used in Magic Duels. \$\endgroup\$ – rcpinto Mar 9 '16 at 15:56

You would need to create 3 states for your AI: Opening, Middle, Closing.

During the Opening State of your AI, it uses a lookup table of all possible moves that it's oppenent chooses. With an exact response to do against it. This may be anywhere between 1-4 moves total, but it helps with search times by reducing it to 1. Creating a look up table is tough, and requires lots of time, and simulations. These tables are used to compete in World Computer Games Championships in Chess, Hex, GO, Breakthrough, and more.

During the Middle State of your AI, it will use the main search algorithm. Monte Carlo Tree Search is a widely used algorithm for searching for strong moves to do. However, just a plane MCTS will not cut it for every case. To reduce the time for this search you would want to implement an Early Playout Termination (EPT) algorithm. This allows the MCTS to stop searching if a condition is met before the end of the search. Along with all of these algorithms you will also want to implement a visit count for each state/command/move, these visits are put on a high precedence for searching. A state/command/move with low precedence will be searched last and least often. Then ontop of that you can implement a common sequence of states/commands/moves, which stores a group of moves in one move.

For the Closing State of your AI, it will have a lookup table for finishing the player off. It will have any number of moves which when it is cable of doing it will do with no tree searching. Basically the same as the opening book, a quick check if there is a win found, then go for it.

During the Middle State of your AI, it could have alternate states where it needs to do certain things, and it will focus on those options during the tree searches. Things such as "Low Health", "Too many cards in hand", "Enemy has no cards". These states will have the AI specifically look for a certain paths in it's tree travesal by it's weight factor. These weight factors will weigh in on your Minimax searches, and ignoring certain paths like using a move point drinking a health potion (Already full health, ignore this path)


Your Answer

