The shortest game of Chinese Checkers and related problems

Autor:	Bell, George I.
Rok vydání:	2008
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics Computer Science - Data Structures and Algorithms 00A08 97A20
Zdroj:	INTEGERS: Electronic Journal of Combinatorial Number Theory 9 (2009) #G01
Druh dokumentu:	Working Paper
Popis:	In 1979, David Fabian found a complete game of two-person Chinese Checkers in 30 moves (15 by each player) [Martin Gardner, Penrose Tiles to Trapdoor Ciphers, MAA, 1997]. This solution requires that the two players cooperate to generate a win as quickly as possible for one of them. We show, using computational search techniques, that no shorter game is possible. We also consider a solitaire version of Chinese Checkers where one player attempts to move her pieces across the board in as few moves as possible. In 1971, Octave Levenspiel found a solution in 27 moves [Ibid.]; we demonstrate that no shorter solution exists. To show optimality, we employ a variant of A* search, as well as bidirectional search. Comment: 22 pages, 10 figures; published version
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/0803.1245 Zobrazit plný text záznamu View this record from Arxiv