MY PEG SOLITAIRE OBSESSION AND ARTIFICAL INTELLIGENCE

Brian Keltch 12-2001

Updated Heuristics 10 - 2002

THE GAME

For some reason I have had a long-standing interest in the mathematics and solution of the common peg solitaire game. The same is simple and consists of a board with holes filled with pegs or marbles. The object is to remove one peg from the board and then successively jump pegs removing the jumped peg. The goal is to remove as many pegs as possible with a perfect score being one peg left. My interest in these stems from the fact that the game looks relatively simple, but it is very difficult to leave only one peg, I don’t think I have ever gotten one peg left without the help of a computer. Two common board configurations are shown below:

French Peg Solitaire

Triangular Solitaire

OTHERS WITH THE ILLNESS

There are other afflicted with this illness. A table of my favorites is below:

http://www.cut-the-knot.com/proofs/pegsolitaire.html	A very nice page by Alexander Bogomolny. It has a nice javascript game, and provides excerpts from one the most frequently reference text by E.R.Berlekamp,J.H.Conway,R.K.Guy, titled Winning Ways for your Mathematical Plays, v2. Which breaks the board or into packages of moves. This allows for a straight forward solution. It’s the scientific method at work. Breaking the problem into small pieces and solving each piece and then integrating a solution.
http://home.sunrise.ch/pglaus/Solitaire/solitaire.htm	Pascal Glauser provides a wonderful genetic algorithm solution to the game. It is a ingenious and fun java application
Ins & Outs of Peg Solitaire	The famous book Ins & Outs of Peg Solitaire / John Beasley Oxford [etc.]: Oxford University Press, 1985 XII, 275 S. : Ill.; 20 cm (Recreations in mathematics; 2)ISBN: 0-19-286145-X describes several techniques to solve the standard game used here and many other games. Having their roots in analysis of solitaire, they show that solitaire is not so "hard" a beginner would guess, but unfortunately the techniques would be rather difficult to implement in a program. Further on, there is no technique leading to a solution for sure; therefore, implementing such a technique would have a heuristic characteristic.
http://ch.twi.tudelft.nl/~sidney/puzzles/	Sidney Cadot a 28-year-old software engineer developed a brute “solution and found all possible sequences that finds all solutions (successful ones). Nice solution diagram. His pages are in English http://ch.twi.tudelft.nl/~sidney/puzzles/ but his reference paper published in 1998 is in German.
http://enchantedmind.com/puzzles/solitaire/solitaire.htm	Another nice java applet version of the game
http://www.santafe.edu/~moore/pubs/peg.html	Wow here is a wild one. I am not sure I understand this one. They say “We solve the problem of one-dimensional Peg Solitaire”. In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that a linear-time algorithm exists for reducing any configuration to the minimum number of pegs. PDF of their paper is available. I wish I understood this.
http://www.inwap.com/pdp10/hbaker/hakmem/games.html	Nice page with solutions for both peg solitaire and triangular solitaire. Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.
http://www.samizdat.com/hiq.html	This link is a solution derived by a third grader (Richard Seltzer, seltzer@samizdat.com ) in 1954 by playing the game in reverse (Show-off!!)
http://www.ahs.uwaterloo.ca/~museum/puzzles/solitare/	This site provides an extensive history of the game. They article blames the French. (Doesn’t it figure!!)
http://www.geocities.com/durangobill/PegSolitaire.html	Bill Butler (aka DurangoBill) does a great job solving both the triangular and 33 peg versions of the game. Besides that he’s a geologist!
www.aaai.org	There are even folks who take game playing seriously, and consider it a part of Artificial Intelligence. See “A Gamut of Games”, by Jonathan Schaeffer, Fall 2001 American Association for Artificial Intelligence. Page 29-46 “Game Playing; The Next Moves”, by Susan L. Epstein, American Association for Artificial Intelligence

WHY IS THIS SO HARD?

My first question has been why is this so hard? To answer this question I first attempted to write a program that would calculate all the possible moves for the traditional solitaire board. This proved to be way too many calculations for my slow program (written in Clipper an x-base compiler) and way too many data points for my 40 MB hard disk. So I temporarily abandoned the project. This, by the way, was probably in the 1989 timeframe. Durango Bill did just this and found 577,116,156,815,309,849,672 different game sequences. That's:

   577 quintillion
   116 quadrillion
   156 trillion
   815 billion
   309 million
   849 thousand
   672
   possible game sequences. This is the complete search space.

A few years ago I resurrected the project, or rather it came to me and I could not expel it from my mind. So this time I decided to go with the simpler board the triangular one that you often see made with golf tees.

Here are the results of the complete search with position five open.

So for example the Move 2 goes from the original configuration with position 5 blank. To the following with two resulting boards

There are only two boards. Each board is unique, and there are not terminations (i.e. you can always make either of the moves from one to two. If we look at the next move there are six possible moves

12-13-14, 7-8-9, and 2,5,9 on the first board and

14-13-12, 10-9-8, and 3,5,9 on the second board. These six possible moves result in only three end boards and no terminations, that is there are no starting positions with out any possible moves. Below is the complete table.

So this tells us it is difficult because of all possible sequences of moves only 1.1 percent will result in one peg left. The most likely is 3 pegs (46%) followed by 4 pegs (34%), and 2 pegs left (15%). So just randomly it is very hard to have one left.

It is also interesting to note that there are many ways to arrive at the same board. For example on Move 11, you start with 108,000 branches. Of these 46,728 positions have no move. And for the remainder they generate 81,408 moves. But of these 81,408 moves only 41 unique boards exist.

WHAT IF YOU WERE TO MOVE RANDOMLY – Monte Carlo Simulation

I wanted to find out what techniques might be helpful to the player during the course of a game. So I first wrote a program that can simulate the playing of thousands of games. That is that on each move the play will randomly select which possible move to make, until no more moves can be made, I then count the pegs left and repeat the process for thousands of games. Here are the results of completely (completely as I can get) random selection of moves for 100,000 simulated games.

ARE THERE HEURISTICS THAT WILL HELP?

A heuristic is simply a rule that can be applied to the sequence of moves that would allow the computer to distinguish between a good move and a bad move. My plan is to try several rules and use the monte carlo simulation to see if I can see an improvement in the percentages of games with 1 peg left. Any suggestions would be welcome. Send to: bwk@cableone.net

The first heuristic I thought of is to rank each potential by the total number of moves available on the resulting board. For example in the board below:

There are three potential moves.

4-2-1. 2-4-7. or 4-8-13. With this few moves it is clear that if move 2-4-7 is made then it can be followed by 7-8-9, thus resulting in only one peg left. If either of the other two moves are made then that will be the last move and there will be two pegs remaining. So this heuristic seems appropriate.

I have modified my program to make this selection. If multiple potential moves score the highest number of “next” moves then I randomly select from the best. Much to my surprise here were the resulting runs.

So the one move result make it much more likely that you will have only three pegs left, but assures that you will never have just one peg left – the object of the game. Why is this?

It is because we have reached a local minimum in our solution or more simply that this heuristic chooses a branch in the selection of moves that eliminates a whole branch of subsequent moves that prevents any path resulting in one move. I did not have to look too many moves ahead to see where the problem was. If we look at move three we see that there are six unique boards. Three boards are mirrored. So if we look at three possible we see that one of the moves has no subsequent moves resulting in one peg left. And unfortunately this move has the highest heuristic for number of follow on moves. So it is selected each time.

In this respect, at least up to move three it is not a very good move. So next I modified my program to see if by delaying the application of the heuristic until later moves I could improve it’s effectiveness in resulting in one remaining peg. So my algorithm would select randomly up to a user defined move, and then select using the one move ahead heuristic. Here is the sensitivity:

These are interesting results. They show that the best time to apply the heuristic is at move 10. This results in a four fold improvement in your probability of getting one peg left. So the heuristic works but it still a very slight advantage over random.

I will next try a heuristic of pattern scoring – that is grouping more than one move together.

NEXT STEPS

I hope to apply a neural network solution to this problem to see if I can emulate the human learning process. It is interesting that most peoples experience with this game is that after the first 10 to 20 games they become much better and generally leave only 2 or 3 pegs with an occasional 4 or 5 pegs. It is difficult to obtain only one peg with out using some clustering techniques. I feel the NN may be a good way to simulate how a human learns this game.