Who will win this world cup? Brazil without Neymar? Lionel Messi? Or are we going to see the Nederland making a big surprise?
If you like coding, statistics and problems that are not trivial… You found the right place. In this post, I will try to show an example to a way for solving this type of questions. For the readers that don’t remember what is Monte Carlo simulation (don’t be shy) – You might want to check a previous post that I wrote last summer and give you an intro to the world of Monte Carlo on Apps script and Google compute engine.
Monte Carlo experiments (simulations) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. In most cases, we will run our simulations many times over in order to obtain the distribution of an unknown probabilistic entity. This tool is often used in physical and mathematical problems and are most useful when it is difficult or impossible to obtain a closed-form expression, or infeasible to apply a deterministic algorithm.
In the real world, we see it being mainly used in three distinct problem classes:
* Optimization.
* Numerical integration.
* Generation of draws from a probability distribution.
OK, there is no time. The game starts in two days.
The Idea
Monte Carlo simulations tend to follow a particular pattern. Here is how we will use this tool:
1. Define a domain of possible inputs. In our case, the odds between the states (=games) and their results. This part is now in the code, we should move it later to be driven from the sheet or a form that users can change.
2. Generate inputs randomly from a probability distribution over the domain. It will be east to use Math.Random and check what we have in terms of the odds we decided for each step in the game. If we have 1:0 for Brazil we can say that they have 60% chance to finish the game with 2:0 or 2:1 because they got the momentum going on. Of course, you can play with these numbers base on your own assumptions.
3. Perform a deterministic computation on the inputs. In simple wording, we run on the data (=inputs) and base on our state machine we decided which team won in each case. We can run it 100, 1,000, 10,000 times etc’. If you wish to run it for ‘real’ with many more iterations, please use NodeJS because the performances will be much better and you won’t be limit to the length of the sheet.
4. Aggregate the results. Calculate how many times each team won and what are the odds base on our inputs.
Odds
This is the heart of our simulation. You could play with the numbers here as you think will be the best assumption.
I got some of the odds from trying to see what the smart guys over at: fivethirtyeight.com did with their SPI and calculations. However, in order to keep it simple, I’ve just picked nice/round numbers to show the concept. This diagram shows the states between BRA-GER with the odds per stage in the semi final.
Code
| /*************************************************************************** | |
| * This is a Monte Carlo simulation | |
| * to see who will win the 2014 World Cup | |
| * Data ideas: http://fivethirtyeight.com/interactives/world-cup/ | |
| * See: http://goo.gl/NV2OLc for a diagram of the odds. | |
| * Author: Ido Green | @greenido | plus.google.com/+greenido | |
| * Date: 4th July 2014 | |
| * *************************************************************************/ | |
| // Decide base on our odds who will win each match | |
| function stateMachine(curLine) { | |
| var path = ""; | |
| var curState = "0:0"; | |
| while (curState != "BRA" && | |
| curState != "GER") { | |
| path += curState + " | "; | |
| var rand = Math.random(); | |
| switch (curState) { | |
| case "0:0": | |
| // We always start at this state | |
| if (rand < 0.3) { | |
| curState = "1:0"; | |
| } else if (rand >= 0.3 && rand < 0.6) { | |
| curState = "1:1"; | |
| } else if (rand >= 0.6 && rand < 0.8) { | |
| curState = "0:1"; | |
| } else if (rand >= 0.8) { | |
| curState = "kicks"; | |
| } | |
| break; | |
| case "1:0": | |
| if (rand < 0.3) { | |
| curState = "kicks"; | |
| } else if (rand >= 0.3 && rand < 0.8) { | |
| curState = "2:0"; | |
| } else if (rand >= 0.8 && rand < 0.9) { | |
| curState = "1:1"; | |
| } else if (rand >= 0.9) { | |
| curState = "BRA"; | |
| } | |
| break; | |
| case "1:1": | |
| if (rand < 0.4) { | |
| curState = "2:1"; | |
| } else if (rand >= 0.4 && rand < 0.7) { | |
| curState = "1:2"; | |
| } else if (rand >= 0.7) { | |
| curState = "kicks"; | |
| } | |
| break; | |
| case "0:1": | |
| if (rand < 0.3) { | |
| curState = "2:1"; | |
| } else if (rand >= 0.3 && rand < 0.5) { | |
| curState = "1:2"; | |
| } else if (rand >= 0.5 && rand < 0.7) { | |
| curState = "kicks"; | |
| } else if (rand >= 0.7) { | |
| curState = "GER"; | |
| } | |
| break; | |
| case "2:0": | |
| case "2:1": | |
| curState = "BRA"; | |
| break; | |
| case "1:2": | |
| case "0:2": | |
| curState = "GER"; | |
| break; | |
| case "kicks": | |
| if (rand < 0.4) { | |
| curState = "BRA"; | |
| } else { | |
| curState = "GER"; | |
| } | |
| break; | |
| } // switch | |
| } // while | |
| var curSheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("Games1"); | |
| var barWon = 1; | |
| var gerWon = 0; | |
| if (curState != "BRA") { | |
| gerWon = 1; | |
| barWon = 0; | |
| } | |
| curSheet.getRange("a"+curLine).setValue(barWon); | |
| curSheet.getRange("b"+curLine).setValue(gerWon); | |
| curSheet.getRange("c"+curLine).setValue(path); | |
| return curState; | |
| } | |
| // Run on the senarios | |
| function runStateSenarios() { | |
| var start = new Date().getTime(); | |
| var curSheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("Games1"); | |
| var numOfSenarios = curSheet.getRange("e1").getValue(); | |
| try { | |
| var brazilWon = 0; | |
| var germanyWon = 0; | |
| for (var i=0; i < numOfSenarios; i++) { | |
| var result = stateMachine(i+11); | |
| if (result === "BRA") { | |
| brazilWon++; | |
| } | |
| else { | |
| germanyWon++; | |
| } | |
| SpreadsheetApp.flush(); | |
| } | |
| var percForBra = Math.round((brazilWon / (brazilWon+germanyWon))*100); | |
| curSheet.getRange("a2").setValue(brazilWon); | |
| curSheet.getRange("b2").setValue(germanyWon); | |
| curSheet.getRange("a3").setValue(percForBra); | |
| curSheet.getRange("b3").setValue(100 - percForBra); | |
| } catch(err) { | |
| Logger.log("Error: runSenarios(): " + err); | |
| } | |
| var end = new Date().getTime(); | |
| var execTime = (end - start) / 1000; | |
| var outStr = "<ul><li>Brazil won: " + brazilWon + " <li>Gremany won: " + germanyWon + | |
| " <li>Brazil get the cup in %" + percForBra + " of times. <li><small>It took: " + | |
| execTime + "sec</ul>"; | |
| var htmlApp = HtmlService | |
| .createHtmlOutput(outStr) | |
| .setTitle('Results') | |
| .setWidth(350) | |
| .setHeight(200); | |
| SpreadsheetApp.getActiveSpreadsheet().show(htmlApp); | |
| Logger.log(outStr); | |
| } | |
| // | |
| function onOpen() { | |
| var ss = SpreadsheetApp.getActiveSpreadsheet(); | |
| var menuEntries = []; | |
| menuEntries.push({name: "Run Simulations", functionName: "runStateSenarios"}); | |
| ss.addMenu("WorldCup Simulator", menuEntries); | |
| } |
Demo
This Google Sheet contain the simulator and the code.
You can set the numbers of times we will run on this by setting E11 cell. After that, you have a new menu ‘WorldCup Simulator’ that will let you run it. You can see the results on the sheet, as I’m using it as our logger (for now). You can see in each game, what is the result and the ‘path’ or the special game that lead to it. At the top of this table you can see the aggregate results that give us a nice summary.
Please feel free to copy it and open the code with ‘Tools’ -> ‘Scripts Editor’. You will be able to change the sheets, odds and run it on your own ideas.
Misc
- Wikipedia – Monte_Carlo_method
- Monte Carlo Simulation On Google Compute-Engine
- If you want to have all the results (so far) from the #worldcup – This post will give you the ability to fetch and work with them.
Happy Hacking and enjoy the game!
Discover more from Ido Green
Subscribe to get the latest posts sent to your email.
Ido Green 
Hi, may I know what formulas you used and how you iterated the game outcomes?