SourceForge Project Created

Well, it's been over a year, and I know that the ripples from the tiny stone I threw into the internet ocean have probably completely subsided by now. Well, I have decided I am going to throw myself into this project, whether or not it attracts involvement or any sort of following, because after a very busy year, I still find myself drawn to this problem.

I have finally created a Sourceforge project, which you can find at https://sourceforge.net/projects/crackingsolitai/, although it is empty at present.

I am busy getting to grips with all the services offered by SourceForge, and how to use them. I may blog a bit on this process.

As Tigger would have said,

TTFN!

Sorting gone bad

One of the reasons that Solitaire is so difficult to formulate, is the sheer number of possibilities involved in a single game. Just the total possible deals from a deck of 52 cards is a number the mind shudders at (52 factorial, or approximately 8 * 10^67). My first goal is to try and strip the game down to its barest essence, reducing permutations as far as possible while still maintaining the structure of the game. I will go into the specific variant of the game I am looking at later, there is enough to crack before we even get to the multitude of variations on the game.

Step 1, the most obvious step in reducing the problem complexity, is to start with a much reduced deck of cards. I need enough to get the effect of intermediate stacks. I am going to start with 4 cards per suit. A total of 16 cards still means about 20 trillion possible deals, but simulations and problem solving should be a lot easier.

My first approach is to treat Solitaire as a very lousy sorting algorithm, starting with 52 shuffled cards, and ending with all 4 suits in order, passing through an intermediate phase with the cards in rank order, alternating colours.

I want to assign a single value to each card, which, if possible, will allow a more mathematical approach. The lowest order component will represent the rank.

Ace = 1
Two = 2
and so forth, up to 4.

The next order component will represent the suit, and will be in the hundreds, to allow for more than ten ranks.

Spades = 100
Hearts = 200
Clubs = 300
Diamonds = 400

These are deliberately chosen so that odd numbers are the black suits and even numbers are red.

The last number I am debating adding is one to represent whether the card is face up or face down. This would perhaps mean adding 1000 to cards that are face down

So for instance, a face down two of hearts would be 1202.

I like the gratification of seeing the processing, so my first experimental program in C# is going to use a textgrid control, with a column for each stack.

Within the next 3 weeks or so I will open a project, either on SourceForge or Codeplex, and put my first “toy” program. This should allow for some playing around with parameters, and testing of initial ideas.

What, why, how, when?

What do I mean by “cracking solitaire?” Well, I want to know if there are rules and strategies that can help win solitaire. I want to know how many winnable games there are. I want to write a program which can play an optimal game of solitaire, not using random guesses and backtracking (if possible). If a game is not “winnable” I want to be able to tell this from the initial deal of cards. I want to know if there is no possible way to win the game, or if it is just a result of getting stuck in an irreversible situation. And lastly, I want to use whatever means – logic, maths, experimentation, programming – or combination of means will get me there. This quest was largely inspired by this post on the "Odd Thinking" blog. Thanks, Julian.

Why do I want to crack solitaire? There are many reasons. Mostly I want to stretch my mind, and I am positive that even if I hit a wall on this one, that the experience will make me a better programmer and problem solver than I am now. I also want to collaborate with great minds. I don’t know whether great minds will want to collaborate with me, of course, but in part this is a fishing expedition, with a particularly meaty problem as bait. For me this problem is an “Everest” at present, but there are probably some minds out there for which this more like a distant hill, requiring no more than a brisk stroll and a slight uphill walk. Anyone that makes a contribution that helps get to the goal will receive recognition on this. Who knows, it may end up as an academic paper. My last reason is final proof of my inherent geekiness or craziness, but I want to do it for fun.

How? Well this is the interesting part – I don’t know. I have some ideas, of course, but no idea if they will lead through to a successful conclusion. The idea that excites me the most is to start with the simplest possible version of the problem, work out rules and probabilities for that level, and then add a single layer of complexity on to that and repeat, until the whole game is described.

When? Ha ha ha. Great question. There will probably be short bursts of activity and inspiration, followed by long periods of stumbling around. If you are going to follow this, it would probably be better to subscribe to the RSS feed than to check the home page.

I also face the standard blogger’s mystery at the moment – will anyone be interested enough to stumble upon this and join in the journey, or will I be a crazy man talking to himself in an empty room? Well, if I develop multiple personalities, I suppose I could simulate some conversation ;-)