11 x 11 Domineering Is Solved: The First Player Wins

Jos W. H. M. Uiterwijk*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

Abstract

We have developed a program called mudos (maastricht university domineering solver) that solves domineering positions in a very efficient way. It enables the solution of known positions (up to the 10\times 1010\times 10 board) to be much quicker.more importantly, it enables the solution of 11\times 1111\times 11 domineering, a board size that up till now was far out of the reach of previous domineering solvers. The solution needed the investigation of 259,689,994,008 nodes, using almost half a year of computation time on a single simple desktop computer. The results show that under optimal play the first player wins 11\times 1111\times 11 domineering, irrespective whether vertical or horizontal starts.in addition, several other new boards were solved. Using the convention that vertical starts, the 8\times 158\times 15, 11\times 911\times 9, 12\times 812\times 8, 12\times 1512\times 15, 14\times 814\times 8, and 17\times 617\times 6 boards are all won by vertical, whereas the 6\times 176\times 17, 8\times 128\times 12, 9\times 119\times 11, and 11\times 1011\times 10 boards are all won by horizontal.
Original languageEnglish
Title of host publicationComputers and Games: 9th International Conference, CG 2016, Leiden, The Netherlands, June 29 -- July 1, 2016, Revised Selected Papers
EditorsAske Plaat, Walter Kosters, Jaap van den Herik
Place of PublicationCham
PublisherSpringer
Pages129-136
Number of pages8
ISBN (Print)978-3-319-50935-8
DOIs
Publication statusPublished - 2016

Publication series

SeriesLecture Notes in Computer Science
Volume10068

Cite this