| Poker-AI.org http://poker-ai.org/phpbb/ |
|
| Fastest way to deal with allins in cfr? http://poker-ai.org/phpbb/viewtopic.php?f=24&t=3238 |
Page 1 of 1 |
| Author: | Fossana [ Fri Jul 26, 2019 4:23 am ] |
| Post subject: | Fastest way to deal with allins in cfr? |
Let’s say two players are allin before the river. Is there a faster way to calculate the utility of each hand for the player of interest than calculating showdown utilities for every runout and aggregating the results? Like for example, if both players are allin before the turn, there’s 48 possible rivers, so you could just do 48 showdown calculations and return the weighted sum of the results. For allins on the flop, you can save time by doing 49*24 runouts rather than 49*48 runouts since the order of the turn and river doesn’t matter. The motivation for this is that I noticed piosolver was 25% faster on a tree that required 14k showdown calculations, 4.8k fold calculations, and 9.6k decision node calculations vs a tree with 9.4k showdown calculations, 8.6k uncontested calculations, and 9.8k decision node calculations (my solver got 50% slower instead, which is what I’d expect due to there being 50% more showdown calculations). The difference is that in the first tree, 7k of the showdown calculations were the result of both players going allin on a street earlier than the river. You could store the equity of every hand in hero’s range vs every hand in villain’s range on the turn, and then just multiply these equities by villains reach probabilities on the turn, but this is O(n^2) whereas doing the showdown calculations requires 48 O(n) calculations. Maybe you can bucket all runouts where flushes aren’t possible? The equities won’t be exact but they may be accurate enough for cfr. I don’t think monte carlo would work since villain’s hands would need to be sampled based on reach probabilities, and getting a random element from an array of probabilities takes O(n) time, which can be brought down to O(1) if you create an alias table, but you’d have to do very few samples to get a large speed improvement and an alias table seems like too complicated of a solution. |
|
| Author: | optimizer [ Fri Jul 26, 2019 4:44 pm ] |
| Post subject: | Re: Fastest way to deal with allins in cfr? |
I use the O(n^2) approach, with computing on GPU. This can be optimised taking into account that often there is more than one showdown node in a tree, so it's possible to batch all evaluations together (this would be a matrix multiplication operation). The funny fact is that this works a little bit better even on the river (like 15% faster for the whole algorithm), because O(n) implementation is quite complex and the constant in the O(n) is big (this is of course depends on the GPU used). BTW the equity matrix can be very efficiently computed using GPU as well. |
|
| Author: | Fossana [ Fri Jul 26, 2019 9:26 pm ] |
| Post subject: | Re: Fastest way to deal with allins in cfr? |
optimizer wrote: I use the O(n^2) approach, with computing on GPU. This can be optimised taking into account that often there is more than one showdown node in a tree, so it's possible to batch all evaluations together (this would be a matrix multiplication operation). The funny fact is that this works a little bit better even on the river (like 15% faster for the whole algorithm), because O(n) implementation is quite complex and the constant in the O(n) is big (this is of course depends on the GPU used). BTW the equity matrix can be very efficiently computed using GPU as well. I’ll definitely have to try out calculating showdown utilities with the GPU. For allins, I realized that the tree I was using (SPR=1, 100% bet sizes) was going to have more allins than a more realistic tree (SPR=5-20), since every bet and call leads to an allin. In other words, I don’t think calculating allins is really a bottleneck worth optimizing. |
|
| Page 1 of 1 | All times are UTC |
| Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |
|