Solving peg solitaire by pure chance

2021-06-12, post № 245

C, #board-game

In all the years I regularly glanced at our peg solitaire on the board game shelf, seldomly even playing it and attempting a solve — moving 31 out of the total 32 pegs such that the final peg ends up at the board’s center —, yet never succeeded. The closest I got always left two or three pegs standing far between each other, calling doom for my solve.

One lobe cleared.

Not being able to solve this game, the other day I had the idea of pseudo-random game space exploration, my optimism driven by both the moderate number of pegs as well as the strict monotonicity of the game leading to all solutions being of the same length and thus in a sense equal — bearing in mind consecutive hops in the same direction are not considered as a singular move.

I combined this search with an alternative approach to pseudo-randomness in C, a language which lacks adequate standard library support for acceptably independently uniformly distributed discrete random variables. One of the quickest and unfortunately not at all clean ways to fake pseudo-randomness is to seed using system seconds — srand(time(NULL)); —, meaning the mere fact a human in the twenty-first century executed the program is enough to exhaustively examine all seeds, and then taking the remainder of a poorly distributed 32-bit value — rand() % n, — defining a uniformity-preserving random variable transformation iff $\log_2 n\in\mathbb{Z}$ , an unlikely case.
In conclusion, this approach leads to predictable non-uniformly distributed results.
Rather than implementing a Mersenne twister or elliptic curve pseudo-random number generator, I opted for the possibly simplest if not most efficient way to get ahold of usable pseudo-random numbers; reading /dev/urandom an unbounded amount of times.
However, now having attained uniformity, my selection for the next move to take is most likely very intricately distributed as sorting all possibly moves and uniformly choosing proved to take too long. As a compromise, I encode all conceivable moves in a single integer $m\in\mathbb{Z}_{4n^2}$ whereby $n=7$ is the board’s dimension, apply a uniformly chosen cyclic isomorphism and select the first possible move. As such, if two moves are close in their encoding, one has a far greater chance to get selected than the other.

And to my delight, this approach does find solutions:

solving-peg-solitaire-by-pure-chance_x3y5u-x1y4r-x2y6u-x1y2d-x3y2l-x5y2l-x0y2r-x4y6l-x3y2l-x2y3d-x3y3d-x0y4u-x5y3l-x0y2r-x4y5u-x2y6u-x3y3r-x6y4l-x6y3l-x1y4r-x3y4r-x3y0d-x3y2l-x2y0d-x1y2r-x4y0d-x3y2r-x6y2l-x4y2d-x5y4l-x3y5u.png

A peg solitaire solve.

Above visualized is the solution

x3y5u x1y4r x2y6u x1y2d x3y2l x5y2l x0y2r x4y6l
x3y2l x2y3d x3y3d x0y4u x5y3l x0y2r x4y5u x2y6u
x3y3r x6y4l x6y3l x1y4r x3y4r x3y0d x3y2l x2y0d
x1y2r x4y0d x3y2r x6y2l x4y2d x5y4l x3y5u

where each entry defines a pin via coordinates with origin in the top-right corner and moves it in one of the cardinal directions ruld.
The visualization is defined as follows: every pin’s move’s index determines the C-shaped indicator’s size and its orientation this move’s direction. One can see that the smallest of the 31 indicators points precisely at the center, implying it is a perfect solve.

Having run the search multiple times, only five scenarios appeared thus far: either it is a perfect solve or the last pin is centered on one of the four sides.

Source: solving-peg-solitaire-by-pure-chance.c