wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Winning strategy for the picking marbles game
        
(Message started by: wonderful on Jan 19th, 2009, 3:08am)
Title: Winning strategy for the picking marbles game
Post by wonderful on Jan 19th, 2009, 3:08am
There are three boxes of marbles. Box 1 has  30 marbles, box 2 has 37 marbles,  and box 3 has 46 marbles. Two people play the following game:


Each in turn picks either 1, 2, 4, or 6 marbles in one of three boxes.  The objective of the game is to force the oponent to pick up the last marble.

What is the winning startegy?
Title: Re: Winning strategy for the picking marbles game
Post by Noke Lieu on Jan 20th, 2009, 3:49pm
From my first poke at it, I'd have to say "Bet $20 bucks on me losing the marble game."  ::)
Title: Re: Winning strategy for the picking marbles game
Post by Grimbal on Jan 20th, 2009, 10:11pm
Nimbers!

The strategy that comes out of that is:
For each box, take the remainder mod 8.  If larger than 3, subtract 3.  That is the nimber of a box.
XOR the nimbers of the boxes giving the nimber of the game.
The strategy is to make any move that brings that number back to 0.
For the starting position:
30 -> 6 -> 3
37 -> 5 -> 2
46 -> 6 -> 3
The game nimber is 2.

To win, you can take 2 from any of the 3 boxes.
Title: Re: Winning strategy for the picking marbles game
Post by Eigenray on Jan 21st, 2009, 3:54am
That's the strategy for normal play.  Misere play is trickier.
Title: Re: Winning strategy for the picking marbles game
Post by Grimbal on Jan 21st, 2009, 6:47am
Right!  Back to the drawing board.  :-/
Title: Re: Winning strategy for the picking marbles game
Post by towr on Jan 21st, 2009, 11:26am

on 01/19/09 at 03:08:50, wonderful wrote:
What is the winning startegy?
Using a computer or cheat-sheet.
And start by taking 2 from any of the piles.
Title: Re: Winning strategy for the picking marbles game
Post by Grimbal on Jan 21st, 2009, 12:03pm
Hey, that's exactly what I said!   ::)
Title: Re: Winning strategy for the picking marbles game
Post by rmsgrey on Jan 21st, 2009, 12:42pm
As I recall, misere play differs from regular play only in the endgame...
Title: Re: Winning strategy for the picking marbles game
Post by towr on Jan 21st, 2009, 1:00pm

on 01/21/09 at 12:42:04, rmsgrey wrote:
As I recall, misere play differs from regular play only in the endgame...
Well, I can say one thing (provided my program is correct), and that's that it only rarely doesn't matter which box you take an X number of marbles from.


For example if we start with
30,37,46  -> 28,37,46  -> 27,37,46
Then to win you must take either 2 from the first box, or 1 or 4 from the last. Anything else and you find yourself in a losing position.
Title: Re: Winning strategy for the picking marbles game
Post by Grimbal on Jan 21st, 2009, 2:29pm
Yes (to rmsgrey).  For standard Nim the misere strategy is the same as for normal play except that when you reach the situation where there are only 1's left, then you must take one more or one less (xor with 1) to change the parity.  I am not sure whether that twist can be implemented in the 3 boxes game.
Title: Re: Winning strategy for the picking marbles game
Post by Eigenray on Jan 21st, 2009, 4:17pm
The following multisets of nimbers (Grundy numbers) for the boxes are losing states (i.e., states you want to leave your opponent with):
{0, 0, 1}, {0, 2, 2}, {0, 3, 3}, {0, 4, 4}, {1, 1, 1}, {1, 2, 3}
everything else is a winning state.
Note that {0,0,1} an {1,1,1} have xor 1 and are losing, while {0,0,0} and {0,1,1} have xor 0 and are winning.  The rest are losing iff xor=0.
(The nimbers for stacks of 0,1,2,... marbles repeat {0, 1, 2, 0, 1, 2, 3, 4}.)
Title: Re: Winning strategy for the picking marbles game
Post by wonderful on Jan 23rd, 2009, 5:23am
Thanks for your interesting discussion. However, it seems that you forget the restriction that each time the players allow to pick 1, or 2, or 4, or 6 marbles. As such, the strategy may differ from the standard nim game.
Title: Re: Winning strategy for the picking marbles game
Post by towr on Jan 23rd, 2009, 5:47am

on 01/23/09 at 05:23:19, wonderful wrote:
Thanks for your interesting discussion. However, it seems that you forget the restriction that each time the players allow to pick 1, or 2, or 4, or 6 marbles. As such, the strategy may differ from the standard nim game.
I don't think they forgot.
You just have to pick the right number of marbles to get from one multiset of nimbers to another.
Title: Re: Winning strategy for the picking marbles game
Post by wonderful on Jan 23rd, 2009, 6:37am
Here is an example:

A, B are two players. A is in the following position: (4, 4, 0), thus, XOR of nimbers = 0.  However, by picking 4 in the first box, A forces B to pick up either 1, 2, or 4 in the the second box. A is left with 3, 2, or 0.  By picking 2, 1, or  0, A is the winner.

In a standard nim with no restriction, if A picked 4 in the fist box, B would just pick 3 in the second box to be the winner.
Title: Re: Winning strategy for the picking marbles game
Post by towr on Jan 23rd, 2009, 7:03am

on 01/23/09 at 06:37:25, wonderful wrote:
Here is an example:

A, B are two players. A is in the following position: (4, 4, 0), thus, XOR of nimbers = 0.
Yes, but the nimber set is {1,1,0}, so it's a win for A

(Read Grimbal's post for how to calculate the nimber of a stack in this game)


Quote:
However, by picking 4 in the first box, A forces B to pick up either 1, 2, or 4 in the the second box. A is left with 3, 2, or 0.  By picking 2, 1, or  0, A is the winner.
Precisely as predicted.
Title: Re: Winning strategy for the picking marbles game
Post by wonderful on Jan 23rd, 2009, 7:25am

on 01/23/09 at 07:03:05, towr wrote:
[quote]Yes, but the nimber set is {1,1,0}, so it's a win for A


There may be some miscommunication here. According to Grimbal, B should be the winner in this case since he puts A in a position s.t. XOR = 0
Title: Re: Winning strategy for the picking marbles game
Post by towr on Jan 23rd, 2009, 7:34am

on 01/23/09 at 07:25:49, wonderful wrote:
There may be some miscommunication here. According to Grimbal, B should be the winner in this case since he puts A in a position s.t. XOR = 0
You have to cleverly combine Grimbal's and Eigenray's posts.

For each box, take the number of elements modulo 8; and if that number is 3 or greater, subtract 3.
Now you have a multi-set of three nimbers.
For example, {0,4,4} goes to {0,1,1} and {30,37,46} goes to {3,2,3}

If this multi-set is (disregarding order) amongst
{0, 0, 1}, {0, 2, 2}, {0, 3, 3}, {0, 4, 4}, {1, 1, 1}, {1, 2, 3}  
Then you lose. Otherwise you win by arranging it so the other player is faced with one of those positions.

Aside from {0,0,0}, {0,0,1}, {0,1,1} and {1,1,1} (i.e. the sets where all numbers are 1 or less) a state is losing iff and only if the XOR of the nimbers is 0. (For those 4 it is reversed)


I'm not sure if there is a clever way to tell how many elements you should pick from which box, but there's only 12 variations to try.
Title: Re: Winning strategy for the picking marbles game
Post by wonderful on Jan 23rd, 2009, 7:54am

Quote:
If this multi-set is (disregarding order) amongst  
{0, 0, 1}, {0, 2, 2}, {0, 3, 3}, {0, 4, 4}, {1, 1, 1}, {1, 2, 3}  
Then you lose. Otherwise you win by arranging it so the other player is faced with one of those positions.


Thanks Towr for the clarification. I appreciate it. However, I actually used the {0, 4, 4} to make the point. If A was in this position, by picking 4 in the second box he won the game.
Title: Re: Winning strategy for the picking marbles game
Post by towr on Jan 23rd, 2009, 7:57am

on 01/23/09 at 07:54:07, wonderful wrote:
Thanks Towr for the clarification. I appreciate it. However, I actually used the {0, 4, 4} to make the point. If A was in this position, by picking 4 in the second box he won the game.
Yes, because game {0,4,4} gets nimbers {0,1,1}, and that's a winning position.
Title: Re: Winning strategy for the picking marbles game
Post by Hippo on Jan 25th, 2009, 12:28pm
I didn't actually think about it ... the case {0,4,4} is presented to represent (8,7,7) position.
(8,7,7)->{0,7-3=4,7-3=4}
(0,4,4)->{0,4-3=1,4-3=1},
Title: Re: Winning strategy for the picking marbles game
Post by towr on Jan 25th, 2009, 12:57pm

on 01/25/09 at 12:28:58, Hippo wrote:
I didn't actually think about it ... the case {0,4,4} is presented to represent (8,7,7) position.
Indeed, and therefore {8,7,7} isn't winnable.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board