Voronoi Game/Puzzle

[BMAD]

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 (Inspired by Phil's puzzle) 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?

example game:

[bonanova]

Some lines go off the paper and others terminate on other lines.

Is it correct to assume that all lines must terminate either on the paper's edge or a previously drawn line?

But if so, why is there not one line (the first one drawn) that terminates on two paper edges?

Does the strategy entail the order chosen to draw the lines?

Can you make clearer what is meant by "ensuring that the border defines area that is closest to the receptive point."

Thanks. It sounds interesting.

Edit:

OK I think I get it.

1. The points uniquely determine the lines, which are not part of the strategy.
2. Cells that surround each point comprise the points closer to it than to any other point.
3. The strategy comes in placing your points.

Edited May 21, 2014 by bonanova
I think I understand my questions

[BMAD]

Some lines go off the paper and others terminate on other lines.

Is it correct to assume that all lines must terminate either on the paper's edge or a previously drawn line?

But if so, why is there not one line (the first one drawn) that terminates on two paper edges?

Does the strategy entail the order chosen to draw the lines?

Can you make clearer what is meant by "ensuring that the border defines area that is closest to the receptive point."

Thanks. It sounds interesting.

Edit:

OK I think I get it.

1. The points uniquely determine the lines, which are not part of the strategy.
2. Cells that surround each point comprise the points closer to it than to any other point.
3. The strategy comes in placing your points.

Yes. your edit is correct.

The edge of the paper are the limits of the finite total area and the points split this area up into 8 distinct smaller areas. Each area is closer to its point than any other point.

Edited May 21, 2014 by BMAD

[bonanova]

I have not analyzed to see whether this will win.
But it seems to have advantages.

Each time my opponent moves I would find the most distant point on the edge of the paper and place my dot halfway on an imaginary line connecting it to his dot.

For example, he goes in the middle, I go halfway (as I think now, perhaps 2/3 of the way) from the middle to one of the corners.

I imagine that areas allocated to dots closer to the edge being bigger then areas allocated to dots that are closer to the center. Like slices of pie.

It would take more time than I have at the moment to (dis)prove this approach, so this is just a guess.

[m00li]

The first player can not lose this game if he plays it logically. consider this:

wherever the 2nd player puts his 'current/last' point, the first player should put his point such that:
his point lies on a line from the center to the 2nd player's 'current/last' point and immediately behind it (i.e. a ray starting from the center will hit 2nd player's 'current/last' point and then immediately hit first player's 'current/last' point)

[plasmid]

The first player can not lose this game if he plays it logically. consider this:

wherever the 2nd player puts his 'current/last' point, the first player should put his point such that:

his point lies on a line from the center to the 2nd player's 'current/last' point and immediately behind it (i.e. a ray starting from the center will hit 2nd player's 'current/last' point and then immediately hit first player's 'current/last' point)

If I'm the second player and I know you'll use that strategy, then after you place your first point, I will draw two lines going through your first point and running parallel to the edges of the paper, and I'll place my four points where those lines reach each edge of the page. Well, maybe just a tiny bit away from the edge so you could still place a point just a little bit farther away from the center than mine. I would then win with 75% of the area.

[m00li]

The first player can not lose this game if he plays it logically. consider this:

wherever the 2nd player puts his 'current/last' point, the first player should put his point such that:

his point lies on a line from the center to the 2nd player's 'current/last' point and immediately behind it (i.e. a ray starting from the center will hit 2nd player's 'current/last' point and then immediately hit first player's 'current/last' point)

If I'm the second player and I know you'll use that strategy, then after you place your first point, I will draw two lines going through your first point and running parallel to the edges of the paper, and I'll place my four points where those lines reach each edge of the page. Well, maybe just a tiny bit away from the edge so you could still place a point just a little bit farther away from the center than mine. I would then win with 75% of the area.

and I concede defeat

[plasmid]

Player 2 can guarantee at least a tie: Put a mirror in the center of the paper. Anytime player 1 places a point, place yours at its mirror image's location. On player 2's final move, since player 1 cannot move again, player 2 is free to look for whatever spot on the paper will give him the most area and he might be able to get a win, but will at the very least be able to get a tie by copying player 1's move.

Finding a strategy for player 1 that forces that to become a tie rather than an outright win for player 2 when he makes his last move is not easy (for me).

[BMAD]

Player 2 can guarantee at least a tie: Put a mirror in the center of the paper. Anytime player 1 places a point, place yours at its mirror image's location. On player 2's final move, since player 1 cannot move again, player 2 is free to look for whatever spot on the paper will give him the most area and he might be able to get a win, but will at the very least be able to get a tie by copying player 1's move.

Finding a strategy for player 1 that forces that to become a tie rather than an outright win for player 2 when he makes his last move is not easy (for me).

How can you mirror player 1's first move in the center of paper?

[plasmid]

Player 2 can guarantee at least a tie: Put a mirror in the center of the paper. Anytime player 1 places a point, place yours at its mirror image's location. On player 2's final move, since player 1 cannot move again, player 2 is free to look for whatever spot on the paper will give him the most area and he might be able to get a win, but will at the very least be able to get a tie by copying player 1's move.

Finding a strategy for player 1 that forces that to become a tie rather than an outright win for player 2 when he makes his last move is not easy (for me).

How can you mirror player 1's first move in the center of paper?

If player 1 places their point at (0, 0), place yours at (0, 1/infinity).

[m00li]

Player 2 can guarantee at least a tie: Put a mirror in the center of the paper. Anytime player 1 places a point, place yours at its mirror image's location. On player 2's final move, since player 1 cannot move again, player 2 is free to look for whatever spot on the paper will give him the most area and he might be able to get a win, but will at the very least be able to get a tie by copying player 1's move.

Finding a strategy for player 1 that forces that to become a tie rather than an outright win for player 2 when he makes his last move is not easy (for me).

How can you mirror player 1's first move in the center of paper?

If player 1 places their point at (0, 0), place yours at (0, 1/infinity).

Assume player 1 knows your strategy

Assuming you place the your first point at (0,1/x), where x is very very large but finite, player 1 keeps it at (0,1/x+1/y),where y is very very large but finite. By your strategy, you will place your 2nd point at (0,-1/x-1/y). Player 1 now keeps his 2nd point at (0,-1/x).

Now, where do you keep your 3rd point, as (0,1/x) is already occupied?

[plasmid]

Player 2 can guarantee at least a tie: Put a mirror in the center of the paper. Anytime player 1 places a point, place yours at its mirror image's location. On player 2's final move, since player 1 cannot move again, player 2 is free to look for whatever spot on the paper will give him the most area and he might be able to get a win, but will at the very least be able to get a tie by copying player 1's move.

Finding a strategy for player 1 that forces that to become a tie rather than an outright win for player 2 when he makes his last move is not easy (for me).

How can you mirror player 1's first move in the center of paper?

If player 1 places their point at (0, 0), place yours at (0, 1/infinity).

Assume player 1 knows your strategy

Assuming you place the your first point at (0,1/x), where x is very very large but finite, player 1 keeps it at (0,1/x+1/y),where y is very very large but finite. By your strategy, you will place your 2nd point at (0,-1/x-1/y). Player 1 now keeps his 2nd point at (0,-1/x).

Now, where do you keep your 3rd point, as (0,1/x) is already occupied?

I would not worry about it, because when he placed his point at (0, -1/x) he captured an infinitesimally small area between points (0, 0) and (0, -1/x-1/y), and I would only be capturing an infinitesimally small area between (0, 0) and (0, 1/x+1/y) if I were to try to mirror it.

[m00li]

thats why i wrote that it needs some refining as theoretically speaking you cannot apply the same strategy any more but have to modify it now,

[BMAD]

Player 2 can guarantee at least a tie: Put a mirror in the center of the paper. Anytime player 1 places a point, place yours at its mirror image's location. On player 2's final move, since player 1 cannot move again, player 2 is free to look for whatever spot on the paper will give him the most area and he might be able to get a win, but will at the very least be able to get a tie by copying player 1's move.

Finding a strategy for player 1 that forces that to become a tie rather than an outright win for player 2 when he makes his last move is not easy (for me).

How can you mirror player 1's first move in the center of paper?

If player 1 places their point at (0, 0), place yours at (0, 1/infinity).

I am confused as to how one can physically make that move

[plasmid]

My earlier response to m00li was a bit tongue-in-cheek, but if you're dealing with points within an infinitesimally small area, it doesn't matter. If you have any number of colinear points within an infinitesimally small area, they will just divide the page into two halves, one controlled by each player, which would not prevent continued use of symmetry. If the points within the infinitesimally small area are not colinear, they will divide the paper into four quadrants (if there are four points, two from each player, within the small area), or six zones with symmetry about whatever mirror player 2 is using (if there are three points from each player), which would not prevent continued use of symmetry for the rest of the game. If the first seven points are all within an infinitesimally small area, it should be straightforward for player 2 to place a point just infinitesimally outside the area that's already been covered in order to take at least half of the page.

Or if you don't buy that argument, then after player 1 plays (0, 0) and player 2 plays (0, 1/x), consider the mirror to be at (0, 1/2x) instead of (0, 0) and you won't run into problems with player 2 placing a point on top of a previous one.

But this brings up an interesting point -- what happens if you disallow infinitesimal distances and force players to use finitely defined points? Player 2 would have to give up a tiny bit of area if player 1 starts exactly in the center and player 1 might be able to turn that tiny advantage into a win over the symmetry strategy. But it would be difficult -- remember that I said that on the final move of the game, player 2 no longer has to follow symmetry and can just place his point wherever it would gain him the most area so he could potentially win instead of just tying. Player 1 would have to start the game with a move in the exact center and come up with a strategy where even the most optimal final move for player 2 could not net him half the page.

I cannot come up with such a strategy for player 1 at the moment.