Image Image Image




Post new topic Reply to topic  [ 39 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Thu Sep 03, 2009 6:01 am 
Offline
Senior member
User avatar

Posts: 106
Favourite Bot: still looking
Action for SB:
Fold 27%
Limp and fold to push 20%
Limp and call a push 4%
Jam 49%

Action from BB against a limp:
Check 55%
Jam 45%

Action from BB against a jam:
Fold 62%
Call 38%

Average EV for SB: -0.03BB

Tysen


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Thu Sep 03, 2009 10:53 am 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
My results are pretty similar (and as there is element of randomness in my calculations, should be OK). Are your figures the exact solution, or also involve some sort of heuristics?

EVjfr-n, 10bb: -0.0305 5906ms

jam: 0.4705
limp/callJam: 0.0558
limp/foldJam: 0.2021
fold: 0.2714

callJam/checkLimp: 0.0422
callJam/jamLimp: 0.3393
foldJam/checkLimp: 0.4796
foldJam/jamLimp: 0.1387

So back to the flop discussion.

When we calculate equity on the flop (for the purpose of optimal play), it would not only depend on the exact hands but also what ranges we play against. Therefore coming to a different estimator than allin equity is pretty tricky for me (at least in the way I tackle this).

On the other hand, using allin equity could be similarly bad. You basically assume - what is rarely the case - that the pot will stay 2bb. That in turn might lead to too many limps, for the "cheap" showdown that they offer in such setup.

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Thu Sep 03, 2009 5:36 pm 
Offline
Senior member
User avatar

Posts: 106
Favourite Bot: still looking
No, it's not exact. I used a gradient decent method. Although this problem is small enough that you could probably form a LP to solve it exactly.

Yeah, flop betting is hard without creating a full-fledged NL bot, which I may end up doing (my math and poker skills are up to the task, but I'm a junior programmer). My current short-term method is just to create some buckets of post-flop situations and see what that gets me.

Although using all-in equity is "bad" it's not as horrible as you might think. It doesn't really assume that there will be zero betting post-flop. What it means is that the eventual loser realizes that he's a loser and doesn't put in any more money. Still a bad assumption, but not useless for very short-stack situations.

Tysen


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Thu Sep 03, 2009 9:54 pm 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
The approach I'm using now allows me to only give a try with few postflop actions, and then it becomes just too slow / eating too much memory.

And in case of check/check or bet/call we face the same problem of how to get the equity.

trojanrabbit wrote:
Although using all-in equity is "bad" it's not as horrible as you might think. It doesn't really assume that there will be zero betting post-flop. What it means is that the eventual loser realizes that he's a loser and doesn't put in any more money. Still a bad assumption, but not useless for very short-stack situations.


Why is that? Do you take the all-in equity multiplied by some implied pot size, or you are saying this will hold even for a pot of 2bb?

My thinking is that not only the loser realizes that he is a loser, but as well he will not call even when he hads the odds to do it. So it's kind of protecting your hand as well against having a large pot built.

Anyway, I think it will be interesting just how inserting few postflop actions change the preflop equity and strategies that were calculated with using allin equity. If there is a significant difference this will give a good indication of what you can expect by adding more postflop, or turn/river actions.

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Fri Sep 11, 2009 9:16 pm 
Offline
Senior member
User avatar

Posts: 223
Favourite Bot: N/A
I have the idea of programming a NE for Heads Up NL holdem.

For the ones that did programmed it, how did you do it?

I'll explain my ideas:
* The set of strategies of SB is SUM (for i=0 to 169) COMBIN(169,i) = 7.48289E+50
* The set of strategies of BB is the same

If we remove the dominated strategy of folding Aces, we get a problem a bit smaller.
* Set of strategies for each player = SUM (for i=0 to 168) COMBIN(168,i) = 3.74144E+50

What I've been thinking is:
A) Start for each player with a strategy of Push AA.
B) For each player, try to improve the strategy by one bit at a time:
1) For all hands in the strategy, try to remove one hand and calculate the new EV
2) For all hands in the strategy, try to add one hand and calculate the new EV
3) Choose the single modificiation from 1) and 2) that improves more the EV
C) Repeat B) for each player until I get a fixed point that is a NE

So, what's your method for the ones that did that? Is there any software for calculating NE strategies in wich you define the players, strategies and payoffs (here as a function of the strategies) and it calculates the fixed point?

For NL Holdem, let's say 100BBs, how much time does it take for your program until you reach the NE?
And finally, how much time did it take to you to program this?

Later I'd like to add more actions (open for SB, 3-bet for BB, 4-bet for SB).


Top
 Profile  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Tue Sep 15, 2009 12:03 am 
Offline
Senior member
User avatar

Posts: 106
Favourite Bot: still looking
Adrian,

Unfortunately, the method you describe is impractical for a number of reasons, the main one being how are you going to possibly test 3e50 combinations against a villain's potential 3e50 combinations? Plus that doesn't allow for mixed solutions (i.e. pushing Q9s 43% of the time).

More efficient methods include ficticious play or regret minimization - there is plenty of information on all of both topics if you do some searching. Hope that helps.

Tysen


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Tue Sep 15, 2009 1:03 pm 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
@trojanrabbit,

I have tried Adrian's method in the past. It has certain benefits over ficticious play. I haven't yet studied regret minimization, so I can't talk for that.

On that - "how are you going to possibly test 3e50 combinations" - why would you see a difference between what Adrian's wrote and ficticious play? In both you need to cope with the exponential explosion when you add more actions ...

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Tue Sep 15, 2009 8:33 pm 
Offline
Senior member
User avatar

Posts: 106
Favourite Bot: still looking
My interpretation of the method described was:

1. Pick a strategy 'X' of the hands to push (of which there are 2^169 strategies)
2. Pick a strategy 'Y' of the hands to call (another 2^169)
3. Add a single additional hand for X(which one? you have to test all of them) and see if it is +EV
4. Remove a single additional hand for X (again you have to test all of them) and see if it is +EV
5&6. Repeat for Y
7. Start again at 3

I guess the things that bothered me about it were the binary nature (no mixing) and only changing one hand at a time. I might have sounded too harsh in my earlier post and if I misinterpreted how the algorithm works, I apologize.

What advantages do you see in this method over fictitious play?

Tysen


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Tue Sep 15, 2009 9:09 pm 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
Oh, wait. I misunderstood Adrian's writing. What I did was actually better (although looking suspiciously similar). The thing is, for a given abstraction over the allowed actions, you can always calculate best response fairly fast (so you don't need this add/remove card approach for the opponent's strategy).

Now, on your writing. On point 3 and 4 "which one" - is basically try anyone, and continue with that as long as it improves.
So it's not that you are looking for the exact optimal subset (of the set of size 169) with which to push, but instead, you are heuristically trying to evolve such subset by adding and removing hands.

In algorithmic theory that's some kind of a greedy algorithm that tries very fast to explore some of the local maximums, without guarantee that the one found will be truly the best one. Such approaches yield surprisingly good results in practice.

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Fri Oct 09, 2009 3:34 pm 
Offline
New member
User avatar

Posts: 3
Favourite Bot: CMU
<bump> :smile:

Great thread. Good to see Tysen here.

Not to take a step backwards, but it doesn't look like Indy ever got confirmation on the 10 and 20bb Jam or Fold values for sb, so I'll offer up what I can.

HU JoF - 10bb

  • sb: { 22+, Ax, Kx, Q7+, Qxs, J8+, J3s+, T9-76, T8-97, T4s+, 95s+, 84s+, 74s+, 64s+, 53s+, .71(43s) } [58.3%]

      Image

  • bb: { 22+, Ax, K5+, Kxs, Q9+, Q7s+, .4(Q6s), JT, J8s+, T9s } [37.4%]

      Image


Results from http://www.HoldEmRanger.com
Code:
864,185,888 evaluations, 349,158 hole card combos

Pre-flop

  Wins     Ties   Equity     Fold
43.27%    1.90%   45.18%      -     ( 22+,A2s+,K2s+,Q2s+,J3s+,T4s+,95s+,84s+,74s+,64s+,53s+,43s(71),A2o+,K2o+,Q7o+,J8o+,T8o+,97o+,87o,76o )
52.92%    1.90%   54.82%   63.36%   ( 22+,A2s+,K2s+,Q7s+,Q6s(40),J8s+,T9s,A2o+,K5o+,Q9o+,JTo / Q6s(60),Q5s-Q2s,J7s-J2s,T8s-T2s,92s+,82s+,72s+,62s+,52s+,42s+,32s,K4o-K2o,Q8o-Q2o,J9o-J2o,T2o+,92o+,82o+,72o+,62o+,52o+,42o+,32o )

So I get...

  • <sb, JoF>= ((770+.71(4))/1326)(.3664(.4518(20)-10)+.6336(1))-((552+.29(4))/1326)(.5)
  • <sb, JoF>= -.045bb

StoxEV (rounded) and HoldemResources (approximation) produce the ~same result.

Attachment:
stockEV.png
stockEV.png [ 23.2 KB | Viewed 2054 times ]


So yeah, this is trivial and actually pretty well-known. In fact 2p2'er eastbay went public w/ this game's value almost exactly 4 years ago to the day (that game featured blinds of 200/400, so sb dropped 18.1/400= .04525bb).


HU JoF - 20bb

  • sb: { 22+, Ax, K9+, K4s+, Q9+, Q6s+, .89(Q5s), J9+, T9-98, J8s-96s, J7s-T6s, T8s-75s, 87s-54s } [40.3%]

      Image

  • bb: { 33+, A5+, Axs, KT+, K9s, .01(QJo), QTs+ } [21.7%]

      Image


Results from http://www.HoldEmRanger.com
Code:
1,382,442,112 evaluations, 141,272 hole card combos

Pre-flop

  Wins     Ties   Equity     Fold
41.88%    2.09%   43.97%      -     ( 22+,A2s+,K4s+,Q6s+,J7s+,T6s+,96s+,86s+,75s+,65s,54s,A2o+,K9o+,Q9o+,J9o+,T9o,98o )
53.94%    2.09%   56.03%   79.11%   ( 33+,A2s+,K9s+,QTs+,A5o+,KTo+,QJo(01) / 22,K8s-K2s,Q9s-Q2s,J2s+,T2s+,92s+,82s+,72s+,62s+,52s+,42s+,32s,A4o-A2o,K9o-K2o,QJo(99),QTo-Q2o,J2o+,T2o+,92o+,82o+,72o+,62o+,52o+,42o+,32o ) 

So I get...

  • <sb, JoF>= ((530+.89(4))/1326)(.2089(.4397(40)-20)+.7911(1))-((792+.11(4))/1326)(.5)
  • <sb, JoF>= -.183bb

Again, StoxEV and HoldemResources produce the ~same result.

And again, yeah, trivial, though probably not as well-known. Anyway, this matches the value that Indy posted earlier in this thread.

Now for something a little more interesting, the 20bb min-raise game you proposed, less sb's option to open-jam...

HU R2oF vs. JoF - 20bb

  • sb
    • min-raise: { 22+, Ax, K7+, K4s+, Q9+, Q8s, JT, J9s+, T9s, .71-.84(K3-, K6o-, Q7-, Q8o, J8-, J9o, T8-, T9o, 98-, 87-, 76-, 65-, 54-, 43-, 32) } [85.2%]
    • call-off : { 22+, Ax, K7+, K4s+, QT+, .25(Q9o), Q8s, JT, J9s+, T9s } [33.6%]

        Image___Image

  • bb, jam: { 22+, Ax, K5+, .63(K4o), Kxs, Q9+, .93(Q8o), Q3s+, .38(Q2s), J9+, J5s+, .08(J4s), T9-98, .64(T8o), T6s+, 95s+, .88(87o), 85s+, 76s-54s, 75s-53s, .5(74s) } [50.0%]

      _____ Image

Here I get...

<sb, R2oF; bb, JoF>= .125bb

Which interestingly enough matches the value that Indy posted earlier in this thread, despite the sb's lack of an (albeit rarely used) open-jam option. But I think this program might tend to undervalue the jammer slightly (eg., the first 2 games result in values of -.054 and -.195 for sb), so that may explain it.

And I suppose the seeming arbitrarity of sb's bet/fold distribution is also indicative of a weakness in the algorithm.


Top
 Profile  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Fri Oct 09, 2009 4:18 pm 
Offline
PokerAI fellow
User avatar

Posts: 1239
Favourite Bot: my bot
@Chipp avatar is Bill Chen, right?


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Fri Oct 09, 2009 9:49 pm 
Offline
New member
User avatar

Posts: 3
Favourite Bot: CMU
Yep.


Top
 Profile  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Fri Oct 09, 2009 11:24 pm 
Offline
Senior member
User avatar

Posts: 100
Favourite Bot: LGC
I tried solving a few of the NL variants discussed here with an LP to get more accurate answers (though I didn't get much greater accuracy as it turned out).

Value is from the SB point of view in big blinds, and is exact to stated accuracy (unless I have a bug).

Jam/Fold
20BBs
value = -0.1832

Call/Check/Jam/Fold
10 BBs
value = -0.026

SB: fold/minraise then fold/call-allin
BB: Jam/Fold
20 BBs
value = +0.117

SB: fold/minraise/jam then fold/call-allin
BB: Jam/Fold
20 BBs
value = +0.117

Note that the final two games do appear to have the same value, but my values disagree slightly with Indiana's and Chipp's values.

Marv


Top
 Profile  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Sat Oct 10, 2009 2:22 am 
Offline
New member
User avatar

Posts: 3
Favourite Bot: CMU
Cool, I appreciate you taking the time to weigh in.

ok|select wrote:
<snip>

Note that the final two games do appear to have the same value [+0.117bb/hand], but my values disagree slightly with Indiana's and Chipp's values.


I see. This leads me to question something I neglected to mention...

indiana wrote:
indiana wrote:
Yes, I have computed the NEQ for this case (SB: push/fold/raiseCall/RaiseFold, BB: push/fold). The EV is not 23 bb/100h, but rather 12.5 bb/100 (same issue that I mistakenly posted the EV in $, not in big blinds).

And here are the numbers:

blinds 1.0/2.0, stacks 40.0

EVsb: 0.23108[$/hand]

<snip strat>


I disregarded the discrepancy here (.125bb per hand and .23108/2= .11554bb per hand) assuming it was due to rake, as I get a nearly identical $value for 5/10 w/ a rake of .05 per 1, cap of 1 (.116bb/hand), but perhaps this is not the case. Indy?


Top
 Profile  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Sun Oct 18, 2009 4:40 pm 
Offline
PokerAI fellow
User avatar

Posts: 7731
Favourite Bot: V12
I'm not sure what's the question here, but basically,

The EVsb of 0.23108 is in $, and as BB is 2$, this makes it an EV of 0.11554.

So the "disagreement" with ok|select is 0.1155 vs 0.117 bb/h. I'm not sure where the difference comes from, but I can imagine that the error is easily on my side.

_________________
indiana


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Fri Feb 11, 2011 11:45 am 
Offline
Junior member
User avatar

Posts: 12
Favourite Bot: TBF
Bumping this somewhat old thread.

The 50% defense push range for the BB is also intuitively correct since it actually coincide with the lower bound that has to be defended without giving the SB opener money (by folding too much).

Also, it seems to me that changing the SB opening to 3x makes the push/fold restriction a much better situation for BB; not as big overbet for the jam, and worse risk/reward for the SB. I'd even say its -EV for SB to open to 3x (excluding other options). Anybody else seeing similar results?


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Thu Nov 29, 2012 8:33 am 
Offline
PokerAI fellow
User avatar

Posts: 1115
Favourite Bot: Johnny #5
I'm officially dumbfounded... For the life of me I can't figure out why this always goes to min-bet 100% of the time. I've used the same CFRM code to solve large HUL games without incident.

Code:
   
    Private Sub createGame()

        GameTreeNode.bb = 2
        GameTreeNode.starting_stack = GameTreeNode.bb * 20

        Dim game as DecisionN = _
        addChildren_PushFold(0, 0, 1, 0, _
        New Double() {GameTreeNode.starting_stack - (GameTreeNode.bb / 2), _
                            GameTreeNode.starting_stack - GameTreeNode.bb}, _
        GameTreeNode.bb + (GameTreeNode.bb / 2), GameTreeNode.bb / 2, "")

    End Sub


    Private Shared Function addChildren_PushFold(ByVal turn As Integer, ByVal round As Integer, ByVal betround As Integer, _
    ByVal total_bets As Integer, ByVal stacks() As Double, ByVal pot As Double, ByVal lb As Double, ByVal hand_history As String) As GameTreeNode

        Dim sb As Double = GameTreeNode.bb / 2
        Dim bb As Double = GameTreeNode.bb

        If hand_history.Length > 0 Then
            Select Case hand_history(hand_history.Length - 1)
                Case "a"

                    Dim fold_value As Double = GameTreeNode.starting_stack - stacks(turn)

                    ' Fold or Call
                    Return New DecisionN(turn, round, hand_history, _
                    New Fold(turn, -fold_value, hand_history & "f"), _
                    New Showdown(GameTreeNode.starting_stack, hand_history & "c"))

                    Exit Select

            End Select
        End If



        If round = 0 Then

            Select Case betround
                Case 0 : Throw New Exception("betround = 0 on preflop.")
                Case 1
                    ' Fold, min-raise, all-in

                    Dim new_stacks(1)() As Double
                    Dim min_bet As Double = Math.Max(lb, bb)

                    new_stacks(0) = stacks.Clone
                    new_stacks(1) = stacks.Clone

                    new_stacks(0)(turn) -= sb + min_bet     ' lb + min bet
                    new_stacks(1)(turn) = 0                 ' all-in

                    Return New DecisionN(turn, round, hand_history, New Fold(turn, -sb, hand_history & "f"), _
                    addChildren_PushFold(turn Xor 1, round, betround + 1, total_bets + 1, new_stacks(0), pot + sb + min_bet, min_bet, hand_history & "r"), _
                    addChildren_PushFold(turn Xor 1, round, betround + 1, total_bets + 1, new_stacks(1), pot + stacks(turn) - sb, stacks(turn) - sb, hand_history & "a"))

                Case 2

                    Dim new_stacks() As Double = stacks.Clone

                    new_stacks(turn) = 0                 ' all-in

                    Dim fold_value As Double = GameTreeNode.starting_stack - stacks(turn)

                    Return New DecisionN(turn, round, hand_history, New Fold(turn, -fold_value, hand_history & "f"), _
                    addChildren_PushFold(turn Xor 1, round, betround + 1, total_bets + 1, new_stacks, pot + stacks(turn) - lb, stacks(turn) - lb, hand_history & "a"))

            End Select

        End If

        ' Should never happen.

        Throw New Exception("Round out of range: " & hand_history & vbCrLf & _
                            "Round: " & round & vbCrLf & _
                            "Stack 0: " & stacks(0) & vbCrLf & "Stack 1: " & stacks(1))

        Return Nothing

    End Function


Top
 Profile  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Mon Feb 04, 2013 9:28 am 
Offline
New member
User avatar

Posts: 9
Favourite Bot: gto
http://www.amazon.com/Expert-Heads-Limi ... 1904468942

this book should help answer some of the questions ITT


Top
 Profile E-mail  
 
 Post subject: Re: Headsup NL Short Stack Nash Equilibrium
PostPosted: Tue Feb 26, 2013 4:06 pm 
Offline
Level1 member
User avatar

Posts: 40
Favourite Bot: own
Just finished my first simulations for a similar game with 10bb stacks and want to share my results:

Player 1 follows a fold/minRaise/shove strategy. Player 2 follows a push or fold strategy when in the SB, when in the BB, he uses the reshoving/calling ranges from the CFRM opponent in Player 1's model.

Both models were learned with 100M iterations chance sampled CFRM. The evaluation was performed by 100M games playing against each others with holecards swiched after each game to reduce variance.

Result: Player 1 outperforms Player 2 with a winrate of 7.64bb/100 even with these shallow stack sizes...


Top
 Profile E-mail  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 39 posts ]  Go to page Previous  1, 2


Who is online

Users browsing this forum: No registered users and 14 guests


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:
Jump to: