Who is most likely to win all the chips?

Question

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?

Answer 1

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):
    masks = numpy.identity(b, dtype=int)
    for c in itertools.combinations_with_replacement(masks, n): 
        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}$.

Answer 2

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.