Betting Game - Compound Probability Question - Page 2 - Gambling and Probability

R Gibert · 07-31-2012, 11:24 PM

Quote:

Originally Posted by R Gibert

I wrote a recursive Python program that solves this game almost exactly. I say almost, because the solution generated uses floating point and I'm not sure about the accumulated rounding errors for the larger cases. I don't expect it to be bad though. For the 10 turn 10 point case, the trailing zeroes are suggestive that it might be exact. I was tempted to rewrite it to compute using fractions to test this, but what's my incentive?

10 turn 10 point case EV ≈ 59.8878152500%
15 turn 15 point case EV ≈ 50.6019287756%
16 turn 16 point case EV ≈ 49.5261583702%

The most it can handle due to Python's limit on recursion depth is in the neighborhood of the 990 turn 990 point case. This has an EV ≈ 0.0000001066%. This solution was generated in only 2 secs. To handle larger cases would require removing the recursion, but I don't think this is worth the bother.

I would expect this puzzle to make a very nice prop. The EV is sensitive enough to strategy errors to allow a bettor to be profitable from both sides even in the 10 turn 10 point case. A lot of people taking the +EV side will only score about 40%. They will probably prefer the -EV side and get killed.

My 1st program was Monte Carlo for the 10 turn 10 point case using this strategy:

if 10*score < 9*turn: score += choice(B)
else: score += choice(A)

where turn is numbered 0 to 9 instead of 1 to 10. Simple and optimal making it perfect for a prop.

Thanks for the nice puzzle.

I'm wrong about the above given strategy being optimal, but it scores very close to optimal up to the 10 turn 10 point case. Where it differs, the decision is close. Here is a strategy table for the 10 turn 10 point case:

Code:

10 turn 10 point EV = 59.887815250000020484%

    10  9  8  7  6  5  4  3  2  1 turns left

 10 ░░ ██ ██ ██ ██ ██ ?? ?? ?? ?? 

  9 ?? ░░ ░█ █░ █░ █░ ?? ?? ?? ?? 

  8 ?? ░░ ░░ ██ ██ ██ ██ ?? ?? ?? 

  7 ?? ?? ░░ ░░ ▓▓ ░█ █░ ?? ?? ?? 

  6 ?? ?? ░░ ░░ ░░ ██ ██ ██ ?? ?? 

  5 ?? ?? ?? ░░ ░░ ░░ ▓▓ ░█ ?? ?? 

  4 ?? ?? ?? ░░ ░░ ░░ ░░ ██ ██ ?? 

  3 ?? ?? ?? ?? ░░ ░░ ░░ ░░ ▓▓ ?? 

  2 ?? ?? ?? ?? ░█ ░░ ░░ ░░ ░░ ██ 

  1 ?? ?? ?? ?? ?? ░█ ░█ ░░ ░░ ░░ 

points
needed


	██ Choice B

	█░ Close Decision B > A, ∆ < 0.1%

	▓▓ A = B

	░█ Close Decision A > B, ∆ < 0.1%

	░░ Choice A

	?? Unknown

For the 11 turn, 11 point case, it starts to perform increasingly poorly. My MC programs produces an EV = 53.87%, whereas the optimal strategy has an EV = 57.75%. A better, simpler rule of thumb is:

if s <= t: choice(A)
else: choice(B)

where s represents points needed and t represents number of turns remaining. It scales much better dropping only about 2.5% in the 40 turn 40 point case. What I came up with before was crap.

R Gibert · 08-01-2012, 12:08 AM

Quote:

Originally Posted by R Gibert

I'm wrong about the above given strategy being optimal, but it scores very close to optimal up to the 10 turn 10 point case. Where it differs, the decision is close. Here is a strategy table for the 10 turn 10 point case:

Code:

10 turn 10 point EV = 59.887815250000020484%

    10  9  8  7  6  5  4  3  2  1 turns left

 10 ░░ ██ ██ ██ ██ ██ ?? ?? ?? ?? 

  9 ?? ░░ ░█ █░ █░ █░ ?? ?? ?? ?? 

  8 ?? ░░ ░░ ██ ██ ██ ██ ?? ?? ?? 

  7 ?? ?? ░░ ░░ ▓▓ ░█ █░ ?? ?? ?? 

  6 ?? ?? ░░ ░░ ░░ ██ ██ ██ ?? ?? 

  5 ?? ?? ?? ░░ ░░ ░░ ▓▓ ░█ ?? ?? 

  4 ?? ?? ?? ░░ ░░ ░░ ░░ ██ ██ ?? 

  3 ?? ?? ?? ?? ░░ ░░ ░░ ░░ ▓▓ ?? 

  2 ?? ?? ?? ?? ░█ ░░ ░░ ░░ ░░ ██ 

  1 ?? ?? ?? ?? ?? ░█ ░█ ░░ ░░ ░░ 

points
needed


	██ Choice B

	█░ Close Decision B > A, ∆ < 0.1%

	▓▓ A = B

	░█ Close Decision A > B, ∆ < 0.1%

	░░ Choice A

	?? Unknown

For the 11 turn, 11 point case, it starts to perform increasingly poorly. My MC programs produces an EV = 53.87%, whereas the optimal strategy has an EV = 57.75%. A better, simpler rule of thumb is:

if s <= t: choice(A)
else: choice(B)

where s represents points needed and t represents number of turns remaining. It scales much better dropping only about 2.5% in the 40 turn 40 point case. What I came up with before was crap.

BTW, if the number of points needed is greater than 13, then use:

if s < t: choice(A)
else: choice(B)

instead. Note that "<=" was replaced by "<". This small change reduces the loss in EV to about 0.25%. By the combining the above 2 strategies, the game is effectively solved for all practical purposes. You are only sub-optimal by fractions of a percent.

Perfect play is problematic for a human. Examination of the 100 turn 100 point strategy table shows a lot of unexpected exceptions when the number of points needed is odd in number, but since the decisions are really close ones in such cases, it does not really matter much "practically" speaking.

**BruceZ** · 08-01-2012, 08:01 AM

Quote:

if s <= t: choice(A)
else: choice(B)

where s represents points needed and t represents number of turns remaining.

Quote:

Originally Posted by R Gibert

BTW, if the number of points needed is greater than 13, then use:

if s < t: choice(A)
else: choice(B)

instead.

We already reported these as optimal up to the 14 point game. The reason this doesn't agree with your optimal table for the 10 point game is because that table is wrong. When you need 7 points in 5 rounds, or 9 points in 8 rounds, there isn't a slight advantage to playing A. You play B, and it ain't even close. EDIT: It's as close as can be, equal, but A is not better. That should be obvious. You always play B as soon as possible when behind. When you need 5 points with 3 rounds remaining, there is no advantage to playing A. You need to win 2 B's and 1 A. Obviously it doesn't matter which one you play first. BBA, BAB, ABB all have the same probability of winning. If you lose any one, you can't recover. I suspect that this error caused your recursive program to recursively make the other errors. This is why you should never trust a computer to do your thinking for you. AFAICT, those are the only differences to the strategies that we gave. That may also clear up the irregularities for higher number of rounds. Of course if you know the optimal strategy for the N point game, then you also know it for the M point game where M < N.

R Gibert · 08-01-2012, 03:25 PM

Quote:

Originally Posted by BruceZ

We already reported these as optimal up to the 14 point game. The reason this doesn't agree with your optimal table for the 10 point game is because that table is wrong. When you need 7 points in 5 rounds, or 8 points in 9 rounds, there isn't a slight advantage to playing A. You play B, and it ain't even close. That should be obvious. You always play B as soon as possible when behind. When you need 5 points with 3 rounds remaining, there is no advantage to playing A. You need to win 2 B's and 1 A. Obviously it doesn't matter which one you play first. BBA, BAB, ABB all have the same probability of winning. If you lose any one, you can't recover. I suspect that this error caused your recursive program to recursively make the other errors. This is why you should never trust a computer to do your thinking for you. AFAICT, those are the only differences to the strategies that we gave. That may also clear up the irregularities for higher number of rounds. Of course if you know the optimal strategy for the N point game, then you also know it for the M point game where M < N.

I've modified my MC version, so that when the points needed is odd, always choose A. Here is the program:

Code:

def BetAB(turns, points, N = 1000000):
    A = [1]*90 + [0]*10
    B = [2]*40 + [0]*60
    wins = 0
    for i in range(N):
        s = points
        for t in range(turns, 0, -1):
            if s&1 == 1: s -= choice(A)   # When points needed is
            else:                         # odd always choose A
                if t < 14:
                    if s <= t: s -= choice(A)
                    else: s -= choice(B)
                else:
                    if s < t: s -= choice(A)
                    else: s -= choice(B)
            if s < 1:
                wins += 1
                break
    print("Wins %.2f%%" % (100*wins/N))

After 10M iterations, this version scored 59.88%, so the "difference" between choices A and B are not significant for s < t. So what you are saying about choice B being clearly better for the (8, 9), (5, 7) and (3, 5) cases does not seem to be correct. I've bolded the part further down where you seem to contradict yourself.

I admit, that in the recursive version of my program, it does generate anomalies in the strategy table. These become more apparent for larger versions of the problem. I'm pretty sure this is due to floating point rounding errors. I've known about this for awhile now and have been on the fence as to whether or not I should try to fix it. A comparison between the recursive version and the MC version did not seem to warrant it.

To reduce this effect, a modification to the original problem to use probabilities in the form of n/256 instead of n/100 might help. Or computing using fractions for the EV would be even better, since truncation errors would still occur.

I'll keep working on this, but in the meantime, you can look at an early version of my recursive version for any errors it might have. Perhaps with more than one set of eyes, this can all be cleared up sooner:

Code:

def evAB(turns, points):
    def ev(turns, points):
        if not ((turns, points) in T):
            if 2*turns == points: T[turns, points] = .4**turns
            elif points == 1 and turns > 0: T[turns, points] = 1 - .1**turns
            elif 2*turns < points: T[turns, points] = 0
            elif points < 1: T[turns, points] = 1
            else:
                miss = ev(turns - 1, points)
                T[turns, points] = max(.9*ev(turns - 1, points - 1) + .1*miss,
                                      .4*ev(turns - 1, points - 2) + .6*miss)
        return T[turns, points]
    
    T = {}
    print("Wins %.20f%%\n" % (ev(turns, points)))

T is a associative array that I use to save previously computed results, so that they do not need to be recomputed. It isn't necessary for the operation of the algorithm. It is only intended as a speed up.

Also, the lines:

Code:

            if 2*turns == points: T[turns, points] = .4**turns
            elif points == 1 and turns > 0: T[turns, points] = 1 - .1**turns

are not necessary either. These too are only intended as a speed up.

cyberfish · 08-01-2012, 03:54 PM

Cool problem is this (at first sight you would say it's -EV).

I've written some Java-prog: it calculates exact EV of a certain strategy up to 24 rounds (no sim, just brute-force calcs).
I guess perfect strategy is:
if (score >= number_of_round + add_on) {play A} else {play B}

Example (24 rounds):
Round 11 - 23: round + add_on=0
Round 3 - 10: round + add_on=1
Round 0 - 2: round + add_on=2

So the more rounds you need the more break-points (>13 rounds/>21 rounds/...) you need to find.

Sry if I missed some things in prev. posts.

edit: 21 rounds should be higher (probably above 24)

**BruceZ** · 08-01-2012, 06:42 PM

Quote:

After 10M iterations, this version scored 59.88%, so the "difference" between choices A and B are not significant for s < t. So what you are saying about choice B being clearly better for the (8, 9), (5, 7) and (3, 5) cases does not seem to be correct. I've bolded the part further down where you seem to contradict yourself.

When you're behind and need an odd number of points, it makes no difference if you play A or B because you will always need to win an A. Otherwise you'd be playing a B when you only need the last point. I was wrong about it making a difference, sorry. But your chart is still wrong, and if you change those to equal, it will agree with the strategy that Sherman and I and now Cyberfish gave, and that Chen verified combinatorially, and that you gave as a rule of thumb. All of your irregularities for odd points remaining will go away because they are all equal. You can easily see that (3,5) must be equal. I didn't contradict myself. I said that you should always play B when behind. It will always be at least as good as playing A.

Quote:

I admit, that in the recursive version of my program, it does generate anomalies in the strategy table. These become more apparent for larger versions of the problem.

The optimal strategy should be straightforward. Always play B when behind. Play B when even if the number of remaining rounds is 14 or greater. I don't know the additional strategy modifications for numbers higher than 14, but if there are modifications, they should simply be a matter of "play B when ahead by P or less when the number of remaining rounds is S or more".

R Gibert · 08-04-2012, 05:06 AM

So what do you think of this strategy table?

Code:

Wins .44577219273765153340

    20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1 turns left

 20 █░ █░ █░ ██ █░ █░ █░ █░ █░ █░ █░ ·· ·· ·· ·· ·· ·· ·· ·· ·· 

 19 ·· ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· ·· ·· ·· ·· 

 18 ·· ░░ █░ █░ ██ ██ ██ █░ █░ █░ █░ █░ ·· ·· ·· ·· ·· ·· ·· ·· 

 17 ·· ·· ░░ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· ·· ·· ·· 

 16 ·· ·· ░░ ░░ █░ █░ ██ ██ ██ ██ █░ █░ █░ ·· ·· ·· ·· ·· ·· ·· 

 15 ·· ·· ·· ░░ ░░ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· ·· ·· 

 14 ·· ·· ·· ░░ ░░ ░░ █░ ██ ██ ██ ██ ██ █░ █░ ·· ·· ·· ·· ·· ·· 

 13 ·· ·· ·· ·· ░░ ░░ ░░ ░█ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· ·· 

 12 ·· ·· ·· ·· ░░ ░░ ░░ ░░ ░█ ██ ██ ██ ██ ██ █░ ·· ·· ·· ·· ·· 

 11 ·· ·· ·· ·· ·· ░█ ░░ ░░ ░░ ░░ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· 

 10 ·· ·· ·· ·· ·· ░█ ░█ ░░ ░░ ░░ ░░ ██ ██ ██ ██ ██ ·· ·· ·· ·· 

  9 ·· ·· ·· ·· ·· ·· ░█ ░█ ░░ ░░ ░░ ░░ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· 

  8 ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░░ ░░ ░░ ░░ ██ ██ ██ ██ ·· ·· ·· 

  7 ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░░ ░░ ░░ ░░ ▓▓ ▓▓ ▓▓ ·· ·· ·· 

  6 ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░░ ░░ ░░ ░░ ██ ██ ██ ·· ·· 

  5 ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░░ ░░ ░░ ▓▓ ▓▓ ·· ·· 

  4 ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░█ ░░ ░░ ░░ ██ ██ ·· 

  3 ·· ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░█ ░░ ░░ ░░ ▓▓ ·· 

  2 ·· ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░█ ░█ ░░ ░░ ░░ ██ 

  1 ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░█ ░█ ░█ ░░ ░░ 

points
needed


	██ Choice B

	█░ Close Decision B > A, ∆ < 1/100

	▓▓ A = B

	░█ Close Decision A > B, ∆ < 1/100

	░░ Choice A

	·· Unknown

R Gibert · 08-05-2012, 03:48 AM

Quote:

Originally Posted by R Gibert

So what do you think of this strategy table?

Code:

Wins .44577219273765153340

    20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1 turns left

 20 █░ █░ █░ ██ █░ █░ █░ █░ █░ █░ █░ ·· ·· ·· ·· ·· ·· ·· ·· ·· 

 19 ·· ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· ·· ·· ·· ·· 

 18 ·· ░░ █░ █░ ██ ██ ██ █░ █░ █░ █░ █░ ·· ·· ·· ·· ·· ·· ·· ·· 

 17 ·· ·· ░░ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· ·· ·· ·· 

 16 ·· ·· ░░ ░░ █░ █░ ██ ██ ██ ██ █░ █░ █░ ·· ·· ·· ·· ·· ·· ·· 

 15 ·· ·· ·· ░░ ░░ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· ·· ·· 

 14 ·· ·· ·· ░░ ░░ ░░ █░ ██ ██ ██ ██ ██ █░ █░ ·· ·· ·· ·· ·· ·· 

 13 ·· ·· ·· ·· ░░ ░░ ░░ ░█ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· ·· 

 12 ·· ·· ·· ·· ░░ ░░ ░░ ░░ ░█ ██ ██ ██ ██ ██ █░ ·· ·· ·· ·· ·· 

 11 ·· ·· ·· ·· ·· ░█ ░░ ░░ ░░ ░░ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· ·· 

 10 ·· ·· ·· ·· ·· ░█ ░█ ░░ ░░ ░░ ░░ ██ ██ ██ ██ ██ ·· ·· ·· ·· 

  9 ·· ·· ·· ·· ·· ·· ░█ ░█ ░░ ░░ ░░ ░░ ▓▓ ▓▓ ▓▓ ▓▓ ·· ·· ·· ·· 

  8 ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░░ ░░ ░░ ░░ ██ ██ ██ ██ ·· ·· ·· 

  7 ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░░ ░░ ░░ ░░ ▓▓ ▓▓ ▓▓ ·· ·· ·· 

  6 ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░░ ░░ ░░ ░░ ██ ██ ██ ·· ·· 

  5 ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░░ ░░ ░░ ▓▓ ▓▓ ·· ·· 

  4 ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░█ ░░ ░░ ░░ ██ ██ ·· 

  3 ·· ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░█ ░░ ░░ ░░ ▓▓ ·· 

  2 ·· ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░█ ░█ ░░ ░░ ░░ ██ 

  1 ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ░█ ░█ ░█ ░█ ░█ ░█ ░█ ░█ ░░ ░░ 

points
needed


	██ Choice B

	█░ Close Decision B > A, ∆ < 1/100

	▓▓ A = B

	░█ Close Decision A > B, ∆ < 1/100

	░░ Choice A

	·· Unknown

This table is derived from a version of my recursive program where all the floating point operations were removed. The calculated value is the exact value without any rounding or truncation. So all the extraneous anomalies are now gone. For example the 100 turn 100 point case gives the exact answer:

Code:

Wins .0731541402524792926292229068689010345115277389324946029743449332063080528170669229894796479561138176

From the program the optimal strategy was derived and appears as follows in my MC version:

Code:

if p <= t - c(p): p -= choice(A)    # choice A
elif even(p): p -= choice(B)        # choice B
else: p -= choice(choice([A, B]))   # choice A or B

The function c(p) is defined as:
c(p) = 4*(p//62) + ((p%62 + 2)>>4)

This was obtained empirically and is verified correct for up to p = 252. It's ugly to look at and it would be nice if it could be simplified.

**David Sklansky** · 08-05-2012, 03:19 PM

This thread shows one reason why smart baseball managers and football coaches can become favorites even if the EV of their scoring output in a particular matchup is slightly less than their opponent.

**David Sklansky** · 08-05-2012, 05:30 PM

Quote:

Originally Posted by BruceZ

Magic. Playing B when you are behind makes the turns non-independent, and it allows you to trade off mean points for positive variance when needed.

But its important to realize that you don't always need the negative EV turns to be non independent. I'll let others elaborate.

**BruceZ** · 08-05-2012, 07:40 PM

Quote:

Originally Posted by David Sklansky

But its important to realize that you don't always need the negative EV turns to be non independent. I'll let others elaborate.

We need non-independence of some of the B rounds to have a positive EV. If our choice depends only on the round, there is no way to have a positive EV because no fixed number of A and B rounds wins over half the time. If we chose randomly between A and B by flipping a biased coin, we will have games with different numbers of A and B rounds, none of which will win over half the time. However, and I think this is your point, we can always play B on some of the rounds without regard to what happens on other rounds and still have a positive EV if we play correctly using non-independence otherwise. We just don't do as well as if we only played B when behind in a 10 round game. We already said that in a game with N or more rounds for N > 13 where we need N points to win, we actually have a higher EV by always playing B on the first round.