Poker-AI.org
http://poker-ai.org/phpbb/

Card Isomorphisms
http://poker-ai.org/phpbb/viewtopic.php?f=24&t=2558		 Page 1 of 1
Author:  HontoNiBaka [ Wed Aug 21, 2013 2:00 am ]
Post subject:  Card Isomorphisms
I have programmed a tool, that can solve unabstracted FL Rivergame. I am using vanilla CFRM.
I want to speed it up by using card isomorphisms, but I dont get the theory behind it so far.

My first idea was to just group the hands by the handrank computed by the 2p2 handevaluator, but I guess
this wont work, because I would lose information about cardremoval?

Is there a site, that explains card isomorphisms in a simple and practical way? And is there a way
to make it even faster using the fact, that I am only analysing rivergame, so no new cards can
change the ranks?

What I basically want to acheive, is to group hands and treat them as one hand, but still have the card removal effect.

For instance if I run AK vs QJ, I do 16*16 terminal node computations, while I could just do one, because each AK and QJ is the same.
But it gets more complicated, when I run AK vs QK and QJ, now I need to bear in mind, that AK blocks KQ and vice versa.
Author:  pulser [ Wed Aug 21, 2013 4:07 pm ]
Post subject:  Re: Card Isomorphisms
Since you're only analyzing rivers, you can group hands with ranks that beats and are beaten by the same ranks together.

Then, for each hand within such a group, count the number of hands removed by card-removal for each of the opponent's groups.

Then, group all hands with (proportionally) identical card-removal effects within a local group together.

You'd then have the smallest lossless abstraction possible. Hope that wasn't too confusing.
Author:  HontoNiBaka [ Thu Aug 22, 2013 5:38 am ]
Post subject:  Re: Card Isomorphisms
pulser wrote:
Hope that wasn't too confusing.


I think, I understand it, thank you. I will try to implement it.

How do I learn more about isomorphisms though? I had isomorphism in CS, but it wasn't helpful for cardgames.

Is there even a general way to find isomorphm cards, or do I just have to think about what cards are strategically equal each time?

Is there something, like a way to abstract it and then just run an algorithm, that I can use in every situation?
Author:  HontoNiBaka [ Fri Aug 23, 2013 11:13 am ]
Post subject:  Re: Card Isomorphisms
I have implemented the grouping of cards.

I have a problem with combining the isomorphisms with the O(n) fast ShowdownNode evaluator.
It all seems to work with the O(n²) evaluator, and it works with the O(n) evaluator, when the cards dont block each other,
but in the case, that there is cardremoval, I have a problem in that line:

Code:
double[] wincr = new double[52];
    for (int i = 0; i < p.length; i++)
   {
      while(j < op.length && oHoles.get(j).getRank() < pHoles.get(i).getRank()){
         winsum += op[j];
         wincr[oHoles.get(j).getCard1()-1] += op[j];
         wincr[oHoles.get(j).getCard2()-1] += op[j];
         j++;
      }
//etc


The wincr basically keeps track of how often a certain card gets blocked. I dont see, how I can do that, without itterating over all cards in the bucket, which would bring me back to O(n2).
Author:  HontoNiBaka [ Fri Aug 30, 2013 5:54 pm ]
Post subject:  Re: Card Isomorphisms
I managed to implement it. I got a big constant factor from keeping track of the blocked cards, but it is still in O(n) and it is still way faster, than without the isomorphisms.

The next question is, how to extend it to the turn. The main idea of course is, to find hands, that are strategically equal, but I dont see an algorithm so far.

I am also still looking for a general purpose algorithm for finding isomorphisms. Of course I am also willing to share infos on my implementation, if anyone can help me to get the general idea.
Author:  ConvexPolytope [ Mon Dec 09, 2013 1:48 am ]
Post subject:  Re: Card Isomorphisms
Check out this paper called "A Fast and Optimal Hand Isomorphism Algorithm" in the Poker Papers Forum. The cool thing is that the author not only explains the algorithm in great detail, but he also provides a C implementation at https://github.com/kdub0/hand-isomorphism
Author:  HontoNiBaka [ Mon Dec 09, 2013 7:41 am ]
Post subject:  Re: Card Isomorphisms
Thanks a lot.
Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/