5
$\begingroup$

Which is the best strategy for this game? Actually is a Nintendo Wii game.

It's a 4 people game.

There is a ladder of 10 steps.

Each player says a number (they can chose between those numbers "1","3","5").

If their number is unique (if he's the only one who said that number in that round), the player may advance of a number of steps equivalent of the number. If there's more than one player who said the same number they cannot advance.

E.G. Player A says "5" Player B says "1" Player C says "3" Player D says "3" Player A advances 5 steps, player B advances 1 step. The remaining 2 cannot advance.

The one who reach the top of the ladder wins.

Usually I chose to say always "5", but I'd like to know what's your point of view on this.

$\endgroup$
4
  • $\begingroup$ There is no winning pure strategy - if everyone plays the same, noone moves. And I'm not sure if there's a single dominating probabilistic strategy. Anyone willing to do the maths? $\endgroup$ Oct 23 '14 at 13:49
  • $\begingroup$ The strategy to always choose 5 sounds good if other players choose uniformly randomly (which is a bad strategy if yours clearly outperforms it). At each step you have a 8/27 ~ 1/3 chance of moving forwards, and you only need to move twice. An opponent that calls either 1 or 3 has a 4/9 ~ 1/2 chance of being uncontested, but they have to succeed 4 resp. 10 times. BUT if two different players choose that, one of the other two is sure to win. $\endgroup$ Oct 23 '14 at 13:57
  • $\begingroup$ The possibility of collusion makes this a very difficult problem. Optimally, you would team up with someone else and agree to choose different numbers. Maybe you are thinking "there is no collusion", but that is somewhat meaningless. Even bad play can be a form of unintentional collusion. Solving this game with 2 players is feasible though. But 4 makes things hard to define. $\endgroup$
    – DanielV
    Oct 23 '14 at 14:52
  • $\begingroup$ To give you an example of what I meant, imagine 3 players show up to a poker table with the exact same value in starting chips. One player plays perfectly, two of them play extremely loosely, both go all in on the first hand. On the second hand, it becomes heads up with one player having 2 times the chips. The "bad" players unintentionally colluded and got an advantage. That is why it is hard to define optimal play for more than 2 players. $\endgroup$
    – DanielV
    Oct 23 '14 at 15:46
3
$\begingroup$

Well, I think this is some kind of prisoner's dilemma. The best strategy always depends on whom you are playing with. How many of the players can you control? Is it only humans, or also AIs? How experienced are your opponents?

Having said that.

Case 1, random opponents Assume your opponents are playing randomly. For any numbers $i,j\in{1,3,5}$ we then have the probability of none of them choosing the number $p_i=p_j$. ($p=(\frac{2}{3})^3$ by the way, but that's actually not important) So you are right always chosing $5$ would be the best choice, assuming the opponents play randomly. This should also work with real human beings, I believe for psychological reasons. People will not stick to the highest number if they don't know the game, or know someone will surely pick it, and can not agree on a joint strategy against you.

Case 1.u, you and your random opponents The chance of your opponents playing strictly randomly and you always playing $5$ and winning after at most three moves is given as $\frac{8^2}{20^2}+2\frac{12}{20}\frac{8^2}{20^2}=0.352$. Meaning that in more than every third game you'd win, so you necessarily do have a serious advantage over the others :-) Your chance of winning actually is severely higher, but for now we are just looking for comparison of strategies.

Case 2, deterministic strategies for all players Now let's lift it one level. We don't require the opponents to play randomly anymore. Assume there is an optimal strategy, and thus obviously assume that all the players are aware of the optimal strategy and thus try to play this optimal strategy. We assume a determined and fair game, i.e. players make their choice at exactly the same time, have exactly the same interface and make their choice without any randomness. But then all four players will always play exactly the same number and thus nobody will ever move forward and thus the game will never end.

Case 3, everybody playing random Can the optimal strategy involve some randomness? Assume it to be purely random. Then your probability of winning is exactly $\frac{1}{4}$ which I guess is as good as it gets assuming everybody is aware of the "optimal strategy". However, as pointed out in Case 1.u everybody playing random is not optimal in terms of best strategy as it can be beaten by the always $5$ guy.

Case 4, adjusting randomness, what needs to be done An optimal strategy will involve randomness, and has to incorporate a high possibility of choosing $5$, and not so high but non-zero possibilities of choosing $1$ and $3$. Should we prefer $3$ over $1$? Yes, for the same reason we have to prefer $5$ over the others. On the one hand we need to move fast, on the other hand we don't want our opponents to move too fast. For the first move at least we will thus have probabilities $p_1<p_3<p_5$. But it gets trickier. In the progress of the game we will have to adjust the probabilities of choosing the numbers. For instance if one player achieves step $9$ then he won't prefer big numbers over smaller numbers for himself anymore, which means that the other players can't rely on him having a low probability for $1$ anymore. So...

Conclusion 1; Case 5, machine learning Feed some computer program with the question. Use as parameters the distances of every players position to $10$ and use some form of machine learning to come up with suitable probabilities. You don't want exact numbers anyway ;-)

Conclusion 2: answer the question "who are the opponents?" and then design a fitting strategy. That's probably more practical solution What's the chance of your opponents actually having implemented the machine learning approach?

$\endgroup$
2
  • $\begingroup$ "the optimal strategy involves some randomness." - as I said in the comments. But what's the optimal set of probabilities, if there is any? $\endgroup$ Oct 23 '14 at 14:10
  • $\begingroup$ @JanDvorak I think I see your point. We want some strategy to outperform all the other strategies... $\endgroup$ Oct 23 '14 at 14:20
2
$\begingroup$

The situation is symmetric in the players (at least in the beginning or when they all are at the same step of the ladder), so if there is any best strategy, we may assume that all players implement it and pick $1,3,5$ with probabilities $p_1,p_3,p_5$, respectively, where $p_1+p_3+p_5=1$.

The following can happen:

  • All pick the same number and no one advances (happens with $p_1^3+p_3^3+p_5^3$)
  • Three pick the same and one advances by five (happens with $3(p_1^2+p_3^2)p_5$)
  • Three pick the same and one advances by three (happens with $3(p_1^2+p_5^2)p_3$)
  • Three pick the same and one advances by one (happens with $3(p_3^2+p_5^2)p_1$)
  • Two pick "1" and the others advance by "3" and "5" (happens with $12p_1^2p_3p_5$)
  • Two pick "3" and the others advance by "1" and "5" (happens with $12p_3^2p_1p_5$)
  • Two pick "5" and the others advance by "1" and "3" (happens with $12p_5^2p_1p_3$)

The expected total progress is then $$ \tag115(p_1^2+p_3^2)p_5+9(p_1^2+p_5^2)p_3+3(p_3^2+p_5^2)p_1+96p_1^2p_3p_5+72p_3^2p_1p_5+48p_5^2p_1p_3$$ and by symmetry the indivdual expected progress is $\frac13$ of this. You may want to determine the maximum of exporssion (1) subject to the constraints $p_1+p_3+p_5=1$, $p_1,p_3,p_5\ge0$.

$\endgroup$
1
  • 2
    $\begingroup$ "All on the same step" should really be emphasized, especially since it is a rare occurrence. As well as not being to step 7 yet, because then the difference between $3$ and $5$ disappears completely. $\endgroup$
    – DanielV
    Oct 23 '14 at 15:21

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.