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%.

23 comments:

  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.

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
    Replies
    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.

      Delete
  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

    ReplyDelete
  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.

    ReplyDelete
    Replies
    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.

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

      Delete
  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?

    ReplyDelete
    Replies
    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

      Delete
    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.

      Delete
  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%....

    ReplyDelete
  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.

    ReplyDelete
  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.

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

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

    ReplyDelete
    Replies
    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.

      Delete
  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?

    ReplyDelete
    Replies
    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?

      Delete
  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?

    ReplyDelete
    Replies
    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

      Delete
    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'."

      Delete
  13. This comment has been removed by the author.

    ReplyDelete