## World Cup Prognostication

### June 29, 2010

We represent a team as a list containing its three-letter abbreviation and current elo rating. The list of teams is given in the order of the round-of-sixteen bracket, so repeatedly running through the list two-at-a-time always matches teams against the proper opponents:

`(define teams`

'(("URU" 1890) ("KOR" 1746) ("USA" 1785) ("GHA" 1711)

("NED" 2045) ("SVK" 1654) ("BRA" 2082) ("CHI" 1883)

("ARG" 1966) ("MEX" 1873) ("GER" 1930) ("ENG" 1945)

("PAR" 1771) ("JPN" 1744) ("ESP" 2061) ("POR" 1874)))

The two formulas are shown below. `Win-expectation`

is the percentage of times that `t1`

defeats `t2`

, and `point-change`

is the number of points by which the winner’s elo rating increases:

`(define (win-expectation t1 t2)`

(/ (+ 1 (expt 10 (/ (- (cadr t2) (cadr t1)) 400)))))

`(define (point-change t1 t2)`

(* 60 (- 1 (win-expectation t1 t2))))

Given the Elo ratings shown above, the United States had a 60.5% expectation of defeating Ghana, just a tiny bit better than three-to-two odds. Ghana earned 36 Elo points for defeating the higher-ranked United States, increasing its Elo rating to 1747 and jumping it over Japan and Korea in the Elo rankings (Japan is yet to play, but Korea lost to Uruguay, so its Elo rating decreased even before Ghana defeated the United States).

`Match`

takes two teams, plays a simulated game, and returns the winning team with its new elo rating:

`(define (match t1 t2)`

(if (< (rand) (win-expectation t1 t2))

(list (car t1) (+ (cadr t1) (point-change t1 t2)))

(list (car t2) (+ (cadr t2) (point-change t2 t1)))))

I should have named the arguments to `point-change`

as `winner`

and `loser`

rather than `t1`

and `t2`

. In my first version of `match`

, I didn’t reverse the parameters in the else clause of the `if`

, because the association of `t1`

to `t1`

and `t2`

to `t2`

was strong, and my simulation was wrong. Fortunately, it was wrong enough that my intuition of the problem suggested an error, and the bug was easy to find and fix.

`Round`

loops over all the teams in a single round of the tournament and returns a list of the winners, which is half the length of the previous round:

`(define (round teams)`

(let loop ((teams teams) (result '()))

(if (null? teams)

(reverse result)

(loop (cddr teams)

(cons (match (car teams) (cadr teams)) result)))))

`Tournament`

simulates rounds until there is only one team left, the winner of the World Cup:

`(define (tournament teams)`

(let loop ((teams teams))

(if (null? (cdr teams))

(caar teams)

(loop (round teams)))))

`Simulate`

runs the requested number of tournaments, counts the winners using the standard unix sort-uniq-sort idiom, and reports the results:

`(define (simulate n)`

(let loop ((n n) (result '()))

(if (zero? n)

(sort (lambda (x y) (> (cdr x) (cdr y)))

(uniq-c string=? (sort string<? result)))

(loop (- n 1) (cons (tournament teams) result)))))

Here is one result of a million simulated tournaments:

`> (simulate 1000000)`

(("BRA" . 223869) ("ESP" . 220378) ("NED" . 191683)

("ARG" . 79709) ("ENG" . 60550) ("URU" . 54380)

("GER" . 49965) ("POR" . 27458) ("MEX" . 24785)

("CHI" . 23526) ("USA" . 14928) ("PAR" . 9382)

("KOR" . 7416) ("JPN" . 6202) ("GHA" . 4901) ("SVK" . 868))

Though all sixteens teams have at least a chance to win (even lowly Slovakia), Brazil narrowly edges Spain for the most simulated World Cup victories. Each simulation is different; although Brazil wins more often than Spain in the simulation shown above, other simulations based on a different random sequence have Spain win more often than Brazil, as the two teams’ Elo ratings are close, and Spain has a somewhat easier draw (assuming Spain defeats Portugal, they will play the winner of the Paraguay/Japan match, which should be a cakewalk, while Brazil, assuming they defeat Chile, will presumably play third-ranked Netherlands, which is very close). There are also changes for the other teams; notice in the simulation above that Germany and Uruguay have swapped places, based on their Elo ratings, and that Chile has fallen two spots while Portugal and Mexico each moved up. And even if you consider Brazil and Spain the two best teams, as many soccer pundits do, notice that between them they win less than half the simulated tournaments.

We used `sort`

, `uniq-c`

and `rand`

from the Standard Prelude. You can run the program at http://codepad.org/vmpwcj3B.

[…] Praxis – World Cup Prognostication By Remco Niemeijer In today’s Programming Praxis exercise, the goal is to write a simulator for the knockout stage of the World […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/06/29/programming-praxis-world-cup-prognostication/ for a version with comments):

Hm, my code doesn’t seem to want to show up. Phil, could you have a look to see if it ended up in the spam queue? The only other explanation I can think of is that the source code highlighter doesn’t like the pragma in my code.

Fixed. It did go to the spam queue. I can’t imagine why.

You wouldn’t happen to have the standard prelude in a file or on the codepad, would you?

It’s an awful lot of stuff, and copy-pasting it all together is a rough task.

Thanks!

Graham: Fixed. See the Contents page or the introduction at the top of the Standard Prelude.

Wonderful. Thanks very much!

I re-ran my simulation after the quarter finals. The new Elo rankings put Netherlands and Spain in a tie for first place with 2085 points, Brazil dropped from first to third with 2072 points, Germany in fourth with 2044 points, Argentina in fifth with 1940 points, and Uruguay in sixth with 1895 points; the United States drops to twenty-fifth with 1749 points. Germany is the big mover with an increase from 1930 points to 2044 points following two wins with big goal differentials against higher-ranked teams. The new

`teams`

variable reflecting the semi-final bracket and the new Elo ratings is`(("URU" 1895) ("NED" 2085) ("GER" 2044) ("ESP" 2085))`

, and the result of a million simulated tournaments is`(("NED" . 378294) ("ESP" . 317881) ("GER" . 231524) ("URU" . 72301))`

. I have been quite impressed with Germany; they are a young team that is visibly improving with each half they play, and I wouldn’t be surprised to see them win the World Cup or, at least, defeat Spain then lose in the final. However, I am sticking to my prediction that the winner of the Brazil/Netherlands game, who we now know to be Netherlands, will win the tournament; Netherlands are a great side, and the numbers back me up.Phil,

Something I don’t quite understand is how you can infer the winner based on a random number (I noticed Remco does something along the same lines too). Are you basically saying the winner of a match is, in spite of the ELO rankings, the toss of a coin? If that’s not the case, are you using actual world cup results to aid in your computations?

Great problem statement by the way (decidedly apropos). Keep them coming!

A simple ruby version commented at http://steamcode.blogspot.com/2010/07/world-cup-simulation.html

Mine in F#

Another try..

Well, this is a bit late, but here’s mine, in Python.

Should probably be updated to account for the rankins as of today and the fixtures in the semis. Spain is the predicted winner.

And the results:

Spain 219542

Brazil 216734

Netherlands 185961

Argentina 78825

England 59688

Germany 50021

Uruguay 48066

United States 41076

Portugal 27293

Mexico 24100

Chile 22260

Paraguay 9498

Korea 6417

Japan 6012

Ghana 3791

Slovakia 716

with online elo ranking in drracket

#lang racket

(require net/url)

(define (elo-ranking country)

(let* ((in (get-pure-port (string->url “http://en.wikipedia.org/wiki/World_Football_Elo_Ratings”)))

(the-line(do ((the-line (read-line in) (read-line in)))

((regexp-match (string-append “>” country “number (car (regexp-match “[0-9]+” value)))))

(define sort #f)

(define merge #f)

(let ()

(define dosort

(lambda (pred? ls n)

(if (= n 1)

(list (car ls))

(let ((i (quotient n 2)))

(domerge pred?

(dosort pred? ls i)

(dosort pred? (list-tail ls i) (- n i)))))))

(define domerge

(lambda (pred? l1 l2)

(cond

((null? l1) l2)

((null? l2) l1)

((pred? (car l2) (car l1))

(cons (car l2) (domerge pred? l1 (cdr l2))))

(else (cons (car l1) (domerge pred? (cdr l1) l2))))))

(set! sort

(lambda (pred? l)

(if (null? l) l (dosort pred? l (length l)))))

(set! merge

(lambda (pred? l1 l2)

(domerge pred? l1 l2))))

(define (uniq-c eql? xs)

(if (null? xs) xs

(let loop ((xs (cdr xs)) (prev (car xs)) (k 1) (result ‘()))

(cond ((null? xs) (reverse (cons (cons prev k) result)))

((eql? (car xs) prev) (loop (cdr xs) prev (+ k 1) result))

(else (loop (cdr xs) (car xs) 1 (cons (cons prev k) result)))))))

(define rand #f)

(define randint #f)

(let ((two31 #x80000000) (a (make-vector 56 -1)) (fptr #f))

(define (mod-diff x y) (modulo (- x y) two31)) ; generic version

; (define (mod-diff x y) (logand (- x y) #x7FFFFFFF)) ; fast version

(define (flip-cycle)

(do ((ii 1 (+ ii 1)) (jj 32 (+ jj 1))) ((< 55 jj))

(vector-set! a ii (mod-diff (vector-ref a ii) (vector-ref a jj))))

(do ((ii 25 (+ ii 1)) (jj 1 (+ jj 1))) ((< 55 ii))

(vector-set! a ii (mod-diff (vector-ref a ii) (vector-ref a jj))))

(set! fptr 54) (vector-ref a 55))

(define (init-rand seed)

(let* ((seed (mod-diff seed 0)) (prev seed) (next 1))

(vector-set! a 55 prev)

(do ((i 21 (modulo (+ i 21) 55))) ((zero? i))

(vector-set! a i next) (set! next (mod-diff prev next))

(set! seed (+ (quotient seed 2) (if (odd? seed) #x40000000 0)))

(set! next (mod-diff next seed)) (set! prev (vector-ref a i)))

(flip-cycle) (flip-cycle) (flip-cycle) (flip-cycle) (flip-cycle)))

(define (next-rand)

(if (negative? (vector-ref a fptr)) (flip-cycle)

(let ((next (vector-ref a fptr))) (set! fptr (- fptr 1)) next)))

(define (unif-rand m)

(let ((t (- two31 (modulo two31 m))))

(let loop ((r (next-rand)))

(if (list a)))

((eq? (car seed) ‘set) (set! fptr (caadr seed))

(set! a (list->vector (cdadr seed))))

(else (/ (init-rand (modulo (numerator

(inexact->exact (car seed))) two31)) two31)))))

(set! randint (lambda args

(cond ((null? (cdr args))

(if (< (car args) two31) (unif-rand (car args))

(floor (* (next-rand) (car args)))))

((< (car args) (cadr args))

(let ((span (- (cadr args) (car args))))

(+ (car args)

(if (< span two31) (unif-rand span)

(floor (* (next-rand) span))))))

(else (let ((span (- (car args) (cadr args))))

(- (car args)

(if (< span two31) (unif-rand span)

(floor (* (next-rand) span))))))))))

(define countries

'("Uruguay"

"Korea Republic"

"United States"

"Ghana"

"Netherlands"

"Slovakia"

"Brazil"

"Chile"

"Argentina"

"Mexico"

"Germany"

"England"

"Paraguay"

"Japan"

"Spain"

"Portugal"))

(define teams

(map (lambda (x) (list x (elo-ranking x))) countries))

(define (win-expectation t1 t2)

(/ (+ 1 (expt 10 (/ (- (cadr t2) (cadr t1)) 400)))))

(define (point-change t1 t2)

(* 60 (- 1 (win-expectation t1 t2))))

(define (match t1 t2)

(if ( (cdr x) (cdr y)))

(uniq-c string=? (sort string<? result)))

(loop (- n 1) (cons (tournament teams) result)))))

(display (simulate 5000))