wu :: forums - Print Page


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

        riddles >> cs >> Winning Strategy
        
(Message started by: birbal on Apr 2^nd, 2012, 12:24pm)

Title: Winning Strategy
Post by birbal on Apr 2^nd, 2012, 12:24pm

A table has two piles of stones, one with m stones in it and another with n stones initially. Two players A and B play a game. In one turn one player can either pick x : 1<= x <= m stones from first pile, or y : 1<= y <= n stones from the second pile, or z : 1 <= z <= min(m,n) stones from both piles. The last player to pick the stone is winner. Device a winning strategy for A if he is starting the game.

Title: Re: Winning Strategy
Post by nova2358 on Apr 3^rd, 2012, 9:18am

Seems this problem can be solved with Dynamic Programming.

Let F(m,n) denotes whether player A will win with m stones in one pile and n stones in another. So F(m,n) = 1 means A will win and F(m,n) = 0 means B will win.

And we have

F(m,n) = max {
1 - F(m-x,n), 1<=x<= m
1 - F(m,n-y), 1<=y<=n
1- F(m-c,n-c), 1<=c<=min(m,n)

}

The Reason to use 1 - F(m-x, n) is that after A's action, if F(m-x, n) = 1, then B will win, so A will lose. Otherwise F(m-x, n) = 0, so B will lose and A can win.

So we have m*n states, and calculating each states costs roughly O(max(m,n)) time. So the total time Complexity is m*n*O(max(m,n)).

First time to reply a question and I assume you know DP. Tell me if anything is unclear to you.

Title: Re: Winning Strategy
Post by pex on Apr 3^rd, 2012, 11:19am

on 04/03/12 at 09:18:40, nova2358 wrote:

F(m,n) = max {
1 - F(m-x,n), 1<=x<= m
1 - F(m,n-y), 1<=y<=n
1- F(m-c,n-c), 1<=c<=min(m,n)

}

Solving the recurrence relation, the winning strategy can be described pretty easily. WLOG, let m < n.
[hideb]If you're faced with (m,n) a multiple of (1,2), you lose. If not, you can always put the other player in this losing situation:
- if 2m < n, remove n-2m stones from the larger pile, leaving (m, 2m).
- if 2m > n, remove 2m-n stones from both piles, leaving (n-m, 2n-2m).[/hideb]

Title: Re: Winning Strategy
Post by nova2358 on Apr 4^th, 2012, 12:30am

on 04/03/12 at 11:19:06, pex wrote:

How did you come up with this solution?

Title: Re: Winning Strategy
Post by pex on Apr 4^th, 2012, 2:30am

on 04/04/12 at 00:30:07, nova2358 wrote:

How did you come up with this solution?

The way I always solve this kind of problems ;) I calculated the first 10*10 values using your recursive formula, noticed the pattern, and then came up with some reasoning to convince myself of the solution.

Title: Re: Winning Strategy
Post by birbal on Apr 4^th, 2012, 2:32am

on 04/03/12 at 11:19:06, pex wrote:

Looks convincing to me though i haven't verified it yet.

Title: Re: Winning Strategy
Post by SMQ on Apr 4^th, 2012, 5:31am

on 04/04/12 at 02:32:30, birbal wrote:

Looks convincing to me though i haven't verified it yet.

I don't know exactly where things went wrong, but it's clearly incorrect: [hide](2,4) is winnable by taking 3, leaving (2,1) which loses for player B[/hide].

I make the first handful of losing combinations (with everything else winning) to be: [hide](0,0) (1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20)[/hide] where [hide]the first number of each pair is the least number not yet listed, and the second number of each pair differs from the first by one more than in the previous pair[/hide].

--SMQ

Title: Re: Winning Strategy
Post by pex on Apr 4^th, 2012, 5:48am

on 04/04/12 at 05:31:48, SMQ wrote:

I don't know exactly where things went wrong, but it's clearly incorrect: [hide](2,4) is winnable by taking 3, leaving (2,1) which loses for player B[/hide].

:[ That's what I get for considering only half the diagram because of symmetry... Back to the drawing board.

Title: Re: Winning Strategy
Post by towr on Apr 4^th, 2012, 5:54am

on 04/04/12 at 05:31:48, SMQ wrote:

I make the first handful of losing combinations (with everything else winning) to be: [hide](0,0) (1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20)[/hide] where [hide]the first number of each pair is the least number not yet listed, and the second number of each pair differs from the first by one more than in the previous pair[/hide].

Neat. If you're in one of these positions you clearly can't put your opponent into one of them. So if you can get from any other position to one of these that would prove you always win. Since by construction every number occurs once (if we disregard (0,0) ) either as smallest of largest of a pair, you can always get from a position not in the sequence to one in it, by keeping the smallest and making the largest equal to the other in the losing pair.

Now all we need is a quick way to decide if we're in a winning position and how to find the winning move.

Title: Re: Winning Strategy
Post by towr on Apr 4^th, 2012, 6:20am

The first number of each pair seems to be part of the Lower Wythoff sequence http://oeis.org/A000201 , a(n) = floor(n*phi)
So we have the pairs (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk*phihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk*phi²http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif) as losing positions.
To find the winning move from (m,n) with m < n we just need to solve m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk*phihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif or m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk*phi²http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif, then take the number of stones from n to complete the pair.

Title: Re: Winning Strategy
Post by pex on Apr 4^th, 2012, 6:52am

on 04/04/12 at 06:20:24, towr wrote:

The first number of each pair seems to be part of the Lower Wythoff sequence http://oeis.org/A000201 , a(n) = floor(n*phi)

From that OEIS page:
Quote:

a(n) is the unique monotonic sequence satisfying a(1)=1 and the condition "if n is in the sequence then n+(rank of n) is not in the sequence"

So, yes, this is what SMQ described. Well done, you both!

Title: Re: Winning Strategy
Post by SMQ on Apr 4^th, 2012, 6:54am

on 04/04/12 at 06:20:24, towr wrote:

To find the winning move from (m,n) with m < n we just need to solve m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk*phihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif or m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk*phi²http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif, then take the number of stones from n to complete the pair.

We need one more case for when m is Lower Wythoff but we would need to add stones to n to make the pair, e.g. (3,4). In that case we need to remove stones from both piles to reach the (n-m)^th Wythoff pair.

--SMQ

Title: Re: Winning Strategy
Post by towr on Apr 4^th, 2012, 7:18am

So in summary:

if m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk phi²http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif
winning move: (m,n) => (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk*phihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif, m)
if m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk phihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif and n-m > k
winning move: (m,n) => (m, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk phi²http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif )
if m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk phihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif and n-m < k
winning move: (m,n) => (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif(n-m)*phihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif(n-m) phi²http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif )
if m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifk phihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif and n-m = k
you lose.

Title: Re: Winning Strategy
Post by SMQ on Apr 4^th, 2012, 8:03am

Here's how I came up with the pattern in the first place: X is a losing position, lines denote legal moves, so everything connected by a line to an X is a winning position. (I used graph paper rather than ASCII art, but you get the idea.)

0 1 2 3 4 5 6 7 8 9 0 X |\ 1 | \ | \ 2 | X-\ | |\|\ 3 | | \ \ | | |\ \ 4 | | | \ \ | | | \ \ 5 | | | X-\-\ | | | |\ \|\ 6 | | | | \ \ \ | | | | \|\ \ 7 | | | | X-\-\-\ | | | | |\|\ \|\ 8 | | | | | \ \ \ \ | | | | | |\ \|\ \ 9 | | | | | | \ \ \ \ | | | | | | \|\ \ \
etc.

--SMQ

Title: Re: Winning Strategy
Post by Grimbal on Apr 4^th, 2012, 9:05am

I heard of this problem before, when I was in high school. I think it was in Scientific American's Mathematical Games.

It was presented as a queen on a larger chessboard. She can move down, left or diagonally down and left. The first player places the queen on the top or right border, then each player in turn makes a move. The one to reach the bottom left wins.

With this representations, the relation with SMQ's graphical solution is quite direct.

At that time, I found an empiric rule to compute m(n), the winning m for a given n.
- d = frac(n*phi) (or frac(n/phi) which is the same)
- if d<1/phi², m(n) = floor(n/phi) is winning
- if d>1/phi², m(n) = ceil(n*phi) is winning
- if d=1/phi², then phi is a rational :-)

Note: frac = fractional part, floor = round down, ceil = round up.
By "winning" I mean that if you can move to that position, you win.

It is curious that you can use the fractional part to discriminate the "high" and "low" positions. I have no idea why it is so.