Poker-AI.org

PROPERTIES

type = "article"
title = "Efficient Monte Carlo Counterfactual Regret Minimization in Games with Many Player Actions"
author = "GIBSON, Richard and BURCH, Neil and LANCTOT, Marc and SZAFRON, Duane"
year = "2012"
organization = "University of Alberta - Department of Computing Science"
url = "http://poker.cs.ualberta.ca/publications/NIPS12.pdf"
language = "en"
size = "9"


SUBJECT

abstract = "Counterfactual Regret Minimization (CFR) is a popular, iterative algorithm for computing strategies in extensive-form games. The Monte Carlo CFR (MCCFR) variants reduce the per iteration time cost of CFR by traversing a smaller, sampled portion of the tree. The previous most effective instances of MCCFR can still be very slow in games with many player actions since they sample every action for a given player. In this paper, we present a new MCCFR algorithm, Average Strategy Sampling (AS), that samples a subset of the player’s actions according to the player’s average strategy. Our new algorithm is inspired by a new, tighter bound on the number of iterations required by CFR to converge to a given solution quality. In addition, we prove a similar, tighter bound for AS and other popular MCCFR variants. Finally, we validate our work by demonstrating that AS converges faster than previous MCCFR algorithms in both no-limit poker and Bluff."

Question about the given implementation (p5).

Line 9: Shouldn't q be multiplied with the frequency of performing action a given infoset I?

(ie.


instead of


)

referring to cumulative profile-formula (attached as picture)

btw @ admins: a (La)TeX-Plugin ([TEX]-BB-Code respectively) would be nice to create this kind of formula

also when looking at line 5 of the algorithm - does anyone know the rationale of dividing the utility by the probability of reaching terminal node z instead of multiplying with it?

say, why


EDIT: Attached algorithm for your convenience

You can multiply your regret and cumulative updates by Q, or divide just the regret update and the leaf node utility.

Thanks

I have another question: Assume the following scenario:

Let Player i be the SB. Right after the hole cards where dealt ASSampling decides the sample two cases: SB checks and SB min-bets. Assume in both cases ASSampling decides to let BB check behind/ call. In each case a chance node (dealing flop cards) follows.

According to the specification different community cards are dealt in each scenario whereas the outcome of all branches are summed up in order to obtain the regret for each action.

Does anyone know about the impact to the convergence rate if you ensure that each chance node returns the same community cards each iteration?

ASSampling will then be a little closer to CS than to pure, random MC

"for games with mores than 2 players, a second tree walk is required and we omit these details",

it is not clear what that means ?

Unless I'm misunderstanding your question, all action nodes are supposed to use the same community cards (relative to the round) when doing an iteration of CFRM.

Can you show more of the quote? It may mean they need to train players separately.

and

Quote:

For future work, we would like to apply AS to games with
many player actions and with more than two players

weird