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

Fast PCS-CFM
http://poker-ai.org/phpbb/viewtopic.php?f=24&t=2715
Page 1 of 1

Author:  Hipp [ Thu Mar 06, 2014 11:07 pm ]
Post subject:  Fast PCS-CFM

In publications from alberta university i found that they are using O(n) computation for a utility in terminal nodes of the tree(Public Chance sampling CFM algorithm). To do that for the particular node, we need to sum opponents reachs(1081 hands), and then for every hand, we substract 91 hands that collide with this hand.
But if we do so, we can't do any "pruning". I made it differently. My solution is O(n^2), but it can skip inner loop in most of situations.
For example, for a termial node that is showdown, it looks something like this:
Code:
for (int i=0; i<1081; i++) {
   if (reach[opponent][i] < 0.00000001) continue; // <--- this avoid lot of computation   
   for(int j=0; j<1081; j++) {
      if (CommonCards(hands[i], hands[j])) continue; //CommonCards checks if two pocket cards sets have a common card            
      if (evaluation[i] == evaluation[j]) continue; //evaluation is an array that contains results from 7 card hand evaluator
      if (evaluation[i] < evaluation[j]) ev[j] += reach[opponent][i];
      else ev[j] -= reach[opponent][i];
   }   
}
for (int i=0; i<1081; i++)
   ev[i] *= amount; //amount represents how much we put in the pot


My experiment shows that it runs faster then O(n) solution.
But even now, my PCS algorithm is slower then Chance-Sampling version (2 or 3 times slower).
I don't know why. Maybe we can avoid some computations in O(n) version, but I didn't figure it out?

Author:  cantina [ Thu Mar 06, 2014 11:47 pm ]
Post subject:  Re: Fast PCS-CFM

Slower in respect to convergence or tree traversal? PCS speeds up convergence to EQ, but the iterations will be slower.

Author:  Hipp [ Fri Mar 07, 2014 12:07 am ]
Post subject:  Re: Fast PCS-CFM

slower in respect to convergence of course

Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/