"Get the Last Token."

I am sure by now most of you have seen some version of the game where you try to be the one to take the last pearl/chip/token, or else force the other person to do the same.

I haven't analyzed it fully, but I was pondering the same sort of game only with three people taking turns. I have a suspicion how that will turn out but let me present to you the game set-up.

21 tokens of some sort are placed on the table in the center. Each player in turn can take either 1, 2, or 3 tokens at a time. You are given the option to pick whether you want to go first, second, or third, and you'll always take your turn in that order. (A, B, C, A, B, C, A, B, C...)

If there is no collusion between the other two, is there a way to guarantee a win, and if so how? If not, is there any way to maximize your chances? What if the object is to avoid taking the last token?

In your analysis, assume a player will make a winning move if given the chance, and if no definitively winning move is available will randomly pick 1, 2, or 3 tokens.

Originally posted by geepamoogle
I am sure by now most of you have seen some version of the game where you try to be the one to take the last pearl/chip/token, or else force the other person to do the same.

I haven't analyzed it fully, but I was pondering the same sort of game only with three people taking turns. I have a suspicion how that will turn out but let me present to you the ...[text shortened]... chance, and if no definitively winning move is available will randomly pick 1, 2, or 3 tokens.

only one person gets to choose his position, the last person to choose has no choice.

--Y 1 2

1 1 0 0
2 1 0 0
3 1 0 0
4 0 0 1
5 0 1/3 2/3
6 1/3 5/9 1/3
7 5/9 2/3 1/9
8 2/3 10/27 8/27
9 2/3 20/81 14/27
10 2/3 25/81 17/27
11 10/27 13/27 2/3
12 13/27 49/81 46/81
13 49/81 151/243 41/81
14 151/243 47/81 118/243
15 151/243 439/729 415/729
16 151/243 1138/3^7 449/729
17 439/729 406/729 151/243
18 439/729 439/729 1345/3^7
19 439/729 4051/3^8 1331/3^7
20 4051/3^8 1345/3^7 439/729
21 4051/3^8 1331/3^7 11953/3^9

Again, I resort to the old chart-making technique. The numbers represent the probability that you (Y) will win if the player at the head of that column is left with the number of that row. 1 is the player after you; 2 is the player before you. Rows 1-4 are easily filled. After that, the Y column is determined by the highest number in the 1 column of the three above it (since you can only pick 1, 2, or 3). That's how you maximize your chances. The numbers in the 1 column are equal to 1/3 * (the sum of the numbers in the 2 column in the three rows above). The numbers in the 2 column are equal to 1/3 * (the sum of the numbers in the Y column). The reason the first four columns don't follow that rule is because 1 and 2 could have guaranteed winning options, so they're not random choices. Your best chance is to choose to go first and take two tokens. Then you have a 4051/6561 (~61.74% ) chance of winning.

Originally posted by Jirakon
Your best chance is to choose to go first and take two tokens. Then you have a 4051/6561 (~61.74% ) chance of winning.

How would the answer be different if you couldn't assume people will choose randomly? If, instead, everyone was following the same "best" strategy.

Originally posted by mtthw
How would the answer be different if you couldn't assume people will choose randomly? If, instead, everyone was following the same "best" strategy.

You mean if the other two players opted to maximize their own chances as well (without colluding specifically against you, of course)?

I don't know.

What I am confident of is that you can't force a win unless you get lucky and even then probably only if the person before you puts you within 3. I do plan on finding some sort of way to perform endgame analysis.

How would the answer be different if you couldn't assume people will choose randomly? If, instead, everyone was following the same "best" strategy.

If people didn't choose randomly, then there wouldn't be a "best strategy". For example, if player 1 was left with 5 tokens, they could basically determine who would win (a 1 guarantees your win, a 2 or 3 guarantees player 2's win). If there's no collusion, and player 1 doesn't care which of you wins, you can't assume which number they would pick, since there's no winning possibility. If you can't assume 1's choice for 5 tokens left, the problem breaks down from then on. That's why you must assume they pick randomly if there's no winning option.

However, if you word it even more specifically, instead of saying that every player always chooses the option that gives them the highest chance of winning, say this:

In every situation, the player whose turn it is falls into one of three categories:

(1) One of their options (1, 2, or 3) yields a higher chance of their victory than the other two.

(2) Two of their options yield the same chance of their victory, and it's higher than that yielded by their third option.

(3) All three of their choices yield exactly the same chance for their victory

Whenever a player is in situation (1), they will definitely choose that option with the highest chance of their victory. Whenever a player is in situation (2), they will definitely choose one of the two best options, but of the two, they will choose one at random. Whenver a player is in situation (3), they will simply select a number at random.

That's a different problem altogether. I might look at that later when I have some more time.

My gut instinct tells me in the problem in its last stated incarnation, it is in your best interest to go first, as this gives you the most control.

I should be able to analyze the wish a 9x21 matrix of values to be sure though.

It the two are colluding against you, then I am almost certain you can't win from any position.

And after further analysis, I find in my problem that if the number of tokens is 21, and if the other two players are rational and attempt to maximize their chances, but will choose randomly given two or three choices which have equal odds, that the whole thing cycles with a period of 5 tokens.

You would in fact, wish to be third and last to have the best odds.

It would essentially be played out in this manner. The first player would take 1, leaving 20. The second player cannot win unless someone makes a less optimal move, and would therefore pick a number randomly. Your best choice would then be to taken so that the total tokens taken is divisible by 5. The process would repeat twice more.

After the first player's 4th turn, there will be 5 tokens left. If the second player takes only 1, then you will lose and the first player will win. If the second player takes at least 2, you can then take the last token.

Check and see if you can find a counter to this..