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/ |