John Conway’s Impossible Game

Conway’s Soldiers was invented by John Conway in 1961.
The structure and rules of the game are quite simple:

  • You have an infinite checkerboard and infinite ‘soldiers’.
  • The board is divided by an infinite horizontal line.
  • A valid move consists of jumping over one neighboring soldier vertically or horizontally (diagonal movement is not allowed).
  • A soldier that was jumped over is removed from the board.

The goal of the game is to place a soldier as far as possible from the horizontal line.

With infinite board and infinite soldiers, you might think that it is very possible to reach any distance, but it might be hard to come up with the correct sequence of moves but shockingly enough, you can reach just a few lines above the horizontal lines, let’s explore.

Cracking The Possible Levels

Before we go and play, if you wish to experiment on your own without me giving you spoilers, you can use this online tool, or this one to play the game.

Disclaimer: I am not associated with these online interactive games in a way.

Well, the time has come, let’s play. 
Level one is fairly easy, requires only two soldiers and one move.

from Wikipedia

Simply get the blue soldier and jump over the red one to reach the green marked spot and that’s it, level one is done.

Moving over to level two, we will need 4 soldiers and 3 moves.

from Wikipedia

Moving red soldier over the blue one, then yellow over black, and finally yellow over red. the yellow soldier got to the green spot, well done.

To complete level three we will need 8 soldiers and 7 moves.

from Wikipedia

Since imagining 7 moves in your head might be challenging I will only show you the setup so you could play around with it in the online tool I mentioned above or with a checkerboard for example.

Note that in the above setup, the soldiers marked as ‘B’ can be replaced with the ones marked with ‘A’ (both setups will get you to level 3).

To complete level 4, we need 20 soldiers and 19 moves.
Same as before, 19 is just too much to imagine (or is it just me?), so here’s the setup.

from Wikipedia

Believe it or not, no matter how hard you try you won’t succeed in completing level 5, no matter how many soldiers you have.
To those of you who are getting triggered by me saying it’s impossible and want to prove me wrong, proceed with caution, it might be time-consuming.

Conway proved that, regardless of the strategy used, there is no finite sequence of moves that will allow a soldier to advance more than four rows above the horizontal line.
The outline of the proof can be found on Wikipedia.

A few years later, Simon Tatham and Gareth Taylor showed that it is possible to reach the 5th line with a sequence of infinite moves.
At the beginning of their paper, they give a good intuition about how Conway proved his argument:

Simon Tatham and Gareth Taylor paper

Aside from their paper, they create a web page containing the proof and cool visualizations.

Reaching the 5th row, Simon Tatham and Gareth Taylor webpage

2 comments on “John Conway’s Impossible Game

  1. Good post. I learn something new and challenging on sites I stumbleupon every day. It’s always helpful to read content from other writers and practice something from other web sites.

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: