Game values of $3\times n$ and $4\times n$ Domineering, and the temperature / boiling-point question (Games of No Chance B11)
Statement
Domineering is the partizan game in which Left places vertical dominoes and Right places horizontal dominoes on a checkerboard, a player unable to move losing. Determine the combinatorial game VALUES (canonical forms, not merely win/loss outcomes) of the $3\times n$ and $4\times n$ boards as functions of $n$. Relatedly: characterize the hot Domineering positions and their temperatures — in particular, is Berlekamp's conjectured boiling point of $2$ correct (no position has temperature $>2$), or does there exist a position of temperature exceeding $2$?
Acceptance. ADVANCES (the expected product): exact canonical-form values for $3\times n$ and/or $4\times n$ Domineering for a range of $n$ beyond those tabulated, each a machine-checkable certificate (the value plus a CGSuite re-computation), and/or a Domineering position of temperature $>2$ (instantly verified by recomputing its thermograph) which would refute Berlekamp's boiling-point-$2$ conjecture. FULLY RESOLVES: a closed formula (with proof) for the $3\times n$ (resp. $4\times n$) value sequence, or a theorem bounding the temperature of every Domineering position by $2$. Provide the values/positions and a verification script.
Background
Games of No Chance 5, Problem B11 (4), 'Domineering' (MSRI Publ. 70, 2017, pp. 143-145), restating Berlekamp's problems. Win/loss OUTCOMES are heavily solved (e.g. $11\times11$ is a first-player win, Uiterwijk 2016; many $m\times n$ decided), but the game-theoretic VALUES of $3\times n$ and $4\times n$ strips, and the hot-position / temperature classification, remain open. Best known: exact or near-exact ('to within ish') values for small boards ($4\times 8,\ 5\times 6,\ 6\times 6$; Wolfe/Calistrate); Berlekamp's overheating/blockbusting analysis of many $2\times n$ and $3\times n$ positions; new temperatures between $1.5$ and $2$ and a position of temperature exactly $2$ (Drummond-Cole, 'Temperature 2 in Domineering'); CGSuite endgame databases (Uiterwijk-Barton, arXiv:1506.03949). Up to size 15 there is exactly one position (up to symmetry) of temperature $2$ and none higher, supporting Berlekamp's boiling-point-$2$ conjecture, but no general upper-bound theorem exists. An attacker needs: (i) CGSuite / a canonical-form engine to compute exact $3\times n$, $4\times n$ values as $n$ grows; (ii) thermograph computation to read temperatures; (iii) for the boiling-point bound, an overheating / mast-value structural argument.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Unsolved problems in combinatorial games (Games of No Chance 5), Problem B11 | paper |
| REF-02 | New Results for Domineering from CGT Endgame Databases (Uiterwijk-Barton) | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.