Wolfram Blog
Andrew Moylan

Simulating the World Cup Knockout Stage

June 24, 2010 — Andrew Moylan, Technical Communication & 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):

Simulated knockout stage

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.

Comparison of FIFA rankings and Elo ratings

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.

Expected performance distributions for Slovakia and Brazil

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.

WinExpectation[diff_]:=1/(1+10^(-diff/400))

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.

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]

%==WinExpectation[r1-r2]//Simplify

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:

eloratings=Import["http://www.eloratings.net/world.html","Data"][[3]];

(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:

TeamElo[team_]:=Cases[eloratings,{rank_,team,rating_,etc___}:>rating][[1]]

It works like this:

TeamElo["Spain"]

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

SimulateMatch[{a_,b_}]:=Match[{a,b},If[RandomReal[{0,1}]<WinExpectation[TeamElo[a]-TeamElo[b]],a,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.

SimulateMatch[{"Australia","Germany"}]

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

Winner[Match[{a_,b_},winner_]]:=winner

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

Table[Winner[SimulateMatch[{"Italy","France"}]],{8}]

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

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

synonyms={"Korea Republic"->"South Korea","Korea DPR"->"North Korea","Côte d'Ivoire"->"Cote d'Ivoire","USA"->"United States"};

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:

groupstandings=Import["http://www.fifa.com/worldcup/standings/index.html","Data"][[3,2,All,2,2,All,1]]/.synonyms;

groupleaders=groupstandings[[All,{1,2}]]

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[{{a1_,a2_},{b1_,b2_},{c1_,c2_},{d1_,d2_},{e1_,e2_},{f1_,f2_},{g1_,g2_},{h1_,h2_}}]:={{{{a1,b2},{c1,d2}}, {{e1,f2},{g1,h2}}},{{{b1,a2},{d1,c2}}, {{f1,e2},{h1,g2}}}}

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:

TreeForm[KnockoutDraw[{{a1,a2},{b1,b2},{c1,c2},{d1,d2},{e1,e2},{f1,f2},{g1,g2},{h1,h2}}]]

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:

FirstRound[draw_]:=Map[SimulateMatch,draw,{-2}]

A simulated first round:

FirstRound[KnockoutDraw[groupleaders]]

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

NextRound[round_]:=round/.{m1_Match,m2_Match}:>With[{m=SimulateMatch[{Winner[m1],Winner[m2]}]},Sow[{m1->m,m2->m}];m]

(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:

KnockoutStage[draw_]:=NestList[NextRound,FirstRound[draw],3]

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

Part[KnockoutStage[KnockoutDraw[groupleaders]],4]

Here are the two semi-finals in another simulation:

Part[KnockoutStage[KnockoutDraw[groupleaders]],3]

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

KnockoutStageTreePlot[draw_]:=TreePlot[Flatten[Last[Reap[KnockoutStage[draw]]]],Right,DirectedEdges->True,AspectRatio->0.9,ImageSize->Full,VertexRenderingFunction->(Inset[#2,#,Background->White]&),PlotRangePadding->0]

KnockoutStageTreePlot[KnockoutDraw[groupleaders]]

(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:

KnockoutStageTreePlot[KnockoutDraw[groupstandings[[All,{1,3}]]]]

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:

data=SortBy[Tally[Table[Winner[Part[KnockoutStage[KnockoutDraw[groupleaders]],4]],{1000}]],Last]

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

Estimated chance of winning World Cup

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

Estimated chance of reaching semi-finals

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

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.

TeamIcon[name_,style___]:=Labeled[SmallFlag[name],Text[Style[name,10,style]],Right]

WinningTeamIcon[name_]:=TeamIcon[name,Underlined,Bold]

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

SmallFlag[team_]:=ImageResize[CountryData[team,"Flag"],20]

Manually defining the flag for England

(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:

{TeamIcon["Mexico"],WinningTeamIcon["Honduras"]}

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

Format[Match[{a_,b_},winner_]]:=Column[Map[If[#===winner,WinningTeamIcon,TeamIcon][#]&,{a,b}],ItemSize->10,Frame->True]

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

Match[{"Argentina","France"},"Argentina"]

Leave a Comment

16 Comments


Luboš Motl

Nice software, bizarre teams. Why is an Italy over there? Didn’t you mean Slovakia? :-)

Posted by Luboš Motl    June 25, 2010 at 12:38 am
alex

Why is Italy over there????

Posted by alex    June 25, 2010 at 1:33 am
Erik Mahieu

Some days ago I sent a Demonstration:http://demonstrations.wolfram.com/SupportYourWorldCupTeam/
I substituted the UK flag/name with your ‘England’ flag which is ‘politically more correct’!
I wonder if I should send in an updated version to the Demonstrations site?
Enjoyed your blog,
Erik Mahieu

Posted by Erik Mahieu    June 25, 2010 at 3:16 am
Praveen kumar kjvs

nice post lets wait and see whats going to happen, whether math can really predict

Posted by Praveen kumar kjvs    June 25, 2010 at 4:02 am
sad

espero que no hayas estudiado una carrera para esto…

Posted by sad    June 25, 2010 at 4:44 am
Helly

I think that was just one possible outcome, not what they predict. They were using the ELO ratings to estimate the probability of outcomes for games. That is just what their RNG happened to spit out that time.

Posted by Helly    June 25, 2010 at 6:45 am
Jones

People are missing the point of this article. It was describing how to simulate the outcome of games with mathematica and elo rankings. Just because the examples they gave use teams already eliminated doesn’t make the whole article moot, you’re supposed to be able to redo these simulations with other teams.

I (and I’m assuming most other people) didn’t understand half of what they were talking about when it came to how to simulate it though, so I would love to see somebody who actually knew what they were talking about redo the simulations with current teams.

Posted by Jones    June 25, 2010 at 6:46 am
Roger

its shot to hell cuz both the finalists are actually on the same side of the bracket now… germany and paraguay will meet in semis if anything

Posted by Roger    June 25, 2010 at 6:46 am
Jeff Green

Whatever…i could write this code with one hand while grinding up coffee beans with the other.

Posted by Jeff Green    June 25, 2010 at 8:44 am
FreddyMusic

Timely and exciting post as a World Cup Shot.

The author need to prepare blog and predict the 16 knockout team a few day before the game run out. So that’s why Italy is there.

Wolfram technical players, Please keep us surprised!

Posted by FreddyMusic    June 26, 2010 at 7:17 am
Andrew

@Jeff Green It’s easy to say that when the code’s already done for you.

Posted by Andrew    June 26, 2010 at 2:36 pm
fd

Great post, actually how to rank things and account for uncertainties has lots of applications as for example resource allocation, where priorities need to be ranked and some decision on allocation should be made.
It is quite nice it accounts and quantifies variation in the outcomes, very rich and interesting model

Posted by fd    June 27, 2010 at 11:54 pm
Carla

Wow, that looks so much like math, but the graphs are cool.

Posted by Carla    June 28, 2010 at 8:15 am
Ben Heideveld

Dear Andrew,

Please give most likely outcomes of finals match!
I used to compute ELO-ratings myself in the seventies, when Arpad E. Elo’s system had just come out. It used a normal distribution and matches influenced the scoring to a lesser of higher extent depending on the so-called K-factor. In your publication you list an Elo ranking of teams, but it was published some time ago. My request is that you publish the Elo-list with actual Elo-numbers and that you update the ranking based on recent games played in the world cup. Could you please compute from there the probabilities that Holland or Spain wins (and Germany versus Uruguay).

Posted by Ben Heideveld    July 9, 2010 at 3:25 am
Chris

It appears the womens world match is a few days away, might be a chance now to add to this blog?

Posted by Chris    June 24, 2011 at 12:46 pm
KevinTran

Nice post

Posted by KevinTran    July 19, 2013 at 10:31 pm


Leave a comment

Loading...

Or continue as a guest (your comment will be held for moderation):