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.
-
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).
-
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.
-
Place the initial position in the Unprocessed container.
(Initialization is complete at this point.)
|
-
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.
-
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.
-
If any neighbors are equal to any positions in the Processed container,
then throw them away because they are duplicate positions.
-
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.
-
Go to #4. The finiteness of the search space ensures that
the algorithm will terminate either in step #4 or in step #5.
|