Poker-AI.org Poker AI and Botting Discussion Forum 2019-07-17T01:52:34+00:00 http://poker-ai.org/phpbb/feed.php?f=25&t=2381 2019-07-17T01:52:34+00:00 2019-07-17T01:52:34+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=8064#p8064 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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


]]>
2019-07-10T07:01:13+00:00 2019-07-10T07:01:13+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=8042#p8042 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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


]]>
2015-10-01T08:31:33+00:00 2015-10-01T08:31:33+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=6825#p6825 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>
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


]]>
2014-08-23T19:06:39+00:00 2014-08-23T19:06:39+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=6251#p6251 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>
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?

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


]]>
2013-11-25T17:35:12+00:00 2013-11-25T17:35:12+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=5323#p5323 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Statistics: Posted by flopnflush — Mon Nov 25, 2013 5:35 pm


]]>
2013-11-25T15:58:35+00:00 2013-11-25T15:58:35+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=5322#p5322 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Statistics: Posted by proud2bBot — Mon Nov 25, 2013 3:58 pm


]]>
2013-11-24T18:53:54+00:00 2013-11-24T18:53:54+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=5321#p5321 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Did this (for testing purposes) with k=200 and only 10 kMeans iterations.

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


]]>
2013-11-24T18:00:12+00:00 2013-11-24T18:00:12+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=5320#p5320 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Statistics: Posted by cantina — Sun Nov 24, 2013 6:00 pm


]]>
2013-11-24T17:25:29+00:00 2013-11-24T17:25:29+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=5319#p5319 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>

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

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


]]>
2013-11-06T09:20:44+00:00 2013-11-06T09:20:44+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=5180#p5180 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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


]]>
2013-08-14T14:24:11+00:00 2013-08-14T14:24:11+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4650#p4650 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> link).

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


]]>
2013-08-13T11:32:47+00:00 2013-08-13T11:32:47+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4641#p4641 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>
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


]]>
2013-08-09T20:11:42+00:00 2013-08-09T20:11:42+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4631#p4631 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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


]]>
2013-08-07T11:29:29+00:00 2013-08-07T11:29:29+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4623#p4623 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>
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


]]>
2013-07-24T10:09:47+00:00 2013-07-24T10:09:47+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4517#p4517 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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


]]>
2013-07-02T14:21:44+00:00 2013-07-02T14:21:44+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4378#p4378 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>
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


]]>
2013-06-12T17:10:45+00:00 2013-06-12T17:10:45+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4318#p4318 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Statistics: Posted by cantina — Wed Jun 12, 2013 5:10 pm


]]>
2013-06-03T22:24:51+00:00 2013-06-03T22:24:51+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4301#p4301 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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


]]>
2013-06-06T17:49:17+00:00 2013-06-03T22:17:58+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=4300#p4300 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>
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


]]>
2013-04-19T16:39:35+00:00 2013-04-19T16:39:35+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3892#p3892 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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


]]>
2013-04-18T23:42:28+00:00 2013-04-18T23:42:28+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3886#p3886 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Statistics: Posted by cantina — Thu Apr 18, 2013 11:42 pm


]]>
2013-04-18T22:57:39+00:00 2013-04-18T22:57:39+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3883#p3883 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>
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


]]>
2013-04-18T05:51:46+00:00 2013-04-18T05:51:46+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3868#p3868 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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 M<N buckets on preflop.

Statistics: Posted by alex — Thu Apr 18, 2013 5:51 am


]]>
2013-04-18T01:47:37+00:00 2013-04-18T01:47:37+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3866#p3866 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Statistics: Posted by Coffee4tw — Thu Apr 18, 2013 1:47 am


]]>
2013-03-15T13:29:43+00:00 2013-03-15T13:29:43+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3238#p3238 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Statistics: Posted by proud2bBot — Fri Mar 15, 2013 1:29 pm


]]>
2013-03-15T23:46:36+00:00 2013-03-15T13:25:31+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3236#p3236 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> 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


]]>
2013-03-15T00:00:02+00:00 2013-03-15T00:00:02+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3210#p3210 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Archive that you are using?

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


]]>
2013-03-13T21:01:38+00:00 2013-03-13T21:01:38+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3184#p3184 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]>
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


]]>
2013-03-13T20:30:08+00:00 2013-03-13T20:30:08+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3179#p3179 <![CDATA[Re: Evaluating State-Space Abstractions in Extensive-Form Ga]]> Statistics: Posted by cantina — Wed Mar 13, 2013 8:30 pm


]]>
2013-03-11T22:44:08+00:00 2013-03-11T22:44:08+00:00 http://poker-ai.org/phpbb/viewtopic.php?t=2381&p=3122#p3122 <![CDATA[Evaluating State-Space Abstractions in Extensive-Form Games]]> 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


]]>