# Conquest vs Last Hero Standing

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.

## The Setup

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:

### Conquest

In Conquest, once a player wins with a deck it cannot be chosen again. Both players may switch decks in each round.

### Last Hero Standing

In Last Hero Standing, once a deck is beaten it cannot be chosen again. Only the loser of a round can switch decks.

## What To Turn In

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:

- Are there payoff matrices for which player 1 is favored in one format, and player 2 is favored in the other?
- Do we expect higher variance in outcomes with one format or the other?
- Would we expect more variety of decks in one format or the other?
- (Any other interesting questions you can come up with.)

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.