Poker-AI.org

Re: Implementation for a Nash Equilibrium solver

2013-07-22T12:27:02+00:00

Heh ok thanks

Statistics: Posted by febbriz — Mon Jul 22, 2013 12:27 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-21T20:45:20+00:00

febbriz wrote:

They also use a LUT for hand rank in the code; it's going to be Huge!

You haven't seen anything yet

febbriz wrote:

Is there a full LUT freely available for: (holecards, board) -> strength?
And a function which takes 7 cards and computes the canonical form that the LUT uses as keys

No. Don't be lazy

febbriz wrote:

there should be 1127*42769 possible canonical forms is that right?

A little less I think

Statistics: Posted by spears — Sun Jul 21, 2013 8:45 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-21T17:50:34+00:00

Is there a full LUT freely available for: (holecards, board) -> strength?
And a function which takes 7 cards and computes the canonical form (there should be 1127*42769 possible canonical forms is that right?) that the LUT uses as keys

Statistics: Posted by febbriz — Sun Jul 21, 2013 5:50 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-21T15:10:11+00:00

Ok thanks

They also use a LUT for hand rank in the code; it's going to be Huge!

Statistics: Posted by febbriz — Sun Jul 21, 2013 3:10 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-21T14:26:34+00:00

febbriz wrote:

Ok thanks for the link

If I just have the buckets, how can I deduce the utility function?
I'd need a LUT telling me for each pair of flops buckets (resp. turn buckets, resp. river buckets), what is the EV

But if I know the winner for this iteration, I can just say that for this round, player X wins the whole pot

Just follow the papers and amax's nice code posted here http://poker-ai.org/archive/www.pokerai ... 335#p40335

Statistics: Posted by spears — Sun Jul 21, 2013 2:26 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-21T14:08:11+00:00

Statistics: Posted by febbriz — Sun Jul 21, 2013 2:08 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-21T12:40:18+00:00

febbriz wrote:

I think I'll make directly LUTs for the river, by using the ideas in
http://www.poker-ai.org/archive/www.pok ... f=3&t=1989

Your ref is good for flop and turn. A better approach for river is viewtopic.php?f=24&t=2485&view=previous

febbriz wrote:

I need a LUT : holecards + board -> "number given by some hand evaluator", and a LUT : holecards + board -> "homemade buckets", right?

I think you just need the second, but I don't know for sure.

Statistics: Posted by spears — Sun Jul 21, 2013 12:40 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-21T09:59:49+00:00

Yes thanks that's the topic I was referring to
I think I'll make directly LUTs for the river, by using the ideas in
http://www.poker-ai.org/archive/www.pok ... f=3&t=1989

But just to be sure before starting, I need a LUT : holecards + board -> "number given by some hand evaluator", and a LUT : holecards + board -> "homemade buckets", right?

thanks

Statistics: Posted by febbriz — Sun Jul 21, 2013 9:59 am

Re: Implementation for a Nash Equilibrium solver

2013-07-20T21:57:43+00:00

febbriz wrote:

My implementation looks ok now, but it can only make 5k iterations/second while there was a thread where people were claiming more than 1M ips. Even though it was on different machines, I guess I still have a lot of room for improvement.

Right now, at each iteration, my algorithm draws 9 random cards, and computes the winner using a c++ hand evaluator as well as the homemade hand buckets with a homemade function. Instead of this last homemade function, i should probably have a huge look-up table, right? I guess it could fit in memory if the LUT contains about 40k*169 entries (for all boards*holecards) storing an index presenting the buckets (at most 20 bits)

Where else should I get LUTs to improve performance?

There are 16432 turns and 1127 holecards and lots of info on LUTS if you search. The next big benefit comes from removing recursion.
http://www.poker-ai.org/archive/www.pok ... view=print

Statistics: Posted by spears — Sat Jul 20, 2013 9:57 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-20T19:22:13+00:00

Statistics: Posted by febbriz — Sat Jul 20, 2013 7:22 pm

Re: Implementation for a Nash Equilibrium solver

2013-07-05T09:01:13+00:00

However I'm still having trouble understanding the EHS and EHS2 history bucketing thing

Statistics: Posted by liuyelian — Fri Jul 05, 2013 9:01 am

Re: Implementation for a Nash Equilibrium solver

2013-05-28T08:39:00+00:00

thanks

for external sampling, i thought i needed to have lookup tables storing the probability of a bucket winning against another bucket when going all-in, and this for each street, but actually i may not need those

at each iteration, i should just draw 9 random cards, check in which bucket they are, and if the hand goes all-in on the flop, give the whole pot to the winner, right?

my program is in c++, which hand evaluator should i use to determine the winner? (something which is not very memory demanding)
and what is the most efficient way to draw 9 random cards? right now i just have an array of bool storing which cards were picked and then pick a random card until i have 9 (distinct ones)

Statistics: Posted by febbriz — Tue May 28, 2013 8:39 am

Re: Implementation for a Nash Equilibrium solver

2013-05-16T17:14:33+00:00

febbriz wrote:

betwin, i think i saw an implementation in c# for rhode island, but i don't remember where

It is here : http://poker-ai.org/archive/www.pokerai.org/pf3/viewtopicba91.html?f=64&t=2922&st=0&sk=t&sd=a&start=40

Statistics: Posted by LOLWorld — Thu May 16, 2013 5:14 pm

Re: Implementation for a Nash Equilibrium solver

2013-05-16T14:56:41+00:00

febbriz wrote:

Also, how legal do you think this is (for big sites like ps or ftp)? I guess computing the strategies and looking at them/learning them is fine, but not while playing right? It's like looking at push/fold nash equilibrium tables while playing, probably forbidden too isn't it?

just keep the solution on another computer? oh, and make sure you put some cloth over your webcam if you have one. and tinfoil the walls in your grinding room.

Statistics: Posted by somehomelessguy — Thu May 16, 2013 2:56 pm

Re: Implementation for a Nash Equilibrium solver

2013-05-16T13:25:52+00:00

betwin, i think i saw an implementation in c# for rhode island, but i don't remember where

My implementation is now working for basic preflop games, now onto the hard work!

external sampling doesn't seem to converge very rapidly, even after 1 billion iteration, strategies for simple 3bet-4bet-5bet games have some (small) regions of hands where the strategy isn't very clear. According to you, what should i improve next?
the strategies sometimes have undefined or non-zero raising frequencies for, for instance, 5betting, while the frequency is 0 for 3betting. This looks normal because a node can be trained in the beginning even though it becomes non reachable after. How can I safely modify the cumulative strategies so that for each hand, frequency(3bet) equals 0 implies that frequency(5bet) equals 0? I mean, doing a simple traversal and setting everything to 0 might not be safe, because it could happen that the frequency of 3betting gets higher than 0 at some point?
for postflop, if I use the "intuistionistic" hand strength, then I'll have to precompute LUT for determining the equity of going all-in for any match up and for any street, right? Basically that's like for preflop when we're using a table giving us the equity of QJs vs ATo etc.

Statistics: Posted by febbriz — Thu May 16, 2013 1:25 pm

Re: Implementation for a Nash Equilibrium solver

2013-05-11T19:15:37+00:00

Check the poker papers section here and especially in the archives for all important poker papers on CFRM and abstraction techniques. All of your questions have been discussed in those basically.

Statistics: Posted by Coffee4tw — Sat May 11, 2013 7:15 pm

Re: Implementation for a Nash Equilibrium solver

2013-05-06T19:32:00+00:00

About the hs and hs^2 metric, from what I understand this is simply the probability of winning the hand against a random hand. Wouldn't it make more sense to use hs or hs^2 (or hs^numberfromopponentmodel?) against the hands the opponent is most likely holding?

The idea of using more natural buckets sounds like using 'features' instead of buckets, creating some huge hyperdimensional feature space. You'll probably want to use some clustering algorithm to reduce dimensionality again (which may or may not bring you close to the hs^2 metric?).

How should one handle bet sizes for NL? Adding different pot%s to the histories seems straightforward but won't that make the tree grow exponentially? What memory would be needed (I have 2 16G machines and willing to upgrade to 128 )?

Has anyone here already posted code (c#?) or a good paper for a basic CFRM algorithm for HUNL? It sure would be helpful for us newbies

Statistics: Posted by betwin — Mon May 06, 2013 7:32 pm

Re: Implementation for a Nash Equilibrium solver

2013-05-04T08:06:36+00:00

Might this be a problem?

Quote:

Let ZI be the subset of all terminal histories where a prefix of the history is in the set I; for
z ∈ ZI let z[I] be that prefix. Since we are restricting ourselves to perfect recall games z[I] is
unique. Define counterfactual value vi(σ, I) as [...]

Statistics: Posted by febbriz — Sat May 04, 2013 8:06 am

Re: Implementation for a Nash Equilibrium solver

2013-05-04T07:43:28+00:00

I'm now starting the implementation, I will first go with external sampling, from the paper Monte Carlo Sampling for Regret Minimization in Extensive Games
However they seem to assume everywhere that their game is perfect recall, but they say at the end:

Quote:

Lastly, it seems like this work could be naturally extended to cases where we don’t assume perfect recall. Imperfect recall could be used as a mechanism for abstraction over actions, where information sets are grouped by important partial sequences rather than their full sequences.

Can I use their work as is? Or do I need to pay extra attention to the fact that my game is played on an (acyclic) graph rather than on a tree?

Statistics: Posted by febbriz — Sat May 04, 2013 7:43 am

Re: Implementation for a Nash Equilibrium solver

2013-04-30T10:18:51+00:00

The size of a megabyte generally depends on whether you're buying or selling it.

Any looking at optimal bots, I always find you need more RAM than you think.

8 core 32GB machine, here we come!

Statistics: Posted by OneDayItllWork — Tue Apr 30, 2013 10:18 am

Re: Implementation for a Nash Equilibrium solver

2013-04-24T21:51:07+00:00

somehomelessguy wrote:

proud2bBot wrote:

no, one action/bucket combo needs 2 doubles = 16 byte. 3 (actions) * 20000 (buckets) * 16 byte = 960000 byte = 0,915MB. Multiply that with the numer of decisions and I'd be surprised if your notebook can handle it... Regarding the tree building: for smaller trees its fine, for bigger ones you might want to generate it programmatically.

i.e. 500.

you made the same calculation he did, all though you used some weird definition of mega

OP estimated "this makes about 10M decisions nodes" - this is a little bit different... And the "weird definition" is pretty standard when talking about storage capacity

Statistics: Posted by proud2bBot — Wed Apr 24, 2013 9:51 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-24T17:09:07+00:00

HontoNiBaka wrote:

somehomelessguy wrote:

proud2bBot wrote:

i.e. 500.

you made the same calculation he did, all though you used some weird definition of mega

A megabyte is not a million byte

depends on who you ask. if you ask IEC, IEEE or common sense you get a million. if you ask bill gates you get 1024*1024.

/nerdrage offtopic mode off.

Statistics: Posted by somehomelessguy — Wed Apr 24, 2013 5:09 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-24T15:35:16+00:00

ye he used 1Mb = 1024*1024 bytes i think
but anyway in the end you get about ~500MB so it should be fine right?

about the trees you're right, i'll program them directly within my code

Statistics: Posted by febbriz — Wed Apr 24, 2013 3:35 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-24T15:32:53+00:00

somehomelessguy wrote:

proud2bBot wrote:

i.e. 500.

you made the same calculation he did, all though you used some weird definition of mega

A megabyte is not a million byte

Statistics: Posted by HontoNiBaka — Wed Apr 24, 2013 3:32 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-24T15:09:30+00:00

proud2bBot wrote:

i.e. 500.

you made the same calculation he did, all though you used some weird definition of mega

Statistics: Posted by somehomelessguy — Wed Apr 24, 2013 3:09 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-24T14:18:37+00:00

febbriz wrote:

if I have 500 betting sequences, 20k buckets/round (no recall), this makes about 10M decisions nodes
for each decision node, i need 2 double per actions; usually i'll have 3 actions, so i need 48 bytes, so a total of 480MB

is this right?

Statistics: Posted by proud2bBot — Wed Apr 24, 2013 2:18 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-24T09:59:57+00:00

also, what do you think would be a nice way to represent betting sequences (this is one input of the program, so it could be in any format)

in JSON it looks like that, but it's already a mess while they just posted the blinds!

Code:

{
  "p": 0,
  "decisions": [{
    "action": "r",
    "value": 0.5,
    "target": {
      "p": 1,
      "decisions": [{
        "action": "r",
        "value": 1,
        "target": {
          "decisions": [
            { 
              "action": "r",
              "value": 3,
              "target": {
                "p": 0,
                "decisions": []
              }
            },
            {
              "action": "c",
              "target": {
                "decisions": []
              }
            },
            { "action": "f" }
          ]
        }
      }]
    }
  }]
}

Statistics: Posted by febbriz — Wed Apr 24, 2013 9:59 am

Re: Implementation for a Nash Equilibrium solver

2013-04-24T09:28:08+00:00

Statistics: Posted by febbriz — Wed Apr 24, 2013 9:28 am

Re: Implementation for a Nash Equilibrium solver

2013-04-23T22:00:52+00:00

If you really want to have that many buckets on the flop, and a similar number on turn/river and analyze anything else than the simplest PoF games, I'd recommend to buy a looooooooooooot more RAM...
Just build a simple game tree with the betting abstraction you want and count the decision nodes on each street. For each bucket you need two doubles to store regret/strategy - that should give you an idea how much buckets you can effort... My guess is: way way less than you think/wish

Statistics: Posted by proud2bBot — Tue Apr 23, 2013 10:00 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-23T19:23:41+00:00

febbriz wrote:

I should have said that my primary objective is not really to make a bot, but a solver that would give me intuition and ideas to integrate into my own game. These are my first ideas on the abstraction that I would use:

Preflop: 169 buckets (or less if that's too much?)
Flop: (72*240 = 17280 buckets) (probably too much)
- Board buckets: (3*8*3 = 72 buckets)
  - (3) monotone, two-tone, rainbow
  - (8) connected, one gap, two gaps, more gaps, paired (high/low) connected, paired (high/low) not connected
  - (3) highcard A, T-K, <= 9
- Hand Strength buckets: (12*5*4 = 240 buckets)
  - (12) sets and better, top2 pairs (no pair in hand), 2 pairs (no pair in hand), TopPair A kicker, TP T-K kicker, TPWK, SecondPair T+ kicker, SPWK, overpair in our hand (includes two pairs), pair in our hand (no overpair, includes two pairs), pair, nothing
  - (5) FD with 2 colors in hand, FD with one color in hand, BDFD with two colors in hand, BDFD with one color in hand, nothing
  - (4) OESD or DoubleGutter with 2 in hand, OESD with one in hand, Gutshots, nothing
Turn, River: ? still need to think about it

Does this look like a useful abstraction to you? Is that too much buckets? Unnecessary buckets?
Do you think that such abstractions are a mess to program? Also, is the abstracted game easy to create, or possible at all?
Also, I'm assuming that when using such abstractions, we cannot take into account blockers, is that right?
How much betting sequences can I analyze if I use that many buckets on a standard laptop with 2GB of ram?

I'm thinking that getting strategies in term of distributions over these buckets would give me a good insight on how to improve my own game, and it would also help me spot my mistakes

Thanks for your help

17000 buckets on the flop is not too bad. the river has far more sequences than the flop, so that is where it will become a problem, especially if you want to recall the past board textures. (and on the turn have 72*(flush hit/blanked, straight hit/blanked, overcard hit/blanked) board buckets etc. by the river both the betting tree and the board buckets will have escalated.

i very much doubt the hand strength buckets you are using would perform better than using a hs^2 or hs^2/hs nested metric, but may be more useful to you for analysis.

Statistics: Posted by somehomelessguy — Tue Apr 23, 2013 7:23 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-23T11:53:24+00:00

Preflop: 169 buckets (or less if that's too much?)
Flop: (72*240 = 17280 buckets) (probably too much)
- Board buckets: (3*8*3 = 72 buckets)
  - (3) monotone, two-tone, rainbow
  - (8) connected, one gap, two gaps, more gaps, paired (high/low) connected, paired (high/low) not connected
  - (3) highcard A, T-K, <= 9
- Hand Strength buckets: (12*5*4 = 240 buckets)
  - (12) sets and better, top2 pairs (no pair in hand), 2 pairs (no pair in hand), TopPair A kicker, TP T-K kicker, TPWK, SecondPair T+ kicker, SPWK, overpair in our hand (includes two pairs), pair in our hand (no overpair, includes two pairs), pair, nothing
  - (5) FD with 2 colors in hand, FD with one color in hand, BDFD with two colors in hand, BDFD with one color in hand, nothing
  - (4) OESD or DoubleGutter with 2 in hand, OESD with one in hand, Gutshots, nothing
Turn, River: ? still need to think about it

Statistics: Posted by febbriz — Tue Apr 23, 2013 11:53 am

Re: Implementation for a Nash Equilibrium solver

2013-04-19T16:38:17+00:00

if you can create a good abstraction by intuition it should work as well, but its very tough to do it manually: you are probably thinking sth like Top pait=r, 2 Pairs, etc, but a TP with 72o on 743r is different than A2 on A72r and also J2o on J552r is different than J2o on JcTc9c8c...

Statistics: Posted by proud2bBot — Fri Apr 19, 2013 4:38 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-19T15:20:37+00:00

febbriz wrote:

what do you think about using intuitionistic buckets (tptk,etc.) instead of EHS or EHS2?

You can always try it and test it against other bots. Personally I dont think its a good idea, because first of all on some boards there will be very little combinations of lets say a pair, so you will be wasting buckets a HS/HS2 rating will automatically take care of relative handstrength on different boards.

I also think, that this kind of thinking comes natural to humans, but has little mathematical justification. In my experience the natural/naive algorithms produce worse results than those based on mathematical principles.

Statistics: Posted by HontoNiBaka — Fri Apr 19, 2013 3:20 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-16T08:56:12+00:00

Dunno if you will find this useful, but since it took me 10 mins to find it I'm going to post it anyway
http://www.poker-ai.org/archive/pokerai ... 20&p=36668

Statistics: Posted by spears — Tue Apr 16, 2013 8:56 am

Re: Implementation for a Nash Equilibrium solver

2013-04-16T07:59:01+00:00

cool, I'll first try with 100 buckets/round and 1000 bettings sequence i guess that should fit in memory

what do you think about using intuitionistic buckets (tptk,etc.) instead of EHS or EHS2?

Statistics: Posted by febbriz — Tue Apr 16, 2013 7:59 am

Re: Implementation for a Nash Equilibrium solver

2013-04-15T20:43:58+00:00

febbriz wrote:

imperfect recall has better results?

So do you think that implementing an abstraction with imperfect recall and about 10k buckets/round + 1000 betting sequences (10M decision nodes total) would make sense and lead to good results?

is CFR still easy to implement with imperfect recall, or possible at all?

yes, imperfect recall is better given a fixed amount of memory.
well, if it fits into your memory, it surely will lead to good results, but I doubt you have the resources just build a game tree and try out how much buckets per round can fit into memory...

Statistics: Posted by proud2bBot — Mon Apr 15, 2013 8:43 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-15T19:22:20+00:00

Statistics: Posted by febbriz — Mon Apr 15, 2013 7:22 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-15T16:24:05+00:00

yes, the keywords are perfect recall (you remember history) and imperfect recall (you dont know which bucket you are coming from). It has shown that the latter typically leads to better results.

Statistics: Posted by proud2bBot — Mon Apr 15, 2013 4:24 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-15T14:32:52+00:00

Thanks, it's very interesting. I have read the first three chapters for now (do I need more for now?)

However I'm still having trouble understanding the EHS and EHS2 history bucketing thing
From what I understood, they use 5 to 10 buckets per rounds, and they make decisions based on the sequence of buckets for PF,Flop,Turn,River. When they use 5 buckets, this increases the number of decision nodes by a factor of ~625

I understand that if you fix yourself 5 buckets/round, then history bucketing will give you better strategies. But now what if you're able to "forget" which buckets you were in, and for instance merge all the states on Turn which have the same Turn bucket (regardless of Preflop/Flop buckets)? In that case you could use about directly use about 600buckets/round and get a game which has ~the same size than the previous one.

This looks closer to the way poker players would think, especially if you define the buckets to be what I said earlier: "nutted hands, top2, 2p, TPTK, TPGK, second pair GK, second pair bad kicker, two overs, one over, flush draw, bdfd, straight draw, bdsd, flush draw + pair, etc." I guess one drawback of this is that you would have to define buckets manually, rather than computer directly from EHS and EHS2

Do you think this would be possible?

Statistics: Posted by febbriz — Mon Apr 15, 2013 2:32 pm

Re: Implementation for a Nash Equilibrium solver

2013-04-06T15:45:34+00:00

I'd recommend to read Michael Johansons Master thesis. Most of the question will e clear after that

Statistics: Posted by proud2bBot — Sat Apr 06, 2013 3:45 pm

Implementation for a Nash Equilibrium solver

2013-04-06T14:04:38+00:00

Hi everyone,

I'm starting an implementation that would take as input a restricted form of a HUNL game, and compute a Nash Equilibrium. It would first of all be restricted in terms of bettings sequences and second, it would use a card/board abstraction for the game to be tractable.

About this last part, I've just read about bucketing, but I'm not sure I understand about history bucketing. Do we really need it? I was thinking about creating buckets for the flop in the form of: nutted hands, top2, 2p, TPTK, TPGK, second pair GK, second pair bad kicker, two overs, one over, flush draw, bdfd, straight draw, bdsd, flush draw + pair, etc., and similar stuff for turn, and for the river I guess you just need hand strength separated in N buckets

Then a decision node in the game would be composed of a betting sequence, and a bucket. If we want to have less than 10M decision nodes for instance, we could use 1000 betting sequences and 10k buckets per round
I think I'm missing something important there, 10k buckets seems a lot!

Finally, I'll use something like external sampling to solve the abstracted game

Would you say that this is currently the best approach to get an approximation of a Nash equilibrium for the whole game?
I'll do the implementation in c/c++ ; how much decision nodes will I be able to handle with external sampling, and how much betting sequences/buckets would you say I should use?

Also, which paper do you think presents the external sampling algorithm in the most understanble way so that I can implement it easily? And would you have other links that would help me understand better this whole thing?

Thanks

Statistics: Posted by febbriz — Sat Apr 06, 2013 2:04 pm