In the computer-based card game Hearthstone, there are two main tournament formats: Conquest and Last Hero Standing. Your goal is to develop a tool that can analyze both formats and compare the win probabilities.
Each player brings five decks to the tournament, call them decks a,b,c,d, and e. For each round of the tournament, one (or both) players get to pick the decks to play, with some constraints established by the format [LHS or CQ].
For any two decks, e.g., a1 and c2, there is a known probability that p1 will win in the match. One can write these probabilities in a table:
| p1 | ||||||
| a | b | c | d | e | ||
| p2 | a | 0.3 | 0.6 | 0.2 | 0.9 | 1.0 |
| b | 0.2 | 0.9 | 0.6 | 0.3 | 1.0 | |
| c | 0.9 | 0.8 | 0.5 | 0.2 | 0.0 | |
| d | 0.5 | 0.2 | 0.5 | 0.7 | 0.0 | |
| e | 0.3 | 1.0 | 0.1 | 0.8 | 0.0 | |
If only a single round were played, one could use the game theory analysis tools we already discussed to construct the proper strategies for p1 or p2 in a straightforward way. But in a tournament setting, the goal is to win three games, and the choices of decks are restricted.
So, consider what happens in each of these formats:
In Conquest, once a player wins with a deck it cannot be chosen again. Both players may switch decks in each round.
In Last Hero Standing, once a deck is beaten it cannot be chosen again. Only the loser of a round can switch decks.
Build an analysis tool that can compute the optimal LHS and CQ strategies for a given payoff matrix. This strategy will give a probability of selecting each deck in every possible match state. Imagine a player at a tournament using your strategy output -- they will want to look up the current match state and get a recommended probability for choosing their next deck.
Ideally, this should be a nice html5 page with inline javascript to do your math and interactive inputs, but you could also build a command-line program.
Answer one or more interesting questions about these formats:
As always, your turn-in should take the form of a git repository and an e-mail to jmccann@cs.cmu.edu. Completed analyses will be awarded 1 point of extra credit, with an additional 1 point available to exceptional solutions.