0
Is there a pattern?
(docs.google.com)
General community for all things mathematics on @lemmy.world
Submit link and text posts about anything at all related to mathematics.
Questions about mathematical topics are allowed, but NO HOMEWORK HELP. Communities for general math and homework help should be firmly delineated just as they were on reddit.
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.
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.
Accirding to the link to the thesis, "optimization" simply means counting games trivially related by permutation as the same game