Problem Statement
I came across the pegboard problem in 1997 while waiting for my pizza at Pizza Hut. It is a triangular board with 15 holes, where there is a peg in each hole except one:
You move a peg over another if you can, i.e. there is a peg to move over and there is a hole to move into. You keep moving the pegs until there is only one peg left on the board.
Monte-Carlo Simulation
We can all solve this problem, eventually: using pure trial-and-error or by thinking a little about the end result and thinking backwards, etc.
After pizza, I went home and put together a simple C code to solve this problem in all its variations (for all locations of the initial empty hole). The code essentially does the trial-and-error method, but much faster. It knew what the initial and end states of the board should be, and moved the pegs if possible. The code then checked the result when the pegs could no longer be moved. If a single peg was left on the board, the puzzle was solved and the steps taken to get there are displayed. If there is more than one peg left, the program re-iterates the process from the initial state. Within a few seconds and hundreds of iterations later, the solution is displayed.
This method of simulation is nothing new. The term 'Monte-Carlo' was coined by John Von Neumann, who was tasked with answering the question: "Would the world be destroyed in a chain-reaction when the atomic bomb is exploded?" This was a very complex question to say the least. The pathways of sub-atomic particles and reactions that may occur as a result all made the problem an open system, i.e. impossible to solve by known mathematical procedures to reach a solution exactly. Simulation by a fast machine was needed. Von Neumann in fact helped the folks at the University of Pennyslvania to create a computer with all the specifications needed to do such a simulation: software to be in memory and re-executed over and over with a memory to store results. To this day, most computers take advantage of the Von Neumann Architecture.
Similar, but simpler, simulations that can be manually made inspired Von Neumann. Most notable of these earlier simulations is called the "Buffon's Needle Problem", where the fall of needles onto a floor made of parallel strips of wood and their observed frequency of intersecting the line between the two strips eventually leads to an approximation of p. This was the work of Georges-Louis Leclerc, Comte de Buffon, who lived in the 18th century France.
Pegboard problem has exact solutions with precise steps that make it a 'closed' system. Brute force technique could also be utilized to solve this problem within a reasonable amount of time. Writing a simulation, in my opinion, is easier, because I don't have to scope out the entire play-space. Dynamic programming would no doubt be a clever way to solve the puzzle, too.
General Structure of the Software
PEGSOLVE.cpp was written with Borland C++ 3.1, and most recently I tested the code using gcc C++ 4.x. The style of programming is that of 'playing' and doesn't employ powerful C++ libraries such as STL.
Define the Scope
The first part of the code defines the system scope with an array, static int orig_pegboard[15], which represents the pegboard. This is used over and over again in the beginning of each iteration.
Define the Elements
The main 'role' within the system is that of a peg, which can move around.
Define the Behavior
Because a move has three elements to it, a _move_set structure is defined that contains the peg to be moved, the peg that will be removed as the first peg is moved over, and the new location of the first peg.
Define the Rules
For each peg in a specific hole, there is a complete set of movements that may or may not be possible. This set is represented by an array called peg_move_rules.
Entities within a constraining scope behaving according to a set of rules make up a system. Outside of this system, we extract out what we need: solution to the pegboard problem. There is a state of the pegboard that we identify as, in fact, the solution, and all the events (peg movements) that transpired to get to the solution are what we need.
Everything defined above will now be used in runtime of a computer application, and here is the pseudo-code:
While (the pegboard is not solved)
{
Reset to the original state of the pegboard.
Reset all move traceability.
Get all the possible moves that can be made
at the current state of the pegboard.
While (there is a move that can be made)
{
Pick a move and just do it.
Keep a track of this move.
Get all the possible moves that can be made
at the current state of the pegboard.
}
}
That's it.
Results
I'll display here the result for one problem. Let the initial state be where Hole #1 is empty. If you run "pegsolve.exe 1", the output would be:
The solution was reached in 130 iterations.
Biasing the Random Number Generator's PDF
Uniformly distributed random number generation assures us the probabilistic equality of any of the numbers generated; i.e. probability (0.1) of a number, say '2', between 1 and 10 is the same as, say '6'.
But why should the random number generation be uniformly distributed? Because otherwise it would require more work. Yet it is reasonable to think that a sequence of moves that lead to fewer pegs in the end are better off than those with more pegs. Perhaps, then, some moves that can be weighted heavier than others in the random selection--albeit no longer uniformly distributed--can lead us to a solution quicker than repeating mistakes of the past iterations. This solution can no longer be called Monte-Carlo simulation because each iteration doesn't begin with the proverbial 'clean slate'. This, according to a professor of AI class I took a few years ago, is a genetic algorithm.
Comparing the Two Results
Below are two tables of results for Monte-Carlo and "Biased Monte-Carlo", respectively. Each column header represents the empty hole number on the pegboard, and the values inside tables represent the number of iterations it took to solve the pegboard puzzle. Orange and blue strips are the averages of the iterations. Far right column contains the sum of iterations.
While there is a clear statistical difference, and an improvement, for hole #1, the overall performance (all of the hole considered) had over 7% improvement. There was no improvement (in fact worse) in the number of iterations for nearly half of the holes. I cannot conclude one method is better than the other; but they are different.
History
- 18th April, 2007: Initial post
