I have been playing solitaire as of lately and I was wondering what the exact odds were of winning. I decided to write my own simple C++ program that plays solitaire. It uses STL extensively and I whacked something together fairly quickly.
In the hopes of validating my results, here is my algorithm. The program implements 12 stacks of cards. The seven main stacks, the four ace stacks and the one play stack. The algorithm does passes on the play stack. For each pass, I do the following:
1. Expose as many cards as possible by moving cards and stacks around the 7 main stacks and to the ace stacks as follows:
A. Move exposed aces and twos to the ace stack.
B. Move cards within the 7 main stacks.
C. Move cards from the main stacks to the ace stacks.
2. Attempt to play a card off the play stack as follows:
A. Move an ace card to the ace stack.
B. Move the card to one of the seven main stacks.
C. Move the card to one of the ace stacks.
D. Become desperate and do the following:
D1. Move cards from the seven main stacks to the ace stacks.
D2. Attempt to place the card on the seven main stacks.
D3. Move cards from the ace stacks to the main stacks.
D4. Attempt to place the card on the seven main stacks.
D5. Shift a stack within the seven main stacks taking care not to repeat the same shift twice. The definition of a shift would be moving everything under a seven of clubs to an exposed 7 of spades. If a unique shift occurs (i.e. I haven’t already done that particular shift, I’ll go back to step D1. This whole shifting scheme took me from about 1 in 5.8 games down to the current 1 in 5.4 games.
After going through the play stack three cards at a time, the pass ends and we go back to step 1 if we played at least one card off the play stack. Otherwise the game is lost. I also implemented basic rules like never clearing whole stacks/cards unless kings are available.
I used STL mersenne_twister to generate my deals. No small feat with Visual Studio 8 as that was a real pain. Here are some fun statistics that I have generated based on the program.
1. Odds of winning are about 1 in 5.4 games
2. Odds of not being able to play a single card off the play stack (aka stock/talon) are about 1 in 55 games.
3. Odds of not being able to move a card on the main stacks (aka tableau) and play a single card off the play stack are about 1 in 377 games.
4. Odds of all seven main stacks showing the same color on a deal are about 1 in 101 deals.
5. The average number of cards remaining in the play stack on any given game is about 10.1
The next step is to modify the program to try and solve a random deal. Solving the deal would involve playing all possible permutations of the deal to see if it can be won. I intend to implement this recursively.
Any help on making this program win more games would be greatly appreciated. I also have concerns about bugs which invalidate the above results.
If any of this vaguely interests you, I’ll be happy to read your email. Email rstefan912 at charter dot net or you can comment here directly.
Here is the source code:
Here is a screen shot of the program:
No comments:
Post a Comment