Wolfram Computation Meets Knowledge

Simulating the World Cup Knockout Stage

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"]

Comments

Join the discussion

!Please enter your comment (at least 5 characters).

!Please enter your name.

!Please enter a valid email address.

17 comments

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

    Reply
  2. 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

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

    Reply
  4. espero que no hayas estudiado una carrera para esto…

    Reply
  5. 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.

    Reply
  6. 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.

    Reply
  7. 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

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

    Reply
  9. 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!

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

    Reply
  11. 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

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

    Reply
  13. 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).

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

    Reply
  15. Fantastic information, dude! Thankyou so much for your work!

    Reply