80% of solitaire deals are now solvable!

I was able to get the solver to solve at around 80% of deals. It is extremely consistent. My sample sizes are only hundreds of deals as it is solving at a rate of about 25 deals an hour. It makes me wonder how they were getting variation in the white paper solver listed in the previous post.

As I suspected, the first version of the solver was flawed. My move logic was flawed and I was skipping permutations. At a cost of making the solver slower (first version solved at a rate of about 40 deals per hour), I was able get my solution rate up to 80%. I discarded the concept of grouping stack moves and went for a far simpler implementation. Stack moves are pretty much treated just like card plays off the play stack. I also refined my strategy for check pointing stacks. My initial implementation would unconditionally check point a stack after a significant action after a skipped action. When I would go play another list, I would look for the stacks in the list of check pointed stacks and not play the stacks if they were found. I implemented a new strategy where I would mark the stacks for pending check point after a skipped action. I would then continue to play the hand and try to check point the stacks after each significant action. If the stacks were found in the previously tried list, I would leave the pending flag set and continue playing. In this manner, the program now seeks out new stacks to solve. Only when I am able to check point the stack (i.e. it doesn't exist in previously tried stacks) do I clear the pending flag. This means I have to spend more time comparing stacks but less time actually playing cards.

Lists of lists are good. My initial implementation of the lists of check pointed stacks was a std::map<int, std::vector<std::vector<Stack>>>. I used the number of cards remaining on the play stack as the key. I never analyzed this map but I figured that some lists were getting exceedingly long and required many comparisons of the stacks. I implemented a new list of check pointed stacks. It is:

static std::map<int, std::map<int, std::map<int, std::vector<std::vector<Stack>>>>> sStacksPlayed;

It has three keys and I tried to do eight but the compiler barfed on it. Something about names being too long. Three was the most I could get. I didn't bother to investigate further but I suspect I could get eight if I got into the business of typedeffing. Now I have a three key map and my keys are as follows:

std::vector<std::vector<Stack>> &lStackList(sStacksPlayed[mCardStacks[eStackPlay].size()][mCardStacks[eStack4].size()][mCardStacks[eStack7].size()]);

I arbitrarily chose the number of cards in the play stack, the fourth main stack and seventh main stack. I started analyzing my triple map after solving a deal and found that the maximum number of stacks in a list was consistently twelve. I had an "oh duh" moment when I realized that the most number of cards you can have on a main stack is twelve. This is good as the most number of stacks comparisons I will do on any attempted check point is twelve.

Most deals solve or don't solve fairly quickly. Periodically a deal comes up where hundreds of thousands of unique stack check points are generated. This really kills my throughput. I would like to collect stats on this.

The main recursion loop is as follows:

void PlayList::playList(const std::vector<Stack> &arCardStacks, int aCardsRemaining, int aLevel)
{
   if (arCardStacks.size() == 0)
   {
      return;
   }

   // -1 means we won't skip any signifcant actions on this game
   Game lGame(mSortStacks, -1, aLevel, false, true);
   if (lGame.play(arCardStacks))
   {
      //std::wstringstream lStream;
      //lStream << _T("Solved!");
      //displayString(lStream.str());
      mSolved++;
      // game stops on first solve - I'll try to have it keep going some day
      return;
   }
   // the number of significant actions in the previous attempt
   int lEndSkip(lGame.skipPlayMoveCounter());
   for (int i = 0; i < lEndSkip && !mSolved && !mStop; i++)
   {
      // i identifies the significant action to skip for this game
      Game lGame(mSortStacks, i, aLevel, false, true);
      mGamesPlayed++;
      if (aLevel == 1)
      {
         std::wstringstream lStream;
         lStream << _T("Level one step ") << i+1 << _T(" of ") << lEndSkip;
         displayString(lStream.str());
      }
      if (lGame.play(arCardStacks))
      {
         //std::wstringstream lStream;
         //lStream << _T("Solved!");
         //displayString(lStream.str());
         mSolved++;
      }
      else
      {
         if (!mSolved && !mStop && lGame.checkPointStacks().size() > 0)
         {
            playList(lGame.checkPointStacks(), lGame.cardsRemaining(), aLevel+1);
         }
      }
   }
}

This recursive implementation leads to concerns about stack space and stack overruns. According to the doco, VS2008 default is 1 meg. My implementation consumes about 10K of stack for each level of recursion. I think I am OK but I need to track my maximum level of recursion. I'm printing out stats every thousand attempted solves and it never seems to solve above 30 levels of recursion. I am not sure why this is.