wu :: forums - Print Page


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

        riddles >> medium >> Square Game Strategy
        
(Message started by: Dudidu on Dec 24^th, 2003, 9:44am)

Title: Square Game Strategy
Post by Dudidu on Dec 24^th, 2003, 9:44am

Consider the following game between 2 players:
They are given a plain made of m[times]n squares. Each players (in his turn) picks one of the (remaining) squares, and removes all the squares that are “below it and to its right” (i.e. if a player choose (i, j) square then all the (i', j') squares s.t. i'[ge]i, j'[ge]j are removed). The loser of the game is the player that chooses the upper/left most square (e.g. square (1, 1)).

1) Suppose n > 1 and m=n. Describe a (very) simple winning strategy for the first player.
2) Suppose m,n > 1. Prove the existence of winning strategy for the first player in the game.
3) Suppose m,n > 1. Devise a winning strategy...

Remark: I don't know the solution to (3) or if it even exists...

Title: Re: Square Game Strategy
Post by Quetzycoatl on Dec 26^th, 2003, 11:48am

I think perhaps I am misunderstanding the game, because it seems to me that the first player can always win by choosing the square at (2, 2), leaving only squares (1, 2) and (2, 1) and the losing square (1, 1). The opponent then chooses one of the two non-losing squares, then player 1 takes the remaining one leaving only the losing square.

I assume there is more to it than this so please explain what I am missing.

Title: Re: Square Game Strategy
Post by Icarus on Dec 26^th, 2003, 6:19pm

That is part of a strategy, but you are mistaken that only (1, 1), (2, 1), and (1, 2) are left behind. (1, k), and (j, 1) are also left behind for all k <= n, j <= m. This leaves many possibilities for player 2. You must figure out player 1 must respond.

Problem (1) is easy to solve. I assume (2) can be shown by means of [hide]strategy - stealing[/hide] (the most common means of showing a strategy must exist without actually producing one). But I have not thought it out as to how.

Title: Re: Square Game Strategy
Post by James Fingas on Dec 29^th, 2003, 10:03am

Here are some winning positions (after your turn):

x

xx
x

xx ... xx
xx ... x

xxx
x
x

xxxx
x
x
x

x ... xxx
x ... x
xx

x ... xxxx
x ... x
xxx

xxxxx
xxxxx
xxx

xxxxxxx
xxxxxxx
xxxx

Here is my contribution towards part 2, but notice that it is not complete. I think we need to delve a little into question 3 to complete it.

[hide]To prove that a winning strategy must exist, imagine the game tree for this game. It is a directed acyclic graph with a single "final node". Colour the nodes according to the following scheme:

1) First colour the final node blue. This is the game position with only one square left. Add it to B, the set of blue nodes.

2) Next, colour pink all the nodes V such that there is an edge from V to a node in B, and add them to P, the set of pink nodes.

3) Now find all nodes V such every edge from V goes to a node in P. There must be at least one such node. Colour all such nodes blue and add them to B.

4) Repeat 2 and 3 as needed (i.e. until the game tree node corresponding to the rectangular mxn grid has been coloured either pink or blue.)

There is a winning strategy for the starting player if the mxn grid is coloured pink, and there is no such strategy if it is coloured blue. I am relatively sure that the following grid sizes are coloured pink:

1xn
2xn
3xn

As for the other grid sizes, I just don't know. The winning strategy is to play to a blue node every turn.[/hide]

Title: Re: Square Game Strategy
Post by Dudidu on Dec 31^st, 2003, 12:52am

on 12/29/03 at 10:03:18, James Fingas wrote:

Here are some winning positions (after your turn)...

James hi,
you gave many positions that may lead to a win, but can you give a recipe (i.e. algorithm) what is the first step that the first player should take, what is the second step he/she should take (in response to the second player's first step) ?

Title: Re: Square Game Strategy
Post by James Fingas on Dec 31^st, 2003, 7:48am

I think the solution to this will not be an algorithm to say what the appropriate move is, but rather an algorithm to decide which positions are winning positions. Figuring out the most appropriate move from that is relatively easy.

I don't have such an algorithm yet, however. It looks like it will be a very complex (complexity O(mn) maybe) to specify the winning positions. But it's still an interesting problem...

Title: Re: Square Game Strategy
Post by Dudidu on Dec 31^st, 2003, 8:19am

on 12/31/03 at 07:48:03, James Fingas wrote:

I don't have such an algorithm yet, however. It looks like it will be a very complex (complexity O(mn) maybe) to specify the winning positions. But it's still an interesting problem...

James, we're probably refering different things :P.
I'm looking for an "algorithm" to the 1^st sub-question (since altough it is quite easy, no one (yet) has suggested a correct strategy) while you are probably refering the 3^rd sub-question...

Title: Re: Square Game Strategy
Post by James Fingas on Dec 31^st, 2003, 8:29am

The winning positions I gave are relevant to the third sub-question more than to the first. The answer to the first sub-question is trivial given the winning positions I've already found:

[hide] Remove the (2,2) square, then mirror your opponents moves on the x=y line. Eventually, only the (1,1) square will be left, and it will be your opponent's turn. [/hide]

Title: Re: Square Game Strategy
Post by Dudidu on Dec 31^st, 2003, 8:52am

on 12/31/03 at 08:29:19, James Fingas wrote:

The winning positions I gave are relevant to the third sub-question more than to the first. The answer to the first sub-question is trivial given the winning positions I've already found...

James,
Your answer to the first sub-question is correct (of course), well done !
Anyway, the second sub-question does not depend on the third sub-question (that can be easily regarded as hard). So, you don't have to solve it (i.e. the third one) in order to "get" the second one...