Poker-AI.org

Poker AI and Botting Discussion Forum
It is currently Fri Dec 06, 2019 11:20 pm

All times are UTC




Post new topic Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Fri Jul 26, 2019 4:23 am 
Offline
Junior Member

Joined: Wed Jun 26, 2019 4:02 am
Posts: 28
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.


Top
 Profile  
 
PostPosted: Fri Jul 26, 2019 4:44 pm 
Offline
New Member

Joined: Tue Mar 20, 2018 1:54 pm
Posts: 4
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.


Top
 Profile  
 
PostPosted: Fri Jul 26, 2019 9:26 pm 
Offline
Junior Member

Joined: Wed Jun 26, 2019 4:02 am
Posts: 28
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.


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

All times are UTC


Who is online

Users browsing this forum: No registered users and 4 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:
cron
Powered by phpBB® Forum Software © phpBB Group