For some reason the peg solitaire game ended up on our table. I played it a couple of times in my younger years and you might have too. The rules are dead simple: take a peg, jump over an adjecent one to a free square and take the other peg away. Try to end up with 1 peg to win.
But it’s not so easy and this seemed like a nice opportunity to do some coding. The board has 33 places where pegs can be placed, leading to roughly 8,5 billion potential positions. Because of the start position and the rules not all of these positions can be reached while playing:
Note that in this chart the y-axis is logaritmic instead of linear. The blue line shows you all ways you could place pegs without minding any rules. For example, you can arrange the 32 starting pegs + 1 free spot in 33 potential ways. In the real game with 32 pegs there is only 1 position that is reachable: the start position. That’s why the orange line is lower. After the initial move, there are 4 reachable positions with 31 pegs and this ‘escalates’ quite quickly.
Let’s now investigate these reachable positions further. They can be divided into 3 different types:
- Winning positions from where you can still reach the winning end with 1 peg
- Dead ends, where you cannot move anymore.
- Losing positions, where you will eventually hit a dead end before you win the game.
While playing you might not know if you are in a winning or losing position. You will certainly notice a dead end though 😉
Some observations:
- The first couple of moves from 32 - 29 there are no reachable losing positions, so any moves you make are still winning
- Eventually there are way more losing positions
- The first dead end is possible at 26 pegs, after only 6 moves. It’s a nice exercise to try to reach it from the start position.
- There are 4 winning positions with 2 pegs left, but 5 winning positions with 1 peg. That sounds strange untill you see it:
These are the only winning positions you can reach.
How do games proceed in practice if you would play randomly?
The blue line shows that given a position, how high the chance is it’s a dead end. The yellow line is cumulative: how high is the chance a game is still unfinished with a certain number of pegs left. 50% of the games end with 6 or more pegs. Therefore, if you finish with 5 pegs or fewer you are doing better then average. You have 0,001% chance to end up with 2 or even 1 peg winning the game. That’s…. not great.
This chart showed when the game will end. What’s also interesting is if you are in a potential winning position, or in an effectively losing position where you can no longer end with 1 peg:
The blue line shows the chance you have of making a move that still keeps you in a winning state. As mentioned, in the beginning you cannot make a wrong move, but after 20 pegs left many time you have 40% chance to pick a winning continuation. When you have 2 pegs left in a winning position you cannot make a mistake anymore.
The yellow line shows you the cumulative chance you are still winning. With 18 pegs left, you have <5% chance to still be in a potential winning position.
To close a fun fact: even though it’s really hard to reach the final state with 1 peg, there are 81723294080159936 different ways in which you can reach it!
0 / 31
Note
A technical explanation on the calculations:
I encoded positions as binary numbers with an empty hole as 0 and a filled hole with 1. For example, a certain position with 5 pegs left becomes 00000001001110000000001000. The index of the binary number is the specific position on the board. I manually wrote down all the potential moves. For each position I checked if which moves are possible. Because it’s a binary number this can be done quite fast. To find a winning path we first compute all the reachable positions, and once we reach the end we calculate back (with reversed rules) to the starting position. This way we can find all the reachable and winning positions.
Computing all the reachable positions is doable in ~20 minutes, but calculating back from all winning positions, didn’t work (with 200M positions memory was full).
I didn’t use the symmetry of the board, that would have reduced the amount of positions to calculate.
Warning
There is a strategy to win. I didn’t look at it because it solves the game. But in case you want to know, here is one video