spears wrote:

I would love to know how commercial programs are as fast as they are, both for solving NE and for calculating BR. Somebody on this board HontoNiBaka? recently pointed out that the trees they use are a lot smaller than you would expect so maybe they exploit isomorphisms. I've never tried myself, but can you use sampling to speed up BR?

I tried to use sampling for BR computing but for some reason results are always different with "brute force" BR calculations. Very different. So i'm sure that i made it totally wrong but didn't find a reason.

What i did is just this:

1. Sample player cards, opp cards and board.

2. Walk the tree like we are walking it in classic BR algo - choosing max ev in player nodes and weighting ev (weights are from average strategy of course) in opponent nodes.

3. In terminal nodes as we have all info about cards and board i can calcultate utility - so everything looks easy here (no hand vs range calculations).

3. As result of this walk i have a br that i sum with other br from other iterations and in the end just divide on iterations count.

For some reason this resulting in wrong BRs. And i think i have some error in approach. Like maybe i don't need to sample opponent cards and only use his range or smth like this. So i tried this and then returned to optimizations of "brute force" approach.

About isomorphisms - yes it could speed up, but for example for simple push/checkdown tree from flop (around 13 nodes at all include checks on turn and river) my BR for one player calculates around 80 seconds in one thread. And this is after i did ALL calculations of hand ranks for showdowns. So literally this is a time that CPU needs to iterate through all tripples like hand1/hand2/board and check which rank is bigger in every utility node. Isomorphism can speed up this but not sure it can speed up somehow to 40 times.

Anyway speed of calculations depends on how we preparing data before tree walk.

I think i should describe my current algo a bit - maybe we can find weak place.

After CFR algo we have a tree. I'm using abstractions, so in each node (actually on each street) for every pair hand/board i have a bucket ("information set" they call it, but i preffer a "bucket"). So as result of CFR algo i have a strategy (probabilities with which i should choose every child action here) for each bucket in every node.

Now i take player's range, opponent's range and initial board (i am working on postlop solver, so i have a board from start - lets assume we are talking about a tree from flop - so i have three board cards on start).

Next i iterate through all player's hands and all possible boards. One iteration has on start player hand, opp range (i don't iterate opp range), full board (5 cards) and a probability of this choise. In general probability here is a player's hand probability, because board has same probability every time.

In iteration main idea is to take opponent's range and update probabilities of each hand walking through tree. In each opponent's node i take every hand from range, calculate a bucket for them (i know a board, so i can get a bucket), and then multiply this hand probability on strategy probability for this bucket in this node. And so on until we are not in utility node.

Inside utility node i still have player's hand (it is needed only here) and updated opponent's range. So i can calculate an utility just comparing hand ranks (with probability) of all opponent's range and player's hand rank.

That's all.

Problem here is that i need to iterate all possible boards. I can't take only opponent's range and with only one tree walk update all hands probabilities for all boards. Because in each opponent's node i need a board to get bucket. And i need a bucket to get strategy to update probabilities. And so on.

Yes of course i can do one tree walk, but then i will need to iterate through all boards in every utility node. Anyway this loop must be somewhere. And as i undestand right there is a major upgrade of this algo that removes this "all boards" loop somehow. But i cant find this ugrade)

Any ideas?) Maybe i'm doing something totally wrong?