Poker-AI.org

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2019-07-17T01:52:34+00:00

ScoobySnacks wrote:

For everyone that experimenting with k-means with the Earth Mover Distance, are you guys using the traditional average to compute the centroids of each group (that is treat each histogram as a vector and compute the average of all vectors in a group)? I ask because the average is not guaranteed to be the centroid of a group for metrics other than euclidean. Do you guys think that is what these papers did? Maybe the average is good enough...

I was so confused by this I asked a question on stack exchange: http://stats.stackexchange.com/question ... 823#112823. Someone there provided a good example of why averaging does not always give you the best centroid. Any comments on this?

I have used the traditional average in the past. I know about the theoretical concerns, but for me it still worked fine. The clusters look reasonable and the resulting bot was pretty good.

Statistics: Posted by HontoNiBaka — Wed Jul 17, 2019 1:52 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2019-07-10T07:01:13+00:00

If I calculate the EMD of all possible histograms in the first round of the game, I get a 169x169 matrix like the small 4x4 EMD matrix in Figure 2 (page 4) of the paper.
After performing kmeans clustering on the 169x169 matrix (kmeans++, multiple restarts, 8 clusters) I get a slightly different result like in Table 1 (page 5) of the paper.
My histograms and EMD values are the same like in the paper that is why I think I am doing something wrong between EMD calculation and clustering.

I think they reduce the 169x169 EMD matrix to a 169x1 EMD matrix because otherwise the matrices are getting pretty huge on the second and third round of the game, right?
I am happy for any hint and I am also interested in exchanging information with others who are on the same journey .

Statistics: Posted by uncut — Wed Jul 10, 2019 7:01 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2015-10-01T08:31:33+00:00

Hi Guyz,

I have decided to code a bit and give a try to this method.

I have clustered preflop hands in 8 clusters and these are the results :
preflop_EMD_Clustered.jpeg
Not exactly the same as in the paper...

My histograms aren't really the same as well :
4s4h_Histo.jpeg

What are your results for preflop clustering and histograms ? Do they match the paper ?

Regards,

MrNice

Statistics: Posted by MrNice — Thu Oct 01, 2015 8:31 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2014-08-23T19:06:39+00:00

Statistics: Posted by ScoobySnacks — Sat Aug 23, 2014 7:06 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-11-25T17:35:12+00:00

Goal here was to cluster complete flops (= 2 hole cards + 3 board cards). The ehs2-distributions are against all possible holecards. I created the graphs to evaluate the results. But they are not as good as they look at first view. Some hands with totally different distributions are clustered together. I believe (and hope) that is because I did not use enough clusters and ran only very few iterations.

Statistics: Posted by flopnflush — Mon Nov 25, 2013 5:35 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-11-25T15:58:35+00:00

Your goal here is to cluster public board buckets, right? Did you use all possible hole cards to create the EHS2 distributions? And if so, did you check the boards within a cluster if they are "meaningful", i.e. represent boards that one would typically group together? I tried this too, but did not get the results I expected.

Statistics: Posted by proud2bBot — Mon Nov 25, 2013 3:58 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-11-24T18:53:54+00:00

I clustered all flops using KMeans++, ehs2-histograms with 100 bars, and EarthMoversDistance. One graph = one cluster. One line = one flop. The heat-pixels are the histogram-bars. I hope that was understandable.
Did this (for testing purposes) with k=200 and only 10 kMeans iterations.

Statistics: Posted by flopnflush — Sun Nov 24, 2013 6:53 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-11-24T18:00:12+00:00

Can you elaborate on those graphs?

Statistics: Posted by cantina — Sun Nov 24, 2013 6:00 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-11-24T17:25:29+00:00

Seems to work.

flop-cluster000.png flop-cluster032.png flop-cluster037.png

Statistics: Posted by flopnflush — Sun Nov 24, 2013 5:25 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-11-06T09:20:44+00:00

Hi,
can you tell me if this is right for earth movers distance?

Code:

   protected double distance(double[] v1, double[] v2)
   {
      double emd = 0, totalDist = 0;
      for (int i = 0; i < v1.length; i++)
      {   
         emd = (v1[i] + emd) - v2[i];
         totalDist += Math.abs(emd);
      }
      return totalDist;
   }

Statistics: Posted by flopnflush — Wed Nov 06, 2013 9:20 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-08-14T14:24:11+00:00

I got exact values and they match what you got for 44. I agree the values given in the paper (figure 3) are wrong. Just to be extra sure they made the mistake, you can quickly check with pro poker tools to see that 44 vs 88+ has EV of 0.1891 and not 0.180 like they have shown in their graphic (link).

Statistics: Posted by nonpareil — Wed Aug 14, 2013 2:24 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-08-13T11:32:47+00:00

Hi, thanks for the reply. So performance issues with a high number of buckets aren't imaginary.

Do you have an OCHS lookup table at hand? Did you calculate exact strengths against every cluster or did you use monte-carlo sampling? When I try to calculate OCHS values for the 4s4h hand I get numbers that are slightly different from the ones in the paper. My numbers are:
0.706792 0.637735 0.51629 0.62033 0.506075 0.570617 0.496239 0.189106

I'd appreciate if you could tell whether you get the same values for 4h4s or not.

Statistics: Posted by alex — Tue Aug 13, 2013 11:32 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-08-09T20:11:42+00:00

10^5 buckets is overkill imo. I got good results with the Hamerly implementation for k-means clustering that you can read about here: http://www.siam.org/proceedings/datamin ... merlyg.pdf. It uses triangle inequality optimizations without requiring a ton of additional memory.

I ran it over 10^7 hand/board combinations with 5000 buckets and (from what I remember) it took about 12-24 hours on a typical desktop CPU until it was swapping only ~0.1% of the observations into different centers per iteration, which was after like 100 iterations I think. I got similar performance with OCHS (8 dimensions) and earth mover's (with 50 histograms/dimensions).

In practice, the number of buckets seems like the biggest factor on time. For comparison, if I pick a tiny number of buckets, like 10, then the Hamerly algorithm can converge in a couple minutes even with the 10^7 observations.

Statistics: Posted by nonpareil — Fri Aug 09, 2013 8:11 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-08-07T11:29:29+00:00

I am thinking about implementing k-means based bucketing.

The tricky part seems to be the search of the nearest centroid. If it is done in a straightforward fashion the time complexity will be O(NK), where N - number of points (card/board combinations), K - number of clusters. The obvious way to speed up nearest-neighbour search is to use k-D trees. It should work fine for everything except the earth-movers distance. The article has about 50 histogram bars, which would give us a 50-dimensional space. And k-D trees don't work that well in high-dimensional spaces, they basicly don't work.

UoA say they used the triangle optimization inequality, but it mostly avoids distance calculations, the number of operations remains O(NK) - that is if I haven't missed anything.

The worst case scenario for turn (earth movers makes no sense on river) is:

~10^7 hand/board combinations to be clustered
~10^5 buckets

giving the time complexity of a SINGLE iteration of about 10^12.

Anybody has an idea how to speed this up?

Statistics: Posted by alex — Wed Aug 07, 2013 11:29 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-07-24T10:09:47+00:00

2Nose:
Yes, I believe your understanding is correct. EMD(A,C)=2 and EMD(A,D)=0.9. The wikipedia article that has the algorithm for 1-D EMD calculation confirms this.

2All:
The article says that the clusterization problem is big, that there are 2,428,287,420 canonical combinations on river. But I believe for distance metrics they mention they can merge some of the canonical combinations. For example, on turn EMD should not care which of the four cards is the one that appeared last. So the following two boards

AcKcQcJc
AcKcJcQc

can IMHO be treated as identical (for those distance metrics).

Statistics: Posted by alex — Wed Jul 24, 2013 10:09 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-07-02T14:21:44+00:00

I am not entirely sure I understand the calculation of earth mover's distance (EMD). Consider the attached histograms A, B, C and D; each consisting of three bins. Omitted values are either 0% or 100%. Let EMD(H1, H2) denote earth mover's distance between two histograms H1 and H2.

EMD(A,B) = 1, because we have to take 100% of "earth" from "pile" bin1 and move it to "pile" bin2.
EMD(B,C) = 1, for the same reasoning
EMD(A,C) = X, where reasonable values for X were
X=1 (same reasoning as above) and
X=2 (move 100% from bin1 to bin2 and carry on to bin3) - as in my understanding so far

EMD(A,D) = 0.9 (0.5 from bin1 to bin 2 and 0.2 from bin1 over bin2 to bin 3). Is that correct?

Statistics: Posted by Nose — Tue Jul 02, 2013 2:21 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-06-12T17:10:45+00:00

I tried KE clustering using Self-Organizing Maps (SOMs) on the flop/turn and got results comparable to my current bucketing methods for HUNL. I'm not sure if a different size histogram or additional/better training with the SOMs would produce better results. I will say that SOMs seemed to be much faster than Kmeans, completing an iteration in about 2.5 hours for the flop histograms.

Statistics: Posted by cantina — Wed Jun 12, 2013 5:10 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-06-03T22:24:51+00:00

proud2bBot wrote:

For KE, you iterate over all hands/boards and store the EHS2 of the next street in an array. E.g. on the flop you iterate over all turns, calculate the EHS2 and store it an an array of size say e.g. 101 entries in the index (Math.round(ehs2*100).

The way I read it: say, on the flop, you roll out all possible boards to the river, then store in a histogram the hand strength of each one of those hands. Maybe this comes out to the same result...

Statistics: Posted by cantina — Mon Jun 03, 2013 10:24 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-06-06T17:49:17+00:00

I'm implementing this now to see how it compares with my current bucketing methods. I'm not using earth movers as the distance metric, though. And, I'm using vanilla KNN to do the clustering.

Questions for others that have done this:
- How big of a histogram did you use? Currently I'm testing histograms with 100 buckets on the flop, and 50 on the turn. Is there an optimal size? I would think the bigger the better, because it offers more detail, but I could be completely wrong.
- Has anyone experimented with other clustering techniques? Such as: Cobweb, Gaussian Mixture Models, SOMs, or Decision Trees?

Edit: I'm testing SOMs now for the turn clustering, KNN is taking a long time (a week running and it's still not finished).

Statistics: Posted by cantina — Mon Jun 03, 2013 10:17 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-04-19T16:39:35+00:00

Coffee4tw wrote:

I only just read this paper and it sounds like Imperfect Recall + Earth Mover's Distance is the current state of the art. Very interesting.

Keep in mind that its for FL, I guess it changes if you play PL/NL...

Statistics: Posted by proud2bBot — Fri Apr 19, 2013 4:39 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-04-18T23:42:28+00:00

Couldn't you integrate such bucketing "choices" into the game itself and solve it along with the EQ? i.e. Dynamic Bucketing. The methods I came up with in the other thread didn't perform that great (yet), but maybe somebody could come up with a better idea of coupling the convergence to the bucketing.

Statistics: Posted by cantina — Thu Apr 18, 2013 11:42 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-04-18T22:57:39+00:00

You can design imperfect recall however you want and they experimented with the in-between cases as well in previous papers. I think the main reason for not exploring it in this paper is that they wanted to compare the two extremes and given that it takes a while to calculate strategies and then run games between the different versions, they probably wanted to stick to a certain time frame. There is significantly more effort required too in designing an abstraction the way you mention it.

There are millions of possibilities that could be tested and each one might or might not be the answer. That is mentioned as well in the paper, currently the only way to know if an abstraction is better than another is to create it, create a strategy and pit it against other ones. That's what people have been doing for years.

Statistics: Posted by Coffee4tw — Thu Apr 18, 2013 10:57 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-04-18T05:51:46+00:00

Why do they call it imperfect recall? It looks like "no recall" to me.
Wish they also tried the in-between case. Like you have N preflop buckets, but when you move to bucketing on flop you assume you have MStatistics: Posted by alex — Thu Apr 18, 2013 5:51 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-04-18T01:47:37+00:00

I only just read this paper and it sounds like Imperfect Recall + Earth Mover's Distance is the current state of the art. Very interesting.

Statistics: Posted by Coffee4tw — Thu Apr 18, 2013 1:47 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-03-15T13:29:43+00:00

If you guys are implementing the approach using LUTs: note that the amount of data that is generated is huge (50M river situations), thus you will get a memory issue if you use larger partitions and floats/doubles. I coped with it by converting the EHS values to bytes (e.g. EHS 0,538752 --> (byte) 54), which introduces a tiny bias but its clustering anyway... Just leave the cluster centers/distances as floats, otherwise it will screw your results.

Statistics: Posted by proud2bBot — Fri Mar 15, 2013 1:29 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-03-15T23:46:36+00:00

Here it is: http://poker-ai.org/archive/www.pokerai.org/pf3/viewtopica90d.html?f=3&t=2777

Note that it's a fully abstracting LUT, which is great in most cases as it's small, but you cannot distinguish for hands {Ks,Qs,Th,4d} if the flop was {Qs,Th,4d}, {Ks,Th,4d}, {Ks,Qs,4d}, or {Ks,Qs,Th}.

Statistics: Posted by proud2bBot — Fri Mar 15, 2013 1:25 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-03-15T00:00:02+00:00

Implementing KMeans is pretty easy and I have some code flying around somewhere for that too but could you post the link to the LUT thread in our Archive that you are using?

Statistics: Posted by Coffee4tw — Fri Mar 15, 2013 12:00 am

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-03-13T21:01:38+00:00

I implemented in it Java, but you dont have one single algorithm but always 2 parts: data generation and data clustering.

For KO, you create the 8 ranges and compute the EHS of your hand vs those ranges.
For KE, you iterate over all hands/boards and store the EHS2 of the next street in an array. E.g. on the flop you iterate over all turns, calculate the EHS2 and store it an an array of size say e.g. 101 entries in the index (Math.round(ehs2*100).

Personally, I was using LUT tables for the data generation (they iterate automatically over all unique hand-board-patterns) and implemented a KMeans algorithm, using the initialization of clusters from KMeans++. I can post the KMeans algorithm (in Java) if there's interest. The LUTs I was using from the old forum (also Java).

Statistics: Posted by proud2bBot — Wed Mar 13, 2013 9:01 pm

Re: Evaluating State-Space Abstractions in Extensive-Form Ga

2013-03-13T20:30:08+00:00

Anybody want to post an algorithm for the KE and KO metrics?

Statistics: Posted by cantina — Wed Mar 13, 2013 8:30 pm

Evaluating State-Space Abstractions in Extensive-Form Games

2013-03-11T22:44:08+00:00

Evaluating State-Space Abstractions in Extensive-Form Games
by: Michael Johanson and Neil Burch and Richard Valenzano and Michael Bowling

Abstract
Efficient algorithms exist for finding optimal policies in extensive-form games. However, human-scale problems are typically so large that this computation remains infeasible with modern computing resources. State-space abstraction techniques allow for the derivation of a smaller and strategically similar abstract domain, in which an optimal strategy can be computed and then used as a suboptimal strategy in the real domain. In this paper, we consider the task of evaluating the quality of an abstraction, independent of a specic abstract strategy. In particular, we use a recent metric for abstraction quality and examine imperfect recall abstractions, in which agents "forget" previously observed information to focus the abstraction effort on more recent and relevant state information. We present experimental results in the domain of Texas hold'em poker that validate the use of distribution-aware abstractions over expectation-based approaches, demonstrate that the new metric better predicts tournament performance, and show that abstractions built using imperfect recall outperform those built using perfect recall in terms of both exploitability and one-on-one play.

http://webdocs.cs.ualberta.ca/~johanson/publications/poker/2013-aamas-kmeans-abstraction/2013-aamas-kmeans-abstraction.pdf

Statistics: Posted by proud2bBot — Mon Mar 11, 2013 10:44 pm