Skip to main content
Top

2017 | OriginalPaper | Chapter

Combining Combinatorial Game Theory with an \(\alpha \)-\(\beta \) Solver for Clobber: Theory and Experiments

Authors : Jos W. H. M. Uiterwijk, Janis Griebel

Published in: BNAIC 2016: Artificial Intelligence

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

Combinatorial games are a special category of games sharing the property that the winner is by definition the last player able to move. To solve such games two main methods are being applied. The first is a general \(\alpha \)-\(\beta \) search with many possible enhancements. This technique is applicable to every game, mainly limited by the size of the game due to the exponential explosion of the solution tree. The second way is to use techniques from Combinatorial Game Theory (CGT), with very precise CGT values for (subgames of) combinatorial games. This method is only applicable to relatively small (sub)games. In this paper, which is an extended version of [7], we show that the methods can be combined in a fruitful way by incorporating an endgame database filled with CGT values into an \(\alpha \)-\(\beta \) solver.
We apply this technique to the game of Clobber, a well-known all-small combinatorial game. Our test suite consists of 20 boards with sizes up to 18 squares. An endgame database was created for all subgames of size 8 and less. The CGT values were calculated using the CGSUITE package. Experiments reveal reductions of at least 75% in number of nodes investigated.

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!

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!

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!

Literature
1.
go back to reference Albert, M.H., Grossman, J.P., Nowakowski, R.J., Wolfe, D.: An introduction to Clobber. Integers Electron. J. Comb. Number Theor. 5(2), 12 p. (2005) Albert, M.H., Grossman, J.P., Nowakowski, R.J., Wolfe, D.: An introduction to Clobber. Integers Electron. J. Comb. Number Theor. 5(2), 12 p. (2005)
2.
go back to reference Albert, M.H., Nowakowski, R.J., Wolfe, D.: Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters, Wellesley (2007)MATH Albert, M.H., Nowakowski, R.J., Wolfe, D.: Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters, Wellesley (2007)MATH
3.
go back to reference 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) 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)
4.
go back to reference Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for your Mathematical Plays, vol. 1–2. Academic Press, London (1982). 2nd edition, in four volumes: vol. 1 (2001), vols. 2, 3 (2003), vol. 4 (2004), A K Peters. Wellesley Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for your Mathematical Plays, vol. 1–2. Academic Press, London (1982). 2nd edition, in four volumes: vol. 1 (2001), vols. 2, 3 (2003), vol. 4 (2004), A K Peters. Wellesley
5.
go back to reference Claessen, J.: Combinatorial game theory in Clobber. Master’s thesis, Maastricht University (2011) Claessen, J.: Combinatorial game theory in Clobber. Master’s thesis, Maastricht University (2011)
6.
go back to reference Conway, J.H.: On numbers and games. Academic Press, London (1976). 2nd edition A K Peters, Natick, MA (2001) Conway, J.H.: On numbers and games. Academic Press, London (1976). 2nd edition A K Peters, Natick, MA (2001)
7.
go back to reference Griebel, J., Uiterwijk, J.W.H.M.: Combining combinatorial game theory with an \(\alpha \)-\(\beta \) solver for Clobber. In: Bosse, T., Bredeweg, B. (eds.), BNAIC 2016: Proceedings of the 28th Benelux Conference on Artificial Intelligence, pp. 48–55. University of Amsterdam/Vrije Universiteit Amsterdam, Amsterdam (2016) Griebel, J., Uiterwijk, J.W.H.M.: Combining combinatorial game theory with an \(\alpha \)-\(\beta \) solver for Clobber. In: Bosse, T., Bredeweg, B. (eds.), BNAIC 2016: Proceedings of the 28th Benelux Conference on Artificial Intelligence, pp. 48–55. University of Amsterdam/Vrije Universiteit Amsterdam, Amsterdam (2016)
10.
go back to reference Müller, M.: Solving \(5 \times 5\) Amazons. In: The 6th Game Programming Workshop (GPW 2001), Hakone (Japan), 2001, vol. 14, IPSJ Symposium Series, pp. 64–71 (2001) Müller, M.: Solving \(5 \times 5\) Amazons. In: The 6th Game Programming Workshop (GPW 2001), Hakone (Japan), 2001, vol. 14, IPSJ Symposium Series, pp. 64–71 (2001)
11.
go back to reference Müller, M., Li, Z.: Locally informed global search for sums of combinatorial games. In: van den Herik, H.J., Björnsson, Y., Netanyahu, N.S. (eds.) CG 2004. LNCS, vol. 3846, pp. 273–284. Springer, Heidelberg (2006). doi:10.1007/11674399_19 CrossRef Müller, M., Li, Z.: Locally informed global search for sums of combinatorial games. In: van den Herik, H.J., Björnsson, Y., Netanyahu, N.S. (eds.) CG 2004. LNCS, vol. 3846, pp. 273–284. Springer, Heidelberg (2006). doi:10.​1007/​11674399_​19 CrossRef
13.
go back to reference Snatzke, R.G.: Exhaustive search in the game Amazons. In: Nowakowski, R.J. (ed.) More Games of No Chance, Proceedings of MSRI Workshop on Combinatorial Games, Berkeley, CA, July 2000, MSRI Publ., vol. 42, pp. 261–278. Cambridge University Press, Cambridge (2002) Snatzke, R.G.: Exhaustive search in the game Amazons. In: Nowakowski, R.J. (ed.) More Games of No Chance, Proceedings of MSRI Workshop on Combinatorial Games, Berkeley, CA, July 2000, MSRI Publ., vol. 42, pp. 261–278. Cambridge University Press, Cambridge (2002)
15.
go back to reference Song, J.: An enhanced solver for the game of Amazons. Master’s thesis, University of Alberta (2013) Song, J.: An enhanced solver for the game of Amazons. Master’s thesis, University of Alberta (2013)
16.
go back to reference Tegos, T.: Shooting the last arrow. Master’s thesis, University of Alberta (2002) Tegos, T.: Shooting the last arrow. Master’s thesis, University of Alberta (2002)
17.
go back to reference Uiterwijk, J.W.H.M., Barton, M.: New results for Domineering from combinatorial game theory endgame databases. Theoret. Comput. Sci. 592, 72–86 (2015)MathSciNetCrossRefMATH Uiterwijk, J.W.H.M., Barton, M.: New results for Domineering from combinatorial game theory endgame databases. Theoret. Comput. Sci. 592, 72–86 (2015)MathSciNetCrossRefMATH
Metadata
Title
Combining Combinatorial Game Theory with an - Solver for Clobber: Theory and Experiments
Authors
Jos W. H. M. Uiterwijk
Janis Griebel
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-67468-1_6

Premium Partner