Poker-AI.org

Hi guys, I am currently working on an FL HU AI using CFRM.

I have a few problems understanding the algorithm on the Zinkevich paper, the data structure for the tree is already a problem.

In line 1 he says:
"if r1 is a player node (meaning r2 is an opponent node)"

Since they are using 2 trees, does this mean, that both nodes represent the same player acting, only in tree 1 he is the player, while in tree 2 he is the opponent? But then I dont understand, why sigma(r2) never gets updated, because I thought, we need the overall action probabilities for computing player 2's regrets.

They're using two trees? Are you sure it's not the same tree, they're just updating player 1 and player 2 separately?

I think they use 2 trees, but maybe I dont understand it correctly:

http://poker.cs.ualberta.ca/publications/NIPS07-cfr.pdf

"We need to iterate over all of the information sets reachable given the joint bucket sequence, and compute probabilities
and regrets. In order to do this swiftly, we represent the data in each information set in a “player view
tree”: in other words, we never explicitly represent every state in the abstracted game: instead, we represent the
information sets for each player in its own tree, with each node n being one of four types:"

"Our algorithm recurses over both trees in a paired fashion"

Also the parameters for the main method:

Algorithm 1 WALKTREES(r1, r2, b, p1, p2)
Require: A node r1 for an information set tree for player 1.
Require: A node r2 for an information set tree for player 2.

Seems like they have 2 trees and traverse both simultaneously.

I have difficulties representing the tree with its information sets. My algorithm works, if I only use a single player node and assign 3 actions with succeding terminal nodes with different values. The strategy converges to a pure strategy of playing the action with the highest payoff.
But I cannot represent following situation: Player 1 has a range of Value and Bluffs and Player 2 has a bluffcatcher. Now Player1 bets parts of his range, but in my tree Player2 optimizes against the bluffs and valuebetes separatelly, I dont know how to represent an information set correctly.

Yes, they use 2 trees, but only for a conceptual view. In practice you'll only use a single tree with nodes from both players. If you want to implement it, check out the later CFRM papers; they often have easy to understand algorithms.

Thanks guys, after I realized it was actually only one tree, I started to make progress. I was using this:
http://www.poker-ai.org/archive/www.pokerai.org/pf3/viewtopicaaeb.html?f=64&t=4810 thesis.

My algorithm is now able to solve the Nuts/Bluff - Bluffcatcher game from MOP. I think it is working, now I only need the bucketing and tree creation.

I have 2 versions of the algorithm, one iterative and one recursive. The iterative needs 600ms for 10^6 iterations for solving a small game, while the iterative one needs 6 seconds. Can this be normal? Is iteration actually slower in java, or is my implementation likelly just sucking?

But, what about the iterative one?

^^
I mean the recursive one needs 600ms