# Who is most likely to win all the chips?

Alice, Bob and Charlie each have 5 chips. Starting from Alice, they take turns to act in the order of Alice, Bob and Charlie. The $$n$$-th person to act must take a total of $$n$$ chips from their opponents. That is, they act like the following:

1. Alice takes one chip from Bob or Charlie
2. Bob takes a total of two chips from Alice and Charlie (It's OK to take two from just one person)
3. Charlie takes a total of three chips from Alice and Bob
4. Alice takes a total of four chips from Bob and Charlie

$$\quad\quad\quad\vdots$$

If a player has no chips, they lose and immediately quit the game. Players are all rational and act to maximize their own winning probability. They will randomize between equally optimal choices.

Question: Who is most likely to win all the chips?

• What happens if n > chips not owned by the nth player to act? Do they just take all remaining chips and win, or does something else happen in this case? Or is that case not even possible? Jun 10, 2022 at 15:54
• @StephenTG That's not possible.
– Eric
Jun 10, 2022 at 15:59
• Never mind, that case can't happen. Player n-1 (who was in the game, and thus had at least one chip) just took n-1 chips, and therefore has at least n for player n to take Jun 10, 2022 at 15:59
• Suggesting brute force attack. There is a lower and upper limit of steps to finish the game (between 11 an 20).
– z100
Jun 10, 2022 at 17:33
• @z100 Not sure where you get an upper bound of 20 from. There are only 15 chips in total, so the 14th turn must end the game if it gets that far.
– fljx
Jun 10, 2022 at 17:50

I would love to be able to add this as a comment as this answer isn't really in the spirt of puzzles but I lack the reputation.

I wrote some python code to brute force solving the problem.

From this I found,

If we let $$N$$ be the starting number of chips for each player.
For $$N=1,2,3$$ Bob and Charlie will each win with probability $$\frac{1}{2}$$
For $$N=4$$ Bob and Charlie win with probability $$\frac{7}{16}$$ and $$\frac{9}{16}$$ respectively.
For $$N=5$$ Bob and Charlie win with probability $$\frac{9}{20}$$ and $$\frac{11}{20}$$ respectively.
These results are weird enough that I used an exact fraction module to check it wasn't a floating point error. Of course it could just be that I wrote bad code (this is somewhat likely) but if not then I don't know why this happens.

Just to make this a proper answer

Charlie is most likely to win.

Update: Here is the code I used.

import numpy,itertools,fractions

def partitions(n, b):
yield sum(c)

def Probs(S,a,k):
if k>n*N:
print('panic')
if len(S)==1:
return [fractions.Fraction(1)]
Best=[]
Max=0
for U in partitions(k, len(S)-1):
V=list(U)
V.insert(a,-k)
R=[a_i - b_i for a_i, b_i in zip(S, V)]
if any(t < 0 for t in R):
continue
L=[i for i in R if i != 0]
b=a+1
b-=R[:a].count(0)
if b==len(L):
b=0
vals=Probs(L,b,k+1)

newvals=[]
t=0
for i in R:
if i==0:
newvals.append(fractions.Fraction())
else:
newvals.append(vals[t])
t+=1

if newvals[a]>Max:
Max=newvals[a]
Best=[newvals]
elif newvals[a]==Max:
Best.append(newvals)

P=[sum(i)/len(Best) for i in zip(*Best)]

return P

N=5

n=3

I=[N for x in range(0,n)]

print(Probs(I,0,1))


Update 2:

Here is my initial understanding of why this is happening. The analysis given by @SQLnoob is correct in determining that on that branch Alice will choose randomly, however it makes the mistake of assuming that Alice cares about their actions earlier in the game. Under the assumption that Alice can never win (among the traversed paths) all of Alice's choices are uniformly random as they are all equally good. This means that it is possible that some earlier paths get chosen which are not equal for Bob and Charlie. This is why there is a discrepancy. Presumably most paths are equal for Bob and Charlie, which is why the probabilities are so close to $$\frac{1}{2}$$.

• Brute force is a perfectly valid approach for puzzles IMO. Sometimes it’s the best / only way to make progress. Can you share the code you used? Jun 11, 2022 at 11:46
• @SQLnoob Yes brute force is fine as a tool to get ideas, but I feel a good solution should explain why something is true. Maybe that is just my bias as a mathematician though. I'll add the code to my answer, however it is really bad and isn't commented. Jun 11, 2022 at 11:49
• I wrote my own program for the N=5 case. I get the same values as Fishbane. Jun 11, 2022 at 14:29
• “ Under the assumption that Alice can never win (among the traversed paths) all of Alice's choices are uniformly random as they are all equally good.” Ah, yes, that makes sense, I was wondering why your answer differed from mine but that explains it perfectly, well done! Jun 11, 2022 at 18:36

Some observations:

The game can't possibly last more than 14 turns, since on the 14th turn the active player must have at least 1 chip and can therefore take the rest of them. Of course, once the game is down to two players, it's a deterministic race to 15, so basically the game boils down to when the first player is eliminated.

Starting from turn 4, a player can force a win if they begin turn $$N$$ with $$8 - \lceil(N/2)\rceil$$ chips. This is because they can eliminate one of their opponents, and they will win the race to 15 against the other opponent. If they start the turn with fewer than that amount of chips, then they should avoid eliminating an opponent and instead attempt to take enough from the other players to ensure that neither of them can force a win in the next two turns.

Given that general strategy,

I suspect that Alice cannot win, and that Bob and Charlie will each win with probability 0.5, depending on Alice's choice.

This is because no one will willingly let another player have a forced win, and so the game will stretch on as long as possible, which is all the way until turn 13. At that point it will be Alice's turn, and since she will have to take 13 chips, she will need to eliminate one of the other players at this point. However, this will leave her with 14 chips, and the next player will take all 14 of them for the win on the very next turn.

So my guess is that the winner is whoever Alice decides to leave in the game on turn 13.

• Just a general comment about the game, not about your answer, if this is correct, then I feel it's quite funny to see that the game is basically Alice choosing the winner of the game 😀 Jun 11, 2022 at 3:27