Proving CA algorithms incorrect (or at least inexact)

[ericfarmer]

I made a minor update to my blackjack CA software (on GitHub), to support computing probabilities and expected values to arbitrary (rational) precision, instead of the usual 64-bit double (floating-point) precision.

For example, playing the usual "realizably optimal" CDZ- strategy with 6D, S17, DOA, DAS, SPL3, LS, the exact expected return as a fraction of initial wager is:

     636491186124390779995774550739146028101753
- ---------------------------------------------
  192719583540554771243108474049609438884038125

or about -0.33%.

This is mostly just a parlor trick of purely academic interest (especially for the probably-unrealistic specific rules in this example)... but it turns out to have some practical utility for analysis. I made these changes motivated by a couple of parallel discussions about CA algorithms for pair splitting. Suppose we have a new algorithm for computing expected values, perhaps using some new post-split playing strategy, or maybe just a more efficient/faster algorithm, etc. How can we check whether our algorithm is "exact"?

Recall that the true count theorem-- or really the "extended" version of it proved by Thorpe to apply to non-linear functions like exact expected return-- essentially says that "the average effect of removal must be zero." That is, if we compute the expected return from playing CDZ- from a full 6-deck shoe (as reported below by my CA, for example, using the above rules):

-0.0033026803733750346

then we should get exactly the same result if we instead compute the average of the expected return after burning the top card of the shoe, but still playing the same "full-shoe" strategy (again as reported below by my CA):

-0.0033026803733748255

These aren't exactly the same, but they should be. So how can we tell if this discrepancy is because of a bug or other flaw in the algorithm, as opposed to simple rounding error due to working in limited double precision arithmetic?

I "typedef"ed the numeric data type in my CA code, to default to double, but to support arbitrary-precision rationals instead. Using the latter, I verified that we always get the exact result above, both off the top of the shoe as well as averaged across possible burn cards (and a few other more complex removal strategies as well).

In other words, if we asked some other analyst to compute the exact return using CDZ- with the above rules, then at least in principle, they should be able to verify exact agreement with the above fraction, if they also used arbitrary-precision rational arithmetic in the implementation of their algorithm... despite possibly disagreeing with the double-precision values above in low-order bits, due to the various rounding error effects of differing order of operations in their (otherwise equivalent) code, using a different compiler and/or a different hardware architecture, etc.

I wrote a related blog post on this subject, with more details and a simpler example demonstrating the issue and potential problems.

[Gramazeka]

CDZ- strategy with 6D, S17, DOA, DAS, SPL3, LS

What the EV SPL 1 ?

[ericfarmer]

What the EV SPL 1 ?

All other rules held the same, -54189564458895562046454825488113665903638/14101432941991812529983546881678739430539375, or about -0.384284099%.

[Gramazeka]

EV = -0.3842840985, for the spl1 case. A tiny Verbesserung.
I have one point in number.

ps. Zenfighter...

[Cacarulo]

It is not my intention to argue about which approach is better or worse.
There have always been and always will be small discrepancies in the calculation of splits.
My optimal calculation for SPL1 is as follows:

EV = -0.38428244655240584%

Sincerely,
Cac

[JohnGalt007]

Thank you for the high-quality post and expertise as always, Eric! Your work has been a huge boon to me in my own blackjack research.

I'd like to be the first to offer an explanation for the small puzzle you mentioned in your blog post, regarding the error in the code.

"The result is -25/169, or about 14.8% of the player’s wager going to the house. Or is it? There is an error in the above code. Let’s leave it as an exercise for the reader to find the bug (hint: one line is missing) … and instead prove that there must be a bug, even without identifying nor fixing it."

The proof is as follows. Consider the situation where the values assigned to card1 and card2 are both equal to 1. Then the second draw should be impossible, since no more cards of that type are left after the first draw. However, the original code doesn't account for this and falsely assumes there are still cards available, thereby leading to a situation where cards are dealt with replacement with a nonzero probability. This results in an overestimation of the probability for drawing identical cards, leading to incorrect calculations of the expected value. Thus, the code should have a line that decrements the value assigned to card1 from the shoe after the first deal, so that the second selection is made from the updated shoe with one card fewer.

[ericfarmer]

EV = -0.3842840985, for the spl1 case. A tiny Verbesserung.
I have one point in number.

ps. Zenfighter...

I had to look up "Verbesserung."

I might be missing the point of your comment, but note that I said, "about," i.e., "approximately." We could both have written "about -0.384284099%", "or "about -0.3842840985%", or "about -0.38%", or "about -0.384284", or "about -0.0038428409851546153026267942850941511161". These are all only approximations, to differing number of digits of precision, of the *exact* rational value given above.

[ericfarmer]

My optimal calculation for SPL1 is as follows:

EV = -0.38428244655240584%

We need to ensure we're talking about the same playing strategy. Note that I indicated CDZ- playing strategy in the top post; your value is the expected return from playing CDP[1] strategy, which allows different playing decisions post-split... but the *same* playing strategy for both *halves* of the split. (We can argue that neither CDZ- nor CDP1 is truly *optimal*, hence my qualifier "realizably"; only ICountNTrack that I know of has computed the truly maximum possible expected return by varying composition-dependent strategy in the second of the split informed by cards dealt in the first half.)

But maximality of values isn't really the point of my post; accuracy is, in particular the ability to verify accuracy using average EOR.

At any rate, this is a great example regardless: I (and I think k_c as well) can reproduce the CDP1 return you specify: using my CA, I get (as fraction of initial wager)

-0.0038428244655240446

Note that this is slightly different than your value... and we're both wrong! That is, the actual exact expected return from playing CDP1 strategy is

-114565182893091296235042792354649911448 / 29812754634232161797005384527862028394375

which you can verify is (approximately) 0.003842824465523997818495261...

Both of our values differ from this in the low order 8 bits of (double) precision. That is, we're computing a (64-bit) double precision value, which has 53 bits of "mantissa" (1 implied and 52 explicit)... but only the most significant 45 of those bits are correct. We lose some accuracy due solely to the cumulative effects of rounding error from working in that limited double precision.

There have always been and always will be small discrepancies in the calculation of splits.

I disagree! This is sort of the point of my post. I said "we're both wrong" above, but that deserves qualification/correction. Sure, there is a small discrepancy between our values above-- but I claim that discrepancy isn't due to differences in "the math," but is instead due solely to the cumulative effects of rounding error from working in double precision. If you were to hypothetically modify your CA code similar to what I've done here, keeping your algorithm exactly as implemented, but "typedef"ing the data type of all intermediate arithmetic operations to preserve the arbitrary-precision rational numerator/denominator representation... then I'm confident that your CA would agree exactly, with no "small discrepancies," with the same rational expected return that I indicate above.

For a much more simplified example to hopefully illustrate my point: what is the probability of a blackjack in this 6D scenario? We can both agree, with no need to accept "small discrepancies," that the exact probability is 192/4043. But suppose that your CA computed and reported this probability using double-precision code like the following:

double p_bj = (96 * 24 * 2) / (312 * 311);

where my CA instead computes the value as follows:

double p_bj = (96 / 312) * (24 / 311) * 2;

As you can see, the "math is the same" in both cases... but the resulting values will be slightly different (differing in just the single lowest ulp), and as above, *neither* of the double-precision results of these operations exactly equals the true probability of 192/4043.

[ericfarmer]

... Thus, the code should have a line that decrements the value assigned to card1 from the shoe after the first deal, so that the second selection is made from the updated shoe with one card fewer.

Correct!

[Cacarulo]

We need to ensure we're talking about the same playing strategy. Note that I indicated CDZ- playing strategy in the top post; your value is the expected return from playing CDP[1] strategy, which allows different playing decisions post-split... but the *same* playing strategy for both *halves* of the split. (We can argue that neither CDZ- nor CDP1 is truly *optimal*, hence my qualifier "realizably"; only ICountNTrack that I know of has computed the truly maximum possible expected return by varying composition-dependent strategy in the second of the split informed by cards dealt in the first half.)

But maximality of values isn't really the point of my post; accuracy is, in particular the ability to verify accuracy using average EOR.
At any rate, this is a great example regardless: I (and I think k_c as well) can reproduce the CDP1 return you specify: using my CA, I get (as fraction of initial wager)

-0.0038428244655240446

Note that this is slightly different than your value... and we're both wrong! That is, the actual exact expected return from playing CDP1 strategy is

-114565182893091296235042792354649911448 / 29812754634232161797005384527862028394375

which you can verify is (approximately) 0.003842824465523997818495261...

Both of our values differ from this in the low order 8 bits of (double) precision. That is, we're computing a (64-bit) double precision value, which has 53 bits of "mantissa" (1 implied and 52 explicit)... but only the most significant 45 of those bits are correct. We lose some accuracy due solely to the cumulative effects of rounding error from working in that limited double precision.

It’s true that neither CDZ- nor CDP1 is fully optimal, though they provide excellent approximations to the exact value. I’d be curious to see the expected value that ICountNTrack calculated,
to determine which strategy comes closest. I also imagine that ICountNTrack’s method is likely feasible only with SPL1.

I completely understand the concept of arbitrary precision, and I fully agree it’s the only way to achieve an “exact” value for any of the "approximations" we’re discussing.
Clearly, double precision (64 bits) has its limitations, leading to some accumulation of rounding errors. But how many exact decimals do we really need?
Sometimes, code optimization and speed are more important for producing a result.

I disagree! This is sort of the point of my post. I said "we're both wrong" above, but that deserves qualification/correction. Sure, there is a small discrepancy between our values above-- but I claim that discrepancy isn't due to differences in "the math," but is instead due solely to the cumulative effects of rounding error from working in double precision. If you were to hypothetically modify your CA code similar to what I've done here, keeping your algorithm exactly as implemented, but "typedef"ing the data type of all intermediate arithmetic operations to preserve the arbitrary-precision rational numerator/denominator representation... then I'm confident that your CA would agree exactly, with no "small discrepancies," with the same rational expected return that I indicate above.

Yes, we are both wrong.

For a much more simplified example to hopefully illustrate my point: what is the probability of a blackjack in this 6D scenario? We can both agree, with no need to accept "small discrepancies," that the exact probability is 192/4043. But suppose that your CA computed and reported this probability using double-precision code like the following:

double p_bj = (96 * 24 * 2) / (312 * 311);

where my CA instead computes the value as follows:

double p_bj = (96 / 312) * (24 / 311) * 2;

As you can see, the "math is the same" in both cases... but the resulting values will be slightly different (differing in just the single lowest ulp), and as above, *neither* of the double-precision results of these operations exactly equals the true probability of 192/4043.

This exercise is interesting. How many exact decimals could we obtain using double precision?
Using arbitrary precision,

bj = 192. / 4043. = 0.0474894880039574573336631214444719267870393272322532772693544397724 462033143705169428642097452386841

For the other two cases, using double precision, I got the following:

bj = (96. * 24. * 2.) / (312. * 311.) = 0.047489488003957455730663639315
bj = (96. / 312.) * (24. / 311.) * 2. = 0.047489488003957462669557543222
bj = 192. / 4043. = 0.047489488003957455730663639315

That means we can get up to 17 correct decimals.

Sincerely,
Cac

[ericfarmer]

It’s true that neither CDZ- nor CDP1 is fully optimal, though they provide excellent approximations to the exact value. I’d be curious to see the expected value that ICountNTrack calculated, to determine which strategy comes closest.

In general E[CDZ-] < E[CDP1] < E[CDP], since the strategy complexity or "expressive power" is strictly greater for each successive strategy. (Intuitively, the maximum over a superset of S can't be *less* than the maximum over S.) That is, in CDZ- we are constraining strategy to depend only on the composition of cards in the current (possibly split) hand, while in CDP1 strategy can vary depending on whether the hand is part of a split. (I'm not bothering to explain CDP, since as discussed in a previous thread, it's not executable at the table.)

I also imagine that ICountNTrack’s method is likely feasible only with SPL1.

ICountNTrack will have to chime in, but I believe this is correct, although I seem to recall that their code can also crank out EVs for SPL3 for some sufficiently small depleted shoes.

Sometimes, code optimization and speed are more important for producing a result.

Yep; when built with #define BJ_USE_RATIONAL, this updated version is hopelessly slow, taking around half an hour to compute one of the 6D values above (compared with milliseconds when typedef'ed to use double).

Again, the point here wasn't speed, but to present a "one-sided" correctness test. When someone comes up with a new pair-splitting algorithm claimed to be exact, my first suggestion is: "Compute the average EOR using your new algorithm. If it isn't zero, then your algorithm *can't* be exact." (But this is complicated by the cumulative effect of rounding error in double precision. If you can test your algorithm in arbitrary precision, then you can isolate and distinguish "small" discrepancies in average EOR due to rounding error vs. actual flaws in your algorithm or bugs in your code.)

This exercise is interesting. How many exact decimals could we obtain using double precision?
Using arbitrary precision,

bj = 192. / 4043. = 0.0474894880039574573336631214444719267870393272322532772693544397724 462033143705169428642097452386841

For the other two cases, using double precision, I got the following:

bj = (96. * 24. * 2.) / (312. * 311.) = 0.047489488003957455730663639315
bj = (96. / 312.) * (24. / 311.) * 2. = 0.047489488003957462669557543222
bj = 192. / 4043. = 0.047489488003957455730663639315

That means we can get up to 17 correct decimals.

Yep, this is ceil(53*log10(2))+1.

[Cacarulo]

Again, the point here wasn't speed, but to present a "one-sided" correctness test. When someone comes up with a new pair-splitting algorithm claimed to be exact, my first suggestion is: "Compute the average EOR using your new algorithm. If it isn't zero, then your algorithm *can't* be exact." (But this is complicated by the cumulative effect of rounding error in double precision. If you can test your algorithm in arbitrary precision, then you can isolate and distinguish "small" discrepancies in average EOR due to rounding error vs. actual flaws in your algorithm or bugs in your code.)

An important point when calculating EORs is that their sum must be exactly zero. But for it to be zero, the strategy must be fixed (this means that we are going to apply exactly the same strategy for each of the removed cards). This way, we can obtain EORs for a TD (total-dependent) strategy as well as for a CD (composition-dependent) strategy. Without resorting to arbitrary precision, it’s possible to achieve 10 or more exact decimals that add up to zero. Four decimals would already be sufficient, as we must remember that EORs are linear estimates.
In my case, I use three types of strategies: TD, 2-card CD, and OP (CDP1). With the first two, I can obtain precise EORs that can also be simulated, for example, with CVData. With the third strategy, it’s not possible to get EORs that sum to zero. It’s probably possible with CDZ-.

Yep, this is ceil(53*log10(2))+1.

Interesting.

Sincerely,
Cac

[Zenfighter]

I had to look up "Verbesserung."

I might be missing the point of your comment, but note that I said, "about," i.e., "approximately." We could both have written "about -0.384284099%", "or "about -0.3842840985%", or "about -0.38%", or "about -0.384284", or "about -0.0038428409851546153026267942850941511161". These are all only approximations, to differing number of digits of precision, of the *exact* rational value given above.

I might be missing the point of your comment

Exactly. Just an excerpt, what he wrote here online from a private mail that I dropped him, many hours before you gave him your own figure. The final part went like this:

6dks, s17, das, spl1, ls
TD EV = - 0.3857506628

Note too, that Farmer’s final EV is a composition-dependent number. In this case we get:
EV = -0.3842840985, for the spl1 case. A tiny Verbesserung.

I had to look up "Verbesserung."

Strange, indeed. [Farm]er having to look after [besser] for a better understanding.

Just my two cents.

Zenfighter