Klondike solitaire solvability
Voima, Mikko (2021)
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-2021060213520
https://urn.fi/URN:NBN:fi:amk-2021060213520
Tiivistelmä
Klondike solitaire remains one of the most popular single-player card games, but the exact odds of winning were discovered as late as 2019. The objective of this thesis was to study Klondike solitaire solvability from the game design point of view. The purpose of this thesis was to develop a solitaire prototype and use it as a testbed to study the solvability of Klondike.
The theoretical section explores the card game literature and the academic studies on the solvability of Klondike solitaire. Furthermore, Klondike solitaire rule variations and the game mechanics are analysed. In the practical section a Klondike game prototype was developed using Unity game engine. A new fast recursive method was developed which can detect 2.24% of random card configurations as unsolvable without simulating any moves.
The study indicates that determining the solvability of Klondike is a computationally complex NP-complete problem. Earlier studies proved empirically that approximately 82% of the card configurations are solvable. The method developed in this thesis could detect over 12% of the unsolvable card configurations without making any moves. The method can be used to narrow the search space of brute-force searches and applied to other problems. Analytical research on Klondike solvability is called for because the optimal strategy is still not known.
The theoretical section explores the card game literature and the academic studies on the solvability of Klondike solitaire. Furthermore, Klondike solitaire rule variations and the game mechanics are analysed. In the practical section a Klondike game prototype was developed using Unity game engine. A new fast recursive method was developed which can detect 2.24% of random card configurations as unsolvable without simulating any moves.
The study indicates that determining the solvability of Klondike is a computationally complex NP-complete problem. Earlier studies proved empirically that approximately 82% of the card configurations are solvable. The method developed in this thesis could detect over 12% of the unsolvable card configurations without making any moves. The method can be used to narrow the search space of brute-force searches and applied to other problems. Analytical research on Klondike solvability is called for because the optimal strategy is still not known.