6
$\begingroup$

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:

https://math.stackexchange.com/questions/92942/applying-a-math-formula-in-a-more-elegant-way-maybe-a-recursive-call-would-do-t

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).

  1. First problem, even if I know everyone's stack, when the number of players is high, the code is too slow to be implemented;
  2. 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. :D

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

$\endgroup$
  • 3
    $\begingroup$ I think that there is a mistake in your formula for the probability of winning. Shouldn't it be $\frac{\textrm{my chips}}{\textrm{total chips}}$? $\endgroup$ – Tomek Tarczynski Feb 1 '12 at 18:01
  • 1
    $\begingroup$ @TomekTarczynski - yes, that must be the case, otherwise the sum of all players' probabilities of winning do not add up to one. $\endgroup$ – Peter Ellis Feb 1 '12 at 18:14
  • $\begingroup$ @Giorgio - if you win at your first table, can we assume that means you have all the chips from your first table, and then go on to play the winners of other tables? Alternatively, is the winner of the tournament the winner of an individual table who has more chips at the end than the winners of the other two tables? What is the significance of the tables, and what does it mean to "win" a tournament of 3 tables? $\endgroup$ – Peter Ellis Feb 1 '12 at 18:18
  • 2
    $\begingroup$ if skill is involved, this becomes a more difficult problem to solve. :) $\endgroup$ – Michelle Feb 1 '12 at 19:01
  • 5
    $\begingroup$ @PeterEllis: I might not discount some utility of the normal distribution. Consider a two-person game in which Player 1 starts with $a$ chips and Player 2 with $b$ chips. Suppose they are equally skilled so that at the end of each turn, the result is that one player gives the other one chip with equal probability. Then Player 1 wins with probability $b/(a+b)$. The fortune of each Player follows a random walk until an absorbing state is hit, and the walk up to this time is approximated by a Brownian motion. If we introduce a third player, we get a diffusion inside the unit simplex. $\endgroup$ – cardinal Feb 1 '12 at 19:21
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer! Seems like you know what you're speaking about ;) But I already know what ICM is and how to implement it into a 6-9 players scenario. I'd like to apply it when we don't have complete infos (we know only our table's/chipleader's/lowest stacks). At the moment I'd use a t-Student Curve to approximate people's stacks but I don't have the needed math/stat skills to build a solid model for this purpouse. Hope you could help. $\endgroup$ – KingBOB Jul 19 '12 at 17:47
  • $\begingroup$ The probabilities of finishing in lower places are very sensitive to the sizes of other stacks, but the probabilities of finishing in the top few places (which pay prize money) are not as sensitive. You can test this using the approximation I suggested, of assuming there are few distinct stack sizes among the players you don't see. If you do feel like modelling the other stacks, then the distribution depends on the type of tournament including the schedule of blinds and antes and the playing style and skill level of your opponents. A clump of players will be overly conservative... $\endgroup$ – Douglas Zare Jul 19 '12 at 19:24
  • 1
    $\begingroup$ and will play few hands, (or will correctly play few hands due to a dearth of playable situations) so for a long time the mode will be the initial stack minus the total of the antes. By the way, many poker sites let you see the stack distributions of tournaments in progress, so it is relatively easy to get data. However, I don't think equities are sensitive to the distribution until you have only a few more players than prizes. $\endgroup$ – Douglas Zare Jul 19 '12 at 19:29
3
$\begingroup$

Do players keep playing until they run out of chips? Suppose we assume players A B C each have some number of chips and keep playing until they have 0. Suppose we further assume odds of winning a hand are either 1/3, 1/3, 1/3 or some other value (per Michelle's comment about skill). Suppose we further assume each pot consists of either win (+2) or loss (-1) -- an unrealistic but simplifying assumption. Then doesn't this become a question of the relative probability of hitting 0 first? There's literature I'm not really familiar with that deals with this (Martingale wagers, but without the increasing bets). With multiple tables, equal chip pools per table and 1 winner per table 2nd round would be p=1/3.

More: I did some quick simulations along these lines. Each player is equally skilled. A always starts with 50% of the chips, B 1/3 of the chips and C 1/6 of the chips. I just varied the total number of chips. I did 3 runs at 3 levels, each consisting of 2000 simulations until only 1 player was left (18,000 simulations total). This suggests that it might indeed be as simple as p(I win) = my proportion of chips. enter image description here

$\endgroup$
  • 1
    $\begingroup$ From en.wikipedia.org/wiki/Random_walk#Gaussian_random_walk we have this formula, which seems analogous to the situation I described, but for two players. "If a and b are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits b or −a is ab. The probability that this walk will hit b before −a is a / (a + b), which can be derived from the fact that simple random walk is a martingale." $\endgroup$ – zbicyclist Feb 1 '12 at 22:42
  • $\begingroup$ I've edited the whole question. You can find it above. I hope you can help me, and tell if this could be feasible by applying some statistical trick ;) Best Regards $\endgroup$ – KingBOB Feb 2 '12 at 21:19
0
$\begingroup$

I suspect you are making this more complex than it needs to be. If there are 27 million players (or even 27 thousand - I think you have a typo) and the game is pure chance and we can reasonably assume that no player has a significant number of chips compared to the total number of chips...

Then your chance of winning is: $\frac{my chips} {total chips}$

Your change of coming second, given you didn't win, is: $\frac{mychips}{totalchips-winnerchips}$ which is effectively the same as your chance of winning. And so on.

Given the vast numbers involved and if as you say it is all chance I doubt it is worthwhile doing any more sophisticated calculation. The secret of "statistical tricks" is to know when to use an approximation :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.