Reaching row 5 in Solitaire Army

Introduction

Solitaire Army, also known as Conway's Soldiers, is a mathematical game similar to peg solitaire. The setup is: you have an infinite peg solitaire board extending in all directions, and the starting position has a peg in every single position on the x-axis or south of it. In other words, every position (x,y) with y ≤ 0 contains a peg.

[491x311 GIF, 5KB]

Legal moves are precisely those of peg solitaire: you may move a single peg exactly two spaces in any of the four orthogonal directions, provided the space it jumps over contains a peg and the space it ends up in is empty. The peg jumped over is removed.

[131x107 GIF, 8KB]

The aim is to advance one peg as far north as possible, using up as many other pegs as you need to help get it there. Reaching y=1, for example, can trivially be done in one move; reaching y=3 is reasonably easy; reaching y=4 takes nearly twenty moves even with optimal play.

There is a well-known proof that reaching y=5 is actually impossible. I won't give all the details of the proof here, so as not to spoil it for anyone who would like to try proving it themself; but the basic approach is to define a numeric value for a peg occupying each square on the board, in such a way that no valid move can increase the value of the pegs it affects, and hence the total value of the board can at best stay the same. The valuation is also defined in such a way that the total value of all the pegs in the starting position is finite (in the same way that, for example, the sum of 1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ... is finite) – and if we work out what that value is, we find that it is exactly equal to the value of a single peg at y=5, so that you cannot reach the fifth row without using all the pegs on the board. But there's an infinite number of pegs on the board, and you are (implicitly) only allowed a finite number of moves, so you can never use them all and hence can never reach the fifth row.

It occurred to me one day, however, that if we could somehow find a way to make infinitely many moves, then the above proof would stop being valid, and it might indeed be possible to reach the fifth row by using up all the pegs on the entire infinite board.

And, indeed, this can be done. On this page I show how.

Basics

If we want to do this, we have to start by making sure we can meaningfully define what it means to make infinitely many moves on a peg solitaire board.

One obvious thing you could do would be to make a lot of moves in parallel, if none of them interfered with each other. For example, you could simultaneously jump every peg in the y=−1 row two spaces upwards, thus removing all the pegs in the y=0 row and completely filling the y=+1 row. This would be an entirely well defined idea, but not particularly useful.

[491x95 GIF, 5KB]

A more interesting possibility, though, is to make moves in an infinite sequence, with each move depending on the result of the previous one.

For example: suppose we started out with a line of pegs extending off to infinity in one direction. We can clearly jump the second peg in the line over the first one; then we can clearly jump the fourth peg over the third into the space we've just made; then we can jump the sixth over the fifth, and so on. Making any finite number of moves from the start of this sequence would be perfectly legal by the standard Solitaire Army rules.

[287x35 GIF, 8KB]

But it's not too much of a stretch to imagine making all the moves in that sequence, and going on forever. Doing so has the property that each individual board position changes between empty and full a small finite number of times; no position changes infinitely often. So for each board position, we can meaningfully talk about its eventual state: whether it ends up with a peg in it or not after our move sequence finishes messing about with it.

So what we would like to do is to allow ourselves to make all the moves in the above sequence, leaving every peg in its eventual state, and then make some more moves afterwards.

A nice way to make this rigorous is to imagine making all those infinitely many moves during a finite space of time, by acceleration. We make the first jump in the sequence at time t=0; the second jump at t=1/2, the third at t=3/4, the fourth at t=7/8, and so on. At t=1, we have therefore made all the moves in the sequence, and yet we haven't run out of time in which we can make more moves.

Making it mathematically rigorous

In this section I set up a more formal mathematical foundation for the intuitive idea of infinite move sequences described in the previous section. If mathematical notation scares you, you can safely skip this section and move on to the next one, where you'll find more actual infinite solitaire moves to scare you instead.

Formally speaking, my model is as follows. I define a function f(x,y,t), with x,y integers and t a real number, which gives the state of the board position (x,y) at time t. The value of f(x,y,t) is at all times either 0 (meaning there is no peg at that position), 1 (meaning there is a peg), or 1/2 (meaning that t is the precise instant of a move which changes the value of that position). The function f is then subject to some constraints:

So we are after a function f which satisfies all of the above constraints, and also has the property that at some time t0 the board is in the starting position (in other words, f(x,y,t0) is 1 if y ≤ 0, and 0 otherwise), and at some later time t1 > t0 there is a peg in the fifth row (f(x,5,t1)=1 for some x; in fact, without loss of generality we may assume that x=0 and that we're specifically heading for the point (0,5).)

I won't go through the tedious details of proving that the construction I've exhibited above satisfies all the constraints on f (apart from the starting and ending ones), but a keen reader shouldn't find it too difficult to do so.

The model I've defined here actually rules out my example of parallel moves, in the precise form I exhibited it above. The one-move-at-a-time rule forbids us from making infinitely many moves in the same instant, as I talked about above. Instead, we must make the moves one after another, in some arbitrary order (although any order will do).

[491x95 GIF, 73KB]

Incidentally, a consequence of the rules as I state them above is the following theorem:

for every time instant t
for every (x,y)
there exists some ε > 0 such that
within the time interval (tε,t+ε)
the position (x,y) is not involved in any move which is not at time t.
The interesting thing about this is that if I were to merely swap round the second and third lines of the statement of that theorem, so that a single value of ε had to work for all (x,y), this would turn it into a constraint which permitted only finitely many moves in any bounded time interval, and hence we would have reverted to exactly the standard definition of the game. This illustrates just how little I've had to change the rules to permit infinite move sequences.

Another useful move

I've given, above, an example of what I describe as a forward infinite move sequence: a sequence of moves which has a clear beginning, but no end, compressed into finite time so that we can make more moves after it. I now give an example of a backward infinite sequence: one with a clear end, but no beginning.

Observe that in the formal definition of my rules all the constraints I defined on my function are time-symmetric, except for the fact that the position being jumped over in a move always changes from full to empty. It is sometimes more convenient in peg solitaire problems to consider the time-reversal of those rules: to play reverse peg solitaire, in which the only legal move is to jump a peg over an empty space and thereby fill it. Any sequence of moves valid in reverse peg solitaire can be time-reversed, and then becomes a valid sequence in ordinary (forward) peg solitaire.

Suppose, in reverse peg solitaire, we start out with a single peg and we wish to turn it into infinitely many pegs. How might we do this? Well, we have to start by making some move: let's jump our starting peg to the left, turning it into two pegs. Suppose we then jump the leftmost of those two pegs left again, turning that into two pegs; and suppose we jump the leftmost peg left again, and keep going. This gives us a forward-infinite sequence of moves in reverse peg solitaire which turns a single peg into an infinite line of which every other space is occupied.

[287x35 GIF, 8KB]

And because every valid sequence in the reverse game can be time-reversed into a valid sequence in the forward game, we can reverse the above manoeuvre to give us a backward-infinite sequence of moves in forward peg solitaire.

[287x35 GIF, 8KB]

This trick, for some reason, tends to make people's brains hurt. People I've talked to seem to take the previous section in their stride: they find it reasonably easy and intuitive to imagine starting a sensible-looking process, carrying it on forever, and then doing other things ‘once it's finished’; but they find it much harder to imagine the analogous process in the reverse direction. ‘At the start of that sequence,’ they complain, ‘no two pegs are adjacent, so no move can be possible. How do you get started?’ However, backward infinite move chains are just as legal as forward infinite ones according to the rules I laid down in the previous section; a forward-infinite chain of moves can legally be performed by doing them at times 0, 1/2, 3/4, 7/8, 15/16, ..., and a backward-infinite chain of moves can be just as legally performed by doing them at times ..., 1/16, 1/8, 1/4, 1/2, 1. If you focus on any individual position (x,y) and any finite region around it, you will find nothing objectionable or counterintuitive taking place in that environment, in either case.

A particularly useful feature of the backward-infinite move sequence I've just described is that its starting position is exactly the same as the ending position of the forward-infinite sequence I described in the previous section: a line of alternating pegs and spaces, stretching off to infinity in one direction. Hence, we can perform the two sequences in immediate succession (so that the moves of the first sequence occur at times 0, 1/2, 3/4, 7/8, 15/16, ... and those of the second sequence occur at times ..., 17/16, 9/8, 5/4, 3/2, 2), and thereby generate a move sequence with the overall effect of transforming an infinite line of pegs into a single peg two spaces beyond its original starting point.

[287x35 GIF, 15KB]

In the following section this doubly-infinite sequence will be used quite a lot, so we'll need a snappy name for it. Gareth called it a ‘whoosh’.

Further complication

I've now described a move sequence which turns a semi-infinite line of pegs into a single peg. Next I'm going to describe a move sequence which turns an entire quarter-plane into a single peg: a ‘megawhoosh’, if you like.

A new concept that will be introduced in this section is the idea of performing an infinite sequence of steps of which each step contains several ‘whooshes’ as described in the previous section, each of which in turn contains infinitely many moves. This isn't too difficult: once we've got the idea of performing infinitely many moves in a finite time, it's then reasonably simple to divide a finite time into infinitely many intervals (e.g. one of length 1/2, one of length 1/4, one of length 1/8, and so on), and then to subdivide each of those intervals up into infinitely many parts as well. This still doesn't break any of the rules I defined above: every move still happens at a distinct instant of time, and no square is filled or emptied infinitely often.

One obvious way to perform a megawhoosh, using that idea, would be to whoosh every column of our quarter-plane upwards independently, and then to whoosh the resulting row inwards to create a single peg:

[491x311 GIF, 1425KB]

But this, it turns out, isn't particularly useful. The single resulting peg ends up two spaces inwards from the quarter-plane; so if we want that peg to end up on the central column, our megawhoosh will have to consume the quarter-plane starting two spaces out from there. That leaves the column next to the central one still to be dealt with, and there's just no sensible way to deal with it.

So we need to do something rather different. I'm now going to exhibit a more complicated but more useful megawhoosh: one which consumes the entire quarter-plane left of the central column, and leaves one peg at (0,3).

This procedure is going to involve a large backwards-infinite sequence of operations, so it's most convenient to describe it in reverse. Hence, we start with a peg at (0,3), and our aim is to make reverse solitaire moves to turn it into the required quarter-plane.

[491x311 GIF, 4KB]

We begin by moving our peg left. This first move gets us out of the central column, and hereafter we will not touch the central column at all.

[491x311 GIF, 4KB]

Next, we whoosh these two pegs downwards, leaving two full columns starting one space above the line. (Since we're currently playing reverse solitaire, of course, the whoosh sequence is also performed in reverse, converting one peg into a semi-infinite line of them rather than vice versa. When we replay this forwards, it will become a normal whoosh again.)

[491x311 GIF, 4KB]

Now we move the top peg of the left column left:

[491x311 GIF, 4KB]

Then we whoosh the resulting two pegs downwards again:

[491x311 GIF, 5KB]

Now repeat those two steps with the top peg of the new left column:

[491x311 GIF, 5KB]

Then keep repeating those two steps infinitely many times. Once we finish that, we have a perfect staircase of pegs descending off to the left:

[491x311 GIF, 5KB]

(What we've just done is a forward-infinite sequence of moves and whooshes in reverse peg solitaire. Hence, of course, when run in the forward direction, it becomes a backward infinite sequence of moves and whooshes, but – just as in the previous section – it's no less legal for that.)

Next we take every other peg on the outer edge of that staircase, starting with the topmost one, and whoosh them all to the left:

[491x311 GIF, 5KB]

Now all we have to do is to move those alternating pegs downwards in each column to fill in the gaps. This takes only a finite number of moves in each column:

[491x311 GIF, 432KB]

And we end up with a tightly packed quarter-plane:

[491x311 GIF, 5KB]

And that's our desired megawhoosh, in reverse. Run the same sequence of moves in the forward direction, and we convert the quarter-plane with x < 0 and y ≤ 0 into a single peg at (0,3), as promised.

The solution

Now that we have the whoosh and the megawhoosh, the actual solution is quick to state:

Here's an animation of the entire solution run in the forward direction. (It takes about 75 seconds to run fully, so if it's half way through by the time you've read this far, wait a little while and it'll start again.)

[491x311 GIF, 3987KB]

Gareth Taylor and I wrote up a more formal article containing the material on this page and some additional proofs and discussion.

Credits

John Horton Conway devised the original proof that y=5 cannot be reached in finitely many moves; he may or may not have invented the Solitaire Army problem itself.

Simon Tatham had the idea of making a serious effort to reach y=5 by means of making infinitely many moves; he laid down the ground rules, invented the whoosh, and wrote this web page.

Gareth Taylor named the whoosh and invented the useful form of the megawhoosh, completing the solution.