Poker-AI.org

Re: Potential-Aware Imperfect-Recall Abstraction with EMD

2014-12-20T17:02:02+00:00

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

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:

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?

That shouldn't be a problem.

Quote:

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

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:

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

Statistics: Posted by flopnflush — Sat Dec 20, 2014 5:02 pm

Re: Potential-Aware Imperfect-Recall Abstraction with EMD

2014-12-18T00:29:05+00:00

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.

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?

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

Statistics: Posted by Alan Napier — Thu Dec 18, 2014 12:29 am

Re: Potential-Aware Imperfect-Recall Abstraction with EMD

2014-12-15T21:04:58+00:00

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

Statistics: Posted by spears — Mon Dec 15, 2014 9:04 pm

Re: Potential-Aware Imperfect-Recall Abstraction with EMD

2014-12-15T17:23:25+00:00

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

Statistics: Posted by flopnflush — Mon Dec 15, 2014 5:23 pm

Re: Potential-Aware Imperfect-Recall Abstraction with EMD

2014-12-15T16:57:15+00:00

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.

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 signiﬁcantly 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.

Statistics: Posted by Alan Napier — Mon Dec 15, 2014 4:57 pm

Potential-Aware Imperfect-Recall Abstraction with EMD

2014-12-09T17:28:01+00:00

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

Statistics: Posted by Alan Napier — Tue Dec 09, 2014 5:28 pm