Solitaire solver

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.