Wolfram Blog : Simulating the World Cup Knockout Stage

June 24, 2010

Andrew Moylan, Technical Communications & Strategy

The knockout stage of the 2010 FIFA World Cup is about to begin in South Africa. At the time of writing, every team has one group stage match remaining, and most teams still have a chance to finish in the top two places in their group and progress to the knockout stage (see the tournament schedule and group stage standings).

There are different approaches to ranking world football teams. The most well known is FIFA’s official world rankings, which are derived from points gained and lost in each match according to a heuristic set of rules that generally reward winning against higher-ranked opponents in more-important tournaments.

A simple alternative with a more statistical basis is an Elo rating system (described in more detail below). A handy property of Elo rating systems is that they directly provide an estimate of the probability that a given team will perform better than another. We can use Mathematica with that to set up simulations of the knockout stage of the World Cup. This lets us estimate things like the chance of each team winning the tournament. We’ll also generate some nice visualizations of the results, such as the following simulated knockout stage (based on the current top two teams in each group):

Elo rating systems are used in many other sports and games, including international Chess and Go competitions. The World Football Elo Ratings website (www.eloratings.net)* maintains up-to-date Elo ratings for all national football teams. The following table compares the top 10 national football teams according to the official FIFA rankings and the alternative Elo ratings, showing some significant differences.

An Elo rating system works by assuming that the performance of a team in a match is a random value drawn from a certain probability distribution. The mean of the distribution is called the Elo rating for that team. The particular shape of the distribution may be freely chosen, but a common choice is ExtremeValueDistribution[α,400/Log[10]]. This is the distribution assumed for the stats we will use from World Football Elo Ratings (see details of how those ratings are calculated).

Here are the expected performance distributions for Slovakia and Brazil, whose latest Elo ratings (at the time of writing) are 1605 and 2100 respectively. The plot shows that Brazil is expected to usually, but not always, have a greater performance.

The assumption that performance follows an extreme value distribution leads directly to the probability that one team outperforms another, as a function of their rating difference.

We can verify this by computing the probability that p1 > p2, where p1 and p2 are the performances of two teams, and r1 and r2 are their Elo ratings.

p2]PDF[ExtremeValueDistribution[r1,400/Log[10]],p1]PDF[ExtremeValueDistribution[r2,400/Log[10]],p2],{p1,-\[Infinity],\[Infinity]},{p2,-\[Infinity],\[Infinity]},Assumptions->{r1,r2}\[Element]Reals]" title="Integrate[Boole[p1>p2]PDF[ExtremeValueDistribution[r1,400/Log[10]],p1]PDF[ExtremeValueDistribution[r2,400/Log[10]],p2],{p1,-\[Infinity],\[Infinity]},{p2,-\[Infinity],\[Infinity]},Assumptions->{r1,r2}\[Element]Reals]" class="alignnone size-full wp-image-2891" width="435" height="173">

To simulate knockout stage matches, we will take this Elo probability of one team outperforming another to be the probability that they win the match—hence the function name WinExpectation.

We can import the latest ratings directly into Mathematica:

(Due to web traffic, www.eloratings.net may be down during the tournament. You can import ratings from Google’s cached version or from Wikipedia instead—see the downloadable notebook near the end of this post for an example.)

We’ll also define a function TeamElo that looks up the rating of a given team:

rating][[1]]" title="TeamElo[team_]:=Cases[eloratings,{rank_,team,rating_,etc___}:>rating][[1]]" class="alignnone size-full wp-image-2894" width="428" height="28">

It works like this:

Now we are in a position to simulate the result of a match between teams a and b.

This SimulateMatch function returns a symbolic representation of a completed match, Match[{a,b},winner], indicating which teams played and who won. I defined a custom appearance for Match objects, which you can see at the bottom of this post.

We can define properties of symbolic objects, such as this simple one:

The winner is not always the same in our random simulated matches.

Next we’ll simulate each round of the knockout stage.

Some synonyms help standardize country names between the different data sources:

"South Korea","Korea DPR"->"North Korea","Côte d'Ivoire"->"Cote d'Ivoire","USA"->"United States"};" title="synonyms={"Korea Republic"->"South Korea","Korea DPR"->"North Korea","Côte d'Ivoire"->"Cote d'Ivoire","USA"->"United States"};" class="alignnone size-full wp-image-2900" width="440" height="43">

For now we’ll assume that the two teams currently atop each group make it through to the knockout stage. We can import the group stage standings directly from the World Cup website:

The teams coming first and second in each of the groups A through H slot into the knockout draw as follows (see the knockout draw on the official website):

KnockoutDraw gives a nested list encoding the structure of the knockout stage. We can visualize the resulting expression using TreeForm, showing the expected binary tree:

To simulate the first round we just need to evaluate SimulateMatch on each pair of team names sitting at the second lowest level of this tree:

A simulated first round:

For subsequent rounds we simulate new matches between the winners of each pair of matches in the previous round:

With[{m=SimulateMatch[{Winner[m1],Winner[m2]}]},Sow[{m1->m,m2->m}];m]" title="NextRound[round_]:=round/.{m1_Match,m2_Match}:>With[{m=SimulateMatch[{Winner[m1],Winner[m2]}]},Sow[{m1->m,m2->m}];m]" class="alignnone size-full wp-image-2907" width="378" height="58">

(The Sow function doesn’t affect the result. It is used here to accumulate rules indicating how each match depends on preceding matches, which will be handy later.)

The entire knockout stage has four rounds in total:

Here is the final match in one random simulation of the whole knockout stage:

Here are the two semi-finals in another simulation:

Every simulation is different. Here is a custom tree plot of a whole knockout stage:

True,AspectRatio->0.9,ImageSize->Full,VertexRenderingFunction->(Inset[#2,#,Background->White]&),PlotRangePadding->0]" title="KnockoutStageTreePlot[draw_]:=TreePlot[Flatten[Last[Reap[KnockoutStage[draw]]]],Right,DirectedEdges->True,AspectRatio->0.9,ImageSize->Full,VertexRenderingFunction->(Inset[#2,#,Background->White]&),PlotRangePadding->0]" class="alignnone size-full wp-image-2911" width="425" height="73">

(We used Reap to gather up the rules accumulated by Sow in the NextRound function.)

Here is a simulation starting with a different set of teams, those currently in first and third place in each group:

We certainly aren’t limited to doing one simulation at a time. Here are the winners of 1000 simulated knockout stages using the teams in first and second place in the current group stage standings:

Here are the same results as a bar chart giving the estimated probability of winning the tournament:

Using our simulation framework we can explore all sorts of things:

What about a giant knockout tournament containing the top 128 national teams?

Download this notebook to see the source code for these examples and try some of your own! You can use the same notebook to run simulations with the final set of teams participating in the knockout stage, once they are determined.**

* Note: All Elo ratings in this post and notebook are from World Football Elo Ratings, whose primary source of international football data is Advanced Satellite Consulting.

** You can view the notebook in the free Mathematica Player. To run your own simulations you need Mathematica—you can request a free trial.

---

Read on to see how to set up the visual representation for teams and matches.

We’ll visually represent each team with a labeled national flag, and winning teams get a bit of extra formatting to help them stand out.

Mathematica has country flags built in, as part of CountryData:

(We explicitly defined the flag for England, which is normally considered part of the United Kingdom by CountryData.)

Here’s how the team icons look:

Using the team icons we can define a visual representation of Match objects:

10,Frame->True]" title="Format[Match[{a_,b_},winner_]]:=Column[Map[If[#===winner,WinningTeamIcon,TeamIcon][#]&,{a,b}],ItemSize->10,Frame->True]" class="alignnone size-full wp-image-2920" width="425" height="43">

Using Format, we told Mathematica that all symbolic Match objects should be displayed in this way: