Poker-AI.org

Poker AI and Botting Discussion Forum
It is currently Sat Mar 28, 2020 3:07 pm

All times are UTC




Post new topic Reply to topic  [ 14 posts ] 
Author Message
 Post subject: Nash Equilibrium and ICM
PostPosted: Wed Jan 08, 2020 7:24 pm 
Offline
Veteran Member

Joined: Wed Mar 20, 2013 1:43 am
Posts: 259
I see that Pio Solver for example has an option to enter a tournament payout structure for the Nash equilibrium computation.
Does anyone have an idea how to integrate ICM into the calculation? Are there any online ressources on this?


Top
 Profile  
 
PostPosted: Fri Jan 10, 2020 10:31 am 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 613
I've never played in a tournament, never used ICM, and given this question all of 2 minutes thought. So in complete expectation of being shot down in flames or ignored here is my idea.

As I understand it ICM tells you the dollar value of the chips in different circumstances. So I'd compute the dollar value of every terminal outcome of the game tree and use that in the calculation of ev instead of the number of chips.


Top
 Profile  
 
PostPosted: Fri Jan 10, 2020 1:26 pm 
Offline
Junior Member

Joined: Wed Mar 18, 2015 10:02 am
Posts: 31
Human poker players calculate pot odds and equity. So with high ICM you need much more equity to call than in ring games, meaning you simply increase threshold for equity to defend a hand. How much equity more you need, it is all approximation, there is no math proof.
Obviously with high ICM you need more with less ICM less equity. E.g if you are shortstack and opponent has more chips than you, and bets river, if you are right before the bubble your ICM is very high, so you only want to call strong hands.
You can use ICMIZER 3, https://www.icmpoker.com/icmizer/
to get a feeling how they use ICM in different spots.


Top
 Profile  
 
PostPosted: Sat Jan 18, 2020 3:22 pm 
Offline
Veteran Member

Joined: Wed Mar 20, 2013 1:43 am
Posts: 259
spears wrote:
I've never played in a tournament, never used ICM, and given this question all of 2 minutes thought. So in complete expectation of being shot down in flames or ignored here is my idea.

As I understand it ICM tells you the dollar value of the chips in different circumstances. So I'd compute the dollar value of every terminal outcome of the game tree and use that in the calculation of ev instead of the number of chips.


Yes that was my first idea as well. I will try it and report the results.


Top
 Profile  
 
PostPosted: Sun Jan 19, 2020 5:01 am 
Offline
Veteran Member

Joined: Wed Mar 20, 2013 1:43 am
Posts: 259
Ok, so the first step will be calculating the ICM equities, I have found the following code in the archive:

Code:
#include <iostream>
using namespace std;

double getEquity(int player, int depth, int payouts, int stacks, double total, double* p_payouts, double* p_stacks)
{
   /*
      func doing the recursive ICM calculation
   */
   double eq = p_stacks[player]/total*p_payouts[depth];

   if(payouts > depth+1)
   {
      for(int j=0;j < stacks; j++)
      {
         if(j != player && p_stacks[j] > 0)
         {
            double c = p_stacks[j];

            p_stacks[j] = 0;
            eq += getEquity(player, depth+1, payouts, stacks, total-c, p_payouts, p_stacks)*c/total;
            p_stacks[j] = c;
         }
      }
   }

   return eq;
}

double getEquity(int player, int payouts, int stacks, double* p_payouts, double* p_stacks)
{
   /*
      player - player index
      payouts - amount of
      stacks - amount of
      p_payouts - pointer containing adress of the payout structure
      p_stacks - pointer containing adress of the stack size structure
   */
   double total = 0;

   for(int j=0;j<stacks;j++) total += p_stacks[j];

   return getEquity(player, 0, payouts, stacks, total, p_payouts, p_stacks);
}

int main()
{
   //-----------------------------------------------------------------------------------------------------
   // Test Examples
   //-----------------------------------------------------------------------------------------------------
   int payouts = 3, stacks = 6;
   double p_stacks[6] = {5500, 3500, 3000, 1500, 1000, 500};
   double p_payoutsSNG[3] = {0.5,0.3,0.2};
   double p_payoutsDON[3] = {0.33,0.33,0.33};
   double p_payouts1st[3] = {1,0,0};

   //SNG structure
   cout << "SNG Equities" << endl;

   for(int j=0;j<stacks;j++)
   {
      cout << "Equity stack " << j << ": " << getEquity(j, payouts, stacks, p_payoutsSNG, p_stacks) << endl;
   }

   //DON structure
   cout << "DON Equities" << endl;

   for(int j=0;j<stacks;j++)
   {
      cout << "Equity stack " << j << ": " << getEquity(j, payouts, stacks, p_payoutsDON, p_stacks) << endl;
   }

   //Winner gets all structure
   cout << "Winner gets all Equities" << endl;

   for(int j=0;j<stacks;j++)
   {
      cout << "Equity stack " << j << ": " << getEquity(j, payouts, stacks, p_payouts1st, p_stacks) << endl;
   }

   system("PAUSE");

   return 0;
}


It gives me the same results as Pio, so it's most likely correct.

My plan is to first compute how stacks change at each terminal node and then to compute the new ICM values for those terminal nodes. The difference in ICM values between the starting stacks and the stacks at the terminal node will then be the value of that terminal node for each player.

I have also read that there are ways to approximate the ICM values, does anyone know anything about that? I will first test it with this code, but an approximation might come in handy if the code isn't fast enough.


Top
 Profile  
 
PostPosted: Tue Jan 21, 2020 9:40 am 
Offline
Veteran Member

Joined: Wed Mar 20, 2013 1:43 am
Posts: 259
OK so here is another question that I encountered: in multiway pots there are nodes which are terminal nodes for one player but don't necessarily end the hand. I cashgame the value of that terminal node for this particular player are the chips that he wins or loses, but in a tournament it should be different. Because the hand isn't completelly over, he won't know the value of his fold (for example after he folded another player might go all-in on the bubble and bust, thus increasing the value of the player who already folded)

I wonder how this can be calculated or at least approximated.

Maybe just simulate the opponent actions up untill the end of the hand, give the current strategy for each player? (I am using monte carlo cfr and would try to change as little code as possible compared to my cashgame implementation)


Top
 Profile  
 
PostPosted: Wed Jan 22, 2020 2:34 pm 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 613
Quote:
but an approximation might come in handy if the code isn't fast enough.


There is something in The Mathematics Of Poker which I haven't read that might be helpful (though I'm doubtful) . If you want I can copy that for you. But I don't understand your concern about performance. You only have to calculate the terminal node values once and it is quite cheap, whereas CFR involves thousands of iterations of more expensive operations.

Quote:
I wonder how this can be calculated or at least approximated.

I probably don't understand the problem, but here goes...
In all cases construct the game tree and calculate the terminal node values, then run the simulation.
1. If you are simulating more than two players then constructing the game tree with terminal node values for all players is a similar process to constructing it for two players.
2. If you are simulating two players but want to take into account a third player who has already folded before the root of the tree then construct the game tree with terminal node values for both players that reflects the increased pot and ICM.
3. If you are simulating two players but want to take into account a third player who has already gone all in before the root of the tree then construct the game tree for two players but with more values at the terminal nodes that reflect the third player, the increased pot and ICM.

If this discussion goes further please let me know which of these 3 concern you.

I'm actually a bit concerned about the validity of all of this. As I understand it, traditionally ICM was used to calculate the chip values before the hand started, and it assumes that all players are of equal skill and implicitly they have an equal chance of winning the hand. Once the hand starts the assumption that they have an equal chance of winning the hand goes out the window. I guess you could calculate the chip values before the hand starts and use those without updating the stacks, but that seems like a wasted opportunity. Alternatively you could modify ICM to take into account the chance of winning the hand based on the cards you hold, but right now I have no clue how to do that. What does Pio do?

Come to think about it, does an ICM correction leave poker as a zero sum game? I'm not sure CFR works properly if it isn't zero sum.


Top
 Profile  
 
PostPosted: Wed Jan 22, 2020 3:37 pm 
Offline
Veteran Member

Joined: Wed Mar 20, 2013 1:43 am
Posts: 259
It was number 1.
I had an optimization in my code where I end the hand if the player who is currently being optimized already folded. But now I just traverse the tree to a real terminal node, where the hand actually ends (a showdown or all except one folded). I think this is how you would normally do it anyway, so this is solved.

This is how my terminal node code looks at the moment:
Code:
int TerminalNodeIcm2p::evaluate(const hand_t& hand, const int position, Game* game) const {
   std::vector<double> oldStacks = stacks; // Stacks before the hand
   std::vector<double> newStacks = oldStacks; // Stacks after the hand ended with this terminal node

   for (int i = 0; i < game->numPlayers; i++) {
      // terminalNode2p is a class from the cashgame solver
      // it computes the change in chips, not icm equity
      int change = terminalNode2p.evaluate(hand, i, game);
      newStacks[i] += change;   // compute stacks after hand
   }

   std::vector<double> oldIcm = ICM::getEquities(oldStacks, payouts); // ICM equity before hand
   std::vector<double> newIcm = ICM::getEquities(newStacks, payouts); // ICM equity after hand

   double res = newIcm[position] - oldIcm[position]; // Return change in ICM equity as the value of this terminal node

   return res;
}


The results at least look reasonable, I will compare them to some commercial tools tomorrow. I don't know how pio does it, all I will be able to do is compare the results. It does make sense to me however, if icm really is a good model of how much a player will win in the tournament, then we should be able to use the change of icm equity as the result of terminal nodes, but I am not really sure.
The game should still be a zero sum game, icm is just the probability of finishing on certain positions multiplied by the payouts of those positions. All the icm equity that someone ganins, someone else has to lose, although it's not linear who gains/loses how much icm eq exactly.


Top
 Profile  
 
PostPosted: Mon Jan 27, 2020 9:38 am 
Offline
Veteran Member

Joined: Wed Mar 20, 2013 1:43 am
Posts: 259
Ok I have compared it to ICMizer and the results are exactly the same for push or fold spots. I think that software can not compute other kinds of spots, but I assume this means that my code is correct.
I mean there are still some theoretical concerns, but if it produces the same results as commercial software I should not be at a disadvantage at least.


Top
 Profile  
 
PostPosted: Tue Jan 28, 2020 11:30 am 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 613
HontoNiBaka wrote:
I mean there are still some theoretical concerns, but if it produces the same results as commercial software I should not be at a disadvantage at least.

Agreed. But there might be an opportunity to do better. Eg by taking account of the true probability of winning the hand rather than assuming it is equal for all players. And if you can find something better, it should be relatively easy to prove that it is better by simulation. I can't find it now, but I vaguely remember reading Piotr had some concerns about the theoretical validity.

https://www.amazon.co.uk/Modern-Poker-T ... 1909457892 looks as if it might be interesting.


Top
 Profile  
 
PostPosted: Tue Jan 28, 2020 3:53 pm 
Offline
Veteran Member

Joined: Wed Mar 20, 2013 1:43 am
Posts: 259
You are right, having something better than ICM would definitely be great. I will check the book out.


Top
 Profile  
 
PostPosted: Mon Feb 10, 2020 4:23 pm 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 613
HontoNiBaka
Having thought this over in my spare moments over the last two weeks I reckon the solution you have is pretty good and I don't don't think there are any significant theoretical concerns. I reckon it takes care of the issues around the hand you hold and your seat position elegantly through the NE calculation without having to do any further work. Not that I'd like to do the maths to prove this statement though....


Top
 Profile  
 
PostPosted: Tue Feb 11, 2020 8:05 pm 
Offline
Veteran Member

Joined: Wed Mar 20, 2013 1:43 am
Posts: 259
spears wrote:
Not that I'd like to do the maths to prove this statement though....

I might not understand it anyway :lol:
Can you explain the intuition behind why you changed your mind on this?


Top
 Profile  
 
PostPosted: Wed Feb 12, 2020 7:24 am 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 613
- My concern was that ICM on its own doesn't take account of player position or the hand every player holds.
- NE calculation does take take account of these things
- By taking the difference of the two ICM values you eliminate the concerns


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 14 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
cron
Powered by phpBB® Forum Software © phpBB Group