I'd recommend to read Michael Johansons Master thesis. Most of the question will e clear after that
| Poker-AI.org http://poker-ai.org/phpbb/ |
|
| Implementation for a Nash Equilibrium solver http://poker-ai.org/phpbb/viewtopic.php?f=24&t=2445 |
Page 1 of 3 |
| Author: | febbriz [ Sat Apr 06, 2013 2:04 pm ] |
| Post subject: | Implementation for a Nash Equilibrium solver |
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 |
|
| Author: | proud2bBot [ Sat Apr 06, 2013 3:45 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
I'd recommend to read Michael Johansons Master thesis. Most of the question will e clear after that
|
|
| Author: | febbriz [ Mon Apr 15, 2013 2:32 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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? |
|
| Author: | proud2bBot [ Mon Apr 15, 2013 4:24 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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. |
|
| Author: | febbriz [ Mon Apr 15, 2013 7:22 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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? |
|
| Author: | proud2bBot [ Mon Apr 15, 2013 8:43 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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...
|
|
| Author: | febbriz [ Tue Apr 16, 2013 7:59 am ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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? |
|
| Author: | spears [ Tue Apr 16, 2013 8:56 am ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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 |
|
| Author: | HontoNiBaka [ Fri Apr 19, 2013 3:20 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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. |
|
| Author: | proud2bBot [ Fri Apr 19, 2013 4:38 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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... |
|
| Author: | febbriz [ Tue Apr 23, 2013 11:53 am ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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:
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 |
|
| Author: | somehomelessguy [ Tue Apr 23, 2013 7:23 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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:
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. |
|
| Author: | proud2bBot [ Tue Apr 23, 2013 10:00 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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
|
|
| Author: | febbriz [ Wed Apr 24, 2013 9:28 am ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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? |
|
| Author: | febbriz [ Wed Apr 24, 2013 9:59 am ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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" } ] } }] } }] } |
|
| Author: | proud2bBot [ Wed Apr 24, 2013 2:18 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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? 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. |
|
| Author: | somehomelessguy [ Wed Apr 24, 2013 3:09 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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 
|
|
| Author: | HontoNiBaka [ Wed Apr 24, 2013 3:32 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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 A megabyte is not a million byte
|
|
| Author: | febbriz [ Wed Apr 24, 2013 3:35 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
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 |
|
| Author: | somehomelessguy [ Wed Apr 24, 2013 5:09 pm ] |
| Post subject: | Re: Implementation for a Nash Equilibrium solver |
HontoNiBaka wrote: 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 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. |
|
| Page 1 of 3 | All times are UTC |
| Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |
|