wu :: forums - Print Page


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

        riddles >> medium >> Squares on a grid
        
(Message started by: Garzahd on Oct 25^th, 2002, 12:58pm)

Title: Squares on a grid
Post by Garzahd on Oct 25^th, 2002, 12:58pm

Just recalled this problem that I read a long time ago. It was listed in a book as an unsolved problem, but it didn't seem that tricky to me. Perhaps that means my solution is wrong, but I'll throw it in and let people think about it.

You're playing a game with your friend on an infinitely large piece of graph paper. You and a friend each have a different color pen. You take turns marking intersections of the grid. The winner is the first person to color 4 intersections that form a square. The square may be of any size, but it must be oriented in the direction of the grid; that is, something like the midpoints of each side of a 2x2 square won't qualify.

What is the optimal strategy for each player? Who wins?

Title: Re: New puzzle: Squares on a grid
Post by James Fingas on Oct 25^th, 2002, 1:41pm

on 10/25/02 at 12:58:08, Garzahd wrote:

What is the optimal strategy for each player? Who wins?

Methinks that the person who goes first wins ;) Interesting problem!

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 27^th, 2002, 8:05am

I think that in optimal playing neither can win..
To make a square you need 4 points, to prevent someones square you need mark just 1 point..

Title: Re: New puzzle: Squares on a grid
Post by william wu on Oct 27^th, 2002, 11:18pm

If my opponent place a dot along one of the imaginary lines connecting the corners of a square, does that block the formation of a winning square? In other words, if red dots are at (0,0), (0,2), (2,2), and (2,0), and a blue dot is at (0,1), has blue blocked red's win?

If such blocking is not allowed, I think you can show that the first player can always force a win in six moves. If you don't believe me, let's play for money :) My first move is (0,0).

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 28^th, 2002, 12:29am

well, one can't really play for money over the internet.. And I wouldn't.. but for the sake of argument, I'll play (1,0)

Title: Re: New puzzle: Squares on a grid
Post by william wu on Oct 28^th, 2002, 1:52am

you're going down ...

(8,0)

Title: Re: New puzzle: Squares on a grid
Post by James Fingas on Oct 28^th, 2002, 6:50am

The person going first can win. Here is the beginning of my proof:

Player A goes first and WLOG (without loss of generality) places his piece at location (0,0).

Player B goes right beside him (I believe this is the best he can do). He goes in location (-1,0) or in location (-1,-1). I think (-1,0) is the better choice, but he will lose either way.

Player A goes in location (2,0).

Now player B has a choice. There are two essential qualities about his next play. It will:
i) Provide or not provide an opportunity to make a square with his first piece
ii) Prevent or not prevent player A from making at least one of the following four squares: (2,0)-(0,2), (2,0)-(4,2), (2,0)-(0,-2), (2,0)-(4,-2).

If he fails to do BOTH of these things, then he will definitely lose--if he fails to do i), then player A gains a turn, and can make an unblocked line of 3 (fatal for player B). If he fails to do ii), then player A will play (2,2), then (4,0), then (2,-2), forcing player B's move each time, then GAME OVER!

Now that we have that out of the way, player B is forced to play in location (4,0), since it is the only one that satisfies both i) and ii).

Player A can now win if he keeps forcing player B's moves, and never allows player B to get three points of a square. Here's how he does it:

A: (2,2)
B: (0,2)
A: (2,-2)
B: (0,-2)

A can now graduate to a larger grid size:

A: (6,2)
B: (6,-2)
A: (2,6)
B: (6,6)

Now A has formed an unblocked line of 3. B is toast:

A: (-2,2)
B: Yikes! (-2,-2)
A: (-2,6) for the win

If, at any point, A gives up the initiative and allows B to force his next move, then B will win. Basically, the person forcing the moves can always dominate. This is, for instance, why A can't play (1,0) after B's second move, making a doubly-unblocked line of 3 (which would win, except that B will keep forcing A's moves until B wins).

Note that the location of B's first move is unimportant, since A can always pick his second move so that B's first move doesn't block any of the four squares I talked about earlier. In fact, if B's first move is far enough away from A's first move, then A can pick his second move so that B's second move cannot satisfy both i) and ii) above, making an even easier win for A.

A good proof: cryptic, handwavy, entirely unconvincing, but true!

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 28^th, 2002, 8:48am

well, even if I'm bound to loose, I won't give up..

(0,8)

Title: Re: New puzzle: Squares on a grid
Post by william wu on Oct 28^th, 2002, 12:58pm

( 0,-8 )

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 28^th, 2002, 1:04pm

(so far, (0,0) (0,1) (8,0) (0,8) (0,-8) )

thus (8, -8)

Title: Re: New puzzle: Squares on a grid
Post by william wu on Oct 28^th, 2002, 1:10pm

(towr: sorry i goofed on my last move ... let's change that to (0,-8). glad i didn't play for money :P so then you respond with (8,-8) to block a win.)

(0,-4)

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 28^th, 2002, 1:15pm

hehe.. yes.. Now I see..
I choose either (-4 4) or (-4, -4)
And then you do (-4,-4) or (-4,4) respectively. And then I loose after the next move..

I understand now =)

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 28^th, 2002, 1:20pm

I can prolong the inevitable with (1,7)

Title: Re: New puzzle: Squares on a grid
Post by william wu on Oct 28^th, 2002, 1:53pm

Yeah. Basically, player 2's initial moves are somewhat meaningless, and player 1 can keep player 2 on the run until a doomsday scenario is created.

Not sure how (1,7) prolongs things ... are you saying you want to finish this game just for the sake of finishing? If so,

(4,4)

[ so far ]
(0,0) (0,1)
(8,0) (0,8)
(0,-8) (8,-8)
(0,4) (1,7)
(4,4)

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 28^th, 2002, 11:00pm

oops.. I made the mistake now, I meant (7,1)

(as in a chance for square (0,1) (7,1) (0,8) (7,8))
after that you'd have to do (7,8) cause else I'd win..

then I could have tried the same on the other side with (-7 1)
and you'd have to do (-7, 8)

then I could do (-7,-6) etc.. actually it could go on for a while..

If you're willing to repair my move to (7,1) I'd be willing to keep trying from there.. It seems I have a chance after all.. At least to significantly prolong the game..

Title: Re: New puzzle: Squares on a grid
Post by william wu on Oct 29^th, 2002, 2:51am

Actually I goofed again, I just played a losing game. My 4th move of (0,4) was nonthreatening and thus allowed you to take the offensive and eventually win ... bleh. Maybe I should just retire from this site and go to sleep. No more drugs for me! :P

Mr. Fingas's nifty analysis explains how player 1 can guarantee victory in at most 8 moves (not 6). All of player 1's moves after the 2nd move have to be threatening. In the first phase, player 1 threatens twice to build a square of edge length n, and then threatens to build a square of edge length 2n and eventually wins. Here's a correction of the game we just played, given that your first two moves are (0,1) and (0,8). All your moves after the first two are fixed.

me you
(0,0) (0,1)
(8,0) (0,8)

(0,-8) (8,-8)
(-8,0) (-8,-8)
(8,16) (-8,16)
(24,0) (24,16)

(8,-16) i have 2 ways to win ((24,-16) and (-8,-16)), so forfeit

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 29^th, 2002, 3:30am

hehe.. good thing we didn't play for money :P

Title: Re: New puzzle: Squares on a grid
Post by william wu on Oct 29^th, 2002, 3:34am

Seriously :P

Now what happens if winning squares can't have their edges interrupted by opponent pieces?

Title: Re: New puzzle: Squares on a grid
Post by towr on Oct 29^th, 2002, 8:18am

I would say that makes it very easy to keep the other player from winning.. And so it'd be a tie..
(Well, actually when the saner of the two gives up the other would win by default..)

Title: Re: New puzzle: Squares on a grid
Post by James Fingas on Oct 29^th, 2002, 9:34am

Yeah, it sounds impossible to force a win. After playing it out a bit on paper, it's ridiculously easy to stop somebody, and to ruin their chances to reuse their pieces in a larger sized square. Besides, any square bigger than 2x2 gives a large number of opportunities to stop it.

I've been thinking: what if the two players cooperated? Could they build up a pattern of dots that didn't contain any squares of either colour? This is similar to another question about colouring every point in the real plane with 2 colours and not making triangles, but, I believe, harder to answer.

Title: Re: New puzzle: Squares on a grid
Post by Garzahd on Oct 29^th, 2002, 11:26am

So I started browsing the internet for this problem, which I tend to do once I've reached the conclusion that I have little left to analyze.

Found an interesting variant: Player 2 gets two moves for each one move of player 1, but he's no longer trying to get a box himself, only to prolong the game indefinitely. The site implied (but did not explain) that player 1 still has a winning strategy. So, is there a way for player 1 to craft a triple threat?

Looks like the game tree for this would get even more absurd. I do have a theory I'm pursuing, though.