Poker-AI.org

Poker AI and Botting Discussion Forum
It is currently Sun Apr 30, 2017 1:18 am

All times are UTC




Post new topic Reply to topic  [ 6 posts ] 
Author Message
PostPosted: Tue Dec 09, 2014 5:28 pm 
Offline
Junior Member

Joined: Wed Oct 01, 2014 6:59 pm
Posts: 11
Potential-Aware Imperfect-Recall Abstraction with Earth Mover’s Distance in Imperfect-Information Games

by: Sam Ganzfried and Tuomas Sandholm

Abstract

There is often a large disparity between the size of a game we wish to solve and the size of the largest instances solvable by the best algorithms; for example, a popular variant of poker has about 10^165 nodes in its game tree, while the currently best approximate equilibrium-finding algorithms scale to games with around 10^12 nodes. In order to approximate equilibrium strategies in these games, the leading approach is to create a sufficiently small strategic approximation of the full game, called an abstraction, and to solve that smaller game instead. The leading abstraction algorithm for imperfect-information games generates abstractions that have imperfect recall and are distribution aware, using k-means with the earth mover’s distance metric to cluster similar states together. A distribution-aware abstraction groups states together at a given round if their full distributions over future strength are similar (as opposed to, for example, just the expectation
of their strength). The leading algorithm considers distributions over future strength at the final round of the game. However, one might benefit by considering the trajectory of distributions over strength in all future rounds, not just the final round. An abstraction algorithm that takes all future rounds into account is called potential aware. We present the first algorithm for computing potential-aware imperfect recall abstractions using earth mover’s distance. Experiments on no-limit Texas Hold’em show that our algorithm improves performance over the previously best approach.

Link: http://www.cs.cmu.edu/~sandholm/potenti ... aaai14.pdf


Top
 Profile  
 
PostPosted: Mon Dec 15, 2014 4:57 pm 
Offline
Junior Member

Joined: Wed Oct 01, 2014 6:59 pm
Posts: 11
has anyone implemented Algorithm 1 and Algorithm 2 from the paper?

Section 2.2 gives a very clear to understand poker example. I thought to bucket flop hands, i make histograms of them on the turn. Eg.: TcQd-7h9hQh would have a histogram

Image

Such histogram could be represented in an array[50]. Something like {0,0, ... , 0.04, 0, 0.04, ...}

Then k++ mean cluster this flop histograms with a EMD distance function.

But they do something else what i dont really get.
Quote:
We note that Figures 9 and 10 depict the distributions of expected turn hand strength, as opposed to full distributions over distributions of river hand strength (since each turn card will lead to a distribution over strength in the next round, not a single value). For example, for the hand TcQd-7h9hQh, if the turn card is Ad, the hand’s expected equity, assuming a uniform random river card and uniform random hand for the opponent, is 0.695 (though it will vary for individual river cards); so the interval for 0.68–0.7 in the histogram would be incremented by one for that turn card. This is significantly more simplistic than our potential-aware approach, which takes into account the full distribution of turn ‘buckets’, which are themselves distributions over equity intervals after the river.


Top
 Profile  
 
PostPosted: Mon Dec 15, 2014 5:23 pm 
Offline
Junior Member

Joined: Sat Nov 02, 2013 2:21 pm
Posts: 26
You should read the Johanson et al. paper and the related thread first, if you haven't already. viewtopic.php?f=25&t=2381


Top
 Profile  
 
PostPosted: Mon Dec 15, 2014 9:04 pm 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 454
I think I get it.

Consider the flop. Figures 7 and 8 show us a similar equity distribution on the river for two different hands. But these figures don’t say anything about what happens on the turn. A comprehensive treatment of this would give us another dimension - a distribution for each of the bars in the distributions. Instead of this they give us a cheaper substitute - a strength distribution on the turn as shown in Figures 9 and 10


Top
 Profile  
 
PostPosted: Thu Dec 18, 2014 12:29 am 
Offline
Junior Member

Joined: Wed Oct 01, 2014 6:59 pm
Posts: 11
flopnflush wrote:
You should read the Johanson et al. paper and the related thread first, if you haven't already. http://poker-ai.org/phpbb/viewtopic.php?f=25&t=2381


Thanks for the link. Really interresting paper and thread. I saw yout kmeans++ implementation on github. Big thanks for it!


Thre is still a lot of unclear spots so i try to go step by step through the authors' algorithm.

First i realised, we have to precluster the hands to calculate potential.
Image
What abstraction algorithm (S) do you recommend? A naive way would be to take all EHS entry for the round, sort them, and divide them into n equal sized Cluster, where size = numer of all combinations for round / number of desired clusters.

But i bet there is some better method.

Image
Then do a bottom up loop from the turn.

Image
Calculate the mean of each river cluster. I guess this is a simple mean calculation. eg.: cluster 1 :{0.2, 0.21, 0.23, 0.25}
0.2 + 0.21 + 0.23 + 0.25 = 0.89 / 4 = 0.2225. Which is not a member of the data set. Could it be problem?

Image
calculate the distance between every river cluster pair's means. Eg. 0.2225 (from above) and 0.332 => 0.1095. Sounds to simple. What do they mean with distance metric d<sup>n+1</sup>?

Image
What does point x mean?

Does this make sence to anyone?
Quote:
Next, we compute histograms Hn(xn), where the i-th element of Hn(xn) is the fraction of the time that chance’s next move will send xn into cluster i in An+1


Top
 Profile  
 
PostPosted: Sat Dec 20, 2014 5:02 pm 
Offline
Junior Member

Joined: Sat Nov 02, 2013 2:21 pm
Posts: 26
Alan Napier wrote:
flopnflush wrote:
You should read the Johanson et al. paper and the related thread first, if you haven't already. viewtopic.php?f=25&t=2381


Thanks for the link. Really interresting paper and thread. I saw yout kmeans++ implementation on github. Big thanks for it!


Thre is still a lot of unclear spots so i try to go step by step through the authors' algorithm.

First i realised, we have to precluster the hands to calculate potential.
Image
What abstraction algorithm (S) do you recommend? A naive way would be to take all EHS entry for the round, sort them, and divide them into n equal sized Cluster, where size = numer of all combinations for round / number of desired clusters.

But i bet there is some better method.

I don't understand what \^r stands for tbh. I think they cluster the final round by OCHS-feature as in the Johanson et al. paper. They split the preflop hands into 8 equally sized ranges by EHS and calculate EHS for every river vs those 8 ranges. Then they cluster them with kmeans using euclidean distance.
Quote:
Image
Then do a bottom up loop from the turn.

Image
Calculate the mean of each river cluster. I guess this is a simple mean calculation. eg.: cluster 1 :{0.2, 0.21, 0.23, 0.25}
0.2 + 0.21 + 0.23 + 0.25 = 0.89 / 4 = 0.2225. Which is not a member of the data set. Could it be problem?

That shouldn't be a problem.

Quote:
Image
calculate the distance between every river cluster pair's means. Eg. 0.2225 (from above) and 0.332 => 0.1095. Sounds to simple. What do they mean with distance metric d<sup>n+1</sup>?

d^{n+1} is the distance metric of the next round. On the Turn it would be the distance metric that was used to cluster the river.

Quote:
Image
What does point x mean?

I think they mean each possible combination of hole- and boardcards, e.g each possible turn.

Quote:
Does this make sence to anyone?
Quote:
Next, we compute histograms Hn(xn), where the i-th element of Hn(xn) is the fraction of the time that chance’s next move will send xn into cluster i in An+1

It does make sense to me. But I'm sorry that I'm not able to come up with an easy to understand explanation. Multidimensional EMD is not easy for the head, since you can't visualize it. But the algorithm is to slow anyway. That's why they invented the heuristic (algorithm 2).


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

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


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