best strategies for 'Squid Game' episode 6 game 4 "marble game" players

Question

Two players each get $n=10$ marbles. Every alternating turn, one player (say, the player whose turn it is) hides an amount of own marbles in fist, and, the other player must guess if hidden amount is odd or even, and, that other player (i.e., the player whose turn it is not) also must bet an amount of own marbles. If guess is right, the player whose turn it is gives (as much as possible) the amount of bet marbles to opponent. If guess is wrong, the player whose turn it is takes the amount of bet marbles from opponent. Next, the turn now alternates to the other player. The game stops when one player has all $2n=20$ marbles.

The losing player gets killed (in the series, that is).

Which strategies for both players (perhaps one strategy for the one who gets first turn, and one strategy for the other player) give maximal probabilities to win (and to not get killed).

We must assume both players know the starting conditions and are perfect mathematicians and logicians.

On a side note: is this an old or new game? If it is a known old game, can anyone tell where its 'official' rules (and, maybe, solution(s)) are documented?

remark

(series details coming so warning: spoiler ahead)

There is a YT video where rules are explained to be: if guesser guesses wrong, guesser must give amount 'h' that was hidden by hider, not amount 'b' bet by guesser.

https://www.youtube.com/watch?v=GX4AkD_vdhw

The video also gives the simple solution for that variant.

And presenter also mentions rules are not clear, but, most people, he says, believe 'h'. Some comments claim otherwise.

Fair enough.

From examples in series it is not entirely clear to me either what the rule is.

There is only one example where guesser guesses wrong.

In that example, guesser bets b=2, and hider hides h=3, and guesser guesses odd. One can see the guesser give 2 (amount b bet), and, next it is shown guesser has only one more left. The guesser stops playing. If the rule were to give 3 (amount h hidden), guesser would immediately loose, and if the guards were paying attention, guesser would have been killed. If the rule were to give 2 (amount b bet) then guesser, upon becoming hider, would also loose. But, current guesser is a cheater so, in both cases (having to give b=2 or h=3), it fits him to hold that last marble.

Note that the cheater is portrayed to be clever and his opponent to be dumb. And the opponent did not know the game.

However, if rule were to have to give h(=3), then guesser would cheat hard in not holding on to the rules, and, be lucky to still be alive. After all, the outcome of each games in the series is said to be fatal, but fair. But, if rule were to have to give b(=2), then guesser would still cheat hard by stopping the game, and, even manipulating opponents marbles. A moderately clever guard paying attention would notice game was not played fair, and, a somewhat more clever guard paying attention would even know guesser lost in any case.

Answer 1

Essentially, this is like one player choosing "odd" or "even" freely, and the other player trying to guess. That game is straightforward: both players should choose "odd" and "even" with equal probability, and then it becomes a martingale so the amount you choose to bet is irrelevant: you win with probability $1/2$.

Your game has an added complication: if it is your turn to hide marbles, and you only have one left, you can only hide an odd number and you lose.

However, all this means is that no-one will ever bet $k-1$ marbles if they have $k$ left: it would be a better strategy to bet all $k$, since this is better if you guess right, and no worse if you guess wrong (you certainly lose either way). Note that it is not possible for your opponent to have exactly $k-1$ marbles if you have $k$, on parity grounds. However, since we've established that no-one would ever bet $k-1$ marbles when they have $k$, it follows that no-one will ever have exactly one marble left at their turn to hide, so the game becomes a martingale again.

tl;dr the best strategy is "always pick even/odd with equal probability, and if you have $k$ bet any number of marbles you like as long as 1) you don't bet more marbles than your opponent has left, and 2) you don't bet exactly $k-1$". Then each player has equal probability of winning.

Answer 2

This game is an example of a recursive game, whose properties were first studied by Hugh Everett in a paper of $1958$, titled Recursive games. A more modern ($2011$) exposition of recursive games, along with the closely related concept of stochastic games of Lloyd Shapley and Dean Gillette, is given in this paper (which I have not read).

This game has $38$ of what Everett called "game elements", which are just the different situations the players can find themselves in throughout the game. Calling the two players Alf and Beth, the game elements can be conveniently labelled $\ A_1, A_2, \dots, A_{19}\ $ and $\ B_1, B_2, \dots, B_{19}\ $. The subscript of each game element is the number of marbles that Alf currently holds (so $20$ minus that number will be the number of marbles that Beth then holds). In game elements $\ A_i\ $, Alf is the better and guesser, while Beth is the hider, whereas in $\ B_i\ $ it is the other way round. For notational convenience I'll add four more game elements $\ A_0, A_{20}, B_0\ $ and $\ B_{20}\ $, representing the various won and lost situations as follows: \begin{align} A_0&:\hspace{0.5em}\text{Alf lost because Beth bet as many marbles as he had and}\\ &\hspace{1.5em}\text{guessed right.}\\ A_{20}&:\hspace{0.5em}\text{Alf won because Beth bet all her marbles and guessed}\\ &\hspace{1.5em}\text{wrong.}\\ B_0&:\hspace{0.5em}\text{Alf lost because he bet all his marbles and guessed}\\ &\hspace{1.5em}\text{wrong.}\\ B_{20}&:\hspace{0.5em}\text{Alf won because he bet as many marbles as Beth had and}\\ &\hspace{1.5em}\text{guessed right.} \end{align}

In $\ A_i\ (i\ne0,20)\ $, Alf has $\ 2i\ $ (pure) strategies $\ (g, b)\in\{\text{odd},\text{even}\}\,\times$$\{1,2,\dots,i\}\ $. If $\ i\ne19\ $, Beth has just two pure strategies, $\ h\in$$\{\text{odd},\text{even}\}\ $, while in $\ A_{19}\ $ she has no choice but to take $\ h=\text{odd}\ $. In $\ B_i\ $, the player's roles are reversed, Beth has $\ 2(20-i)\ $ pure strategies $\ (g, b)\in$$\{\text{odd},\text{even}\}\,\times$$\{1,2,\dots,20-i\}\ $, and it is in $\ B_1\ $ where Alf has no choice but to take $\ h=\text{odd}\ $. In theory, the players could make their choices of strategies depend on all the past history of the game, but one of the results of Everett's investigation is that the players don't have to do that to play optimally.

If Alf chooses the strategy $\ (g,b)\ $ in $\ A_i\ (i\ne0,20)\ $, and Beth chooses the strategy $\ h\ $, then the outcome is a new game element $\ B_{\min(i+b,20)}\ $ when $\ g=h\ $, or $\ B_{i-b}\ $ when $\ g\ne h\ $. Likewise, If Beth chooses the strategy $\ (g,b)\ $ in $\ B_i\ (i\ne0,20)\ $, and Alf chooses the strategy $\ h\ $, then the outcome is a new game element $\ A_{\max(i-b,0)}\ $ when $\ g=h\ $, or $\ A_{i+b}\ $ when $\ g\ne h\ $. The game starts in either the game element $\ A_{10}\ $ or $\ B_{10}\ $, and terminates whenever the outcome of a game element is either $\ A_0\ $ or $\ B_0\ $, when Beth wins and receives payoff $\ {+}1\ $, and Alf loses and receives payoff $\ {-}1\ $, or $\ A_{20}\ $ or $\ B_{20}\ $, in which case Alf wins and receives payoff $\ {+}1\ $, and Beth loses and receives payoff $\ {-}1\ $.

It's possible for the players to choose strategies for which the game will never terminate. This will occur, for instance, if the game starts in $\ A_{10}\ $, Alf always chooses strategy $\ (\text{odd},1)\ $ in that game element, and the strategy odd in $\ B_{11}\ $, and Beth always chooses the strategy even in $\ A_{10}\ $ and strategy $\ (\text{even},1)\ $ in $\ B_{11}\ $. If the game never terminates, then both players receive payoff $\ 0$.

Because there are only a finite number of strategies in each game element, another of Everett's results guarantees that there exist optimal stationary mixed strategies for both players. "Stationary" here means that the strategy chosen in each game element is independent of the past history of the game.

Finally, a third result of Everett's tells us that if $$ v:\big\{A_0,A_1,\dots,A_{20},B_0,B_1,\dots,B_{20}\big\}\rightarrow\mathbb{R} $$ is a function such that \begin{align} v\big(A_0\big)&=v\big(B_0\big)=v\big(B_1\big)=-1\ ,\\ v\big(A_{20}\big)&=v\big(B_{20}\big)=v\big(A_{19}\big)=1\ ,\\ \end{align} for each $\ i\in\{1,2,\dots,18\}\ ,\ v(A_i) $ is the value of the matrix game with payoff matrix $$ \pmatrix{v\big(B_{i-1}\big)&v\big(B_{i+1}\big)\\ v\big(B_{i-2}\big)&v\big(B_{i+2}\big)\\ \vdots&\vdots\\ v\big(B_0\big)&v\big(B_{\min(20,2i)}\big)\\ v\big(B_{i+1}\big)&v\big(B_{i-1}\big)\\ v\big(B_{i+2}\big)&v\big(B_{i-2}\big)\\ \vdots&\vdots\\ v\big(B_{\min(20,2i)}\big)&v\big(B_0\big)}\ , $$ and for each $\ i\in\{2,\dots,19\}\ ,\ v\big(B_i\big)\ $ is the value of the matrix game with payoff matrix $$ \pmatrix{v\big(A_{i+1}\big)&v\big(A_{i+2}\big)&\dots&v\big(A_{20}\big)&v\big(A_{i-1}\big)&v\big(A_{i-2}\big)&\dots&v\big(A_{\max(0,20-2i)}\big)\\ v\big(A_{i-1}\big)&v\big(A_{i-2}\big)&\dots&v\big(A_{\max(0,20-2i)}\big)&v\big(A_{i+1}\big)&v\big(A_{i+2}\big)&\dots&v\big(A_{20}\big) }\ , $$ then the optimal strategies in the game elements $\ A_i\ $ and $\ B_i\ $, respectively, are to choose the optimal (mixed) strategies in the above matrix games. Alf's optimal strategy in $\ A_{19}\ $, and Beth's optimal strategy in $\ B_1\ $, is $\ (\text{odd},1)\ $.

In fact, $$ v(A_i)=\cases{\frac{i}{10}-1&for $\ i\ne19 $\\ 1&for $\ i=19 $}\\ v(B_i)=\cases{\frac{i}{10}-1&for $\ i\ne1 $\\ -1&for $\ i=1 $}\\ $$ is the (unique) function that satisfies these conditions, and solving the matrix games above when this function is used confirms that the strategies given in Especially Lime's answer are optimal.

If $\ i\ne1,19\ $, then the probability that Alf will win from game element $\ A_i\ $ or $\ B_i\ $ is $\ \frac{i}{20}\ $ and the probability that Beth will win is $\ 1-\frac{i}{20}\ $. The probability is $1$ that Beth will win from game element $\ B_1\ $ and that Alf will win from game element $\ A_{19}\ $.

Update: I mentioned in a comment below that I originally excluded strategies where a player bets more marbles than his or her opponents holds, because such a strategy is non-optimal and I thought including them would unnecessarily complicate the notation. I have since realised that these strategies can be included without overly complicating the notation, and a few days ago I modified the answer to allow them as possibile choices for the players.

Also, the original payoff matrices only included half the better-guesser's strategies, given by the size of the bet. I've now modified them to include all the better-guesser's strategies. The $\ k^\text{th}\ $ row of the payoff matrix for $\ A_i\ $ represents Alf's strategy of betting $\ k\ $ marbles and guessing odd if $\ k\le i\ $, or the strategy of betting $\ k-i\ $ marbles and guessing even if $\ k>i\ $. The $\ k^\text{th}\ $ column of the payoff matrix for $\ B_i\ $ similarly represents the same strategies for Beth.

Answer 3

it's not an answer but significant remark:

let's conciser case when you are guessing opponents odd/even amount of marbles hidden and opponent has odd number of marbles overall then P(your correct guess when opponent has odd number of marbles) > 0.5 $$P(correct) = \frac{\#(odd,odd) + \#(even,even)}{\#allpairs}$$

code [(i, i+1, ((i**2 + (i+1)**2)/(2*i+1)**2)) for i in range(1, 10)]

output [(1, 2, 0.5555555555555556), (2, 3, 0.52), (3, 4, 0.5102040816326531), (4, 5, 0.5061728395061729), (5, 6, 0.5041322314049587), (6, 7, 0.5029585798816568), (7, 8, 0.5022222222222222), (8, 9, 0.5017301038062284), (9, 10, 0.5013850415512465)]

so probably you want to bet odd number of marbles when you have odd number and even when you have even number of marbles, to have in next move even number of marbles so opponent will have probability of correct guess equal to $0.5$ not higher

probably you can't have winning strategy at this point so just play all in on first bet :)

Answer 4

EDIT: This strategy is for a slightly different marbles game, where only one player wagers marbles, and the other player guesses the parity of the wager.

The thing to notice is that the sum of odds 1+3+5+7+9=25 where as the sum of evens is 2+4+6+8+10=30, so that guessing evens in the beginning has a higher expected return of $\frac{5}{55}$. So in general if your opponent has an even number of marbles in total you should guess even. If your opponent has an odd number of marbles in total, then you should guess odd to get a positive expected return.

The other thing to notice is if you are in the lead, then you should wager smaller amounts, since that way the standard deviations are smaller, and you stay in the lead. On the other side of the strategy if you are behind, then wagering more so you can get into the lead.

Once in the lead it's likely you will win, if you play conservatively. For instance you should never bet more marbles than you opponent can pay.

Of course if you opponent knows your strategy then will win. so a mixed strategy with a favor towards the method described above will be winning.

As some thoughts of variations of the game, if $n=1$ then the game is determined and the first guesser wins. If $n$ is small the first guesser is more likely to win, as $n$ gets larger the game becomes more fair. The game where you guess mod $k$ instead of even and odd has an identical strategy.

EDIT: I thought the game rules were that one player holds marbles and the other player guesses how many marbles the player is holding. If incorrect they lose that many marbles to the other player. If correct they win that many marbles from the other player. The Squid game rules are that both players hold different amounts of marbles.

For the Squid game-marbles game the thing to realizes when you are guessing is that (assuming you can not hold zero marbles) sometimes your opponent has more odd numbers to hold than even numbers to hold, for example if you have 3 marbles in total, you can hold 2 or 1 or 3, so two odd options and one even option. In this case you should guess odd since you have a $\frac{2}{3}$ chance of being correct assuming uniform randomness. However if you have a total of 2 marble, then you have equal number of even options as odd options, namely 1 or 2.

Next how much do you wager? you want to wager an amount so that if you win/lose then you have an even number of total marbles, so that your opponent can not exploit the above guessing strategy above. For example if your opponent has 16 marbles then you want to wager 2 or 4 marbles so that you have an even number 0,2,4,6,8 total marbles for the next round of guessing.

The comments about mixed strategy always apply to random games where both players are perfect mathematicians. See Von Nuemanns solution to poker.

As for extensions of the game, the first guesser has an advantage that lessens with larger total number of marbles in the game. Interestingly if you switch the guessing to $mod 3$ then choosing how much to wager becomes more challenging.

Answer 5

This 'answer' is not an answer but rather confirms 'lonza leggiera' and 'Especially Lime' splendid answers, and, I hereby bring barely anything new.

Assume odd/even is chosen randomly by 'hider' (e.g. by tossing a perfect coin) with probabilities 1/2 (which is possible, as pointed out by 'Especially Lime' by never betting k-1 marbles (when 'guesser' has amount k marbles), and is sub-optimal strategy anyway). Then n=1 is impossible to play and n=2 is trivial.

Assume 'guesser' guesses randomly with probabilities 1/2 as well, resulting in a fifty-fifty chance to guess right or wrong (see '(*) note:' below).

So I tried n=3 (and n=4) on paper. It is a not a hard exercise. Let, for given n, p(k) be the probability to win when 'guesser' has k marbles and plays best strategy. Then what is p(n)?

I tried 3 strategies:

(s1) bet random amount from {1, ... , k-2, k} with equal probability

(s2) always bet 1

(s3) always bet maximum

(but never bet more than opponent has)

In each case p(k) is a particular sum involving some (1 - p(l)), dependent on strategy, and, as there are only a finite amount of states, this results (via recursion, since p(k) depends on other p(l) and potentially on itself) in a set of 2*n-2 linear equations for the unknown p(k) to solve.

For all strategies (s1) (s2) (s3), one finds payoff p(n)=1/2 (I used online linear equation solver to not make (as I always do) mistakes).

So all this confirms (and both follows) 'lonza leggiera' and 'Especially Lime' result(s) and reasoning(s).

It still would be nice of one could write (or provide a reference to) a self contained proof that does not depend on too much theory.

Finding and writing the linear equations to solve the unknown p(k) is possible (a bit tedious but straightforward) for any chosen strategy (I mean 'guesser' strategy for 'betting' certain allowed amounts). Solving the equations is standard mathematics which can be done by computer.

But then: proving such equations always give p(n)=1/2 for any choice (and any n) is more challenging.

In any case, 'Especially Lime' "best strategy" is also a 'Nash equilibrium', where players have nothing to gain by changing only their own strategy.

As for 'lonza leggiera' payoff formula p(k) for probability to win when being 'guesser' and having k marbles:

 p(k) = k / (2*n) for k <> n-1
      = 1         for k == n-1

(giving p(n) = 1/2), perhaps there is a way to prove this directly by induction or by other method.

(*) note: so this all assumes odd/even 'hiding' and 'guessing' strategy with equal probability 1/2 is used. Such strategy itself is a best 'matching pennies' so called 'mixed strategy' 'Nash equilibrium'.