Heads-up limit hold’em poker is solved
by: Michael Bowling, Neil Burch, Michael Johanson, Oskari Tammelin

Abstract
Poker is a family of games that exhibit imperfect information, where players do not have full knowledge of past events. Whereas many perfect-information games have been solved (e.g., Connect Four and checkers), no nontrivial imperfect-information game played competitively by humans has previously been solved. Here, we announce that heads-up limit Texas hold’em is now essentially weakly solved. Furthermore, this computation formally proves the common wisdom that the dealer in the game holds a substantial advantage. This result was enabled by a new algorithm, CFR+, which is capable of solving extensive-form games orders of magnitude larger than previously possible.

http://www.sciencemag.org/content/347/6218/145.abstract

Thanks for the response. I tried Pure CFR with several different negative thresholds, but it didn't converge faster in my tests.

I also tried a form of PCS that only uses the current strategy when training. It also performed worse when using a 0 threshold on the river compared to not using one at all. When using a card abstraction (and imperfect recall) there can be several board rundowns that result in the same bucket, so there is still variance on the river I think.

Has anyone seen improvement when trying something like CFR+ but with sampling? I feel like there should be some compromise between Vanilla CFR with no abstraction and one with buckets and sampling cards and actions.

Of course, there could be bugs in my implementations, my tests were not run for very long, maybe it does better with larger card abstractions, etc. I did get CFR+ working in toy games just fine though, based off Oskari's demo code.

Finally, unlike with CFR, we have empirically observed that the exploitability of the players’ current strategies during the computation regularly approaches zero. Therefore, we can skip the step of computing and storing the average strategy, instead using the players’ current strategies as the CFR+ solution.

To address the memory challenge we store the average strategy and accumulated regrets using compression. We use fixed-point arithmetic by first multiplying all values by a scaling factor and truncating them to integers. The resulting integers are then ordered to maximize compression efficiency, with compression ratios around 13-to-1 on the regrets and 28-to-1 on the strategy. Overall, we require less than 11 TB of storage to store the regrets and 6 TB to store the average strategy during the computation, which is distributed across a cluster of computation nodes.

PCS should work better than monte carlo, but there will still be actions that "prove useful" due to variance and not because they're actually useful. Using PCS and only using CFR+ on the river could work though (no variance there).

Maybe it's possible to use some negative treshold instead of 0 to provide some buffer against variance in sampling versions.

i.e.

Here's a brief paper by Oskari on CFR+ with pseudocode: http://arxiv.org/pdf/1407.5042v1

He says that CFR+ is meant for "vector-form" updates, and cites http://poker.cs.ualberta.ca/publication ... 12-pcs.pdf with more info about that. The pseudocode from both papers are very similar...

My current interpretation is that CFR+ works with public chance sampling (go through all hands for each player, but just one board). My concern is if it means you have to do Vanilla CFR iterations and go through all boards as well.

I'm curious to hear of any attempts to implement this. It'll take time to get some old PCS code working again

Where did you find this quote?

- poor convergence rate in monte carlo variations