Java-Solitaire: Play or find solutions with a genetic algorithm!

(peg-solitaire)

Your browser does not support java or java is diabled

With this applet you can play solitaire on one hand: Open a solitaire-window with the button play your game and use your mouse and the buttons to move, go back and forth through the history of moves or let rerun the whole game.

On the other hand, you can let the applet search a solution. This is not a built-in, predefined solution, but sought in real-time; it takes some minutes. (As soon as the applets download to your browser has completed, you may cut the line to your provider, as the connection isn't required any longer.): You start with the X-Button, sit back and wait until the applet displays Done. Solution found in nth population after nn tries. The icons shown are candidates, which the applet generates and tests (evaluates) whether they lead to the solution or to a pattern near the solution. When the applet has finished, you click on the candidate in the upper left corner to open a solitaire-window in which the found solution can be played (use the >>-Button).

When the applet is running, the >>-Button changes into a X-Button, which you stop the applet with. With Make Population you restart the search with a new population; this happens automatically after several unsuccessful tries.

Clicking on a candidate opens a solitaire-window, where the evaluation game of that candidate is shown, even if it is not the one that solves the game. Shift-click opens an info-window displaying several parameters of the candidate.

There exists a mean "XL-version" of solitaire with 4 extra holes (follow the link to find out why it is mean), also known as the french type, called the 36-peg-solitaire. With the radio-buttons you may switch between the two versions, but the existing population is deleted with every switch and a eventually performing run is aborted.
Because the standard layout is more popular, the rest of the explanations (except of the special chapters on the french typ) apply to that version.

Update history

11.10.99 Capter Discussion updated

Solitaire-Window

The rules of the game are simple: each stone that can jump either horizontally or vertically over its neighbour and land on a free place is allowed to be moved. The stone it jumped over is removed. The goal is to remove all stones but one, and this last one being placed in the centre of the board.

If you move the mouse-pointer over a stone that can be moved, that changes its shape. Click on the stone, drag and drop it at the (or one of the) highlighted aims to perform the move, or drop it elswhere to abort. The move is illustrated, and you may make the next one. With the button < you go one or more moves back, with > you go forward again. With the >>-Button the game plays to the end of the move history. As soon as you make a new move with drag and drop, it is insert in the history and the rest of the history is discarded.

 

Info-Window

With Shift-Click on a candidate you open an info-window. There, you see the weights for the places in detail, and the moves that are performed in the evaluating-game. The moves are given by their start- and end-coordinates: The stone is taken from the former and lands on the latter, jumping over the coordinate in the middle, removing the stone on that place. The coordinate-system with its origin in the upper left corner (like usual graphical coordinate-systems) enumerates the columns and rows by 0 to 6. Some points (0,0 or 1,5, for example) are inexistent. (3,3) denotes the middle of the board.

 

Search-Technique

Candidates

Solving Solitaire with crude number crunching is very time-consuming, so an adapted method had to be found: SolApp generates a population of solution candidates that are made up by randomly selected weights between 1 and 10 for every place (hole on the board). These weights determine the need for a stone on that place.

In the upper main part of the applet, the candidates are shown with their weights represented by a colour-scale on a dark-grey background, as long as they are not yet evaluated.

Candidates are evaluated to determine their fitness: A single solitaire game guided by the weights is simulated, and the resulting pattern is compared with the solution-pattern. The number of places corresponding to the solution (a stone in the middle, where one is expected or an empty hole elsewhere, where no stone is expected) is the fitness of the candidate.

To simulate the game, the candidate starts with the initial pattern having all stones set but in the middle and repeats the following processing: For all allowed moves from the current pattern the resulting pattern after this single step and the total weight of all occupied places are calculated. The move leading to the pattern with the maximum total (see note) is selected and performed, giving the start-pattern for the next step with one stone less. This is repeated as long as there are either possible moves or more than 11 stones left. After the 11-stone-stage, the evaluation enters a new phase for the following reason:

Patterns with many possible moves are those with at about as many stones as holes. When there are only 11 stones left, the number of possible moves begins to decrease (on average), so SolApp can afford to recursively simulate all possible move sequences to evaluate all reachable patterns from the 11-stone-stage, among which is perhaps the sought solution. If not, the reachable pattern with the highest total is taken for the fitness of the candidate.
When evaluation of a candidate is done, it is repaint showing the final pattern on a light-grey background.

 

Genetic Algorithm (GA)

The weights of the different places are not completely independent, but the places of the game that are symmetric to the middle hole always have the same weight. That means, a candidate is made up of 7 classes (A to G) of weights, each for a set of symmetric places. A set of the 7 weights can be considered as genotype of a candidate.

  A B A  
C D C
A C E F E C A
B D F G F B D
A C E F E C A
  C D C  
A B A

We have now a population of individuals (the candidates) with a genotype (the 7 weights) and a fitness (the quality of the final pattern of a game played based on the candidates weights). These are the basics to run a genetic algorithm.

When all candidates of the initial population are evaluated, they are ordered by their fitness. If no one yields the sought pattern, the genetic algorithm of the Genitor-type (see Genetic Algorithms - an Intuitive Introduction for an introduction) is applied: Two (different) candidates are selected, preferring the ones with high fitness. The weights of the selected candidates are combined (each of the seven weights is independently taken from one of both selected candidates with equal probability) to produce an offspring, which is evaluated and insert into the population at the place given by its fitness. Then a candidate with low fitness is chosen and removed from the population, to maintain a constant number of candidates in the population. After a certain number of tries (at about 70), the probability to find a solution with a new offspring is lower than finding one with a randomly created candidate, so the applets restarts a new run with a new population of randomly produced candidates.

If the final pattern of a candidate is the sought solution (either among the start-population or during recombination), the applet stops. Because the population is sort by fitness, the candidate with the solution is always found in the upper left corner.

One detail of the search-method

Of course, there can be different moves leading to different patterns with the same totals of weights. The applet maintains a list of all theoretically possible moves. The sequence of the different moves in this list is arbitrary but constant. In the case of different moves leading to pattern with equal weights, the first move in the list is selected.(back to text)

 

Number-crunching

A crude number-crunching approach might enumerate recursively all possible moves beginning with the start-pattern: For every possible move, the resulting pattern is calculated. For its possible moves, this resulting pattern is calculated and so on. If there exists a sequence of moves that leads to the solution pattern, this algorithm will find it. Unfortunately, you will (on average) get very old and probably rebooted your PC before that happens. We make an estimation of the number of moves to be calculated:

On average, there will be at about 4 possible moves for every pattern of the game. In the beginning and in the end, there are few holes and few stones, respectively. In these situations you will probably have less than 4 possible moves. On the other hand, in the middle of the game with about as many holes as stones, you can move several stones, perhaps even in more than one direction each. There, you clearly have more than 4 possible moves, so we take 4 as a low-end-estimate. With randomly selected (out of the allowed ones) moves starting with the start-pattern, there will on average let's say 28 moves be performed until the game ends up in a dead end (with a maximum of 31 moves, when you have only one stone left). That makes 4 ^28 = 7.2 x 1016 moves to perform. With a Computer calculating a million moves per second (and that is certainly not your browser running a java-applet), it still takes 2284 years.

OK, on average, you will perform only a part of the moves, because you find a solution before every possible sequence is simulated. With this idea and not knowing how many solutions exist out there, I ran such a recursive algorithm for 24 hours without finding a single solution. And you won't wait even one single hour, will you?

Of course, the sketched algorithm is suboptimal: It doesn't make use of the fact that moves in the beginning of the game can be considered as symmetrical to backward-moves in the end of the game. There are geometric symmetries in the game, which reduces the move-sequences to be calculated to a quarter. Moves in separate regions of the board can be performed in either sequence without changing the result. Using these facts would make recurring algorithms more efficient and more complicate at the same time. Besides, SolApp also takes advantage of these symmetries: it only defines guidelines, which places should be occupied without taking care of the sequence of moves.

Sidney Cadot pointet out to me that the depth-first algorithm presented here is "perhaps overly conservative...". As a matter of fact, it runs with very little memory as only the current path is stored. Unfortunately, the algorithm doesn't notice (and has no possibility to) when it enters a certain pattern for the second (and third and forth) time from another direction. It continues to test all possible paths (=move-sequences) leading from this pattern away, and it does so every time it visits the pattern. As a result, all possible permutations of different paths leading from one pattern to another are examinated, far to much to find one single solution.
Sidney himself developed a breath-first algorithm that examins every possible move for all patterns with the same number of stones and stores the reachable patterns for the next step. This greatly reduces the overhead of searching through the same patterns again and again. But it uses quite a considerable amount (about 3 GB) of memory or disk to save the reachable patterns. However, like this it is possible to calculate the entire solitaire-game (that means all possible solutions, mathematically spoken the entire state-graph) within 20 hours with a reasonable equipment (PC with 200MHz-CPU).

Summing up, we can say that a number-crunching approach either runs almost forever or needs rather large amounts of memory, got aviable only recently. Even in the latter case, there's quite a lot to calculate.

36-peg-solitaire

There exists a version of solitaire with 4 extra holes, also known as the french type. The weight-classes were attached to the different places according to the following table, which also illustrates the layout of the board; the places marked with "C" are the extra-holes:

  A B A  
  C D E D C  
A D F G F D A
B E G H G E B
A D F G F D A
  C D E D C  
  A B A  

Unfortunately, the problem starting with a pattern with 36 pegs and the central hole empty and stopping with one peg in the middle is unsolvable. In the original game with this board, diagonal moves are probably allowed which makes the puzzle solvable. In 1998, this was discussed in the newsgroup rec.puzzles; two different proofs for the non-existence of a solution where posted, which can now be found on www.deja.com (make a power-search for the key-word "hi-q" limited to the forum "rec.puzzles"). The simpler of both proofs is copied out of the rec.puzzles archive and commented in the next chapter.

Because there is no "perfect" solution, and to comfort the hopeless seekers of such a solution, the applet searchs for a way from the above start-pattern to a final pattern with two pegs left, one in the middle (place marked with "H" in the table above) and one peg in the middle of exactly one arm (marked with "B"). This happens to be the only pattern with two pegs and one of them in the middle, that is reachable from the depicted starting-pattern, as a consequence of the cited proof. All you have to do is clicking the radio-button labeled with 36-Peg-Solitaire and press the Start-Button >>.

Non-existence of a solution for the 36-peg-solitaire

The following is an excerpt of the rec.puzzles-archive. See Puzzle-Links for references to the archive.

==> competition/games/peg.solitaire.p <==
...
What is the solution for the following board, where the goal is to leave one peg in the center?

* * 1 1 1 * *
* 1 1 1 1 1 *
1 1 1 1 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1
* 1 1 1 1 1 *
* * 1 1 1 * *

==> competition/games/peg.solitaire.s <==
...
There is no solution.

Mark the board with 3 colors like this (Table 1, table 2 will be discussed later on):

  1 2 3 4 5 6 7
1 * * A B C * *
2 * A B C A B *
3 A B C A B C A
4 B C A B C A B
5 C A B C A B C
6 * B C A B C *
7 * * A B C * *
  1 2 3 4 5 6 7
1 * * D E F * *
2 * E F D E F *
3 F D E F D E F
4 E F D E F D E
5 D E F D E F D
6 * D E F D E *
7 * * D E F * *
Table 1 Table 2

let a(n)=(number of pegs on a square with color A after move number n) modulo 2
let b(n)=(number of pegs on a square with color B after move number n) modulo 2
let c(n)=(number of pegs on a square with color C after move number n) modulo 2

then a(n)=1-a(n-1)
b(n)=1-b(n-1)
c(n)=1-c(n-1)
for all 0<=n<=35 .

but a(0)=b(0)=c(0)=0 , so a(35)=b(35)=c(35)=1 ,
which is not possible , as there is only 1 peg after 35 moves.

So far for the proof of the archive. There is a collorary I needed in the previous chapter:
Collorary: If there exists a solution with 2 pegs (after 34 moves), having one peg at position 44, the second peg must be at positions 41 or it's symmetricals 14, 74 and 47.

Proof: a(34) = b(34) = c(34) = 0, the first peg at 44 makes b(35) = 1, so the second peg has to be on a place with color B, too. The type of coloring can be arbitrarly chosen between like in table 1 or in table 2; a solution must conform to both (and any similar) type of coloring. With the coloring in table 2, the second peg has to be on a place with color E, as the place 44 is marked with E. So, the places marked with B in table 1 and E in table 2 are of course 44, and the desired 41, 14, 74 and 47.

 

The Function of SolApp

To discuss the function of SolApp, the representation of the solitaire-game as a graph is needed:
Every possible pattern can be considered as a node of a graph. There are 33 places that can each be occupied or not by a stone, so we can represent the occupied place by a 1 and the free place by a 0. Like this, we describe every possible pattern with 33 bits, which we also use to enumerate the nodes.1)

The (directed) edges of the graph join patterns that are one move apart. A sequence of moves is the directed path leading from the start-configuration to the end-configuration.2)

You can imagine the nodes ordered on successive planes by the number of set bits (though it is not possible to imagine a 33-dimensional hypercube). We will consider only those nodes that are connected by at least one path with the beginning or the end. On the first plane let's say in the left, there is only one node: the start-pattern with all bits set but one in the middle place. On the next plane, there are the 4 nodes representing the 4 (symmetric) patterns reachable from the start. On the next plane, there are more nodes; the bundle of paths form like a funnel getting larger from one plane to the other.

On the other hand (at the right), we have the opposite situation: There is only the solution-situation laying in the last plane with one bit in the middle position. In the 2nd-last plane, there are the 4 nodes we can reach the solution from (in other words: having a directed edge to the solution). The funnel looks in the opposite direction than in the beginning.

The trouble lies in the some middle planes, where the two funnels intermix: some nodes are connected with the beginning, but not with the end. That is where we would not like to go to, but who can tell us when we are there?

SolApp makes use of the fact, that the patterns on the far right planes connected with the end look somehow similar: when you have all stones in the periphery of the board, you will hardly get to the end. That's what gave the idea of the weights: some places are important to be occupied that there is a path to the end, others are not. The first stage of evaluating leads to a node on the 11th-last plane that more or less is given by the weights. In the second stage the path from the found node to the end is sought, or, if there is none, the distance of the nearest node to the solution is calculated. Obviously, distances to the solution and weights are weakly but positively correlated. If not, the GA would not produce better results than simple trial-and-error; that it does is shown in the next section.

In a small experiment, I found that for every 150th node produced in the first stage is on a path to the end. That's why the change from stage 1 to 2 is on the 11th-last plane: The probability to find a solution is not too bad, with reasonable calculation needed to test all possible paths.

One question remains: why did the 24-hour recursive search not produce any solution, compared to the density of nodes leading to a solution on the 11-last plane ? The answer is perhaps, that I used the same constant list of moves for the loops in every layer and like this got in a region in the left funnel far away from the thin lines of the right one, to say it metaphorically. The result could be different, if the moves were selected randomly.

On the other hand, the density of solution-nodes on the 11th-last plane could be less than 1/150, but the first stage of SolApp could lead to a better selection of nodes, because it tends to keep the pattern more or less symmetrical. In this point, further investigation is needed. However, the weights are required as genotype to run a GA, what excludes a totally random-driven first stage, but the weight-classes could be distributed in an other and perhaps better manner on the board.

Notes

1) Two patterns, all 0 and all 1, are impossible, because there is already an empty hole in the beginning and there must remain one stone in the end. Other patterns are not reachable; you cannot have for example only one place free on another position than the middle, for as soon as you make a move, there are already two holes. It are the symmetric of those patterns where the solution cannot be reached from, in the end of the game. back to text
2) This is not a subset of the edges of a hypercube, for they join nodes having a humming-distance of exactly 3 but 1: 2 bits change from 1 to 0 for the place taken the jumping stone from and the stone in the middle taken off the game, and 1 bit changes from 0 to 1 for the place the jumping stone lands. back to text

 

Experiment

167 runs of the SolApp-algorithm were performed. A run started with 30 candidates, all of them were evaluated. If a solution was already found in these 30 candidates, the run fell in class 1. If not, up to 250 generations with one new offspring per generation were performed. Depending on the number of generations needed to find a solution, the run fell in a class from 2 to 12. If no solution was found within the first 250 generations, the run fell in class 13.

class low limit high limit average found solutions evaluations in class per run runs entering class total evaluations in class probability for evaluation to be a solution
i u o n s NC n0 e p
            (n0(1) = N);
n0(i) = n0(i-1) - s(i-1)
e=(n0-s)*NC + s*(NC/2) p=s/e
1 1 30 15.5 30 30 167 4560 0.66%
2 31 40 35.5 16 10 137 1290 1.24%
3 41 50 45.5 14 10 121 1140 1.23%
4 51 60 55.5 11 10 107 1015 1.08%
5 61 70 65.5 7 10 96 925 0.76%
6 71 80 75.5 9 10 89 845 1.07%
7 81 90 85.5 8 10 80 760 1.05%
8 91 100 95.5 3 10 72 705 0.43%
9 101 110 105.5 5 10 69 665 0.75%
10 111 120 115.5 6 10 64 610 0.98%
11 121 130 125.5 5 10 58 555 0.90%
12 131 280 205.5 11 150 53 7125 0.15%
13 281 inf.   (42)   42   runs finding no solution 
no of runs in Experiment (N) 167        

Given the runs that are not solved in a certain class (=n0-s) times the number of generations calculated in that class (=NC), plus the runs that are solved (s) times half the number of evaluations (=NC/2, because a solution is found after half the evaluations in that class on average), gives the total of evaluated candidates in that class (e). The number of found solutions (s) in relation to that total of evaluations is the probability for a single evaluation to be a solution in a certain class. The evaluation is the time-consuming step of the algorithm, so we want to perform only evaluations in classes with high probabilities.

We see three results:

  1. Every 150 randomly generated candidate leads to a solution (p(i=1) = 0.66%)
  2. Up to 70 evaluations per population, the probability for a solution to be found is better than with randomly generated candidates. After 70 generations, the probability decreases, presumably because of convergence of the population. So it is best to stop the run and begin with a new population.
  3. In about 3 of 4 runs, a solution is found.(167-42 = 125 successful runs / 167 total runs)

 

Discussion

The algorithm implemented in SolApp certainly outperforms a number-crunching approach in finding an arbitrary solution, though it does not guarantee to find a solution in every run.
The famous book Ins & Outs of Peg Solitaire describes several techniques to solve the standard game used here and many other games. Having their roots in analyisis 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; therfore, implementing such a technique would have a heuristic characteristic, as SolApp does.

Another advantage of SolApp comes from it simplicity: it's adaption to other solitaire problems should be easy. However, it remains to be investitaged if it's even fast on other problems, as the distribution of the weight classes over the board would need to be adapted.

So, summing up, SolApp shows that a GA can be used for a sufficiant loosley defined problem without having many informations about the inner structure of a problem. "Loosley defined" accounts for the fact that we are satisfied with every solution, without further restrictions like a minimal count of successive moves with the same stone.

 

Literature

There is practically only one book about solitaire. Easy to read also for non-mathematicians.

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

Credits

The solitaire-board was painted with POV-Ray(tm) for Windows, which is copyrighted freeware by the POV-Team. Visit them on their homepage.

To support a scrolling pane in java 1.0, which this applet is written in, I used the LightwightComponentScroller written by John Lehmann (johnl@axis.com.au), Paul Bedworth (paul.bedworth@ed.ac.uk), Tim Macinta and David Geary. Further details see Paul Bedworth's homepage.

 

Ursula + Pascal Glauser 19.07.1999


back home: Ursula und Pascal Glauser's Homepage

See my list of puzzle-links

Other puzzles on this homepage