As the story goes, Pellison designed the game for the entertainment purposes of Louie XIV. With the game dating back to the 17th Century, it was said to be invented by a French Mathematician, Pellison. Peg Solitaire has a long and interesting history. The same perl script is adapted to provide the tables that follow, detailing the steps of the two winning games animated above.Package from the back Peg Solitaire Game from BeerliSchweiz The History of Peg Solitaire or Solitaire ImageMagick is an open source graphics toolkit, that is surprisingly powerful but suffers from user-hostile documentation. The perl script uses the PerlMagick module from ImageMagick to create the images and the animation. The black arrow indicates the peg to be moved and points in the direction the jump will take place (in the script I use compass directions of East, North, West, or South.) A shaded circle represents a peg or marble, and an unshaded circle is a slot that could take a peg, but currently has none. (Less than a minute of processing time in any case.)įor the GA, the data structure for the board at any given stage of the game uses a 49 character string ('-' for cells in the 7x7 grid not in use, '1' for cells with pegs, and '0' for cells that could hold a peg, but currently do not.īut staring at long strings of dashes, ones, and zeros is not appealing, so I created this perl script to translate the sequence of moves represented by the strings of '-' and '1' and '0' into a graphical representation of the board.
When provided with this task, the GA finds the one peg solution in about 1,600 generations, although it takes over 5,000 generations to get the desired solution. For a reasonable substitute, I discovered that it was possible to start with the upper left slot empty and end with a single peg in the lower right slot. After adapting the GA to deal with the change in the shape of the board, I discovered that the best I could ever do was to end with two marbles if I started with the middle space empty.įurther research revealed everything from speculation that the French game had, at one time, allowed diagonal moves, to actual mathematical proofs that a single peg in the middle was an impossible result when starting with the middle peg empty on a Continental board. the board wasn't the same as the standard Hi-Q board! Four extra pegs (marbles) had been added at the internal vertices.Īfter some feverish Googling, I learned that the Bombay set is based on the French or Continental version of the game. Starting from a population of 100 random walks through the game, and creating new attempts in each generation from random variations in any of the top ten scores from the previous generation, a "winning" game is almost always discovered within 2,000 generations.Ī winning game of Peg Solitaire on the French board.Ĭloser inspection of the new game from the Bombay Company revealed a different problem. more than 617 trillion combinations to process.Ĭhanging the objective from "find ALL of the solutions" to "find ANY solution" invited a new approach based on a simple genetic algorithm (GA). sometimes as high as nine) then there are 3 31 combinations, and we've been through all that math before. If there are about three possible moves on any given turn (it's often more.
On any given turn there are only a few available moves, and a peg or marble disappears with each turn, so it should quickly simplify, right? Right? Wrong. but it became apparent that it was unlikely to stop running in my lifetime.
thousands of them thanks to the boundless symmetry of the board. The resulting C program generated solutions. which was a fairly colossal waste of time. My profound sense of mathematics being what it is, my first approach was a depth-first algorithm like the one used in the Scramble Squares problem. Time goes by and when I received a really nice Solitaire game this past Christmas (from the Bombay Company, the board uses large multi-colored marbles instead of pegs), I felt ready to tackle it again. A winning game of Peg Solitaire on the English board.