Math Gurus: Probability & Statistics of Solitaire?

Factual Questions
21

I’m not sure that the difference between playing the percentages and an upper bound for wins is at all trivial. The question of whether to move a king from the deck or a king from a column containing cards to a vacant column is pretty tricky early in the game when you don’t how many aces are in the deck or whether you will get any other chances to cycle through the deck.

My only conclusions so far: (i) this problem is a nightmare. I can’t even think how to begin to set it up. (ii) sdimbert’s winning fraction is pretty damn high.

picmr

22

**

Dex, I think that you are on to something here.

**

FWIW, I actually have access to two Palm Pilots and play this game on both. I have already posted my first set of results. My second set of stats is [sup]16[/sup]/[sub]110[/sub] for a winning percentage of 13%.

picmr,

Thanks! :slight_smile:

23

My winning percentage on the 200LX palmtop is around 11%. However, it does depend on what rules you play. I’ve found that there are many situations where I could win, if I did a certain thing which I consider to be cheating so I don’t do it.

The Microsoft version, and the version I wrote for the 200LX, will allow you to move a partial stack of cards to another stack. In other words, if one stack contains 9-8-7-6-5, and you need to get to that 8, it will let you move the 7-6-5 to another 8. I consider this cheating - either you move the whole stack or nothing.

24

Curt,

I don’t think that the move you describe is cheating, according to Hoyle.

And, No, I am not going to provide a cite. I’m too tired.

25

Dex,

Sorry but I still disagree.

Here is sdimbert’s original question:

So his strategy is important. Especially if it is true that the average is only 5%. If that is true your error margin is unacceptable. With his current startegy we do have an estimate of how often he wins, 13%. However, we have not factored in for such things as making no mistakes and not cheating. I think what he is looking for is, given his strategy what percentage would he win if he played perfectly. He is trying to find out how well he is doing relative to a perfect player using his strategy. By ignoring strategy you wont be able to answer his question.

26

I’m not saying ignore strategy. Well, OK, so I am. But I’m saying it in context. Bear with me here.

I’m saying that the winning ratio is (presumably) the number of all games that wind up a WIN (all cards in the aces pile) divided by the number of all possible games. We could determine number of all possible games fairly easily, it’s just straight probability: how many arrangements of the deck are there. Now comes determining the number of all games that end up a WIN.

We first need to define whether a game is a WIN or not. Why is that a problem? Well, for example, if a hundred people play the same game and all 100 people win, we’d call that a WIN. Right? But suppose only 90 people win – the other people didn’t move the right red 8 to the black 9. Or only 50? or only 10? Or only 1?

Suppose the game is set up that no actual human player of the 100 won, but if you could see all the cards, you could determine an illogical but winning strategy?

So how do we count the number of games where you win, if we don’t even know what constitutes a winning game?

Now, my main hypothesis: for MOST games, out of 100 plays, there will be either 100 wins or 100 losses (OK, 99, 'cause some jerk won’t even SEE the black 9.) Let’s not quibble, you know what I mean here: my hypothesis is that standard play (perhaps with an algorithm for decided what to do in certain ambiguous cases) will result in a WIN or in a LOSS. My sub-hypothesis is that the number of games where “strategy” is important, where two different players can get two different results, is small. (NOTE: This is NOT true for Freecell, because there are LOTS of different moves available. But for normal straight solitaire, it’s normally mindless, there aren’t a lot of choices of moves. Freecell claims that EVERY game can be won if you’re clever enough.)

So, bear with me. HYPOTHESIS: The number of games where different players get different results is small. OK? Nowl IF my hypothesis is true, THEN we can approximate the percent of games ending in wins by sampling. What’s called the Monte Carlo method. Playing lots and lots of games and seeing what the imperical results are. OK so far?

IF my hypothesis (that the number of games that would yield different results for different players is small) is false, then we’re stuck. There’s no way to categorize games as wins or losses, and no way to answer the question. It now becomes like predicting the outcome in a game of chess. And, by the way, that leaves us with only one approach – again, to take samples, and hope we can get some coherent results. I’m sure that people know the approximate number of times that an expert chess game ends in a draw, even if they have no idea what the true underlying probability/mathematics are.

So, whether my hypothesis is true or false, I’m still left with the idea of using a sampling approach to estimate the probability. QED.

27

I am not sure if this matters or not, but I don’t really pay much attention when I play solitaire.

I mean, I look at the cards and think about my moves, but, out of the (almost) 300 games I’ve logged, I don’t think that I have been “tricky” more than 4 or 5 times.

By “tricky” I mean skipping a legal play in order to allow some other, better play to come about.

Usually, I just slog through it, starting over whenever I lose, because I know it is just a matter of time until I win.

So, have I proven that a simple computer could win 12 - 15% of the time?

Or is it just that only 12-15% of the hands dealt randomly are winnable?

28

Thanks for making my point. :smiley:

Your concept of winning depends on strategy. Now if we ignore strategy we could state that on average x% of the games will be won. However, for a sophisticated player who has been playing for some time this would be an underestimate IMO, and an overestimate for those just trying out the game the first time.

Let me try to reword what I think sdimbert’s question is (he can correct me if I am wrong). The way I read it he is wondering how he is doing against the perfect player who is using his strategy. That is a player who has perfect recall and has the ability to see all the options. That is, how does he stack up against this “super-human” sdimbert. Not how is he doing against everyone else (although maybe that is what he is interested in).

IIRC chess is solvable via backward induction. The problem is that nobody can see all the possible moves and hence can’t actually solve the problem.

29

[QUOTE]
*Originally posted by kesagiri *
**

Ummmmmmmm… no.

Sorry, kesagiri, but that’s not what I meant at all. What’s the use of creating a construct who can “see all the options?” That’s just silly.

I think we can all agree that there exists some deals from a random deck which are unwinnable by any player of any level of skill or sophistication.

Once that is stipulated, we can turn our attention to the more important (and more complicated) question. How many such deals exist?

I mean, this isn’t a very tuff question, is it? I’m not a math person, but how many different ways are there to arrange 52 cards? Isn’t the answer 52!, as someone pointed out a while ago? If I understand what a factorial is, than 52! = 80,658,175,170,943,900,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000.

Or, 8.06581751709439E+67, if you prefer. (That is a big number.)

So, now that we have established a finite number of deck combinations, wouldn’t the number of possible “deals” be the same? I think so. If so, we have established a finite number of possible “starting deals.” 15% of that number is: 1.20987E+67. Still a big-ass number, but much smaller than the previous one.

I am not sure what my point here is, but I think that the magnitude of these numbers supports Dex’s assertion that strategy is a negligible factor in considering the original question.

So… where is my mistake?

30

sdimbert,

Thanks, I guess you didn’t mean

But actually meant “what percentage of the games are winnable on average ignoring strategy.”

The ‘making no mistakes’ I took to mean that you had perfect recall (i.e. you would know when to play a playable card and when not too) and also, where to place the playable card when given the choice. (This would actually be youd use some sort of probabilitic rule based on past games, probably a Bayesian Perfect strategy or something like that.)

Given the number of games the computer has in its memory I don’t think the possible number of deals is 52! See Brad’s link, there are 32,000 deals. Of course even this number of deals might be quite difficult to calculate how a given strategy would perform.

Think of it this way. Suppose there is only one deal (no 52! or 32,000) then looking at strategy wouldn’t be that tough IMO.

31

I think I might be miffed at having someone tell me what I meant. I’m not sure…

Anyhow, we still haven’t answered the question I asked. Look back up to the OP and read it again. The whole thing. The question is in the last paragraph.

What I was really asking is, do other people win significantly more (or less) than 12% - 15% of the time?

Based on what was said so far, I would guess that Dex would say no, relying on the assertion that strategy does not have an appreciable effect in a game as simple as Klondike. It seems kesagiri swings the other way.

I am still up in the air.

Anyone else play a lot of solitaire? We need more data!

32

Kesagiri, the link I got that off of was discussing Freecell, not Klondike.

I haven’t found any info on how MS Klondike gets its deals, or how many possibilities it restricts itself to. It wouldn’t surprise me if it was very similar to Freecell, though. Maybe somebody else knows…

33

Oh yes, I see “…the way I play…” doesn’t refer to strategy. How silly of me. Sheesh.

Nope, strategy doesn’t affect one chances of winning a game…nope.[/sarcasm]

34

[QUOTE]
*Originally posted by kesagiri *
**

Hey, do us all a favor, OK? Thicken the skin a bit and leave the sarcasm at home. :rolleyes:

The question you have so easily dismissed is exactly what I was asking. There is no doubt in my mind that there are many people who are better solitaire players than I am. What I want to know is if their additional skill/strategy/know-how translates into a significant increase in winning percentage or not?

Now, Dex (and others) have theorized that the answer is no. You claim otherwise. So, prove it.

35

Dex seems to have concluded a priori that the answer is no. I however think he is not realizing what a strategy is. For example:

Wouldn’t his algorithm correspond to a strategy? Couldn’t different algorithm’s make different “decisions” based on different criteria? Seems that way to me.

Further he is limiting himself to the case where a win is defined as all players either win the game or lose. I contend that different strategies will have different success rates, his test couldn’t test for strategies as it excludes the cases when some people win and some don’t.

No, not okay. This is not an hypothesis, but an assumption. You have defined winning in such a way as to exclude the case where some players win and others loose.

Maybe not, how about defining winning given a strategy. That is a game is winnable with strategy S1, but not with strategy S2. This would allow us to test the hypothesis. Of course we’d have to try and figure out when a player makes a bad choice out of carelessness vs. strategy. A computer simulation might help here.

36

There are most definitely situations where I’ve won a game that I would have lost, had I not used my strategy, and games where I lost where I would have won, had I had acess to or recall of a greater amount of information. Further, these games seem to occur more frequently than one in a hundred (although I’ve never counted), and would thus be a change of more than one percentage point.

As for defining deals as “win” or “loss”, let’s consider a hypothetical computer (hypothetical because this would probably take a real computer longer than the lifetime of the Universe), that remembers the position of every card which it has seen, and based on all available information, computes the probability of winning, for any given possible move at each decision point. I think that we can safely say that this computer employs perfect strategy. Game theory doesn’t even come into play, since there is no intelligent opponent basing decisions on our actions.
Now, we take our perfect computer, and let it try all of the 52! possible deals, and record when it wins and loses. We now have an absolute number of games that will be won with perfect strategy, and hence a win probability. This number may be extremely difficult (read: impossible) to compute, but it is possible to define it.
Now, for the third step: We write a real computer program that uses a set of heuristics such as those I listed to play as well as we can design it, to (hopefully) approximate the hypothetical perfect strategy. We then run this program on a thousand, or a million, or 2[sup]15[/sup], or however many random deals, to approximate the 52! , and count the results. Further, we could write several different strategies for our computer, including a mindless one (always make a move if possible, and when more than one is possible, choose one randomly), and compare the performance of the various algorithms, and thus test Dex’s claim that strategy is insignificant. This problem is by no means intractable, especially to any programmers who have already written a Solitaire game.

37

I wrote a program using a simple strategy to play solitaire. It does not allow splitting of a sequence once it is made. I had it play one million games with each of three different methods of dealing from the hand: 3 cards at a time (7.55% wins), 2 cards at a time (15.96%) and 1 card a time (29.45%).

The usual method of playing is dealing 3 cards at a time, but by looking at all the cards in the hand and very careful planning of moves based on the order of those cards, it should be possible to increase the winning percentage, but not any higher than with the 1 at a time method. The one at a time method gives full access to every card in the hand, since you are allowed to go through the hand as many times as you want (unlike Vegas rules). Plotting when to use playable cards with the 3 at a time method greatly increases the accessiblity of the cards in the hand, but doesn’t give full access, so it shouldn’t be quite as good as one at a time dealing.

38

Hmmm, well it certainly isn’t non-cooperative game theory, but I think you could still use game theories structure to help look at this problem.

As for your computer, I was thinking more in probabilistic terms. That is given what the computer knows, when it moves the last card from one of the seven stacks to one of the ace stacks what is the probability that the card uncovered is going to be a red king for example.

That is we have

Prob(Red King|I)

Where I is what the information available at that time.

Then once we observe the new card we can revise the above probability using Bayes Theorem.

There have been some interesing applications of Beyesian Learning to junk e-mail filters. My intuition tells me something similar might work here.

39

**Chronos[/]: I am confused by your comments. You seem to be saying, on the one hand, that writing a program to play solitaire (or building a computer to run said program) is imposible, while on the other hand, you say that it can be done. I am sure that the fault is mine - I am misunderstanding you. I just don’t see where.

Manlob: Your program seems to be lousier than even I am, since I average 15% playing three-at-a-time.

**kesagiri/b]: You have officially moved over my head. Rock on! Just keep the rest of us idjits posted and try to use small words when possible. :slight_smile:

40

Sorry about that, sdimbert. What I meant was that it’s practically impossible (but still theoretically possible) to build a computer to play perfect solitaire, but that it should be easy to make a computer that’s just pretty darn good, but imperfect.

*kesagiri, that may well work, but I didn’t realize that that was considered game theory. Consider me corrected.