The Shortest Game of Chinese Checkers and Related Problems

DOI10.1515/INTEG.2009.003MaRDI QIDQ3625132zbMATH OpenOpenAlexFDO

Authors George I. Bell

Publication date 9 May 2009

Published in Integers (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.1245, https://eudml.org/doc/129798, http://www.emis.de/journals/INTEGERS/papers/jg1/jg1.Abstract.html, http://www.integers-ejcnt.org/vol9.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Stern-Halma

Mathematics Subject Classification ID

2-person games (91A05)

Abstract: 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.

Recommendations

• Optimal Leapfrogging
• Checkers is solved
• Diagonal peg solitaire
• scientific article; zbMATH DE number 988828
• N by N Checkers is Exptime Complete

Cited in

(3)

• Optimal Leapfrogging
• scientific article; zbMATH DE number 5590109 (Why is no real title available?)
• Solitaire Mancala Games and the Chinese Remainder Theorem

This page was built for publication: The Shortest Game of Chinese Checkers and Related Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3625132)