Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Using Partial Tablebases in Breakthrough Read chapter Read first chapter

2016 | OriginalPaper | Chapter

11 \(\times \) 11 Domineering Is Solved: The First Player Wins

Author : Jos W. H. M. Uiterwijk

Published in: Computers and Games

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 10\) board) to be much quicker.
More importantly, it enables the solution of \(11\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 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 15\), \(11\times 9\), \(12\times 8\), \(12\times 15\), \(14\times 8\), and \(17\times 6\) boards are all won by Vertical, whereas the \(6\times 17\), \(8\times 12\), \(9\times 11\), and \(11\times 10\) boards are all won by Horizontal.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Nash Equilibrium in Mastermind
next chapter A Reverse Hex Solver
Footnotes
1
We note that solving a board investigating a single node is not exactly the same as perfectly solving a board, since in the latter the board is solved using characteristics of the board solely, without generating the possible moves, whereas in the former the possible moves are generated, but immediately proven to contain at least one winning move or only losing moves.
 
2
Although Drummond-Cole determined the outcome classes for \(8\times 26\) and \(26\times 8\) (H and V), these results were not included in his table of known outcome classes for Domineering [11].
 
Literature
1.
Albert, M.H., Nowakowski, R.J., Wolfe, D.: Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters, Wellesley (2007)MATH
2.
Barton, M., Uiterwijk, J.W.H.M.: Combining combinatorial game theory with an \(\alpha \)-\(\beta \) solver for Domineering. In: Grootjen, F., Otworowska, M., Kwisthout, J. (eds.) BNAIC 2014 - Proceedings of the 26th Benelux Conference on Artificial Intelligence, pp. 9–16. Radboud University, Nijmegen (2014)
3.
4.
Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for Your Mathematical Plays. Academic Press, London (1982). 2nd edn. A K Peters, Wellesley, MA, in four volumes: vol. 1 (2001), vols. 2, 3 (2003), vol. 4 (2004)MATH
5.
Breuker, D.M.: Personal communication (2014)
6.
Breuker, D.M., Uiterwijk, J.W.H.M., van den Herik, H.J.: Replacement schemes and two-level tables. ICCA J. 19, 175–180 (1996)
7.
Breuker, D.M., Uiterwijk, J.W.H.M., van den Herik, H.J.: Solving 8 \(\times \) 8 Domineering. Theor. Comput. Sci. (Math Games) 230, 195–206 (2000)MathSciNetCrossRefMATH
8.
Bullock, N.: Domineering: solving large combinatorial search spaces. M.Sc. thesis, University of Alberta (2002)
9.
Bullock, N.: Domineering: solving large combinatorial search spaces. ICGA J. 25, 67–84 (2002)
10.
Conway, J.H.: On Numbers and Games. Academic Press, London (1976)MATH
11.
12.
13.
van den Herik, H.J., Uiterwijk, J.W.H.M., van Rijswijck, J.: Games solved: now and in the future. Artif. Intell. 134, 277–311 (2002)CrossRefMATH
14.
15.
16.
Lachmann, M., Moore, C., Rapaport, I.: Who wins Domineering on rectangular boards? In: Nowakowski, R.J. (ed.) More Games of No Chance, vol. 42, pp. 307–315. Cambridge University Press, MSRI Publications, Cambridge (2002)
17.
18.
Uiterwijk, J.W.H.M.: Perfectly solving Domineering games. In: Cazenave, T., Winands, M.H.M., Iida, H. (eds.) Computer Games, Workshop on Computer Games, CGW at IJCAI 2013, Beijing, China, Revised Selected Papers, vol. 408, pp. 97–121. Communications in Computer and Information Science (2014)
19.
Uiterwijk, J.W.H.M.: The impact of safe moves on perfectly solving Domineering boards. Part 1: analysis and experiments with 1-step safe moves. ICGA J. 37(2), 97–105 (2014)CrossRef
20.
Uiterwijk, J.W.H.M.: The impact of safe moves on perfectly solving Domineering boards. Part 2: analysis and experiments with multi-step safe moves. ICGA J. 37(3), 144–160 (2014)CrossRef
21.
Uiterwijk, J.W.H.M.: The impact of safe moves on perfectly solving Domineering boards. Part 3: theorems and conjectures. ICGA J. 37(4), 207–213 (2014)CrossRef
22.
23.
Metadata
Title
11  11 Domineering Is Solved: The First Player Wins
Author
Jos W. H. M. Uiterwijk
Copyright Year
2016
Book
Computers and Games

Print ISBN: 978-3-319-50934-1

Electronic ISBN: 978-3-319-50935-8

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-50935-8_12

Premium Partner

    Image Credits