I recently stepped out of two months of continuous fire drills at the office, and found myself pretty much stranded on the couch Saturday afternoon. There wasn't a drop of inspiration to sink my teeth into anything. However, I was saved from a long afternoon of drinking until drooling by my new cell phone, which arrived with a raft of mindless games. After a couple hours' worth of solitaire, I started to regain the will to think. An interesting mathematical problem had appeared, which I thought I'd share here and see if I could inspire a little feedback. By 'solitaire', I'm talking about a broad variety of card games. For the moment, I'm not too concerned with the specific rules, but it is important to choose only those games where you lose most of the time. Generally, you start out with a minimum of cards showing, and as you step through the deck, you may add cards to the showing set when they are consecutive and of the correct suit. Usually you 'try' to expand the showing set as fast as you can, because there is positive feedback here - the more cards that are showing, the more you can add later. But in many games there is a finite limit to this and in some varieties the limit is quite small (I'm talking specifically here about the 'Four Piles' game as played on my Ericcson T68i)... you're quickly making a rough guess about what opportunities to 'pass' on. In any case, there isn't a whole lot of strategy involved. Mostly, it's about getting a deck shuffle that works.This is the interesting part to me: Winning deck shuffles must have good statistical qualities. The cards must be ordered in a way that big segments are sorted correctly (because you usually play lower cards on top of higher cards or vice-versa). For instance, if you took a brand-new deck of cards with everything in order, and proceeded to play solitaire without shuffling, you'd probably win. I didn't build any monte carlo models, but raw experience shows that you lose most of the time - that is, the statistical condition is quite strong. My question is something like this: Is there a mathematical condition which can identify a very large proportion of the winning deck shuffles which employs some conditions on the sorting?I think it's a good question because you should get something like continuity for the discrete set, which allows for a fair amount of defects. I am not any kind of expert in this type of problem, so I'd enjoy hearing from any of you who might be. Probably the best tool for understanding this would be a decent solitaire model that I really could drive with MC. In my life I spent enough time with statistical mechanics to believe that the precise structure of the solitaire game is not that important.If you follow the P(win) probability through the life of the game, you would expect to see some interesting things. As you play, you have a hunch whether you're going to win or not. But you do hit points where you know a big uncertainty is in front of you. If you get the right card, you will make it, and if you don't, you're dead. These jumps in P(win) or sd(win) must coincide with the accumulation of defects in the deck shuffle. You can probably figure out why I like this problem now... it's a little like option hedging where the underlying process is fairly good, but not great. If there is too much jumping, optimal hedging is still going to result in mediocre hedge performance.

How about approaching the problem backward? Many solitaire games end (if the player is successful) with the sorted cards. These cards can be placed on intermediate piles according to certain rules, then reassembled into a shuffled deck. Either by calculation or Monte Carlo, you could deduce the distribution of cards in a winning shuffled deck and compare this to a random shuffled deck.Consider, for example, a game that gave the player n spaces on which to place cards. Once a card is played on a space, only the next higher card in the same suit can be played on top of it. Piles of cards can be placed on other piles subject to the same restriction. The player goes through the deck once and must place each card on an empty space or pile. The game ends when all the cards are sorted into ascending order by suit on four spaces (win) or the player cannot place a card (loss).Start with the cards sorted in ascending order by suit on four spaces. Pick a pile with at least two cards at random, take a random number of cards between 1 and the number of cards in the pile minus 1, and move them to a vacant space. Continue until all spaces are full. Then reassemble the deck by picking a square at random and removing the top card, then repeating the process until all 52 cards are in the deck.