Abstract
Combinatorial games are a special category of games sharing
the property that the winner is by denition the last player able to move.
To solve such games two main methods are being applied. The rst 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 paper1 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.
the property that the winner is by denition the last player able to move.
To solve such games two main methods are being applied. The rst 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 paper1 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.
Original language | English |
---|---|
Title of host publication | BNAIC 2016: Artificial Intelligence |
Subtitle of host publication | 28th Benelux Conference on Artificial Intelligence, Amsterdam, The Netherlands, November 10–11, 2016, Revised Selected Papers |
Publisher | Springer Verlag |
Pages | 78-92 |
Number of pages | 15 |
Volume | 765 |
ISBN (Print) | 9783319674674 |
DOIs | |
Publication status | Published - 2017 |
Event | 28th Annual Benelux Conference on Artificial Intelligence (BNAIC) - Amsterdam, Netherlands Duration: 10 Nov 2016 → 11 Nov 2016 https://bnaic2016.cs.vu.nl/ |
Publication series
Series | Communications in Computer and Information Science |
---|---|
Volume | 765 |
ISSN | 1865-0929 |
Conference
Conference | 28th Annual Benelux Conference on Artificial Intelligence (BNAIC) |
---|---|
Country/Territory | Netherlands |
City | Amsterdam |
Period | 10/11/16 → 11/11/16 |
Internet address |
Keywords
- SEARCH