I found a way to speed this up even more by noting that because the precision is limited anyway, unless we run billions of iterations it is unnecessary to calculate the logarithm with high precision. So we can replace it with a precomputed lookup table. With that technique and optimized sorting my C# code now runs 1 million iterations in less than 4 seconds for 180 players/18 payouts (single threaded on a 3.8 GHz Core i7).

Note that -ln(x)/q has an exponential distribution with parameter q. Hence if there are efficient random number generators for exponential random variables, this may also be a way to get even better performance.
I like the interpretation of this: the tourney of a player can be seen as a stationary continuous markov chain with two states: dead and alive. The expected life left in the tournament is proportional to the number of chips he has in front of him. The player with the longest life wins, the runner up gets second etc. A well known result is that the time spent in a state is exponentially distributed, as we previously have observed.

I must say this thread is pretty exciting to read, watching poker evolve step by step in this forum. It's amazing.

This does converge to the ICM result. Trojanrabbit and halftilt have the right basic idea.

First you have to show that the probability of player 1 finishing behind player 2 is:

S2 / (S1 + S2)

This is simple calculus. It will happen if P1 < P2, which happens if R1^(1/S1) < R2^(1/S2) where R1 and R2 are the random numbers for the two players. I'm using plexiq's insight that normalization doesn't affect the algorithm, so you can work with the raw stack sizes instead of the Qi's. Since all the Ri's are positive, we can raise both sides to the S1 power to get R1 < R2^(S1/S2). The probability of this, for given R2, is clearly R2^(S1/S2).

Now we need some calculus. The unconditional probability of this happening, before we know R2, is the integral from 0 to 1 of R2^(S1/S2). That is R2^(S1/S2 + 1)/(S1/S2 + 1); which is 1/(S1/S2 + 1) at R2 = 1 and 0 and R2 = 0. 1/(S1/S2 + 1) = S2/(S1 + S2) as required.

This shows the algorithm gives the same result as ICM for two-player tournaments. To show it holds for larger tournaments, we have to show that if you remove any one player, the relative ranking probabilities of all the other players are unaffected. This is clearly true for the algorithm, since it is a ranking.

To see why this forces the ICM result, suppose we know the probability of player 1 finishing behind player 2. We now add player 3, and compute the probability of player 3 finishing behind player 1, and behind player 2. Let's call these Pr(1,2), Pr(3,1) and Pr(3,2) respectively.

Pr(3,1) = probability of player 3 finishing third, plus 1-Pr(1,2) times the probability of player 3 finishing second

Pr(3,2) = probability of player 3 finishing third, plus Pr(1,2) times the probability of player 3 finishing second

We can solve these two equations to learn:

Probability that player 3 finishes third is [(1-Pr(1,2))*Pr(3,2)-Pr(1,2)*Pr(3,1)]/[1-2*Pr(1,2)]
Probability that player 3 finishes second is [Pr(3,1)-Pr(3,2)]/[1-2*Pr(1,2)]

And, of course, the probability that player 3 finishes first is one minus those two probabilities.

Every time I add a player, given the pairwise probabilities I can compute his probability of any finish. If I add a player to an n player tournament, he has n+1 possible finishes. I have n equations, because I know his pairwise probabilities of finishing behind any of n players. I have one more equation, because the probability of the new player finishing in all places must sum to 1. n+1 equations in n+1 unknowns can have only one solution.

I would call this a clever Monte Carlo algorithm for computing the ICM result.

This is why I love 2p2. I share an idea and lots of people find ways of making it better. Everyone wins.

Tysen

By the way, if you want to speed things up further, there are tricks to make Monte Carlo more efficient.

One is "importance sampling." The small stack sizes only matter when they draw a random number near one. You could exclude them from 99% of the computations, but when you include them draw from 0.99 to 1 instead of 0 to 1. For each value of Q, you could determine an exclusion probability.

Another is to include a control variate. In this case, an obvious candidate is the player's expected winnings with an average stack. You know this has to equal the total prize pool divided by the number of players. For each player, in addition to computing expected winnings, you could compute expected winnings given an average stack, using the same random draws (in other words you rank the player's draw of Ri among the Qi's of the other players). If the latter number came out higher than expected, you could adjust the former number downward, because the player drew better-than-expected random numbers.

You might also consider quasi-random variates. You could generate a large matrix of random numbers once, then adjust it so that every row and column had exactly a mean of 0.5 and a standard deviation of the square root of 1/12. You could match higher moments as well, or dictate the fraction of variates in each row and column that are in various bins. The techniques can remove a lot of the random noise and make your simulations converge faster.

This isn't right.

A modest amount of fiddling with an ICM calculator would show this to be false. It ignores one of the basic rule of thumbs concerning ICM properties—Your equity is greater if your opponents stack sizes vary widely as compared to when their stack sizes are bunched closely together. What you assert is only true when all the stacks sizes are exactly equal.

I find both these ideas very interesting. I need to study the theory more.

I think I can speed up my implementation even more by using the distribution of the first x (e.g. 1000) iterations to optimize some parameters, so that in later iterations not only do we not need to sort most of the items (which I have already implemented) but they can be immediately discarded (thus saving a lot of memory accesses). This will result in a small percentage of failures, i.e. not enough remaining places for all payouts. We can detect these, reset the pseudo-random number generator and re-run that iteration with more conservative parameters until it succeeds.

I have also thought of improving the result by doing post-processing to enforce that equal stacks receive the exact same equity and that larger stacks always get larger equity than smaller.

Yes, you are correct. I should have said, rank each player's Ri among the Ri's, not Qi's, of the other players.

There are other possible control variates as well. Thinking about it a little more, using the Ri's may not be a good one. For players with small stacks the average Ri draw is much less important than number and distribution of extreme high Ri's. Perhaps a better approach would be to keep track of the probability of finishing first, which we know must equal the chip stack as a fraction of total stacks. If the simulated value is higher or lower than expectation, you could adjust. In this case, however, the adjustment is not altogether clear, since "extra" firsts might come at the expense of seconds. Here some post-processing to enforce a smooth distribution of probabilities of finishing first, second and so on; with the exact correct value for first; might help.

Since you know the chip-value function has to be very smooth, this is a promising approach. You could use a curve-fitting technique on the results to make them more accurate.

If you do this, you might consider using Monte Carlo simulation to estimate a derivative as well as a value for each player. That is, compute each player's equity, and using the same Ri, calculate their equity with one additional chip. This will give you a much better estimate of the derivative than comparing total estimated equity of two players with slightly different stacks.

Given that the assumptions are not completely realistic, it may be useless to strive for too much accuracy in the estimate. For actual decision making, having a consistent set of values with reasonable derivatives is the important thing. Since no one really knows the true equity of players you might get more useful results with a limited number of iterations and some clever post processing of results.

Here's another method that could speed up convergence. It assumes that the slow step is the sort.

Call the sorted Pi's T1 for the highest Pi, T2 for the second highest Pi and so on. Normally the player with Pi = T1 gets Z1, the player with Pi = T2 gets Z2 and so on.

Consider an out of the money player in this simulation, that is one with Pi < Sk where there are k prizes. We can compute exactly his expected prize, given all the other players' Pi's.

His chance of getting first is Qi*[1 - T1^(1+1/Qi)]/(1+Qi)
His chance of getting second is Qi*[T1^(1+1/Qi) - T2^(1+1/Qi)]/(1+Qi)
His chance of getting place j is Qi*[Tj-1^(1+1/Qi) - Tj^(1+1/Qi)]/(1+Qi)

Instead of awarding player i zero in this simulation, you can award him his expected winnings given all the other Pi's.

For players in the money, you have to consider the Ti's ignoring that player. In the formula above, if j is greater than or equal to the player's place, you have to substitute j+1 instead.

You can think of this as for each original simulations, you do an infinite number of simulations for each player, keeping all other players constant. My guess is 1,000 simulations done this way gives more accuracy than 1,000,000 simple simulations.

Isn't this the same thing that plexiq suggested (and dismissed) in post #2?

I didn't read plexiq's suggestion in this way, but now that you mention it, that may be what he meant. If so, his reason for rejecting it is incorrect, I think, because this method is much faster than computing a full ICM.

However, I claim no intellectual primacy here. These are all standard techniques for improving Monte Carlo.

Actually, I found that I get different results with and without stack normalization. Without stack normalization, I had results closer to ICM. With normalization, I had errors:

Without normalization (100000 trials):
Player player6 Stack = 6000
Player player2 Stack = 2000
Player player8 Stack = 8000
Player player1 Stack = 1000
Player player7 Stack = 7000
Player player3 Stack = 3000
Player player9 Stack = 9000
Player player4 Stack = 4000
Player player5 Stack = 5000
Avg stack = 5000
Player player6 wins = 13476.5
Player player2 wins = 4845.3
Player player8 wins = 17086.6
Player player1 wins = 2489.1
Player player7 wins = 15343.7
Player player3 wins = 7168.5
Player player9 wins = 18802.6
Player player4 wins = 9349.5
Player player5 wins = 11438.2

Stack normalization (100000 trials):
Player player6 Stack = 6000
Player player2 Stack = 2000
Player player8 Stack = 8000
Player player1 Stack = 1000
Player player7 Stack = 7000
Player player3 Stack = 3000
Player player9 Stack = 9000
Player player4 Stack = 4000
Player player5 Stack = 5000
Avg stack = 5000
Player player6 wins = 12176.2
Player player2 wins = 5656.8
Player player8 wins = 15443.1
Player player1 wins = 10243.8
Player player7 wins = 13936
Player player3 wins = 6676.2
Player player9 wins = 17091.4
Player player4 wins = 8474.1
Player player5 wins = 10302.4

Most likely, you have a bug in your code (which version are you using?). I get the same results with and without normalization, e.g:

I did some research on this back in the day. Check out my replies in this old post:
http://forumserver.twoplustwo.com/36...t-sngs-193170/

Out of curiosity, I tried applying this to analyzing a hypothetical situation on the bubble in the main event. I defined a scenario with 703 players remaining of whom 693 cash. I used the actual payout schedule from the 2011 main event. I plugged in stack sizes roughly analogous to the stack sizes in this year's main event after day 3. I found that a 10BB stack has an EV of about 26K, while a 20BB stack has an EV of about 39K. In other words, doubling up from 10BB to 20BB gives a roughly 50% boost to your EV. (Factoring in antes, it's more like a 55% boost.)

I used this to evaluate a situation where you are in the big blind with 10BB, and it is folded to the small blind who covers you and pushes. I assumed his range was any pair, any ace, any two broadway. Factoring in antes, you need about 59.5% equity to be +EV. According to PokerStove, against this range for opponent, the hands you should call with are 99+, AJs+, and AQo+.

Comments?

egj: Nice analysis. I did something similar. One helpful simplification is to measure stack sizes in the unit "starting stacks" (S) and $ amounts in "buyins" (B).

I took the actual stack sizes and payouts for the EPT London 2011 ME, with 10% of players left of the bubble (115 players left, 104 prizes). I ran the simulation with 20G iterations. I then fitted an exponential curve to the resulting data, with r-square of 0.9991. The result is the following formula, which approximates the $ value of a stack as a function of its size:

f(b) = 1.7282 * s ^ 0.7118

where b is the $ value and s is the stack size (b = 1 means one buy-in amount and s = 1 means the number of chips that players started with).

I have not done further analyses, but based on this formula it should be straight-forward (albeit laborious) to do NE push/fold analyses. [Note that in this case the effective stack size is not the only driver, but also the absolute stack sizes of the pusher and caller].

It would also be interesting to look at additional tournaments to see if the results are similar, and to see how the results change closer to and further away from the bubble.

Did anyone write a program of this were I can put n different stacksizes and payoutstructures? I would do it myself but I suck hard in coding.

It's like coding with training wheels.
You'll pick it up really fast if you already code C#.

Which ICM calculators have implemented this, e.g., Holdemresources or ICMizer?

The 20 payout/player calculator on holdemresources uses an optimized (exact) version of the normal ICM algorithm. The algorithm by Tysen is mainly useful for very large instances. It probably starts to perform better than my implementation somewhere around 27-30 players/payouts if you want decent accuracy.

Imo these instances are already too big to run on the server though, i don't like single requests to take almost a minute. I assume ICMizer has similar reasons for not adding it.

The algorithm would be fine for a downloadable tool though, SnG Solver or SnGWiz could easily add it.

I've tried just drawing an exponential variable for each player with as mean his current stack size and ranking those per iteration, which yields similar values as the proposed method in OP. I've used Shermans code:

There is a mistake in the code I posted, it should be

I only see 10 players in the holdemresources webpage. How can I use the 20-player option?

Has any ICM product added the algortihm so I can buy it, e.g., PT4, HEM2, SNGWiz?