Thore Husfeldt

Hearthstone Algorithms Design Exercises

with 2 comments

Exam time again. I’ve tried to produce exam questions for my current algorithms design class themed after Blizzard’s collectible card game Hearthstone. For a variety of reasons I decided to abandon the idea for the exam, but the ideas are cute enough for a blog post. Here are the first three. The target audience are algorithms design students struggling with Chapters 1–8 of Kleinberg and Tardos’s Algorithms Design book (so: graph traversal, greedy, divide and conquer, dynamic programming, network flow, NP-hardness). Enjoy!

Hearthstone Basics

Each card in the game Hearthstone depicts a minion. Each minion has 3 values: Attack, Health and Cost, given as integers a, h, and c. Here’s a minion with Attack 3, Health 2, and Cost 4:

xMBCWkKf

For the purpose of these exercises, these values are unbounded, positive integers. During the game, both players have a number of minions in play. In a turn of Heartstone, the player assigns his minions to fight enemy minions. Each minion gets to target a single enemy minion, initiating a fight between the two minions. When a minion with Attack A fights a minion with Health H, the other minion’s Health is reduced to max{0,H-A}. Note that both minions fight, and each deals damage to the other, regardless of who initiated the fight. Also note that an enemy minion can be involved in many fights each turn, when it is repeatedly targeted. When a minion’s Health is reduced to 0, it is removed from play.

For each of the problems below, state which algorithmic design technique should be used, or if the problem is NP-hard. Also give the best asymptotic worst-case running time.

Cleanup

You and ZombieMage02 both have the same number of minions in play. It is your turn. Can you take them all the enemy minions in one sweep?

Input:
The enemy minions (a1,h1),…,(an,hn) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2

Output: “Yes,” if your minions can take out all enemy minions this turn. “No,” otherwise.

Tanks

TwoOrcsOneCup has two minions in play. Both completely overpowered and powerful enough to wipe out your hero when it becomes TwoOrcsOneCup’s turn again. You have n minions in play. Can you take out both minions this turn?

EPfTXn7N FmSMUX1Z

Input: The enemy minions (a1,h1),(a2,h2) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2

Output: “Yes” if your minions can take out both enemy minions this turn.

Charge!

Showdown time. Your hero has almost no Health left and OprahWindfury’s mage keeps pummeling you with fireballs. This has been going on for hours—time to end this! Luckily your hand is full of high-powered cards with Charge, which can attack immediately.
Get out as many of these guys as you can afford!

Input Your available mana K. The minions with Charge on your hand, (a1,h1,c1),…,(an,hn,cn) ∈ N2.

Output: The total number of Attack points you can play this round.


Cards generated using achievementgen.com

Advertisements

Written by thorehusfeldt

May 18, 2015 at 20:24

Posted in Uncategorized

2 Responses

Subscribe to comments with RSS.

  1. Hi, this is a very enjoyable exam. Here is what I think,

    1. Since the number of minions are the same for both sides, we can sort our side attack power; a’_1 … a’_n . Then, sort enemy minion’s health; h_1 … h_n. Assume both series are sorted in non-increasing order (1st is the largest, nth is the smallest). Because each minion can attack only once, we can clean up iff a’_i >= h_i for all i.

    2. I think this problem can be reduced to 2-partition when total attack = h1+h2. What we need to fix is that 63 =! 94. To fix this we just add two very large numbers (for example at least sum of our attack) that has the difference of 31 (let’s say x and x+31) in order to make sure that x and x+31 is on the different side when we do the partition. So this is weakly NP-hard.

    3. This one is knapsack, so it is also weakly NP-hard.

    wjiam

    December 8, 2015 at 22:22

    • Sorry, i just found out that my second answer is totally wrong. Reduction must be done in the opposite direction. Given 2-partition problem, we can scale the input number such that each partition sum up to 1. Then, we add 2 more numbers, i.e. 62 and 93, to make both side sum into 63 and 94 respectively. So, if we can kill these two monsters, we can solve 2-partition.

      wjiam

      December 13, 2015 at 17:32


Leave a Reply

Please log in using one of these methods to post your comment:

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

%d bloggers like this: