Mathematical analysis of the metagame (you be the DCI)

It's hard. So much has changed in the last year. Walking ballista was printed in January. Paradoxical Outcome in September. Leovold in August (not as big but I do love Leovold). Last summer grixis pyromancer was fantastic. Now it is unplayable. While a lot has changed I would probably start after the restriction of Lodestone Golem last spring. While it wouldn't be perfect it would give probably the best general idea of matchup percentages.

Paradoxical has been around for almost a year, I'd start with that printing. Unless you want to wait until something else is printed; like you said 1 P9 is not enough and with the current rate of printings, there is something new every other set.

Unfortunately the problem with going back very far is that we've tweaked the classification. Hypothetically someone could go back and change the archetypes around to have a consistent classification (the win rates will update themselves).

@diophan One could just do key cards rather than archetypes (which by their very nature are somewhat arbitrary... #imlookingatyoujoesephcampbell)

So I scraped the metagame reports from Diophan and ChubbyRain from last June until this April, including P9s, Eternal Extravaganzas, the TMD Open and Vintage Champs.

The final matrix (of win counts this time, not win %; to calculate win percentage of deck i against deck j, compute M(i,j) / (M(i,j) + M(j,i)) ๐Ÿ˜ž

9
Shops	96	181	58	48	36	63	43	80	40
Gush	138	354	78	96	77	97	99	132	83
Dredge	38	92	17	34	18	23	25	30	25
BigBlue	43	82	27	27	13	30	25	27	28
BlueControl	26	61	10	19	20	24	18	19	17
Combo	34	72	38	21	18	31	25	36	26
Oath	41	80	31	37	14	31	40	45	30
Eldrazi	53	123	47	30	21	42	44	49	32
Other	21	68	26	21	6	20	25	25	12

I plugged this data into my code and got the surprising result:

Equilibrium Metagame:
Shops 100%
Gush 0%
Dredge 0%
BigBlue 0%
BlueControl 0%
Combo 0%
Oath 0%
Eldrazi 0%
Other 0%

Sure enough, according to the aggregated match win data, Shops has a winning match percentage against the entire field... not sure what to make of this.

@evouga

If your program and theory is good, then I guess it sort of reinforces what we all already know... Shops is the best

edit If you get a chance, can you add in some //comments . I'd like to try and trace the program but cannot decipher it.

last edited by desolutionist

@desolutionist said in Mathematical analysis of the metagame (you be the DCI):

@evouga

If your program and theory is good, then I guess it sort of reinforces what we all already know... Shops is the best

edit If you get a chance, can you add in some //comments . I'd like to try and trace the program but cannot decipher it.

Here is the code with more comments. I'm happy to explain if there are parts that are still confusing.

#include <Eigen/Core>
#include <Eigen/Dense>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Calculates whether the metagame is in equilibrium, given a matrix of win probabilities P and a set of dominated decks.
// 'dominated' is a bit field encoding whether each deck is present in the metagame, or hated out. A '0' in bit position
// i means that the deck is dominated (not present in the equilibrium metagame) and '1' means the deck is present.
//
// Returns true if an equilibrium exists given the set of dominated decks. If the equilibrium exists, the composition of
// the metagame is stored in 'result.'
bool hasEquilibrium(const Eigen::MatrixXd &P, int dominated, Eigen::VectorXd &result)
{
	int ndecks = P.rows();
	result.resize(ndecks);

	// constructs a list of non-dominated decks. idxmap[i] is the ith non-dominated deck.
	int idx = 0;
	vector<int> idxmap;
	while (dominated > 0)
	{
		if (dominated % 2 == 1)
		{
			idxmap.push_back(idx);
		}
		idx++;
		dominated /= 2;
	}

	int subdecks = idxmap.size();

	// Extracts from P the submatrix Pn corresponding to only the non-dominated decks.
	Eigen::MatrixXd subP(subdecks, subdecks);
	for (int i = 0; i < subdecks; i++)
	{
		for (int j = 0; j < subdecks; j++)
		{
			subP(i, j) = P(idxmap[i], idxmap[j]);
		}		
	}
	// solves Pn m = 0.5.
	Eigen::VectorXd rhs(subdecks);
	rhs.setConstant(0.5);
	Eigen::FullPivHouseholderQR<Eigen::MatrixXd> solver(subP);
	Eigen::VectorXd sol = solver.solve(rhs);

	// check that the linear system did indeed get solved
	if ((subP*sol - rhs).norm() > 1e-8)
	{
		cerr << "Warning: linear solve failed on domination strategy " << dominated << endl;
	}

	// the metagame composition m can fail to be an equilibrium metagame for several reasons:
	// - it requires that one of the decks make up a negative proportion of the metagame;
	// - it implies that one of the "dominated" decks has a >50% win percentage (in which
	// case we were incorrect in labeling that deck as dominated.)

	// check the first condition
	for (int i = 0; i < subdecks; i++)
	{
		if (sol[i] < 1e-8)
			return false;
	}

	// check the second. Calculate the win percentage of all decks, given P and m.
	result.setZero();
	for (int i = 0; i < subdecks; i++)
	{
		result[idxmap[i]] = sol[i];
	}

	Eigen::VectorXd candidate = P*result;
	
	// check all win percentages are <= 50%.	
	// Of course for the non-dominated decks we will get a win percentage of exactly 50%
	// so we only really care about what the value is for the dominated decks.
	for (int i = 0; i < ndecks; i++)
	{
		if (candidate[i] - 0.5 > 1e-8)
			return false;
	}
	return true;
}

int main()
{
	// read in the number of decks
	int ndecks;
	cin >> ndecks;
	if (ndecks < 1)
	{
		cerr << "Error: you must provide at least one deck win percentage to analyze" << endl;
		return -1;
	}
	if (ndecks > 30)
	{
		cerr << "Error: too many decks" << endl;
		return -1;
	}
	if (ndecks > 18)
	{
		cerr << "Warning: this analysis runs in exponential time. It may take quite a while to process a metagame with " << ndecks << " decks" << endl;
	}

	// read in deck names and win counts
	Eigen::MatrixXd wins(ndecks, ndecks);
	vector<string> names;
	for (int i = 0; i < ndecks; i++)
	{
		string name;
		cin >> name;
		names.push_back(name);
		for (int j = 0; j < ndecks; j++)
		{
			int nwins;
			cin >> nwins;
			wins(i,j) = nwins;
		}
	}

	// contruct the win probability matrix from the win counts.	
	Eigen::MatrixXd P(ndecks, ndecks);

	for (int i = 0; i < ndecks; i++)
	{
		for (int j = 0; j < ndecks; j++)
		{
			P(i, j) = double(wins(i, j)) / double(wins(i, j) + wins(j, i));
		}
	}

	// check for all possible sets of dominated decks. Each integer from 1 to 2^{# decks} encodes a different set
	// of possible dominated decks, where each '0' bit in the integer represents a dominated deck.
	// Since it is impossible to have a metagame where all decks are dominated, we skip the dominated=0 case.
	for (int dominated = 1; dominated < (1 << ndecks); dominated++)
	{
		Eigen::VectorXd breakdown;
		if (hasEquilibrium(P, dominated, breakdown))
		{
			cout << "Equilibrium Metagame:" << endl;
			for (int i = 0; i < ndecks; i++)
			{
				cout << names[i] << " " << 100*breakdown[i] << '%' << endl;
			}
		}
	}
}

So assuming we all agree that Vintage is not really a one-deck format, there are a few possible explanations for the above data:

  1. The format's best players play Shops, and its worst play decks that prey on Shops, so that the win percentage of Shops against its predators is not accurately reflected in tournament results;

  2. Even though Shops as a whole has a winning match percentage against all other archetypes as a whole, individual builds of Shops are weak against individual builds of, say, Big Blue, and this finer-grained relationship between the decks is not captured in the aggregate data.

I have no idea how to correct for #1 (if it's even true), but #2 could be fixed by going back through Diophan and ChubbyRain's data and doing a more fine-grained taxonomy, splitting archetypes that contain multiple, strategically-varied builds.

I can try doing this, but as it represents a very significant time investment, I'd like to get your thoughts first about what taxonomy you consider reasonable: if you had to decompose the metagame over the past year into ~15 archetypes so that

  1. decks with similar strategic roles in the metagame (and similar win percentage against other archetypes) are grouped into the same archetype;

  2. decks with different strategic role, but similar core, are classed as different archetypes;

what groups would you pick?

last edited by evouga

Based on your assumptions and what you input for winrates the second time around the conclusion is clear since shops does not have a sub 50% winrate.

I discussed this a bit with Matt and the assumption that winrates are static is what's giving a lopsided equilibrium in this state. Realistically speaking the higher proportion a deck is of the metagame the more people will tune their deck to beat it. This is why we see so many pyroblasts in a metagame where 60%+ of decks are blue. Note that I'm not criticizing what you did: I think it's interesting and it's also unclear how (or minimally a pain) to model tuning decks.

I'm rolling with the assumption that winrates are static for the remainder:

Since as mentioned before the conclusion that shop becomes 100% of the meta appears to depend on none of its winrates being below 50%. You'll notice in your first set of data that shops had a 40% winrate against oath but in the aggregate it had a record of 43-84, or ~51% winrate.

Because of this, a natural question is "how likely is it that shops really has a sub 50% winrate against oath?" The oath versus shops matchup is much discussed, since oath is in many people's eyes the deck to play if you expect a bunch of shops. I do not know much of any stats, but it's fun to learn, so I tried to figure this out. We have a binomial distribution, a sample of n=84 and a winrate of ~51% in the sample size. I had no idea how to figure this out, but based on https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval the first mentioned method seems reasonably accurate. Assuming I know how to use a z-table and didn't mess up the calculation, it's ~9% likely that shops has a sub 50% winrate against oath, which is lower than I expected. Anyone who actually knows stats should feel free to call me out for doing something stupid ๐Ÿ™‚

last edited by diophan

I'd like to plot the fluctuations in the actual meta game breakdowns. (From month to month)

Many thanks for doing this analysis. I've always been interested in game theory and the modern vintage metagame is a great case study!

I actually think it's entirely possible that vintage is a 'one deck format'. There are many ,many reasons for this, here are just a few off the top of my head:

We can't assume that everyone has perfect information. With the advent of MODO vintage and analyses like this one, we are trending towards more information, but it is far from perfect. Some players still show up with outdated decks. And I'd argue most don't know the 'win percentage' of archetype A vs. Archetype B.

We can't assume everyone is a rational player, whose sole goal is to win. People have deck and play style preferences that push them towards sub-optimal strategies. Some play to have fun, so winning is secondary.

Another hypothesis is it is much easier to 'screw up' playing blue than shops, i.e. blue decks have a larger decision tree and therefore also more opportunities to make mistakes. Given that most vintage players are fairly casual and are not on the pro tour/grand prix/scg tour grind, they are more likely to make mistakes when on a blue deck.

I don't know if there's a solution to this problem outside of more restrictions. The power of shops since printing of lock pieces started in Mirridon has always been that even if you packed a metric ton of hate, you still lose if you can't cast any of them. That problem still exists and will continue to exist as long as there are turn 1 spheres powered out by workshops. We know workshops are not going anywhere, so that leaves thorn or sphere, both of which seem way to underpowered to be restricted.

P.S. Frank Karsten wrote an excellent article examining what makes a good constructed format using game theory, highly recommend everyone to read!: https://www.channelfireball.com/articles/what-can-game-theory-tell-us-will-make-a-good-constructed-format/

last edited by hankzhong

@diophan said in Mathematical analysis of the metagame (you be the DCI):

I discussed this a bit with Matt and the assumption that winrates are static is what's giving a lopsided equilibrium in this state. Realistically speaking the higher proportion a deck is of the metagame the more people will tune their deck to beat it. This is why we see so many pyroblasts in a metagame where 60%+ of decks are blue. Note that I'm not criticizing what you did: I think it's interesting and it's also unclear how (or minimally a pain) to model tuning decks.

One thing you can do is to introduce a new hypothetical deck to the metagame with adjusted win percentages. These percentages are inevitably going to be to some extent hypothetical, but for example, say you added a tuned Gush deck with artifact hate, which boosted the matchup against Shops to 55% at the cost of 5% less effectiveness against other blue decks:

10
Shops	0.5 0.567398 0.604167 0.527473 0.580645 0.649485 0.511905 0.601504 0.655738 0.45
Gush	0.432602      0.5 0.458824 0.539326 0.557971 0.573964 0.553073 0.517647 0.549669 0.55
Dredge	0.395833 0.541176      0.5 0.557377 0.642857 0.377049 0.446429  0.38961 0.490196 0.54
BigBlue	0.472527 0.460674 0.442623      0.5  0.40625 0.588235 0.403226 0.473684 0.571429 0.51
BlueControl 0.419355 0.442029 0.357143  0.59375      0.5 0.571429   0.5625    0.475  0.73913 0.48
Combo	0.350515 0.426036 0.622951 0.411765 0.428571      0.5 0.446429 0.461538 0.565217 0.48
Oath	0.488095 0.446927 0.553571 0.596774   0.4375 0.553571      0.5 0.505618 0.545455 0.45
Eldrazi	0.398496 0.482353  0.61039 0.526316    0.525 0.538462 0.494382      0.5 0.561404 0.49
Other	0.344262 0.450331 0.509804 0.428571  0.26087 0.434783 0.454545 0.438596      0.5 0.45
GushPrime 0.55      0.45 0.46 0.49 0.52 0.52 0.55 0.51 0.55 0.5

You get

Shops 29.8689%
Gush 29.8689%
Dredge 0%
BigBlue 0%
BlueControl 0%
Combo 0%
Oath 0%
Eldrazi 0%
Other 0%
GushPrime 40.2621%

Now the new Gush deck (and its original, Shops-soft variant, which preys on the Shops-hardened version) take up 70% of the metagame. With enough match data about different variants of the different decks, presumably these percentage adjustments could be made less hypothetical.

last edited by evouga

@evouga

I had the same thought, which is why I wanted to look at the change in metagame breakdowns to see exactly what percent of people switch decks as opposed to tweaking their current one.

I plotted the metagame breakdowns from the P9 Challenges since October and the common trend seems to be that an increase in percentage of metagame share for a particular archetype was almost always followed by a decrease the following month and vice versa. There was only one instance in which a deck (Oath) saw a continued decrease in metagame share over two consecutive events.

last edited by desolutionist

@evouga going back to the post where you show the Equilibrium Metagame with shops at 100% and everything else at 0% I'm very curious to see what the other deck's charts look like - specifically big blue, blue control, oath and eldrazi.

@evouga said in Mathematical analysis of the metagame (you be the DCI):

So assuming we all agree that Vintage is not really a one-deck format, there are a few possible explanations for the above data:

  1. The format's best players play Shops, and its worst play decks that prey on Shops, so that the win percentage of Shops against its predators is not accurately reflected in tournament results;

  2. Even though Shops as a whole has a winning match percentage against all other archetypes as a whole, individual builds of Shops are weak against individual builds of, say, Big Blue, and this finer-grained relationship between the decks is not captured in the aggregate data.

Fascinating and great posts. There's always: Few people can afford the cost of Workshops. This puts a cap on the number of players who can play the deck, so discourages others from adjusting their decks to beat it, and so it lets the few Workshop players do disproportionately well. What happens if we create a rock-paper-scissors metagame (with the favorable matchups being, say, 60-40) but only let 10% of the people play rock instead of the one-third weโ€™d expect?

That 10% plays rock. 90% play scissors. Rock has a great win percentage, but only because itโ€™s too rare to justify anyone playing paper.

Or, as mentioned, players are not very good at recognizing or switching to the best decks so even if there's a current best deck not everyone switches to it, so it's not worthwhile to build a deck so targeted against it.

An old but relevant post: http://www.archive.themanadrain.com/index.php?topic=21004.msg334559#msg334559
"The price and rarity of Workshops means that Workshop decks are going to be scarce at most sanctioned events (except GenCon and other huge tournaments). This results in Workshop decks not appearing commensurate to their power and makes metagaming against them more difficult."

Someone needs to tell the Northeast that Workshops need to be scarce.

@mickey.nobilis said in Mathematical analysis of the metagame (you be the DCI):

Someone needs to tell the Northeast that Workshops need to be scarce.

We can handle that. Just starting playing:
4x ingot chewer
4x ancient grudge
4x dack fayden
4x fragmentize
4x pithing needle
4x shattering spree

in every deck. They'll get the message. haha

@Khahan I mean, that seems like overkill, but... yeah. Why don't people just do that to shops...? I mean. Ben Perry is in my metagame, running insano 2 card Monte and I put 1 mainboard Null and at least two more in the side of every tourney I know he's at... why the heck not?

For the life of me I've never understood why players don't just decide to crush certain kinds of decks that they know they will run into.

last edited by Topical_Island

@Topical_Island said in Mathematical analysis of the metagame (you be the DCI):

For the life of me I've never understood why players don't just decide to crush certain kinds of decks that they know they will run into.

Because no matter how powerful shops is (or is deemed to be), the majority of the Vintage playerbase will always play blue-based decks. So you're asking to get crushed in any tournament if you played a deck with the cards listed above since the majority will be blue players.

So actually that is precisely what people do with their decks and why Misstep, Flusterstorm and such are played in the maindeck, despite being dead versus shops. It's to beat other blue decks that they know they'll face.

last edited by Hrishi

@Hrishi I have gone to tourney's where out of aprox. 20 players, I can be certain that 5-7 of them are on Shops, or something artifact heavy... We act like this is a big data problem when in fact it's much more like a scouting problem. We know what people play. Vintage is the least fluid constructed format. To say nothing of just making a deck that crushes one archetype and plays close to even with some others, which is theoretically quite feasible. I love this thread, and this work is great so I am not trying to create a this vs that sort of false dichotomy... but seriously, decks like Landstill or Monored Hate get way overlooked because they are theoretically underpowered over thousands of games... when we can find out with even a little testing that they will smoke those three decks that keep winning down at your local card shop.

  • 33
    Posts
  • 13435
    Views