Poker-AI.org

Poker AI and Botting Discussion Forum
It is currently Mon Nov 13, 2023 5:26 pm

All times are UTC




Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Fast PCS-CFM
PostPosted: Thu Mar 06, 2014 11:07 pm 
Offline
Junior Member

Joined: Fri Jul 05, 2013 9:57 pm
Posts: 15
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?


Top
 Profile  
 
 Post subject: Re: Fast PCS-CFM
PostPosted: Thu Mar 06, 2014 11:47 pm 
Offline
Veteran Member

Joined: Thu Feb 28, 2013 2:39 am
Posts: 437
Slower in respect to convergence or tree traversal? PCS speeds up convergence to EQ, but the iterations will be slower.


Top
 Profile  
 
 Post subject: Re: Fast PCS-CFM
PostPosted: Fri Mar 07, 2014 12:07 am 
Offline
Junior Member

Joined: Fri Jul 05, 2013 9:57 pm
Posts: 15
slower in respect to convergence of course


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Powered by phpBB® Forum Software © phpBB Group