New results for Domineering from combinatorial game theory endgame databases

DOI10.1016/J.TCS.2015.05.017zbMATH Open1331.91053arXiv1506.03949OpenAlexW1895534228MaRDI QIDQ500968FDOQ500968

Authors: Jos W. H. M. Uiterwijk, Michael Bartoň 

Publication date: 8 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We have constructed endgame databases for all single-component positions up to 15 squares for Domineering, filled with exact Combinatorial Game Theory (CGT) values in canonical form. The most important findings are as follows. First, as an extension of Conway's [8] famous Bridge Splitting Theorem for Domineering, we state and prove another theorem, dubbed the Bridge Destroying Theorem for Domineering. Together these two theorems prove very powerful in determining the CGT values of large positions as the sum of the values of smaller fragments, but also to compose larger positions with specified values from smaller fragments. Using the theorems, we then prove that for any dyadic rational number there exist Domineering positions with that value. Second, we investigate Domineering positions with infinitesimal CGT values, in particular ups and downs, tinies and minies, and nimbers. In the databases we find many positions with single or double up and down values, but no ups and downs with higher multitudes. However, we prove that such single-component ups and downs easily can be constructed. Further, we find Domineering positions with 11 different tinies and minies values. For each we give an example. Next, for nimbers we find many Domineering positions with values up to *3. This is surprising, since Drummond-Cole [10] suspected that no *2 and *3 positions in standard Domineering would exist. We show and characterize many *2 and *3 positions. Finally, we give some Domineering positions with values interesting for other reasons. Third, we have investigated the temperature of all positions in our databases. There appears to be exactly one position with temperature 2 (as already found before) and no positions with temperature larger than 2. This supports Berlekamp's conjecture that 2 is the highest possible temperature in Domineering.

Full work available at URL: https://arxiv.org/abs/1506.03949

Recommendations

• scientific article; zbMATH DE number 2214425
• New values in Domineering
• scientific article; zbMATH DE number 2214427
• Misère domineering on \(2 \times n\) boards
• scientific article

zbMATH Keywords

numberscombinatorial game theoryDomineeringinfinitesimalsnimbers including *2 and *3temperaturestinies and miniesups and downs

Mathematics Subject Classification ID

Combinatorial games (91A46)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Blockbusting and domineering
• An analysis of alpha-beta pruning
• New values in Domineering
• Solving \(8\times 8\) Domineering
• Title not available (Why is that?)
• Games solved: Now and in the future
• Snakes in Domineering games
• New results of exhaustive search in the game Amazons
• An update on Domineering on rectangular boards
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Winner determination algorithms for graph games with matching structures
• Bounding game temperature using confusion intervals
• Winner determination algorithms for graph games with matching structures
• Title not available (Why is that?)
• Polymerization and crystallization of snowflake molecules in Domineering
• New values in Domineering
• Title not available (Why is that?)
• Simplicial complexes are game complexes
• Canonical forms of uptimals
• Toppling conjecture

This page was built for publication: New results for Domineering from combinatorial game theory endgame databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q500968)