Jerry Bryan's Web Pages

Baker's Game Recent Programming

Recently, I wrote a new Baker's Game solver using more modern technology, both hardware and software.  All generated positions are maintained in memory using tools from the C++ Standard Template Library.  I use the STL's set container to maintain two collections of positions, those that have been processed and those that have not.  It is necessary to maintain both collections in order to detect duplicate positions.

The new algorithm is much simpler than my original one, and indeed is not even a tree search at all.  The new algorithm does depend on having a fast machine with a lot of memory.  Here's the basic algorithm.

  1. Create two STL containers (STL sets) that are initially empty, one to contain Processed positions and one to contain Unprocessed positions.  Processing a position consists of generating all its neighbors (see #5, #6, and #7).
  2. Create an initial position, shuffling the deck using a high quality pseudo-random number generator and using low order bits of the computer's time-of-day clock to seed the high quality pseudo-random number generator.
  3. Place the initial position in the Unprocessed container.
     
    (Initialization is complete at this point.)
     
  1. Remove one position from the Unprocessed container.  If there are no positions to be removed from the container, then all possible positions have been examined without finding a winning solution.  Count the game as not winnable, and stop.
  2. Generate all neighbors of the position from #4.  Neighbors are those positions that can be reached in one move.  If any of the neighbors have all the cards in the payoff cells (also called home cells), then the game has been won.  Count the game as winnable and stop.
  3. If any neighbors are equal to any positions in the Processed container, then throw them away because they are duplicate positions.
  4. All the rest of the neighbors (if any) are inserted into the Unprocessed container.  It's possible that one of the neighbors being inserted into the Unprocessed container is the same as a position that is already there.  This condition is of no consequence to the algorithm and does not need to be tested for explicitly because of the way the STL set container works.  That is, the STL set container does not allow for insertion of duplicate elements.  So the attempted insertion of a duplicate position into the Unprocessed container will be ignored.
  5. Go to #4.  The finiteness of the search space ensures that the algorithm will terminate either in step #4 or in step #5.

Return to Jerry's Home Page

This page last edited on 23 Aug 2011.