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?
Login
Register
FAQ
Search
