Faster/clearer computation of dealer probabilities?

iCountNTrack

Well-Known Member
#42
ericfarmer said:
Following is a summary of some timing tests that I ran last night. There are some interesting results that I am not sure I fully understand, so any review or comments are appreciated.

The calculation for which I measured execution time is: given a number of decks, compute the set of probabilities of outcomes of the dealer's hand (bust, 17-21, or blackjack) for each up card, assuming S17. I evaluated my code and assume_R's code using a slightly modified version of the test wrapper earlier in this thread, and iCountNTrack's code using a Mathematica wrapper around Run[] system calls to his latest executable.

To accurately estimate execution time for one calculation of a given shoe, I ran 100,000 iterations of my code (for each number of decks), 10,000 iterations of assume_R's, and 100 iterations of iCountNTrack's. (This was in the interest of time, since there were order of magnitude differences in speed.)

The following plot shows the resulting single-iteration execution times vs. number of decks. My code, assume_R's, and iCountNTrack's are shown in blue, magenta, and, well, goldenrod or whatever (Mathematica's defaults).



The bottom two curves make sense to me: there is consistently about a 15x difference in speed between my and assume_R's implementation, with single deck being slightly faster, but things leveling off quickly as the shoe grows, to where even 1000 decks would yield these same times, about 0.000174 second and 0.002678 second, resp.

But the log-scale plot hides the very linear increase in execution time of iCountNTrack's code, which I don't understand. Following are just those times, on a linear scale with a least squares fit:



Not sure what is happening here.
Thanks Eric for the detailed and well presented study. The reason my code runs slower as the number of decks increases is because my code was not designed to calculate dealer's probabilities because they are not needed by my algorithm. My algorithm is geared towards generating ordered card sequences for player and dealer.

I think it is a good place to talk a little more about my algorithm. As i have mentioned before my code is oriented towards calculating the probabilities of all possible net wins on the round. This is basically what I do

let's say we dealt the following ordered sequence for the player after a double vs a dealer's 9
8,3,3
The dealer got the following ordered sequence
9,3,4,10 (total of 26, dealer bust)

What i do now is look at the total number of cards in the round which is 7. And the total number for each denomination in the round, 3 "Threes", 1 "Four", 1 "Eight", 1 "Nine", 1 "Ten". I then calculate the probability of drawing a 7 card slug composed of 3 "Threes", 1 "Four", 1 "Eight", 1 "Nine", 1 "Ten" from a full deck (or any composition).
The calculated probability in this case is 32/877961175 or 3.6448081E-8.

Since the dealer busted and the player didnt, the net win on this round is a +2 (since it is a doubled hand). So the above value is added to the variable accumulating a net win of +2.
So in summary, we need the total number of cards in the round, the total number of each rank, and obviously the player's hand total and dealer hand total to figure out the outcome on the round.
This is basically the heart of my algorithm, and that is why i dont need to look at dealer's probabilities.
I calcualte them using the same approach described above (obviously only looking at ordered dealer's sequences), now the reason it runs slower is because it is computationally more expensive to calculate the probability of drawing a certain slug from an 8 deck shoe than from a 1 deck shoe.

Please see below a sample output from my CA for a 7,7 vs 6 (1 split, S17, DAS)

Code:
******************ChemMeister iCountNTrack*******************
**************Blackjack Combinatorial Analyzer v 0.5**************
This is a combinatorial analyzer that is geared towards calculating player's
probabilities of the various possible outcomes of a round of blackjack
Before I can make a GUI in Visual Studio, the only rules supported are S17/H17,
DAS, ENHC (entering sequential input for 5 mns is not fun :)). Since splits EV are 
calculated with post-split optimal strategies, calculations for 2 and especially 3 splits
will take a long while to finish, and might crash if your computer doesnt have enough RAM. 
A faster multi-threaded version is at works.please report any bugs to me. Enjoy!!
 
player's Hand  7,7
dealer's upCard  6
 
player's probabilities for standing
p_-1 = 0.587113
p_0 = 0
p_+1= 0.412887
p_+1.5 = 0
EV for standing= -0.174225 ± 0.984706
 
player's probabilities for doubling
p_-2 = 0.662625
p_0 = 0.0416909
p_+2= 0.295684
EV for doubling= -0.733882 ± 1.81512
 
player's probabilities for hitting
p_-1 = 0.662625
p_0 = 0.0416909
p_+1= 0.295684
EV for hitting= -0.366941 ± 0.907559
 
player's probabilities for splitting
p_-4 = 0.0211505
p_-3 = 0.13668
p_-2 = 0.232415
p_-1 = 0.0691998
p_0 = 0.0374809
p_+1= 0.0592694
p_+2 = 0.204007
p_+3 = 0.187876
p_+4 = 0.0519218
EV for splitting= 0.209924 ± 2.43316
 

assume_R

Well-Known Member
#43
Well now you're just showing off haha :laugh:.

My biggest overhead is the exponential number of stack recursion calls which your non-recursive implementation is clearly not going to be burdened by.

On another note, were you able to think of any ways to avoid the repeating "if" statement that is taking up most of your computation time (see my screenshot of your profiled code)? This would make your code even faster!
 
#44
iCountNTrack said:
So in summary, we need the total number of cards in the round, the total number of each rank, and obviously the player's hand total and dealer hand total to figure out the outcome on the round.
This is basically the heart of my algorithm, and that is why i dont need to look at dealer's probabilities.
I calcualte them using the same approach described above (obviously only looking at ordered dealer's sequences), now the reason it runs slower is because it is computationally more expensive to calculate the probability of drawing a certain slug from an 8 deck shoe than from a 1 deck shoe.
Very good description, I think I understand a little better now. And this is why I think execution time for dealer probabilities is only a marginally useful metric. To see why, let's move on to player EV. Consider how long it takes to compute the overall EV for a round (e.g., 0.153119996% for the same single deck, no resplit setup as your example above).

My dealer calculations might be relatively fast... but to compute overall player EV, I have to do a lot of them, for many different removed subsets. And I mean a lot: 4,849 iterations in your single deck example, up to 7,316 for 6+ decks... and that is without resplitting. When resplits are allowed, I evaluate dealer probabilities 10,231 times even for a single deck, up to a maximum of 25,941 times for 6+ decks.

(Since this is where all of my time is spent, overall execution time varies nicely linearly as this number of shoe subsets. That is, on the same machine as the results posted earlier, single deck no resplit takes 0.594 second, up to a maximum of 5.312 seconds for 6+ decks with resplitting allowed.)

It would be much more interesting, I think, to compare these numbers against other CAs, instead of just dealer probabilities. Is this something that you can readily measure? For example, can you start with no cards in the player's hand when you do your "traversal"?
 

iCountNTrack

Well-Known Member
#45
ericfarmer said:
Very good description, I think I understand a little better now. And this is why I think execution time for dealer probabilities is only a marginally useful metric. To see why, let's move on to player EV. Consider how long it takes to compute the overall EV for a round (e.g., 0.153119996% for the same single deck, no resplit setup as your example above).

My dealer calculations might be relatively fast... but to compute overall player EV, I have to do a lot of them, for many different removed subsets. And I mean a lot: 4,849 iterations in your single deck example, up to 7,316 for 6+ decks... and that is without resplitting. When resplits are allowed, I evaluate dealer probabilities 10,231 times even for a single deck, up to a maximum of 25,941 times for 6+ decks.

(Since this is where all of my time is spent, overall execution time varies nicely linearly as this number of shoe subsets. That is, on the same machine as the results posted earlier, single deck no resplit takes 0.594 second, up to a maximum of 5.312 seconds for 6+ decks with resplitting allowed.)

It would be much more interesting, I think, to compare these numbers against other CAs, instead of just dealer probabilities. Is this something that you can readily measure? For example, can you start with no cards in the player's hand when you do your "traversal"?
I have no doubt that your CA will beat mine hands down, dealing ordered card sequences is a really slow process and unfortunately it is the only way i could think off to calculate players probabilities as shown in my above post. There are a couple of extra tweaks, but the biggest speed boost will be from making multi-threaded version.
But to give you an idea, with no resplitting allowed for a single deck we are talking 4-5 minutes
 
#46
iCountNTrack said:
So in summary, we need the total number of cards in the round, the total number of each rank, and obviously the player's hand total and dealer hand total to figure out the outcome on the round.
This is basically the heart of my algorithm, and that is why i dont need to look at dealer's probabilities.
I calcualte them using the same approach described above (obviously only looking at ordered dealer's sequences), now the reason it runs slower is because it is computationally more expensive to calculate the probability of drawing a certain slug from an 8 deck shoe than from a 1 deck shoe.
Responding separately to your last comment: do I understand correctly that it currently takes longer to calculate the probability of drawing the 7-card slug in your example from an 8-deck shoe than it does for drawing the same 7-card slug from a single deck? It seems like this should vary approximately linearly as the size of the slug, not the size of the shoe.

For example, wouldn't something like the following pseudocode yield the same probability as in your example?

Code:
int n = shoe.numCards; // e.g., 52
double p = 1;
for (int c = 1; c <= 10; ++c)
{
    for (int k = slug.cards[c], s = shoe.cards[c]; k != 0; --k, --s, --n)
    {
        p *= static_cast<double>(s) / n;
    }
}
The execution time for this loop should be independent of the shoe size, with one inner multiplication per card in the removed slug.

Am I misunderstanding your comment?
 

MangoJ

Well-Known Member
#47
iCountNTrack said:
I have no doubt that your CA will beat mine hands down, dealing ordered card sequences is a really slow process and unfortunately it is the only way i could think off to calculate players probabilities as shown in my above post. There are a couple of extra tweaks, but the biggest speed boost will be from making multi-threaded version.
If you can avoid all conditional statements by some mathematical tweaks, you can go for graphics hardware (nVidia CUDA) in a massive parallel approach running on the GPU. Since each of your sequence can be evaluated independently, this will scale quite nicely.

The recursive approach is well suited for multi-threads (i.e. each upcard is a thread), but will probably fail on massive parallel hardware.

Your ordered card approach could turn out much more superior!
 

iCountNTrack

Well-Known Member
#48
ericfarmer said:
Responding separately to your last comment: do I understand correctly that it currently takes longer to calculate the probability of drawing the 7-card slug in your example from an 8-deck shoe than it does for drawing the same 7-card slug from a single deck? It seems like this should vary approximately linearly as the size of the slug, not the size of the shoe.

For example, wouldn't something like the following pseudocode yield the same probability as in your example?

Code:
int n = shoe.numCards; // e.g., 52
double p = 1;
for (int c = 1; c <= 10; ++c)
{
    for (int k = slug.cards[c], s = shoe.cards[c]; k != 0; --k, --s, --n)
    {
        p *= static_cast<double>(s) / n;
    }
}
The execution time for this loop should be independent of the shoe size, with one inner multiplication per card in the removed slug.

Am I misunderstanding your comment?
I am not sure your snippet would work, I will have to test it. I use the following equation to calculate probabilities



calculating the factorial of 400 takes more time then 52
 
#49
assume_R said:
Well now you're just showing off haha :laugh:.

My biggest overhead is the exponential number of stack recursion calls which your non-recursive implementation is clearly not going to be burdened by.

On another note, were you able to think of any ways to avoid the repeating "if" statement that is taking up most of your computation time (see my screenshot of your profiled code)? This would make your code even faster!
Sorry, I certainly do not mean to point and say, "Look, mine is fastest!" I find this to be an interesting "polymath" approach to these problems, no matter who is responsible for which implementations. (And I am still unconvinced that others aren't doing this stuff even faster. I remember Usenet discussions in rgb almost 15 years ago with someone named Max Berger, and although my memory is vague, I seem to recall him mentioning a few anecdotal execution times that made me wonder, "How is he possibly doing that?" :))

I haven't gotten back to looking at the dealer optimization in a while. I was pretty sidetracked re-working my splitting algorithm to get that right.
 

iCountNTrack

Well-Known Member
#50
MangoJ said:
If you can avoid all conditional statements by some mathematical tweaks, you can go for graphics hardware (nVidia CUDA) in a massive parallel approach running on the GPU. Since each of your sequence can be evaluated independently, this will scale quite nicely.

The recursive approach is well suited for multi-threads (i.e. each upcard is a thread), but will probably fail on massive parallel hardware.

Your ordered card approach could turn out much more superior!
Hahaha these seem like very nice suggestions for a seasoned programmer not for a novice guy like me.
But the multithreading version seems to be the most promising since i can run the outermost loop in parallell where the first card of the sequence is dealt.
 

London Colin

Well-Known Member
#51
MangoJ said:
If you can avoid all conditional statements by some mathematical tweaks, you can go for graphics hardware (nVidia CUDA) in a massive parallel approach running on the GPU. Since each of your sequence can be evaluated independently, this will scale quite nicely.

The recursive approach is well suited for multi-threads (i.e. each upcard is a thread), but will probably fail on massive parallel hardware.

Your ordered card approach could turn out much more superior!
I was going to mention the CPGPU possibility too, in the other thread where OpenMP was mentioned.

It's something I've had my eye on for a while, without so far trying it out. OpenCL may be a better way to go than CUDA, as it is more portable and apparently can utilize both multi-core CPUs and GPUs.

The disadvantages of the CPGPU approach seem to be that -
  • Only top-end, expensive graphics cards support double precision.
  • The programming language for the GPU code is based on C, not C++.
  • Recursion is not directly supported for code that runs on the GPU.
But I think it still could provide benefits, perhaps with recursive code executing on the CPU, kicking off non-recursive tasks on the GPU as it goes along.
 

MGP

Well-Known Member
#52
If you want to know who has the fastest CA it's T Hopper. His CA does the entire calculation for all values including splits and calculating a final EV in a fraction of a second.

I don't know if he visits this page at all but he used to be on the BJ Math page.

I can't just separate out my dealer probs calcs as there's too much incorporated so I can't compare to you guys but my basic format is very similar to Eric's. In any case, since even with weird rules and bonuses and all the stats collected the calcs take less than 1 minute, I'm not that worried about it and it's something I can live with.

MGP
 

assume_R

Well-Known Member
#53
MGP said:
If you want to know who has the fastest CA it's T Hopper. His CA does the entire calculation for all values including splits and calculating a final EV in a fraction of a second.
How? Are all possible shoe states' dealer probabilities up to 8 decks just loaded from a file or something for S17 and H17?
 
#54
iCountNTrack said:
I am not sure your snippet would work, I will have to test it. I use the following equation to calculate probabilities



calculating the factorial of 400 takes more time then 52
Cool! The snippet implements the same formula, for example yielding p=32/877961175 for the given slug in your earlier example, where slug.cards == your k_i. You mention "calculating the factorial of 400"; I am guessing, then, that you have a separate function (or a section of code that implements the function) that computes the falling factorial (n)_k, and you compute the given formula in terms of products/ratio of those (n)_k's?

If so, then I think this should yield a huge speedup, even for single deck, as well as eliminating the linear increase in time with shoe size. I am curious to see what you think, and how it goes.
 

iCountNTrack

Well-Known Member
#55
ericfarmer said:
Cool! The snippet implements the same formula, for example yielding p=32/877961175 for the given slug in your earlier example, where slug.cards == your k_i. You mention "calculating the factorial of 400"; I am guessing, then, that you have a separate function (or a section of code that implements the function) that computes the falling factorial (n)_k, and you compute the given formula in terms of products/ratio of those (n)_k's?

If so, then I think this should yield a huge speedup, even for single deck, as well as eliminating the linear increase in time with shoe size. I am curious to see what you think, and how it goes.


Thanks I will take a look at it :)
 

MGP

Well-Known Member
#56
assume_R said:
How? Are all possible shoe states' dealer probabilities up to 8 decks just loaded from a file or something for S17 and H17?

Nope. He calculates them. He'd have to explain it if he wanted to and if he sees these posts.
 
Top