I am trying to calculate the number of winning Solitaire games based on a paper by Rob Reijtenbach, linked here for your reference: https://theses.liacs.nl/2169. I made a chart, linked in the above URL, which depicts his calculations. I am trying to find the winning percentage based on seven tableau columns, not just three, and out of 52 cards, not just 12. I don’t know if this is possible since he used optimizations to not blow up his supercomputer, but I figured that I can ask. Thank you.
I suspect you are right, and this is not human/computer accessible right now. Note in the conclusion of the paper by Rob Reijtenbach, they argue that determining if a game is losing is already tricky computationally (and suggest using AI to get approximations/guess relevant games).
This fits my intuition - even if you fix the game (you know all the cards starting positions), there are an awful lot of legal move orders. There is a nice discussion of this problem via this paper: The complexity of Solitaire (abstract link, I haven’t found an accessible copy). A quote from the introduction: “n a paper entitled Solitaire: Man Versus Machine, Yan, Diaconis, Rusmevichientong and Van Roy [10] report that a human expert (and distinguished combinatorialist, former president of the American Mathematical Society!) patiently recorded data on his playing 2000 games of thoughtful solitaire, that is, the intellectually more challenging Klondike in which the complete initial game configuration is revealed to the player at the start of the game. The expert averaged 20 min per game and was able to win the game 36.6% of the time. Pointing to the prohibitive difficulty of obtaining nontrivial mathematical estimates on the odds of winning this common game, Yan et al. then describe heuristics developed using the so-called rollout method, and they report a 70% win rate.”
I haven’t thought hard about the proof of NP-completeness, to see if we expect a lot of complicated and nuanced cases for win vs loss. So it’s plausible that 52 will be solvable, but certainly at some point this problem becomes very hard. If there were a nice pattern, we could likely use it for P vs NP.
I understand, but looking at my chart, is there a pattern to be found within the numbers? For example, is there a function relating the number of columns to the possible games (e.g. 2/165, 3/665280) or number of cards to the possible games (e.g. 12/165, 12/665280), et cetera?) Essentially all I am looking for is a function relating two of these variables.
Ah. I see. For this, someone will need to dive into what ‘after optimizations’ means I think. I don’t think the 6 examples are enough to read it off, a quick search on OEIS for the 3 cards per suit cases finds nothing.
Accirding to the link to the thesis, “optimization” simply means counting games trivially related by permutation as the same game
I’ve been looking for this website but didn’t remember what it was called. Thank you for that at least. And yes, this is probably a long shot to find a function for these numbers because there does seem to be a pattern, but every website that I’ve tried cannot seem to find a graph for them.
