Artificial Intelligence types in Deck Simulator for Hearthstone

The evaluation of deck strength done by the simulator is critically dependent on the brains behind the computer-controlled players which are making the decisions at each turn. The types of choices that have to be made include:

  • What cards should be redrawn at the beginning of the game?
  • What cards should I play?
  • What target(s) should I choose for spells and effects?
  • What minions should I attack with and whom should I target (other minions or the enemy player)?
  • For “choose-one” type spells, which spell should be used?

As of the current version of the game, there are 7 different types of AI players available when you configure a simulation. However, for the most part these can be divided into two types of play style, Heuristic and Planner.

Heuristic style is where I have handpicked a bunch of rules (around 30) to control different aspects of the game. For example, when there are no Taunt minions in play, should I attack the enemy player directly or try to kill his/her minions first? Should I only play minions when their battle cries have a valid target, or play them as soon as I can? There are a bunch of heuristics like this that I created one-by-one through many game replays and thinking about what a human would do.

The best example of the Heuristic style is the “Evolved AI (Strong)” player which is has the added benefit of a series of rules which I optimized via hundreds of iterations of a evolutionary algorithm. The process for ‘evolving’ a strong AI is not directly available in the game at present, but some day I hope to make it so.

“1st generation (weak)” is also a heuristic AI, but it is very simple with only a few rules, and is therefore very weak. I left it in mainly for historical reasons and so you can see the full effect of a good AI vs a bad one.

The other style, Planner, is significantly more advanced and involves looking at an entire turn instead of action by action. The planner looks for different possibilities in terms of the above choices (card playing, attacks, etc.) and then does a evaluation for the end result at the end of the turn after those actions are done. This allows finding multi-card combos, such as casting a spell to deal 1 damage to a enemy minions, then attacking that same minion to destroy it.

As you might guess, planner AI types are generally stronger than heuristic AI, however they take more time because of the many scenarios that have be evaluated each turn. “Evolved Planer (quick)” and “Evolved Planner (med)” are two examples of this AI type, where the first looks at a relatively limited number of possibilities and the second looks at many more possibilities.  The weighting factors used for these AIs were also optimized to use evolutionary algorithms, hence the “Evolved” portion of the name.

So which AI should you use in your simulations?

If you want a quick, rough estimate of decks’ relative strengths, use the “Evolved AI (strong)”, and if you want a better estimate which will take significantly more time, use “Evolved Planner (med)”. Another drawback of Planner-style AIs is they take up much more memory, so if you run a long simulation with many participants there is a chance your device will run out of memory and the simulation will be stopped automatically. In that case you can try with less participants, less matches per pairing, or without Planner-style AIs.

I spent a good portion of my time optimizing these AIs to make them strong, although there are still cases where they will not always make the best plays. Fortunately, I noticed that the strength ranking of a few decks doesn’t seem to change too much regardless of which AI is used (excepting the “1st generation (weak)” one). I still may add the ability to tweak AI parameters in a future release just because it’s fun.

 

 

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s