Image Image Image




Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Efficient Nash Equilibrium Approximation through Monte Carlo Cou
PostPosted: Wed Feb 22, 2012 10:01 pm 
Offline
Junior member
User avatar

Posts: 38
Favourite Bot: Mine :D
Efficient Nash Equilibrium Approximation through Monte Carlo Counterfactual Regret Minimization
Michael Johanson, Nolan Bard, Marc Lanctot, Richard Gibson, and Michael Bowling


Abstract: Recently, there has been considerable progress towards algorithms for approximating Nash equilibrium strategies in extensive games. One such algorithm, Counterfactual Regret Minimization (CFR), has proven to be effective in two-player zero-sum poker domains. While the basic algorithm is iterative and performs a full game traversal on each iteration, sampling based approaches are possible. For instance, chance-sampled CFR considers just a single chance outcome per traversal, resulting in faster but less precise iterations. While more iterations are required, chance-sampled CFR requires less time overall to converge. In this work, we present new sampling techniques that consider sets of chance outcomes during each traversal to produce slower, more accurate iterations. By sampling only the public chance outcomes seen by all players, we take advantage of the imperfect information structure of the game to (i) avoid recomputation of strategy probabilities, and (ii) achieve an algorithmic speed improvement, performing O(n2) work at terminal nodes in O(n) time. We demonstrate that this new CFR update converges more quickly than chance-sampled CFR in the large domains of poker and Bluff.

Download : http://poker.cs.ualberta.ca/publications/AAMAS12-pcs.pdf


Top
 Profile E-mail  
 
 Post subject: Re: Efficient Nash Equilibrium Approximation through Monte Carlo Cou
PostPosted: Fri Mar 16, 2012 9:40 pm 
Offline
Junior member
User avatar

Posts: 12
Favourite Bot: MyBot
Hmm, I couldn't get how they use PCS with (EHS^2) bucketing.
Do they work with 2 vectors(pi_i and pi_-i) of 1326 floats (one for each player preflop card pair) on each iteration? Or they use some bucket translation magic? I don't know how to translate from preflop buckets to flop buckets (I mean reach/pi_i vector) otherwise.


Top
 Profile E-mail  
 
 Post subject: Re: Efficient Nash Equilibrium Approximation through Monte Carlo Cou
PostPosted: Sat Mar 17, 2012 4:12 pm 
Offline
PokerAI fellow
User avatar

Posts: 1115
Favourite Bot: Johnny #5
My understanding: yes, to your first question.


Top
 Profile  
 
 Post subject: Re: Efficient Nash Equilibrium Approximation through Monte Carlo Cou
PostPosted: Sat Mar 17, 2012 11:23 pm 
Offline
Junior member
User avatar

Posts: 25
Favourite Bot: Polaris Orange
Yes, just vectors of 1326 doubles. It doesn't matter what the underlying abstraction is.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: