Solving Cram using Combinatorial Game Theory
| Autor: | Uiterwijk, JWHM, Cazenave, Tristan, van den Herik, Jaap, Saffidine, Abdallah, Wu, I-Chen |
|---|---|
| Přispěvatelé: | DKE Scientific staff, RS: FSE DACS NSO |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
050101 languages & linguistics
Theoretical computer science Process (engineering) Computer science BETA (programming language) 05 social sciences ComputingMilieux_PERSONALCOMPUTING Combinatorial game theory 02 engineering and technology Solver Alpha (programming language) 0202 electrical engineering electronic engineering information engineering Domain knowledge 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences computer computer.programming_language |
| Zdroj: | Advances in Computer Games: 16th International Conference, ACG 2019, 91-105 ISSUE=1;STARTPAGE=91;ENDPAGE=105;TITLE=Advances in Computer Games Lecture Notes in Computer Science ISBN: 9783030658823 ACG |
| ISSN: | 0302-9743 |
| DOI: | 10.1007/978-3-030-65883-0_8 |
| Popis: | In this paper we investigate the board game Cram, which isan impartial combinatorial game, using an alpha-beta solver. Since Cram is anotoriously hard game in the sense that it is difficult to obtain reliableand useful domain knowledge to use in the search process, we decided torely on knowledge obtained from Combinatorial Game Theory (CGT).The first and most effective addition to our solver is to incorporateendgame databases prefilled with CGT values (nimbers) for all positionsfitting on boards with at most 30 squares. This together with twoefficient move-ordering heuristics aiming at early splitting positions intofragments fitting in the available databases gives a large improvement ofsolving power. Next we define five more heuristics based on CGT thatcan be used to further reduce the sizes of the search trees considerably.In the final version of our program we were able to solve all odd x oddCram boards for which results were available from the literature (evenx even and odd x even boards are trivially solved). Investigating newboards led to solving two boards not solved before, namely the 3 x 21board, a first-player win, and the 5 x 11 board, a second-player win. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|