1
$\begingroup$

This is inspired by the question at Game about placing pennies on table

"Consider the following two player game. Each player takes turns placing a penny on the surface of a rectangular table. No penny can touch a penny which is already on the table. The table starts out with no pennies. The last player who makes a legal move wins. Does the first player have a winning strategy?"

The first player will win by placing a penny in the centre of the table, then can always symmetrically match the opponent's moves reflecting across the central point (assuming equivalent dexterity), until the second player has no remaining move.

However, suppose we are playing as the second player, and we observe that the first player does not know this strategy - it appears that the first player has played in a 'random' (edit: leaving a central play possible) position on the board.

Can the second player use this bad first move to create a winning strategy? Even if the first player then returns to playing 'perfectly'? How?

If not, what is the second player's best option for a chance to win?

Further to discussion: If the first player can return to play in the centre later on (or, even if the second player plays directly in the centre), the first player will take back their winning strategy.

Can the second player partially cover the centre enough in order to prevent this/gain the "central play" advantage? Can we be specific about what the second player should do in each case?

  • 0
    Note: I will try to award the bounty to the most insightful of these answers before the time elapses, but really I would prefer a more complete answer.2012-04-15

4 Answers 4

6

Considering similar games, I don't think that the second player necessarily will have a winning strategy. Either the first or the second player will have a winning strategy, but which player will depend on the dimensions of the board.

The "gold standard" of a strategy for impartial games like this involves a Grundy function $G$, which always exists (Sprague-Grundy theorem) but can be hard to find. It takes a board position as input and returns a non-negative integer. It returns a positive number for first player wins and zero for second player wins.

With $G$, the problem of perfect play is solved: Consider all the board positions $P_i$ that you could move to. If there's a position such that $G(P_i)=0$, then move there... and your opponent has no hope.

$G$ has these properties:

  • During the endgame, there will be a few "islands" in the sea of pennies where one can still play. Each island is a mini-board with its own Grundy value. The Grundy value of the entire board is the bitwise XOR, a.k.a. nim-sum, of the Grundy values of the islands.

  • If you are at board position $P$, and can move to any one of the board positions $P_i'$, then $G(P) = mex(G(P_i'))$, where "mex" means the minimum excluded value. That is, the least non-negative integer not in the set $\{G(P_i')\}$.

To train myself to play against other people, I would study the Grundy values of small board positions. I would write a computer program to draw bunches of them grouped by their Grundy values, then look for patterns. My strategy would be to avoid symmetry and place the pennies to create islands with known Grundy values. Then play perfectly just in the end-game.

In the game Cram, players place 1x2 dominoes on a square grid. The last player who makes a legal move wins. From the table of Grundy values in Wikipedia's page on Cram, you can see that:

  • 4x4, 5x5, and 4x6 islands are first-player wins.
  • 4x5 and 5x7 islands are second player wins.
  • There's not much else known about who wins despite a lot of searching by computer.
5

If the distance between the center of the first penny and the center of the table (which I'll call the origin) is between $R$ and $\sqrt 3 R$, where $R$ is radius of the pennies, mirroring the first player's moves is a winning strategy for the second player. This is because it is always possible to mirror a penny that does not cover the origin, and two opposite pennies placed as above leave no room on either side to sneak in a penny that does cover the origin.

  • 0
    Like! but this creates a curious asymmetry which might affect the strategic advantage of playing at the origin?2012-04-08
4

Assume the player must place the penny on a lattice-point:

If the table contains an even number of lattice-points, the second player always wins. An odd number of points and the first player always wins.

If the player can place the penny on a lattice-line, thus blocking two lattice-points, then the above still holds (the evenness-oddness of the count does not change).

Edit: I misspoke: the evenness-oddness does change for the player!

If player two, on an even turn, blocks two lattice-points, it becomes an even turn for player one. It's a lot like the "picking up the matches" game.

Strategy to guarantee the win when only one lattice-line remains playable:

If even-oddness is in player's favor: play a lattice-point, else play the lattice-line.

  • 0
    At the point in the game when there is one open lattice-line and only single lattice-points open elsewhere, you can use the strategy in the last two lines of my answer.2012-04-12
2

If you were only allowed to place the pennies on the points of a hexagonal lattice (with the lattice points far enough apart so that pennies can't overlap), then the first player would still win: play opposite the second player, treating the two 'critical points' (the centre of the table, and the point opposite the first move) as opposite.

As Rahul's answer shows, the lattice-point condition is necessary.

Updated to add: After Rudy Toody's answer, I realise that this strategy is overkill. Equally effective is the strategy "play anywhere you like".

  • 0
    Further: if the lattice points are far enough apart so that the pennies don't overlap, then Player 2 can never win (no matter the strategy) because there should be an odd number of points.2012-04-11