I have modified the game player to try and solve deals. It is currently running and solving in the range of around 73% (557 solves out 763 deals). There is a white paper which claims success at a rate of 82 to 91.44%. You can find it here:
http://web.engr.oregonstate.edu/~afern/papers/solitaire.pdf
I think I found the source and I might try building it and reproducing their results (depends on time available).
My implementation is fairly straightforward and brute force. A game of solitaire can be broken down into a series of actions. I'll classify the actions into three basic groups based on my implementation of the game player. Stack moves and exposing cards on the tableau stacks are the first type of action. The other type of action is moving a card from the play stack (stock/talon) to the main stacks or ace stacks (foundation stacks). The third type of action is shifting piles and moving cards to/from the main stacks to/from the ace stacks in hopes of creating a space for the card showing on the talon stack. The solver is really only concerned with the first two types of actions. Shifting stacks and moving cards really doesn't do anything until you actually move a card from the talon.
The first step in modifying the program to solve deals was to track the first two types of actions. I did this with a simple counter. Once I was able to identify actions, I was then able to envision making "mistakes" when a game is played. A "mistake" being that you fail to move a stack/card or you fail to play a card from the talon. Skipping a card play from the talon is trivial. Skipping a move is non-trivial as once you skip one move, this can have effects on successive moves. Thus the stack moves identified in step one of my play algorithm were grouped into a series of moves. When I attempt to skip a move within a series of moves, I must take care not to make any other moves within the series that touches the stacks involved in the initial skipped move. The excluded stack list is cumulative as any stack involved in the new skipped move must be added to the list. I am worried that this logic is insufficient and may be the cause of my discrepancy with the white paper results above.
Once I have a list of significant actions, I can then replay a lost game by skipping significant actions. For example, if the lost hand involved 35 significant actions, I can then replay the hand, skipping each action. It's easy to see the permutations involved grows quickly as each of these hands can then generate another list of games with skipped actions. Rather than build lists of skipped actions, the algorithm lends itself easily to a recursive solution. Take a lost hand and play a list. Playing a list involves skipping the 1 through n actions. While playing these hands, after you skip an action and then make the next significant action, you then have stacks which can be "check pointed" (i.e. I save off the state of the stacks). If that hand fails to win, you can then play a list of games off the check pointed stacks creating all permutations of the initial skipped action stacks. This clearly leads to massive numbers of potential solutions. Clearly there will be deals which cause the computer to go off into solve mode, never to return.
A definition of insanity is doing the same thing over and over, expecting different results. A definition of an insane computer program would be something similar. In order to lend some sanity to this solution, I implemented a std::map of stacks. I use the number of cards remaining in the play stack after a failed try as the key. As I play lists, I save off the state of the stacks into the map. Before I play a new list, I check to make sure that this particular set up of stacks has not already been tried or is being tried. If it has, no sense running a play list on it. With this approach, I am able to process deals at a rate of about 50 per hour. This is on a pretty old computer running a single thread on 32 bit.
I've invested parts of four weekends on this little foray and I'm not certain I want to continue. The TODO list is starting to grow. Based on my order of priority:
1. Clean up source code and post it.
2. Carefully review my skipped move logic above.
3. Build the white paper source and try and verify their results.
4. Modify the solver to count up solutions to a deal rather than stopping after solving it once. Generate statistics about how many solutions exist on average for any given deal. This would give us an idea of how "forgiving" deals are (i.e. how punitive mistakes are). My intuition tells me that good deals are hard to lose.
5. Buy a hardware random number generator (cost of about $230?) and run my games with that.
6. Port to x64.
7. Enhance to use multiple threads. I should be able to get this running on a machine with 8 cores and I'll try running 7 threads.
I am committed to getting item 1 done next week, after that I don't know.
Monday, April 29, 2013
Saturday, April 27, 2013
Odds of winning a game of solitaire
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:
Subscribe to:
Posts (Atom)