Poker-AI.org

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

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



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.

You should read the Johanson et al. paper and the related thread first, if you haven't already. viewtopic.php?f=25&t=2381

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

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.

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.


Then do a bottom up loop from the turn.


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?


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ⁿ⁺¹?


What does point x mean?

Does this make sence to anyone?

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.

That shouldn't be a problem.


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.


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


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).