22
$\begingroup$

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.

$\endgroup$
13
  • 1
    $\begingroup$ Well, the second player can win with probability at least $1/2$, by betting all $10$ marbles in the first round and guessing a uniformly random parity. Also it seems that there is nothing to do with hiding marbles in fist. One may simply say that the bet is won with probability $1/2$, and the strategy is only in choosing the amount to bet. $\endgroup$
    – WhatsUp
    Oct 10, 2021 at 1:41
  • 1
    $\begingroup$ I just finished watching this show last night. I feel sure both the marble game and the bridge game are going to receive plenty of mathematical dissection. $\endgroup$
    – Deepak
    Oct 10, 2021 at 1:46
  • 1
    $\begingroup$ @Deepak thanks for mentioning bridge game as well, which, but I may be wrong, looks easier and would deserve a separate question indeed :-) $\endgroup$ Oct 10, 2021 at 1:50
  • 1
    $\begingroup$ @Deepak, I 100% agree about such aspects like 'deviations' and 'time limit' for both marble and bridge games. And the human aspects. Not only is 'time limit' crucial but also (no spoiler) what comes after exceeding 'time limit'. Strategies depend on such aspects. So let's assume that what comes after exceeding 'time limit' is known by the players and by all people searching to find best strategies. The people who watched the show know it. $\endgroup$ Oct 10, 2021 at 11:29
  • 1
    $\begingroup$ I can perhaps reveal that missing information later but for now some people can already search. Note that, if players are equally smart and equally fast without any limitation, then, with the rules from the series, there is enough time to not exceed limit. So I guess the question of finding best strategies for player 1 and 2 is valid, given this, agreed, pure 'idealized' mathematical (not human, humans are not ideal) interpretation. $\endgroup$ Oct 10, 2021 at 11:30

5 Answers 5

10
+100
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I'm not sure it's the case that 'you can only hide an odd number', though of course that makes no difference in the analysis; it hinges on whether one's allowed to hide zero marbles or not, and I don't know the source material well enough to say one way or the other. $\endgroup$ Oct 11, 2021 at 19:13
  • $\begingroup$ @EspeciallyLime : avoiding having to bet 1 marble is a neat trick ! I try to understand and convince myself that the amount one bets can be any (with the two restrictions you mention) $\endgroup$ Oct 11, 2021 at 19:40
  • $\begingroup$ @EspeciallyLime : also, when it is someones turn to hide even or odd amount of owned marbles, are you saying there is no better strategy possible than to randomly choose 'even or odd' (e.g., by throwing a coin ('head or tail'))? $\endgroup$ Oct 11, 2021 at 20:01
  • $\begingroup$ It's not equal probability. See my answer. I don't understand how your answer is upvoted and mines downvoted, I think the majority of you all would lose the squid game... $\endgroup$
    – Mars
    Oct 11, 2021 at 22:11
  • $\begingroup$ Hi @Mars, what -exactly- (and why) would then be 'best' strategie(s) to start hide (even or odd amount in fist?) for first person in turn, and, amount(s) to start bet (1 to 10) for first person not in turn? Basically (if I understand well) EspeciallyLime claims one can just let a coin toss choose even or odd and one must avoid guessing 9 (starting with both 10). So far for the start of the strategies. FWIW: I am, of course, puzzled as well, otherwise I would not ask, but some concrete figures would help. $\endgroup$ Oct 11, 2021 at 23:28
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ The idea that you know opponent amount of marbles (and if that number is odd or even) has been mentioned, and, you make a point in that knowing so might help guessing, BUT, only if opponent would just randomly choose amount to hide. However, as long as (hiding) opponent has more than one (and even one can and should be avoided) marble, opponent can choose odd or even according to any good or best strategy and/or algorithm. $\endgroup$ Oct 13, 2021 at 21:08
  • $\begingroup$ Thank you for saying this. It's almost identical to what I said in my answer except better exposition. Your computations, make it clear that the probabilities are not equal if you hold an odd number of marbles. $\endgroup$
    – Mars
    Oct 13, 2021 at 21:30
  • 1
    $\begingroup$ @FirstNameLastName I showed what will happen when opponent has odd number of marbles (I assume that you know this information before guess), hides uniformly random amount of marbles and you guess uniformly random odd/even $\endgroup$
    – quester
    Oct 14, 2021 at 6:19
  • $\begingroup$ quester & Mars : If 'hider' uniformly hides random amount of available marbles, then, that offers 'guesser' a good strategy indeed to win indeed !, But then, did 'hider' really choose 'best' hiding strategy? Perhaps uniformly hiding random amount of available marbles is, precisely because of simple, neat counter 'guesser' strategy, not best 'hider' strategy? Perhaps uniformly hiding even or odd amount of marbles is better 'hider' strategy? After all we look for best strategies for both players. ... $\endgroup$ Oct 14, 2021 at 21:07
  • 1
    $\begingroup$ @FirstNameLastName true if 'hider' chooses odd/even with $p=0.5$ then it's best move from hider and probably it's a strategy to achieve Nash equilibrium in this game, because if guesser knows that these probabilities are uneven then choice with higher probability should be an obvious choice $\endgroup$
    – quester
    Oct 15, 2021 at 6:37
3
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Oct 18, 2021 at 15:38
1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Thanks for idea!. I rather also think: expected return +/- for both is related to what 'player whose turn it is not' bets, not to what 'player whose turn it is' holds in its fist. $\endgroup$ Oct 10, 2021 at 21:40
  • $\begingroup$ @FirstNameLastName If you are the first person to guess then choosing evens will have an expected return of $\frac{30-25}{30+25}=\frac{5}{55}$. Think about the $n=1$ game, then choosing odds results in an expected return of $\frac{1-0}{1+0}=1$, and the $n=2$ game choosing evens results in an expected return of $\frac{2-1}{2+1}=\frac{1}{3}$. $\endgroup$
    – Mars
    Oct 10, 2021 at 22:23
  • $\begingroup$ Thanks for reaction. I am not sure about the 1/11 ... So @Mars if you are the first person to guess, exactly how many of the 10 marbles do you want to bet? It does not have to be one single best choice. Are you perhaps saying all even choices are equally best choices? $\endgroup$ Oct 11, 2021 at 0:42
  • $\begingroup$ @FirstNameLastName Oh, I had the game rules different from the show. :/, see edit to answer. $\endgroup$
    – Mars
    Oct 11, 2021 at 2:41
  • 1
    $\begingroup$ The player who hides some marbles does not need to do so randomly like you assume in the 2/3 chance example you give ... as long as one has more than 1 marble and it is ones turn to hide some marbles, one is able and free to hide an odd or an even amount according to some strategy (for example always even). But certain moment, with enough bad luck, one has only one marble left (as also happens with one couple in the series). $\endgroup$ Oct 11, 2021 at 18:34
0
$\begingroup$

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

$\endgroup$

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.