Tuesday, October 6, 2009

Klondike Solitaire - is it beatable ?

I am one of those people who can play klondike (sometimes also just called solitaire) for hours and hours. And I was always looking for the best strategy to play. When searching on the internet I noticed that there is next to no websites on strategy and zero information on the expected value (EV) of this game.
One of the few pages with some insight on this topic is OddThinking but this is a slightly different game than the one I am interested in. I prefer the vegas style game where you can only move through the deck exactly once and any card that has been moved up has to stay up.
As stated before I could not find an analysis of this game online which is strange because this game can even be played in some online casinos for real money. So I build myself a simulator to play it automatically. Here are my first results:
My best strategy so far is able to move up about 9.3 cards in average. Which would result in a house edge of 7%. I am confident that it still can be improved.
A Monte Carlo run of 1000 plays per deck (meaning a certain deck or single game is played 1000 times with totally random moves) is able to score a average of 14.5 cards. Of course this value can never be reached by any "real" strategy it will only give a upper threshold.
A "real" strategy has to make a decision on the next move by the information which is currently available (we call this a information set). Since Klondike is a game of imperfect information (because some cards are still hidden) there might be different games which have the same information set. All visible cards are exactly the same but the hidden cards are distributed differently. Our strategy always has to make the same move which of course will result in different results on each unique game. Monte Carlo will choose different moves each time and will ignore the information set. That is the reason why a strategy will never beat the Monte Carlo approach (if the game has imperfect information).

More to follow.....