New algorithm to calculate ICM for large tournaments

I think I’ve discovered a new algorithm to accurately calculate ICM equities for large numbers of people. I’ve done some searching and wasn’t able to find any evidence that this has been used before, so I think I’m the first. If someone else has come up with this before, then my apologies…

First, why is this important? Traditional ICM calculations require you to do a number of calculations proportional to the factorial (n!) of the number of players remaining in a tournament. This is why you never see ICM calculators that can handle more than 10 players – it can take hours to calculate for 15 people and days to years to calculate more than that. My new algorithm can produce very accurate numbers in less than a minute, even if you have over 50 players.

Software developers may find this useful and do what was previously considered impossible, perhaps incorporating some concepts around the bubble factor from Kill Everyone. I will personally be doing some research of my own now that this door is opened.

This algorithm works on the principle of ICM where you imagine that all of the chips in the tournament are randomly given numbers and each player’s place in the tournament is based on their highest scoring chip. However we can use some math tricks to make the calculations easier. If each chip is given a random number between 0 and 1, and we have n chips, then the probability that all of our chips will score x or less will be x^n. We can also scale things so that we can work with smaller stacks since fractional chips are okay in this formula. This has the advantage that we only have to generate 1 random number for each player rather than 1 number for each chip.

Here is the algorithm:

Given n players
Given stack sizes S = S1, S2, … Sn
Given prizes Z = Z1, Z2, … Zn
Get normalized stack sizes Q = Q1, Q2, …Qn by dividing S by average stack

Simulate 1 tournament:
For each player i, generate a “place” for each player (Pi) by generating a random number between 0 and 1 and raising it to the power of 1/Qi. Pi = rand ^ (1.0 / Qi)
Sort players by their place P – higher is better
Award prizes Z according to P

Repeat for as many tournaments as desired and calculate the average prize value for each player. The error will be proportional to 1/sqrt(iterations) so the more iterations you run, the more accurate it will be.

I’ve tested this out and compared them to traditional ICM calculations and they converge to the same numbers.

Tysen