Pick and Choose

Wacky · 2003-07-14, 19:41

Here's another strategy game for you to analyze.

Two players make a single line of twelve tokens. They could be dominoes, coins, or whatever. They are placed so that each token (except the two end tokens) touches each of its two neighbors, and no other. Now, one of the end tokens is moved away a bit so that there are two lines. The first contains one token and the second contains all the rest.

The players take turns removing the tokens. In each turn, a player must take either one token or two. However, if he takes two, they must be touching neighbors. No tokens are ever moved except when they are removed.

For clarification, if the tokens are taken from the end of a line, the line gets shorter (or disappears). If they are taken from any interior place in the line, that line is divided into two lines by the gap left by the tokens removed.

The objective is to remove the last token.

Is there a winning strategy for either player?

If so, what is the strategy?

alienz · 2003-07-14, 21:06

http://world.std.com/~reinhold/math/nim.html

The answer is here,

Wacky · 2003-07-14, 21:24

Sorry, Nim is a different game. Please reread the rules.

Orgasmic Troll · 2003-07-14, 23:15

I have been approaching this problem in a less than graceful manner, namely, working backwards from winning positions (i.e. *, **) representing the possible positions at n as partitions of n.

So far (assuming I haven't made an error .. that would suck), I have gotten up through 9 pieces, and the positions where the next player will lose with optimal playing on both sides is 8+1, 6+3, 6+2+1, 5+3+1, 4+1+1+1+1+1, and 3+3+3

for eight pieces left, the losing positions are 4+4, 4+2+2, 3+2+1+1+1, 2+2+2+2, 2+2+1+1+1+1, and 1+1+1+1+1+1+1+1

This was much more manageable at 5 pieces :) I suppose I could keep on going until I exhaust the possibilities at 10 and 11 pieces left, but I still don't have a really graceful definition of the optimal strategy.

Maybeso · 2003-07-15, 00:16

Travis,

Ive been trying to do the same, with not much more luck. :?

Something that might help you is to eliminate "good" positions that the previous player wouldn't give to you.
ie. The final winning position of **. The possible positions before that are (I think):
[code:1] ***, ****, ** *, and ** ** which a good player would make

**, ** *, * *, and ** * respectively. [/code:1]Notice that only the first one, ***, leads to your result, and based on its previous positions, it can be avoided by a good player. (again, I think)
So it should be pruned from your search.

The only winning stratagy I can think of is:
1. Reduce the game to an even number of lines of one or two tokens each.
2. Always leave an even number of lines of one or two tokens each.

The trick is how to complete step 1 while preventing your opponent from doing so. ;)

c00ler · 2003-07-16, 20:02

The first one wins!

hints:
1)first move - make 1+3+7
2)one, who makes a+a+b+b+a+a (symmetrical position), loses

P.S. If objective is not to remove the last token then the first wins too.
And first winning moves are 1+3+7

and 1+5+5
P.P.S. It's much harder to analyse the game with modified rules; it's solution is much longer.

2003-07-14, 19:41	#1
Wacky Jun 2003 The Texas Hill Country 3²×11² Posts	Pick and Choose Here's another strategy game for you to analyze. Two players make a single line of twelve tokens. They could be dominoes, coins, or whatever. They are placed so that each token (except the two end tokens) touches each of its two neighbors, and no other. Now, one of the end tokens is moved away a bit so that there are two lines. The first contains one token and the second contains all the rest. The players take turns removing the tokens. In each turn, a player must take either one token or two. However, if he takes two, they must be touching neighbors. No tokens are ever moved except when they are removed. For clarification, if the tokens are taken from the end of a line, the line gets shorter (or disappears). If they are taken from any interior place in the line, that line is divided into two lines by the gap left by the tokens removed. The objective is to remove the last token. Is there a winning strategy for either player? If so, what is the strategy?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Help to choose components for a Ryzen rig	robert44444uk	Hardware	50	2018-04-07 20:41
If you choose an answer at random	Uncwilly	Lounge	12	2018-02-14 15:00
Which settings to choose for best work?	jmb1982	Software	2	2009-04-07 09:33
Choose your own exponent?	Unregistered	PrimeNet	3	2003-12-10 04:32
Pick a stone, or two, .... or three	Wacky	Puzzles	5	2003-06-24 16:11

2003-07-14, 21:06	#2
alienz Jun 2003 3·7 Posts	http://world.std.com/~reinhold/math/nim.html The answer is here,

2003-07-14, 21:24	#3
Wacky Jun 2003 The Texas Hill Country 3²×11² Posts	Sorry, Nim is a different game. Please reread the rules.

2003-07-14, 23:15	#4
Orgasmic Troll Cranksta Rap Ayatollah Jul 2003 641 Posts	I have been approaching this problem in a less than graceful manner, namely, working backwards from winning positions (i.e. , *) representing the possible positions at n as partitions of n. So far (assuming I haven't made an error .. that would suck), I have gotten up through 9 pieces, and the positions where the next player will lose with optimal playing on both sides is 8+1, 6+3, 6+2+1, 5+3+1, 4+1+1+1+1+1, and 3+3+3 for eight pieces left, the losing positions are 4+4, 4+2+2, 3+2+1+1+1, 2+2+2+2, 2+2+1+1+1+1, and 1+1+1+1+1+1+1+1 This was much more manageable at 5 pieces :) I suppose I could keep on going until I exhaust the possibilities at 10 and 11 pieces left, but I still don't have a really graceful definition of the optimal strategy.

2003-07-15, 00:16	#5
Maybeso Aug 2002 Portland, OR USA 274₁₀ Posts	Travis, Ive been trying to do the same, with not much more luck. :? Something that might help you is to eliminate "good" positions that the previous player wouldn't give to you. ie. The final winning position of . The possible positions before that are (I think): [code:1] , *, , and * which a good player would make , ** , , and * * respectively. [/code:1]Notice that only the first one, ***, leads to your result, and based on its previous positions, it can be avoided by a good player. (again, I think) So it should be pruned from your search. The only winning stratagy I can think of is: 1. Reduce the game to an even number of lines of one or two tokens each. 2. Always leave an even number of lines of one or two tokens each. The trick is how to complete step 1 while preventing your opponent from doing so. ;)

2003-07-16, 20:02	#6
c00ler Jul 2003 25₁₀ Posts	The first one wins! hints: 1)first move - make 1+3+7 2)one, who makes a+a+b+b+a+a (symmetrical position), loses P.S. If objective is not to remove the last token then the first wins too. And first winning moves are 1+3+7 and 1+5+5 P.P.S. It's much harder to analyse the game with modified rules; it's solution is much longer.