5
$\begingroup$

The game of Domineering can be played on any board consisting of some subset of $\mathbb{Z} \times \mathbb{Z}$. In particular, consider the boards $K_n$ generated by iterating the following inductive construction (a discrete analogue of the process generating the Sierpinski Carpet): \begin{eqnarray*} K_0 &=& \{(0,0)\} \\ K_{n+1} &=& \{(x+a\cdot 3^n,y + b \cdot 3^n) \mid (x,y) \in K_n, (a,b) \in \{-1,0,1\}^2 \setminus (0,0)\} \end{eqnarray*} Now, $K_0$ is obviously a second-player win, since it is impossible to place a domino (either horizontally or vertically) on a board consisting of a single tile. It is not hard to check that $K_1$ is likewise a second-player win -- the following (alpha-beta pruned) game tree demonstrates this, where we haven't tried to reduce the size of the tree by any symmetry considerations, but without loss of generality we assume that the opening move is by the player placing dominoes vertically ("V"):

see noamz.org/images/gametree-carpets1.svg

Here is an example of a game played on $K_2$, where this time we've decided to let the horizontal player ("H") make the first move, and they lose in round 31:

see noamz.org/DC2019-roundrobin/AG-vs-AD-15.svg

The game tree for $K_2$ is too large to exhaust by brute force, but from some Monte Carlo experiments, it appears to me that the second-player also has an advantage on $K_2$.

On the basis of this "strong evidence" (two verified cases and an empirical example!), I am led to the following

Conjecture: The Domineering board $K_n$ is a second-player win for all $n\ge 0$.

Can you prove this conjecture/guess? Or can you find a counterexample?

Improve this question
$\endgroup$
5
  • $\begingroup$ Is there not a strategy-stealing argument, where player 2 can always mirror the first player? Since there is a hole missing in the middle, this should work... EDIT: Ah, i see, the players have forced orientations... hmm. $\endgroup$
    – Per Alexandersson
    Commented Dec 13, 2019 at 8:19
  • 1
    $\begingroup$ Nice thought, but right, naively mirroring won't work, even if the mirroring is across one of the diagonals so that the second player plays the correct orientation. Here's an example where the second player gets stuck in round 10: noamz.org/images/mirror.svg. In fact, the basic problem is that the second player cannot mirror if the first player places a domino on the diagonal, since one of the tiles of the mirrored domino will be already occupied. $\endgroup$
    – Noam Zeilberger
    Commented Dec 13, 2019 at 11:51
  • $\begingroup$ Do you have any reason why you have considered the Sierpinski Carpet? $\endgroup$
    – domotorp
    Commented Jan 13, 2020 at 10:56
  • 1
    $\begingroup$ $K_2$ can be explicitly solved using Obsequi (github.com/nathanbullock/obsequi) in seconds and is indeed a second-player win. $\endgroup$
    – Gabriel C. Drummond-Cole
    Commented Feb 7, 2021 at 23:55
  • $\begingroup$ nice, thanks for letting me know! $\endgroup$
    – Noam Zeilberger
    Commented Feb 8, 2021 at 6:51

0

Reset to default

You must log in to answer this question.