[Math] Game about placing pennies on table follow-up

game theory

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?

Best Answer

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.
Related Question