Edited Question:
As I promised I've edited this question. The previous version was written with the intention of simplifying the real question, but it ended in losing the real significance. Now I'm posting the "whole story". 😉
My purpose is to calculate $n$ players' equity in a poker tournament (their probability of ending the tournament) in every $j$ place (1st, 2nd, and so on).
I've previously solved this problem in 2 different ways you can find
here:For the Maths:
And for the code:
https://stackoverflow.com/questions/8605183/how-to-translate-this-math-formula-in-php
So, when I know every players' number of chips, I can easily apply those formulas and get their equity.
There are 2 problems involved that hopefully can be solved with a statistical method. (I'm not a mathematician so I'm not sure it will be feasible).
- First problem, even if I know everyone's stack, when the number of players is high, the code is too slow to be implemented;
- Second problem, this code should work by knowing only a limited number of stacks, belonging to the players of the analyzed table.
Optimistically these 2 problems can both be solved with some kind of approximations.
In particular the formulas mentioned above should be applicable to scenarios with 27,45,90 players who are distributed in tables of 9.
For example in the case of 27 players there would be 3 tables: when there are 18 players left they will be redistributed in 2 tables and when there are only 9 left the final table will be opened.
It's not important to take into account the players' skill since it's a high variance game where its influence is reduced to the minimum, and mostly there are coin flips that eliminate players.
So I'm in a situation where I know:
- My number of chips.
- The number of chips of the other 8 players of my table.
- The total number of chips.
- The average number of chips.
- The maximum and minimum number of chips.
As I suggested in the previous question, this seems to me (from my humbles math skills) to be a gaussian curve, with a maximum, a minimum and an average number of chips.
I think that's all. If you need additional details please leave a comment, and I will add them as soon as possible.
I wanna thank you for your interest, and for all the previous comments and answers. I hope your statistics can help me solve this. 😀
Best Regards,
Giorgio.
Old Question:
I'd like to calculate or approximate the probability that I have to win a tournament where every player has a determined amount of chips.
Let's consider a scenario where there are 9 players and I know everyone's number of chips, to calculate my probability of winning I would do: my chips/(tot chips – my chips).
Now imagine those 9 players are put on 3 different tables of 3 players each, and I know the chips only of the 2 players of my table and mine obviously. I also know the total number of chips, the max and min amount chips the players have and the average stack.
Is it possible to make an approximation of my probability of winning?
I have only basic math skills but I think players' stack could be approximated to a gaussian curve, then use some "statistical trick" to calculate my probability.
Thanks in advance for any hint!
Best regards,
Giorgio
Best Answer
The model described in the links is not the diffusion model. The model you are trying to implement is called the Independent Chip Model or ICM. They give different estimates for your expected share of second and lower place prizes. Here are two ways to describe the ICM:
(1) Determine the winner so that each player's chance to win is proportional to his chip count. Then remove that player's chips, and determine the second place player so that each non-winner's chance to place second is proportional to his chip count. Repeat.
(2) Randomly remove the chips one at a time so that each remaining chip has the same chance to be removed next. When your last chip is removed, you are eliminated.
It's not obvious that these are the same model. In fact, it's clear that the first description only depends on the proportion of chips, and doesn't require that the number of chips is an integer. It's not obvious that the second method gives the same chance to place second if the stacks are $(100,200,300)$ as for $(1,2,3)$. (In other models, these situations are different.) However, you can see that these are equivalent (when both are defined) by a third description:
(3) Each player marks all of his chips. Then they are shuffled and ordered. Players are ranked by their highest chips.
Description (1) corresponds to looking at the top of the ordering. Description (2) corresponds to looking at the bottom.
You can find a lot of information about the Independent Chip Model on the web because it is used by serious tournament poker players, particularly those who play Sit-N-Go (SNG)/Single Table Tournaments (STTs). See, for example, this Nash Equilibrium Calculator for push/fold decisions in STTs which uses the ICM. There are other models like the diffusion model, but the Independent Chip Model seems good enough and is easier to compute. You can find a section on the ICM in my book, The Math of Hold'em, and I have also made videos on it for poker instructional sites.
One of the other answers asks why bother since it's all luck. Understanding equities assuming that you have no skill advantage (but the stacks are not equal) is how many serious poker players GET an advantage. Getting all-in with a $60\%$ chance to win and negligible dead money is sometimes great, and sometimes terrible. The equities say which. Also, if you run a poker server, you need to be prepared to divide the prize money fairly in case the server crashes during the tournament. A poker server asked me for help with this.
As you have noted, a naive implementation which computes your chance to place $p$ out of $n$ players sums over many terms, $(n-1) \times (n-2) \times ... \times (n-p) = \frac{(n-1)!}{(n-p-1)!}$. This may be too large in practice. One improvement I use in my program ICM Explorer is to memoize the probabilities with each subset of up to $p-1$ opponents removed. If you are computing each probability, this takes $n 2^{n-1}$ steps instead of $(n-1)!$, which makes the difference between whether you can calculate the case $n=10$ crisply, and whether you can calculate the case $n=20$ in under a second versus not at all.
If you have repeated stack sizes among your opponents, you can remember how many of them have been eliminated instead of which subset. This is particularly useful when you are analyzing multitable tournaments where you only see the stacks at your table, or only a few front-runners, and you assume everyone else you don't see has the same stack size. This makes calculating your equity feasible for large tournaments. This method has a complexity roughly equal to $k \prod_{i=1}^k (m_i+1)$ where there are $k$ different stack sizes among your opponents whose multiplicities are $m_1, ... ,m_k$.
There is one implementation I know about which lets the user calculate ICM equities for multitable tournaments. This uses a simulation. The author assured me that it converges rapidly to within a $0.1\%$ chance for each place. In case you need more accuracy, one simple variance reduction method works very well: Estimate your luck from being chosen or not to finish next at each step by the exact calculations with fewer distinct stack sizes. Subtract this estimate of luck (a vector) from the vector of probabilities obtained in the simulation.
For example, suppose your stack is $1000$, and you have $2$ opponents with stacks of $500$ and one with $1500$.
If one of the players with $500$ wins, your remaining opponents will average $1000$, so you estimate your chances using the ICM exactly assuming $2$ opponents with $1000$ chips. Since all stacks would be equal, by symmetry all $3$ players would have an equal chance to finish second, third, and fourth, so your place distribution would be $(0,1/3,1/3,1/3)$.
If the big stack wins, your remaining opponents average $500$, and the ICM says your place distribution is $(0,1/2,1/3,1/6)$.
If you win, obviously your place distribution is $(1,0,0,0)$.
The weighted average is
$$\frac{1000}{3500}(0,1/3,1/3,1/3) + \frac{1500}{3500}(0,1/2,1/3,1/6) + \frac{1000}{3500}(1,0,0,0) = (2/7,13/42,5/21,1/6).$$
So, if in your trial, you win, then you estimate your luck for that step by $(1,0,0,0) - (2/7,13/42,5/21,1/6)$, and subtract this from the result of the trial. If the big stack wins, the trial isn't over, but you estimate your luck for this step by $(0,1/2,1/3,1/6)-(2/7,13/42,5/21,1/6)$, and subtract this and future luck estimates from the outcome of the trial.
The luck estimate averages to $(0,0,0,0)$ and greatly reduces the number of trials needed to achieve a given level of accuracy, particularly for the places closer to first, which are most important for estimating your fair share of the prize money.
The distribution of the other stacks matters, but except in extreme situations, you only see a large effect if you are close to the "money," which means that there are at most a few more players than there are prizes. Let's assume the prize structure is the one PokerStars uses for $180$ player tournaments: $0.3, 0.2, 0.119, 0.08, 0.065, 0.05, 0.035, 0.026, 0.017$ for places $1-9$, and a flat $0.012$ for places $10-18$.
Let's consider $2$ pairs of situations. First, you are one of $180$ equal stacks. Your equity is $1/180$ of the prize pool, or $0.5556\%$. Suppose you have doubled up, eliminating one player, and you have $178$ opponents with a stack half as large as yours. According to the ICM, your chance to finish in first place is $1.1111\%$, second $1.1049\%$, ... $18$th $1.0056\%$ for an equity of $1.0917\%$. The quotient $0.5556/1.0917 = 50.887\%$ is how much equity you need to want to get all-in with no dead money with $180$ equal stacks.
Suppose there are $60$ players with a stack equal to yours (including you), $60$ with half of your stack, and $60$ with half again as much as your stack. According to the ICM, your equity is $0.5572\%$ of the prize pool. Next, suppose you double up against an equal stack. Your equity increases to $1.0948\%$ of the prize pool. The equity you need to risk elimination for this is $0.5572/1.0948 = 50.894\%$.
Your expected share of the prize money didn't depend much on the stacks of the other players, and the equity you need to risk your whole stack depended even less on the stacks of the other players. These become sensitive to the stacks of your opponents once you get down to about $25-30$ players left with $18$ prizes.