2009 · 197 citations · 7 references
ComputingDecision SciencesAlgorithmsDecision TheoryGame TheoryMonte Carlo MethodsMonte Carlo SimulationNash EquilibriumRandomized AlgorithmsReinforcement LearningStochastic GamesApproximate Nash EquilibriumCounterfactual RegretImperfect Information GamesLearning With Imperfect InformationMonte Carlo SamplingNash Equilibrium ComputationNoncooperative GamesSampling
One efficient method for computing Nash equilibria in large, zero-sum extensive games is counterfactual regret minimization (CFR). In the domain of poker, CFR has proven effective, particularly when using a domain-specific augmentation involving chance outcome sampling. In this paper we introduce MCCFR, a Monte Carlo version of the algorithm capable of applying equivalent updates (in expectation) on sampled histories which has bounded overall regret with high probability. We show empirically that, although MCCFR requires more iterations, its lower cost per iteration results in overall faster convergence, particularly as the game size increases. 1
7
A Simple Adaptive Procedure Leading to Correlated Equilibrium
Sergiu Hart, Andreu Mas‐Colell · Econometrica · 2000 · 1.1K citations · Full text
An analog of the minimax theorem for vector payoffs
David Blackwell · Pacific Journal of Mathematics · 1956 · 758 citations · Full text
Regret Minimization in Games with Incomplete Information
Michael Bowling, Michael Johanson, Martin Zinkevich et al. · 2007 · 510 citations · Full text
Goofspiel — the game of pure strategy
Sheldon M. Ross · Journal of Applied Probability · 1971 · 43 citations