wu :: forums - Print Page


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

        riddles >> medium >> Voronoi Game/Puzzle
        
(Message started by: BMAD on May 23^rd, 2014, 6:12am)

Title: Voronoi Game/Puzzle
Post by BMAD on May 23^rd, 2014, 6:12am

You and an opponent are sharing a regular sheet of paper. You will play an area game. Your opponent goes first and marks a single point in the center of the paper. You will make a mark in a different location and then it is their turn, your turn and so on. The game continues until you each have four points on the paper. As this is the "Voronoi Game", the paper is then divided into 8 areas. An area is created by drawing perpendicular lines between the nearest points until enough perpendicular lines define the area (ensuring that the border defines area that is closest to that receptive point). Is there a strategy that you can utilize to ensure you have the largest total area at the end of the game?

In summary:
The points uniquely determine the lines, which give the size of each point's cell.
Cells that surround each point comprise the points closer to it than to any other point.
The strategy comes in placing your points.

Title: Re: Voronoi Game/Puzzle
Post by rmsgrey on May 23^rd, 2014, 9:03am

So you score all the area that's closer to one of your points than to one of the opponent's?

Title: Re: Voronoi Game/Puzzle
Post by BMAD on May 23^rd, 2014, 9:10am

yes.

Title: Re: Voronoi Game/Puzzle
Post by Grimbal on May 23^rd, 2014, 9:23am

I first thought the 2nd player must win since he has more choice in the 1st move and plays all his moves knowing his opponent's move.

But this reasoning should apply also if each player plays 1 point. And it fails.

Title: Re: Voronoi Game/Puzzle
Post by Grimbal on May 23^rd, 2014, 9:59am

But I think 2nd player can win the game by [hide] dividing the paper in 4 smaller rectangles and playing the 4 centers (or very close). [/hide]

Title: Re: Voronoi Game/Puzzle
Post by towr on May 23^rd, 2014, 12:17pm

Maybe [hide]the way to look at it is that player one picks the point and player two picks a dividing line through it. Player two can pick his point arbitrarily close and at any side of player one's point; so if he does, that's what it comes down to in the limit. In particular, player two can pick which side of the line is his, and so can always pick the better side of the area divided by the line, if there is one (which there isn't for N=1).[/hide]

Title: Re: Voronoi Game/Puzzle
Post by BMAD on May 23^rd, 2014, 2:49pm

But player 1's third move also determines a dividing line

Title: Re: Voronoi Game/Puzzle
Post by towr on May 24^th, 2014, 12:35am

Player 1's move only determines the point the line has to go through. (Bearing in mind that I'm mapping the original problem to one that's equivalent for a subset of possible solutions.) So in that approach player 1 chooses a Voronoi cell, and player 2 divides it in two and picks a half.

Actually, that's probably not the right approach for looking at it, because the Voronoi cell player 1 chooses will change the previous existing ones, so he'd pick one that takes area from player two and then player two would get only around half back using this approach. So this is not a good strategy.