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

Solution 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.

Solution 2:

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 :)

Solution 3:

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.

Solution 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.