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.

Peg solitaire board game