For card games like Klondike, and other variants of Solitaire, can the odds of winning be determined explicitly, by direct consideration and calculation of the possible permutations? Or, is the solution found only by running a simulation repeatedly and then using the empirically derived value? I’m pretty sure that it must be the latter, but am curious.
More generally, are there some, presumably simpler, variations of Solitaire for which the odds of winning can be calculated explicitly? For example, there’s a version of solitaire (the name I can’t remember) where you deal four cards onto four piles. If two or more of any one suit are showing, you keep only the highest card showing of that suit. If/when all four of the top cards for the four piles are of different suits, you deal out four more cards, one onto each pile (column). If a pile (column) gets emptied, you can transfer the top card of one of the remaining three piles to the empty space, and use that as the first card of the pile. You win if you’re left with only the four aces. <== my sense is that the odds of winning at this game may be explicitly calculable (but I wouldn’t want to try! :eek: )
Any well defined game (solitaire or not) can of course have its outcomes determined directly. The issue is the complexity of turning the formulas into a number. I.e., doing the calculation. Some games are easy, some not so easy (NP-Complete or worse).
Note that you never, ever, trust a simulation to tell you the actual outcome of a game. A low probability but high end result situation may be missed and you have garbage.
You could explicitly calculate the odds but not before the universe collapses in a Big Crunch. Even setting up a simulation would have its own challenges but might be possible.
I think (but am not prepared to prove) that it would be possible to mathematically determine the odds of a winnable game, but that it would be computationally intractable to do so. There are 52! ways to shuffle the deck, which is about 5.38 x 10[sup]67[/sup] (quick calc, may be off). If you could analyze 1,000 shuffles per second it would take about 1.7 x 10[sup]57[/sup] years to complete the analysis.
Simulation is usually used in such cases, such as in schedule analysis where each task has a range of possible completion dates. Such simulation is called Monte Carlo simulation. You could use a pseudo-random number generator to develop a card-shuffling algorithm. Then you would have to have a method to determine whether a given shuffle produces a winnable game. This is much more difficult, I think, than *defining * a shuffle that produces a winning game, since for the latter you could start with a winning outcome and work backwards.
The other thing to remember with classic Klondike is that it is not completely deterministic. The player makes choices which can affect the outcome. So an algorithm to determine whether a given shuffle is winnable would have to branch each time the player could make a decision. This could lead to a large number of branches rather quickly, presenting its own computational challenges.
BTW if you want to guarantee that you’re playing a winnable game, try this.
Clock Patience is one such Solitaire variety. Play is entirely deterministic. Wikipedia gives the odds of winning as 1/13, but doesn’t discuss their calculation – I’m pretty sure the odds of winning are exactly the odds of dealing the first 13 cards in such a way that they do not contain a cycle.