Poker-AI.org

Re: My CFR implementation is too slow.

2019-08-14T10:52:37+00:00

You need to be curious,to do it

Statistics: Posted by KidorioL — Wed Aug 14, 2019 10:52 am

Re: My CFR implementation is too slow.

2019-07-30T17:36:40+00:00

I have a new idea for speeding things up. If P1’s range is AA,KK and P2’s range is QQ,JJ, then the reach probabilities for each player would consist of two floats, but I think it would be better to merge the ranges and pretend both players have the same range. This would result in reach probabilities consisting of four floats with some of the reach probabilities initialized to zero for both players. This makes the showdown utility calculations faster because you don’t have to compare the current player’s hand ranks to the opponent’s hand ranks. You just have to iterate over the hands that have the same rank in the current player’s range. This saves like 1326 condition checks for 100% ranges.

I think this only speeds things up if the ranges have a decent amount of overlap though.

By the way, another way to speed things up is to update the opponent’s strategy sum rather than the current player’s strategy sum on each iteration. This way you don’t have to keep track of or calculate the current player’s reach probabilities at all (just the opponent’s). The convergence rate is the same.

Statistics: Posted by Fossana — Tue Jul 30, 2019 5:36 pm

Re: My CFR implementation is too slow.

2019-07-19T14:17:43+00:00

spears wrote:

Is bounds checking on or off?

I think my compiler is turning bounds checking off since I was getting some illegal read operations earlier.

Statistics: Posted by Fossana — Fri Jul 19, 2019 2:17 pm

Re: My CFR implementation is too slow.

2019-07-19T14:09:36+00:00

Is bounds checking on or off?

Statistics: Posted by spears — Fri Jul 19, 2019 2:09 pm

Re: My CFR implementation is too slow.

2019-07-19T13:39:07+00:00

This is rather preliminary, but I converted all of my Java code to C++ and did a lot of optimizations (mainly loop unrolling and taking advantage of the fact that reach probabilities/strategy sums/regret sums can be smaller on the river due to the river card blocking a bunch of hands), and my solver is currently 10% faster than piosolver, at least for turn subgames.

Statistics: Posted by Fossana — Fri Jul 19, 2019 1:39 pm

Re: My CFR implementation is too slow.

2019-07-06T10:02:55+00:00

Just implemented DCFR (discounted CFR) which converges faster than CFR+. Only 2x slower than piosolver now.

Statistics: Posted by Fossana — Sat Jul 06, 2019 10:02 am

Re: My CFR implementation is too slow.

2019-07-06T07:26:34+00:00

Great work. Thank you for the contribution.

Statistics: Posted by spears — Sat Jul 06, 2019 7:26 am

Re: My CFR implementation is too slow.

2019-07-06T06:07:54+00:00

Implemented CFR+ and it seems to be a lot faster than PCS. I compared the speed of my CFR+ implementation to piosolver on the following turn subgame:

OOP range: 100% of hands
IP range: 100% of hands
board: KdJdTd5s
pot size: 100
effective stack size: 1000
turn bet sizes: 0.5pot, 1pot
turn raise sizes: 0.5pot
river bet sizes: 0.25pot, 0.5pot, 1pot
river raise sizes: 0.5pot
donking is allowed
allin threshold = 0.67

It took piosolver 13.5s to solve this subgame down to an exploitability of 0.413% of the pot per hand. It took my CFR+ implementation 54.8s (300 iterations) to solve the same subgame down to an exploitability of 0.404% of the pot per hand. I suspect if I exploit isomorphisms I can halve this time, especially since the board I used has three cards of the same suit.

Another thing I did to speed things up was convert all 2d arrays to 1d arrays. In languages like C++ and C#, 2d arrays are actually stored as 1d arrays internally, but in Java, 2d arrays are an array of arrays. This has a lot of overhead and made my program 33% slower before.

Not sure why PCS is so slow, maybe because it there's a lot of overhead involved in traversing the tree and variance. I found that PCS+ converges a lot faster. For PCS+, every time the number of iterations was divisible by the number of possible runouts, I reset negative cumulative regret to 0, and I also updated cumulative strategy like so: cumulativeStrategy += (1 + iterationCount/numRunouts) * strategy * reachProbability. For a turn subgame, the number of possible runouts is 48, and for flop subgames it would be 49*48=2352.

Here's how to deal with board card chance nodes in CFR+:
1. Set the reach probability for hands that conflict with the turn/river card to 0.
2. If you're dealing the river, divide the utilities that propagate back up by 44, and if you're dealing the turn, divide the utilities by 45. The reason you do this is because let's say you have a hand AcAh and your opponent has 460 combos that don't conflict with this hand. For each of the 46 possible rivers (52 - 4 cards on board - 2 cards contained in AcAh), on average, 20 of your opponents combos will be blocked by that river card, so you get a utility for AcAh that was computed against 440 combos on average rather than 460.
3. Divide hero's reach probabilities by 46 if dealing the river and by 45 if dealing the turn. If hero holds AcAh and there's 4 cards on the board, then there are 46 different rivers that hero can see with this hand, so the reach probability for each of these rivers is 1/46 for AcAh. This is actually not completely accurate because if your opponent's strategy is one in which they mostly have KK in a spot, then it's less likely your AcAh will see a K river. Though I find in practice just using 1/46 is fine instead of manually calculating the actual reach probability for each river.

Here's how to deal with board card chance nodes in PCS:
1. sample board cards ahead of time
2. set the reach probability for hands that conflict with the board (including the sampled cards) to 0 before starting the iteration
3. at terminal nodes, make sure that the utility for hands that conflict with the board is 0, otherwise nonzero utility will be propagated up and you'll have nonzero regret for hands that you can't even have on the board (do the same with CFR+)

Statistics: Posted by Fossana — Sat Jul 06, 2019 6:07 am

Re: My CFR implementation is too slow.

2019-07-05T01:23:02+00:00

I think my PCS implementation is actually correct. It does converge to 0 after a million iterations. Just kind of disturbing how it can go from 22% exploitability to less than 1% exploitability in 10k iterations and then it takes another 50k iterations to drop below 0.1% exploitability and then another 750k iterations to drop below 0.01% exploitability. Perhaps that's the nature of CFR, but I don't understand how commercial solvers work so quickly.

Statistics: Posted by Fossana — Fri Jul 05, 2019 1:23 am

Re: My CFR implementation is too slow.

2019-07-04T21:28:49+00:00

I figured out why dividing the reach probabilities for each of villlain's hand by 44 when dealing the river makes sense now. Think about this way: how many rivers are possible for one of villain's hands? There are 4 cards on the board and 2 cards in hero's hand, so that leaves 46 rivers. Villain's hand will block 2 of of those rivers, leaving only 44. If you divide by 46, then you will mistakenly get 44/46 + 0 + 0 = 44/46, when the probability needs to add up to 1.

Statistics: Posted by Fossana — Thu Jul 04, 2019 9:28 pm

Re: My CFR implementation is too slow.

2019-07-04T18:15:23+00:00

spears wrote:

Fossana wrote:

When calculating best response, do you need to weight the probability of cards being dealt by the opponent’s strategy? Like if you get to a node where the opponent gets to that node with the majority of their Ax combos, then having an equal chance of dealing an A as other cards doesn’t make much sense.

Consider the simple but slow method where you pass a single best response player's hand and the equilibrium player's hand distribution down the tree and you pass a single ev back up the tree. In that case you can modify the equilibrium player's hand distribution at the root to reflect the collisions between the br player's

Consider the faster method where you just pass the equilibrium player's hand distribution down the tree and pass a vector of evs back, each ev representing alternative br players hand holding. In that case I guess you have to account for the collisions at the terminal nodes instead. (Have you not figured this out already in your PCS solution?) I'm not sure if I ever figured that out properly, because I disappeared down a rabbit hole of complexity looking at hand abstraction.

It might be worth looking at Amax's code. http://www.poker-ai.org/archive/www.pok ... &sk=t&sd=a I see there are other sources available now too.

My code is heavily based on Amax's code. I have implemented the best response calculations both the fast and slow way, but I need to divide the EVs I get from chance nodes by 44 rather than some other number to get the right answer.

Statistics: Posted by Fossana — Thu Jul 04, 2019 6:15 pm

Re: My CFR implementation is too slow.

2019-07-04T17:35:42+00:00

Fossana wrote:

Consider the simple but slow method where you pass a single best response player's hand and the equilibrium player's reach vector down the tree and you pass a single ev back up the tree. In that case you can modify the equilibrium player's reach vector at the root to reflect the collisions between the br player's hand and eq players hand.

Consider the faster method where you just pass the equilibrium player's reach vector down the tree and pass a vector of evs back, each ev representing alternative br players hand holding. In that case I guess you have to account for the collisions at the terminal nodes instead. (Have you not figured this out already in your PCS solution?) I'm not sure if I ever figured that out properly, because I disappeared down a rabbit hole of complexity looking at hand abstraction.

It might be worth looking at Amax's code. http://www.poker-ai.org/archive/www.pok ... &sk=t&sd=a I see there are other sources available online now too.

Statistics: Posted by spears — Thu Jul 04, 2019 5:35 pm

Re: My CFR implementation is too slow.

2019-07-04T16:23:12+00:00

spears wrote:

Fossana wrote:

I figured out one of the issues. In my best response calculations, when I dealt a river card, I was dividing the EV of each hand by 48 (52 - 4 cards on board), but you need to divide it by 44 for some reason (52 - 4 cards on board - 4 cards in player's hands). Sort of makes sense but at the same time it doesn't.

Does that solve the (lack of) convergence problem?

It converges to a lower level of exploitability now but it still gets stuck pretty quickly. I’ve compared my best response calculations with piosolver and I seem to be getting the same EVs, but dividing by 44 instead of 48 when dealing the river can’t possibly be right. Dividing by 44 must be making up for some other mistake in my best response code.

I may implement vanilla cfr just to test my best response when the opponent’s strategy isn’t uniform mixed like it is before any cfr iterations.

When calculating best response, do you need to weight the probability of cards being dealt by the opponent’s strategy? Like if you get to a node where the opponent gets to that node with the majority of their Ax combos, then having an equal chance of dealing an A as other cards doesn’t make much sense.

Statistics: Posted by Fossana — Thu Jul 04, 2019 4:23 pm

Re: My CFR implementation is too slow.

2019-07-04T09:58:54+00:00

Fossana wrote:

Does that solve the (lack of) convergence problem?

Statistics: Posted by spears — Thu Jul 04, 2019 9:58 am

Re: My CFR implementation is too slow.

2019-07-03T20:04:26+00:00

Statistics: Posted by Fossana — Wed Jul 03, 2019 8:04 pm

Re: My CFR implementation is too slow.

2019-07-02T22:52:47+00:00

If anyone is curious, I'm getting faster convergence if I reset negative cumulative regret to 0 after every iteration and if I multiply the cumulative strategy by (n/(n+1))^2 after updating it whenever iterationCount % possible board runouts == 0, where n = iterationCount % possible board runouts. Basically applying CFR+ techniques to PCS.

Statistics: Posted by Fossana — Tue Jul 02, 2019 10:52 pm

Re: My CFR implementation is too slow.

2019-07-02T22:46:54+00:00

spears wrote:

Quote:

I also checked that river cards were being dealt uniformly, so that's not the issue.

Are you sampling rivers? Can you create a small version of the game that doesn't sample rivers to eliminate errors arising from sampling?

By turn subgame I mean four cards are already on the board and then I sample rivers. If I don't sample river with four cards on the board then I'm just doing vanilla CFR instead of PCS.

Statistics: Posted by Fossana — Tue Jul 02, 2019 10:46 pm

Re: My CFR implementation is too slow.

2019-07-02T22:03:08+00:00

Quote:

I also checked that river cards were being dealt uniformly, so that's not the issue.

Are you sampling rivers? Can you create a small version of the game that doesn't sample rivers to eliminate errors arising from sampling?

Statistics: Posted by spears — Tue Jul 02, 2019 10:03 pm

Re: My CFR implementation is too slow.

2019-07-02T21:11:06+00:00

I have a new interesting problem. My solver is converging to 0% exploitability for river subgames, but for turn subgames it will hit a low exploitability (1-3%) after only 20-30k iterations, but then the exploitability will barely improve after another million iterations. I thought maybe it had something to do with the size of the game tree, but on river game trees with tons of bet sizes and ranges consisting of 60x as many hands, my solver still converges fine. I can't even converge on a turn subgame with 18 combos for each player, 1 bet size, and a stack to pot ratio of 1.

For turn subgames, I sample the river ahead of time and set the reach probabilities for the appropriate hole card combinations to 0, but maybe I need to be renormalizing in some way.

Statistics: Posted by Fossana — Tue Jul 02, 2019 9:11 pm

Re: My CFR implementation is too slow.

2019-07-02T21:01:27+00:00

spears wrote:

Is the lifetime of one array entirely within a method and the other not?

In either case, the lifetime of the array is contained within a single method call. The arrays aren't passed down recursively or anything. The only difference I can think of was that the strategy array was being created by a method in another class and returned to the method that needed it whereas the subgame counterfactual utilities array was being created within the method itself.

Statistics: Posted by Fossana — Tue Jul 02, 2019 9:01 pm

Re: My CFR implementation is too slow.

2019-07-02T20:05:55+00:00

Is the lifetime of one array entirely within a method and the other not?

Statistics: Posted by spears — Tue Jul 02, 2019 8:05 pm

Re: My CFR implementation is too slow.

2019-07-02T19:09:32+00:00

It's kind of weird, but creating a new array every time I get the strategy at a node slows things down by a factor of 3 relative to having that array be preallocated. However, I seem to get no speedup from preconstructing arrays for subgame counterfactual utilities, even though these arrays are the same size as the strategy ones.

Statistics: Posted by Fossana — Tue Jul 02, 2019 7:09 pm

Re: My CFR implementation is too slow.

2019-07-01T22:43:06+00:00

My implementation is multithreaded now and 3x faster. It takes less only a few seconds to solve a river subgame but it takes several minutes to do a turn subgame, which is bad since piosolver only takes a few seconds to solve turn subgames.

I wishI could tell if my implementation of PCS is any good or not. I'm not aware of any benchmarks. I'm getting 750 iterations per second (1 iteration = full walk of game tree for each player) for a tree consisting of 1352 information sets.

For some reason my program gets stuck after a while on larger trees (i.e. exploitability won't go any lower and it hovers around the same value).

I experimented with pruning where if the opponent's reach probability with a hand is ~0, then I skip the float operations for that hand at terminal nodes. As far as I can tell this makes the algorithm 3-5% faster, but I haven't tested it fully.

I'm going to work on isomorphic hands and turns next and see how much that speeds things up.

Statistics: Posted by Fossana — Mon Jul 01, 2019 10:43 pm

Re: My CFR implementation is too slow.

2019-07-01T15:33:13+00:00

Thanks. Interesting

Statistics: Posted by spears — Mon Jul 01, 2019 3:33 pm

Re: My CFR implementation is too slow.

2019-07-01T15:06:17+00:00

spears wrote:

You been on this less than week and know as much as I figured out in several years so I'm not sure I can help much. I think Noam Brown managed to prune the trees so that might help. What do you know that is faster than CFR+?

There is a variant called Lazy CFR that allegedly converges 500 times faster than CFR+ (their Lazy CFR+ variant specifically). Pretty bold claim, but they do lazy updates, meaning they update the strategy at an information set every few iterations rather than every iteration. So on each iteration they only update O(log n) information sets. I’m having trouble understanding their pseudocode but I got most of it figured out.

There is also a variant called instant CFR, but I haven’t looked to deeply into it.

Statistics: Posted by Fossana — Mon Jul 01, 2019 3:06 pm

Re: My CFR implementation is too slow.

2019-07-01T14:41:53+00:00

You might get some ideas from viewtopic.php?p=7843#p7843

Statistics: Posted by spears — Mon Jul 01, 2019 2:41 pm

Re: My CFR implementation is too slow.

2019-07-01T13:52:56+00:00

Statistics: Posted by spears — Mon Jul 01, 2019 1:52 pm

Re: My CFR implementation is too slow.

2019-07-01T10:42:13+00:00

Finally got best response implemented and was able to test my PCS implementation. Everything is working since exploitability is converging to zero, but as I mentioned before my program is too slow. It takes several minutes to solve a turn subgame. It can do a river subgame pretty quickly though.

These are the functions taking up the most time in my code:

* Terminal node evaluation. I'm doing this in O(n) rather than O(n^2). Currently I'm doing 12 float operations * the number of hands in the largest range. I'm trying to think of a more clever way to account for card removal.

* Decision node evaluation. I have to create new arrays at these nodes for reach probabilities and counterfactual utilities.

* Updating cumulative strategy, getting current strategy, and updating cumulative regret.

These are things that I'm already doing:

* I have a LUT for evaluating hands on the river.

* When I sort player's ranges on the river, I add the sorted ranges to a map so I can retrieve them later for the same board.

I tried the following but they didn't improve speed:

* Creating arrays ahead of time (object pooling). Thought this would help since I create new arrays all the time for reach probabilities and counterfactual utilities.

I haven't parallelized my algorithm yet and I'm not accounting for hand isomorphisms (AhKh, AsKs, and AdKd are strategically the same on 9c7c5c), but even if my program became 4-8x faster it would still be way too slow, so I feel like I'm doing something fundamentally wrong.

Piosolver used to use cfr, so while the algorithm they're using now is faster, the fact that they used it before means it's viable. There's also a lot of new CFR variants, a couple of which may be faster than CFR+ and PCS.

Statistics: Posted by Fossana — Mon Jul 01, 2019 10:42 am

Re: My CFR implementation is too slow.

2019-06-30T07:25:39+00:00

Lots of people, me included, would love to know how piosolver works so fast. I read somewhere that it doesn't use cfr but some form of gradient descent.

Statistics: Posted by spears — Sun Jun 30, 2019 7:25 am

Re: My CFR implementation is too slow.

2019-06-29T23:42:43+00:00

I've implemented PCS-CFR and I'm getting 787 iterations per second (1.27 ms per iteration, 1 iteration = 1 full walk of the game tree for 1 player) without any form of parallelization. Is that good? Bad? Average? My turn subgame consists of 1352 information sets and both players have 100% ranges. I heard somewhere that you'll have good converge after 1000 iterations * # of information sets which means my program would take 29 minutes to converge which is really bad since piosolver only takes 10 seconds for the same subgame.

Statistics: Posted by Fossana — Sat Jun 29, 2019 11:42 pm

Re: My CFR implementation is too slow.

2019-06-28T16:31:14+00:00

Now that I'm passing in vectors of reach probabilities for both players ranges and doing O(n) terminal node evaluations I'm getting 18 iterations per second. This is much better than 1 iteration every 1.5 minutes.

Kind of worried it's operating too fast and there's something wrong with my code...

Statistics: Posted by Fossana — Fri Jun 28, 2019 4:31 pm

Re: My CFR implementation is too slow.

2019-06-28T15:11:56+00:00

Quote:

I’m using Java.

That's fast enough to start with. Just as long as you aren't using python.

Quote:

Instead of dealing two hands and walking the tree for every possible combination of two hands, is it faster to pass in a 52x52 2D array (1x1326 may be better) for both ranges?

I think passing in one 1326 long array of double and one int is faster than two ints and a double but it is a very long time ago that I compared the two so can't remember. The meat of the work is the same but the two ints has a lot more traversal overhead.

Passing in two 1326 long arrays of doubles is much faster than passing in one 1326 long array of double and one int but that speed up mostly comes from the faster showdown comparison (proportional to 1326 rather than 1326 * 1326). As I wrote before I think means you lose card removal effects.

Quote:

I have heard of vector form CFR being faster than scalar form CFR. Not sure if vector form CFR refers to vectors for private information.

If you can find the quote I'll see what I think it means.

Statistics: Posted by spears — Fri Jun 28, 2019 3:11 pm

Re: My CFR implementation is too slow.

2019-06-28T12:23:15+00:00

spears wrote:

Quote:

3700 * 1326 * 1326 = 6.5 billion

This sounds like each decision node is visited by just two hands. Is that what you are doing?

I have used two alternative schemes:
- visit with one training hand and a vector of opponent hands
- visit with a vector of training hands and a vector of opponent hands. If you order the river hands you can do 1326 comparisons at showdown instead of 1326 * 1326 comparisons. Unfortunately I think this also means you lose card removal effects.

I suggest you try CFR+ or sampling.
http://poker.cs.ualberta.ca/publication ... cm2017.pdf
https://poker.cs.ualberta.ca/publicatio ... 12-pcs.pdf

What language are you using?

I’m using Java. C++ is probably faster, but I’m more familiar with developing a GUI in java (I’m hoping to make a commercial solver).

Either I’m not touching enough nodes per second or my game tree is too big or my approach is wrong.

Instead of dealing two hands and walking the tree for every possible combination of two hands, is it faster to pass in a 52x52 2D array (1x1326 may be better) for both ranges? I’m not sure if that would speed things up because it sounds like you end up multiplying this by a 52x52 strategy 2D array for every action and you end up just doing more work at each node, but perhaps I’m wrong.

I have heard of vector form CFR being faster than scalar form CFR. Not sure if vector form CFR refers to vectors for private information.

Statistics: Posted by Fossana — Fri Jun 28, 2019 12:23 pm

Re: My CFR implementation is too slow.

2019-06-28T08:12:53+00:00

Quote:

3700 * 1326 * 1326 = 6.5 billion

Statistics: Posted by spears — Fri Jun 28, 2019 8:12 am

My CFR implementation is too slow.

2019-06-28T05:59:41+00:00

I implemented vanilla CFR and it touches 70 million nodes per second. I'm trying to solve turn subgames currently (both players have 100% ranges, 4 cards on board specified, one bet/raise size allowed on each street). Unfortunately, one full traversal of the game tree requires touching 6.5 billion nodes, so it would take 1.5 minutes to traverse the whole game tree once. That's obviously way too slow for one iteration as I imagine solving the turn subgame to a low level of exploitability would take 10,000 iterations. Maybe there's something wrong with my game tree and it shouldn't consist of 6.5*10^12 nodes. My game tree has 3700 decision nodes and there is a chance node for dealing the river. I take care of dealing hole cards separately. Anyways, 3700 * 1326 * 1326 = 6.5 billion.

Thoughts?

Statistics: Posted by Fossana — Fri Jun 28, 2019 5:59 am