Saturday, May 23, 2009

Winning Solitaire?

Okay, I admit it: Sometimes I play Microsoft Solitaire (i.e., "Klondike" Solitaire: draw 3, with 3 re-deals, Vegas scoring). Of course, it's the most widely-played computer game of all time. Occasionally I go on these benders and play it quite a bit for a few days.

Most games are lost, but I can usually eke out a win in about 20-30 minutes of playing. However, just today I probably lost 30+ games in a row over maybe 2 hours. Still no win so far today. I have to be careful, because I get in a habit of quickly hitting "deal" instantly after a loss (my "hit", if you will), and after an extended time by hand starts to go numb and I start making terrible mistakes because my eyesight starts getting all wonky. (Is it fun? No, I feel a vague sense of irritation the whole time I'm playing, until I actually win and can finally close the application. Hopefully.)

So this brings up the question: What percentage of games should you be able to win? Obviously I don't know, but my intuition says around ~20% or so maximum. I'm also entertaining the idea of building a robot solver, improving its play, and seeing what fraction of games it can win. Apparently this an actually outstanding research problem; Professor Yan at MIT wrote that this is in fact “one of the embarrassments of applied mathematics” in 2005.

The other thing is that all of the work done on the problem apparently uses some astoundingly variant definitions for the game. First, the "solvers" that I see are all based on the variant game of "Thoughtful Solitaire", apparently preferred by mathematicians because it gives you full information (i.e., known location of all cards), and are therefore encouraged to spend hours of time considering just a few moves at a time (gads, save me from these frickin' mathematicians like that! Deal with real-world incomplete information, for god's sake!).

Secondly, they use the results from this "Thoughtful Solitaire" (full information, recall; claiming 82% to 91% success rate) simultaneously for the percentage of regular Solitaire games that are "solvable". But this meaning of "solvable" is only a hypothetical solution rate for an all-knowing player; that is, there are many moves during a regular game of Solitaire that lead to dead-ends, that can only be avoided by sheer luck, for the non-omniscient player. If they're careful the researchers correctly call this an "upper bound on the solution rate of regular Solitaire" (and my intuition tells me that it's a very distant bound); if they're really, really sloppy then they use the phrases "odds of winning" and "percent solvable" interchangably (when they're not remotely the same thing).

So currently we're completely in the dark about what the success rate of the best (non-omniscient) player would be in regular Solitaire. I'll still conjecture that it's got to be under 50%.

1. I would have kind of thought that the odds of winning Klondike would be calculable and known (hence it being “one of the embarrassments of applied mathematics”). On the other hand, 52! Is pretty damn big.

BTW, losing 30+ games in a row's got to suck. But if it only took 2 hours, that's an improvement over losing a couple games of StarCraft and *still* not getting that fix. Not that I know anyone who's been susceptible to that.

2. Ha! Indeed.

I can see that one of the problems with Solitaire is that, in addition to the 52! possible shuffles, you also have to account for (a) the hidden information, and more keenly, (b) what is the "best" strategy?

I could imagine an tree-searching system where, at every possible move, it maps out every possible hidden card-lay and maps out the most-likely "best" move (starting from 45! and working your way down each move), but that would take a good bit of processing power.

3. I've been tracking my 3-card solitaire hands by batches of 100 hands. (NB: I have limited recall of the last two moves, so I can peek at a hidden card).
Result: my average for 2000 hands is 37.6% wins and 39.2% for the last 500 (i feel like my insights are improving ;-) )
Best streak is 7 wins in a row, and worst is 13 losses in a row. Happy to share more data.

1. Thanks for the info! Although I must say that being able to peek at a card makes for a very different game, that's really a lot of info to take advantage of. And I don't know how many draw-cards/passes you're playing with?

I've got a computerized solver written (no peeking) that gets 7.4% wins for draw-3/pass-3, or 52.9% for draw-1/pass-infinite, I keep meaning to write that up at some point.

4. I put together a C++ program to try and figure out what the odds are. My version has infinite number of go rounds on the play stack (no limit of three re-deals). The results are about one win in 5.4 games played. The statistical set was millions of games played. This past weekend, I modified the program to try and solve deals. I have a very small sample set but it tentatively appears that about 50% of lost hands are solvable. This is very small statistical set mind you. The real problem is, when a deal isn't solvable, it's taking the program hours and millions of tries to figure that out. I'm going to try running on a computer with more power and multi-thread the whole thing. The task is still monumental and will require lots of computing time to build up a decent statistical set. There's also the business of random number generation for dealing decks. I'm using STL mersenne_twister and a real hardware generator will eventually be needed. I also need to improve the performance. It uses STL and I wasn't trying to make it fast, just thorough.

All of these results will be rendered moot when someone finds a bug in my program. I put some statistics and the source code here if it interests you:

http://webpages.charter.net/jstefan/solitaire.htm

5. I've been using "F2" at the initial deal to abandon a deal before I play, this does not impact my score, and I only play hands where I can uncover at least 3 covered cards. I have even been using the "undo" when faced with 2 possible choices for uncovering another card. Even doing this I'm only able to keep my win percentage at about 8%. My take is Microsoft Solitaire is not worth playing because it simply is not using fair randomness. Whether this is from lazy programmers or they're simply being jerks I cannot say, but I can say my win average should be higher given my selectiveness with playing. It's no fun playing a game where the odds of winning are so heavily stacked against you.

1. I used to do as you and reject games that have no opportunity to "reveal" on startup. But, over time and out of curiosity, I found that it really made no difference in my overall win percentage. I have been playing solitaire for as long as I have had a computer and I reset after about 5000 games since beyond that it is nearly impossible to improve. I have declined from 27% 10 years ago to 22-23% now (age, 70 yrs.,not MS solitaire is likely the issue.. I find that the reset helps to prove new strategies and steps that I develop as I go.

2. Gary, what parameters are you playing with (draw one/three, standard scoring)?

6. I have played 2987 hands over a 3 year period and have won 614 times for a win percentage of 20.5%. My high score is 8907 after winning a hand in 87 seconds. How does this stack up to you others out there?

1. I found that the game changed under Windows 7 from XP. I was able to get higher scores with XP.
Below are some combinations of score/time (Maybe someone knows the algorithm for score? I have had different scores with the same time, so #moves must also be in there somewhere)
Score,Time
10136,74
9299,81
8494,89
8112,94
7957,96
7500,103

2. Here's what it says in the Win7 Help page -- "Under Standard scoring, you receive five points for moving a card from the deck to a column, and 10 points for each card added to a Home stack. If a game takes more than 30 seconds, you also receive bonus points based on the time it takes to finish. The bonus formula: 700,000 divided by total game time in seconds. Thus, the highest possible Standard score is 24,113!"

I don't think that formula has changed between versions. Note that if you move from deck -> home directly (+10) you get less points than if you go deck -> column -> home (+15). That's about all I know, as personally I play by Vegas scoring myself.

7. I have played 2679 and won 1751. I can not get past 63% though, and even though I have started afresh on other machines the win percentage always seems to hover around 63%....

8. You might like http://www.solitairecraving.com/. There, the games are "solvable", in the sense that a solution exists. You get to replay the game until you solve it. It seems to me that's preferable to losing freshly dealt games because you've made a wrong move.

9. I have noticed that MS Solitaire on my computer has all of twenty different ways to deal the cards, and the only randomness in the dealing is which one it chooses; I have seen it deal the same way three times in five games before. I've played the game so many times I've started to accidentally memorize which moves to and don't work for each configuration. My win percentage is 30%, out of almost 6k games played. Current win streak is seven games, and I haven't broken that streak yet.

1. That is super-weird, and not something I've ever seen. What version of Windows are you on?

10. even dealing 1 at a time instead of 3 my estimate is 42%

1. That's pretty reasonable. I've got a computer simulator that for draw-1-infinite-pass wins 53% of the time. For other game parameters the rate is much lower.

11. I play about a thousand games a year and I currently have a win percentage of 37%, 3-card deal, standard scoring. I do tend to hit undo a lot, I'm pretty meticulous about trying all promising branches and like to think I only miss a few winable games. Anyone know what percentage I miss?

1. I'm pretty sure that playing with arbitrary "undo"s is equivalent to the "Thoughtful Solitaire" game where the CS researchers claim an 82-91%win rate. You might want to consider downloading a "Thoughtful Solitaire" program (all cards visible) if that's the game you like to play?

12. Most of the time I'm like everybody else... can go two hours without winning. But several times each year I win three in a row, and once I won five in a row. What's that... Divine interference? Anybody else?

1. As a professional mathematician, I refer to that as "random numbers f*ing with your head". It's probabilistically almost certain to happen if you play enough games.

http://barnyard.syr.edu/cover.pdf

2. Aristotle in The Rhetoric wrote: "One might perchance say this was probable -- That things improbable oft will hap to men.... For what is improbable does happen, and therefore it is probable that improbable things will happen. Granted this, one might argue that 'what is improbable is probable'."

13. This comment has been removed by the author.

14. It is 100% certain that there is no shuffling in Windows Klondike solitaire. Fact is that in a real game, a percentage of shuffles result in not a single play being possible. Get a real deck of cards and try it! I will guarantee you that such unplayable shuffles NEVER, EVER happen in this solitaire game. Ergo, you are playing an assortment of selected shuffles residing in a database (the selected ones having a reasonably large number of moves possible until you have reached a "sticking point.". Obviously, the programmers are avoiding the moments of disappointment and "unfairness" created by the player being dead ended before a single card is played.

Much to my amazement, I can find not a single person who has set out to discover the size of the "selected shuffles" data base. All of the statistical analysis of shuffles on the internet completely miss the fact that the shuffles are all fixed. The ONLY random process is the selection of which shuffle is loaded from the "playable shuffles" data base. I admit to having played enough games that I very often recognise the shuffle being offered, and correctly predict whether or not it is one that I can win. When stuck, I can frequently remember that the sticking point is due to such-and-such card being stuck in an inaccessible place, and it keeps on repeating every time I get that particular "shuffle" Also, I get shuffles where I immediately know "Oh this one is a very quick win.", and sure enough, that's exactly what it is.

Some people admit to playing out every "branch" to see which one has the best probability of success, and I do that 100%. Some people also complain that you can not replay a game. This is completely false. Just hold down Ctrl-Z and you will be returned to the start of your game in less than 2 seconds (on my 5 year old laptop). Any game can easily be replayed for as many times as you have the patience

I have the shuffles so well remembered at this point that the game is becoming boring for me. I will soon probably abandon playing Klondike because of the increasing predictability. I doubt that the designers ever thought that anyone would play enough games for that to happen! I certainly never anticipated that the game could be "worn out", but if your memory works, it most definitely can happen.

1. Hmmmm. I must admit that I thought I'd seen games in the past where no moves could be made... although I must admit it's very uncommon. Theoretically it's 0.025% and since I've only got 2219 games on record the expectation would be only 0.55 times it would have happened (i.e., only 50/50 to see it once). You should only be seeing 1 such no-play event every 4,000 games... I'd say you'd need to have something like 100,000 games on record to have solid evidence of that being the case?

2. I can confirm (as a tremendous coincidence) that just tonight I got a game with no plays possible. This is in MS Windows Solitaire running on Windows 7 Home Premium (Version 6.1, Build 7601, Service Pack 1), Draw 3. Screenshot linked below.

15. I think the thing that bothers me with computer versions os solitaire is there are a lot of them out there and using computer generated games instead of using physical cards is you're relying on a programmer to reproduce the experience of using actual cards. But programmers design the games with the idea of people continuing to use them, so it's in their best interest to have people win more often than you would with a deck of cards. I win with my computer game about 40%-50% of the time without trying very hard. I know I couldn't possibly do that well with cards. Since I'm good at solitaire, I'd rather have it replicate the experience with cards to make it harder, but I think most people would rather win more.

1. What application and what parameters are you using?

16. Interesting comments. I play 3-card-draw MS Klondike (Win7)and currently have 57% over 4 years (3863/6712). I (mostly) F2 skip any game where I can't see opening play of the 2 right-most piles and one ace. I also Cntl-Z to try replays, but not to excess... I don't have much patience.

1. Well, I just learned something: you can skip (F2) at the start of the game and it doesn't count for your loss/games played statistics. I've never done that or ever use Ctl-Z (I'm super hardcore, I guess); I think we can say that makes a big difference, because the best I can do is an 8% win ratio. Thanks for the insight!

2. I disagree on "undo"'s being equivalent to Thoughtful Solitaire, though I do think tending toward approximately equivalent is logical but not knowing which one of the astronomically possible sequences are under the covered cards makes it only equivalent for winnable shuffles. My favorite game conditions to play are 3 card deal and "cherry pick" using F2, unlimited go arounds on play stack and play for speed wins, but if a quick win isn't possible then exhausting all possibilities/trees pursue any win using "undo" with no regard to time. If I play without any need for speed and cherry pick with F2 most selectively, my win rate is over 50%. My conscious ability to predict 3 deal sequencing is limited but do think I will eventually be able project out about triple my current abilities. I strongly suspect the programmers have built the game to give specific shuffles depending on player behavior and that they collect that data for future revisions of the game. I'd suggest that the previous poster of the
"repeated shuffles" and is "getting bored with the game" is the subject of a "test how quickly at what win rate a player will get bored" algorithm. The number of possible playable shuffles is way too high IMO.

Engineers of any sort are the badasses of our species, scientists the high priests.

On on

17. Is it just my imagination or is there a high percentage of consecutive cards in the playing deck. In other words, playing a red eight leaves a playable black seven showing. Mathematically, this should occur 1 out of 26 times, but seems to happen far more often. I haven't kept track, and I may just be noticing when it happens more than when it doesn't. It's always nice to be able to play two cards in a row, but it seems far from random. Anyone else seeing this?

18. I’m surprised not to have seen more (any?) interest in Bill Turnbull’s Solitaire Tester, http://www.roziturnbull.com/bill/Solitaire/solitaire.htm. Obviously, a work of remarkable effort. It appears to answer exactly the question that most ordinarily curious Klondike players want answered: What are the outcomes that a player who is consistently attentive, misses no possible moves, and uses the simplest logic in making choices should expect? It is also really fast, which makes it useful for gathering reliably large data samples. My only regrets are that the number of game variations is not larger and frequency distribution tables of game outcomes no doubt exist but are not visible.
The “cards to draw” options are limited to 1 and 3, and the “times around deck” options are 1, 3, and “Lots.” Adding draw 2 and draw 4, and adding 2 and 4 times around the deck would likely provide enough more data points to make some useful inferences about the statistical structure of the game. Also, showing the frequency distributions for the numbers of cards winding up in the suit stacks could be useful. These distributions are curious.

1. Thanks for the link; I'm pretty sure I have seen that before. The results listed on the home page (8.7% win rate on draw 3/decks 3) is quite close to my personal play rate (currently 201 wins in 2371 games, for a 8.5% win rate). I have my own solitaire simulator program that wins around 7.7% with the same rules. I do think there are some strategies that could improve my simulator's play.

19. At one time I became obsessed with playing Vegas scoring, where you are only allowed one time through the deck, and are awarded points (only if the card comes up from the foundation, so you need to put an ace on an available two before moving it in order to score). I achieved the maximum number of points a few times out of hundreds (and I do mean hundreds) of games. So that is possible. But I don't think I'd play solitaire in a Vegas casino.

20. I play Klondike on my cell phone and actually win 74 % of my games... but I also start my games over and over again, if I have the feeling my cards can be played smarter. That's for me more interesting than just starting a new game over and over... -to find a strategy of how to play the cards.
Before, I just used to start new games and my score was about 25 % wins... but it bored me!

21. I play The Klondike Solitaire draw 1 on my iPad 12.9 and my iPhone 6s. Once, I actually won 18 games in row. No clue how that happened. I do frequently use the undo button but, not obsessively so. Using a predictor that one usually can win about one game in every 5.4, 18.5%, I came up with a probability of 0.185 x 10 to the power of minus 7. So, I guess that says that the impossibly improbable is still possible. Go figure. I just accepted that it happened and, went on. It is not all that uncommon for me to win 3 or 4 games in a row. Go forth. Have fun! I suppose if The Klondike Solitare statisticians could find the incident in my history. I played all 18 one night on my 12.9.