12
$\begingroup$

Alice and Bob are playing a betting game. Each has 20 chips to start with. They move alternatively starting with Alice. In their moves, they name a number $n$ and toss a fair coin: if head, they get $n$ more chips from the casino; if tail, they give $n$ chips to the opponent, where $1\leq n \leq$ total # of chips owned by the current player. A player wins if they reach 100 chips first, or if the opponent loses all their chips.

Question: How should Alice and Bob bet? Who has a higher winning probability?

$\endgroup$
2
  • 4
    $\begingroup$ Interesting question. It seems in the beginning one should bet as little as possible, since the other person's turn is basically a risk-free gamble for you. Every bet size has an expected value of 0 for the bettor, but a value of n/2 for the opponent, so smaller bets help your opponent less. That said, things will get more complicated as the game proceeds - if the tally is 99 to 50, Bob may be justified in placing a win-or-bust best of 50 chips, since by betting 1 chip at a time, he's very unlikely to catch up before Alice wins . $\endgroup$ Jul 2 at 15:11
  • $\begingroup$ i think Bob is better off going for n=1 in each bet. For Alice, she has no choice but to take the gamble of going for the max n she can, for first turn she should go for n=20 $\endgroup$ Jul 3 at 10:23
6
$\begingroup$

Nuclear Hoagie's remark is a good start.

I evaluated the best strategy with a computer and here is what came out:

enter image description here

enter image description here

The images show the best bet for Alice for each chip count. Alice's chip count is on the x-axis, Bob's chip count is on the y-axis, from 0 to 99. The origin is at the bottom left. The color indicates the best bet: red=1, yellow=25, green=50, cyan=75, blue=99.

Sometimes multiple bets are equivalent. The first images shows the smallest bet that is optimal. The second image shows the largest bet that is optimal.

As Nuclear Hoagie saw, as soon as Alice has 50 chips and is behind Bob, she should bet it all for a 50% chance of winning. That is the blue part on the 2nd picture. Note that it is enough to bet just enough chips to reach 100.

If Alice and Bob have 50 chips but Alice is leading, she knows Bob will bet it all on the next move. So she should try to take a chance at winning the game first by aiming for 100.

In short, if both player have >= 50 chips, an optimal strategy for Alice is to bet just enough to reach 100.

On the picture you see that in the lower left the optimal bet is 1. This is because on average a bet wins nothing for the player but half the bet for the opponent. It is better to minimize it.

OK, near the right and top borders it becomes messy. I won't bother explaining what happens there. I don't know in fact.
But considering that players start by betting 1 on each move, they will inch forward pretty much along the diagonal and have little chance to reach the messy parts.

So a good approximation for the optimal strategy is:
- If one player has <50 chips then bet 1.
- else bet just enough to reach 100.

There is a small exception for the case where Alice has >50 and Bob has 49. If Alice plays 1, Bob might reach 50 and might go for all-or-nothing. That is why in this case it might be better to play everything. It seems to be the case only if Alice has 60 chips or more. Below 60 it seems that it is interesting to bet just enough so that when Alice looses, her chip count goes below 50 and Bob won't play it all.

And here is the winning probability map for Alice. Red is a 0% win, green is 50%, blue is a 100% win.

enter image description here

$\endgroup$
11
  • $\begingroup$ First 2 images, how can Alice bet 50 at the green spikes at the top? Alice doesn't have 50 chips at the tip of the spikes. $\endgroup$
    – Eric
    Jul 3 at 12:27
  • 1
    $\begingroup$ The program I wrote? For every position it checks all legal moves for Alice, computes the probability to win and chooses the best one for Alice. The probability to win averages the probability for Bob to loose for the 2 outcomes. The probability for Bob to win when it is his turn is the same as for Alice. The formula is circular so it involves Markov chains. $\endgroup$
    – Florian F
    Jul 4 at 14:04
  • 1
    $\begingroup$ Can you post the script? I really want to take a look. $\endgroup$
    – Eric
    Jul 4 at 16:19
  • 1
    $\begingroup$ Here is is, valid 24 h. codeshare.io/bvvRKV $\endgroup$
    – Florian F
    Jul 4 at 18:24
  • 1
    $\begingroup$ As I said the calculations are circular. I did not resolve it the proper way by inverting a matrix. I just repeat the calculations (nbRounds times) until it converges. (btw pas = Probability for Alice, s for plural). $\endgroup$
    – Florian F
    Jul 5 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.