Death Army Robot Firing Squad

Death Army Robot Firing Squad

A couple of weeks ago I was watching youtube and I watched the first part of a video about this puzzle, and I felt (when I finally watched the second half) that he didn't do it justice in trying to solve it himself - he presented the problem, possibly not in a great way, didn't set the historical context, and then just published one of the answers. And I felt that perhaps I could give you a better shot of it.

In the past week, after I had been tackling this problem, I've had two distinct conversations, the first was with another lead developer who was bemoaning the fact that young developers are trying to solve problems that were solved before. The second was with the father of a computing student, who was complaining that he wasn't allowed to use cool frameworks for his project, but instead was frustrated that he was being taught things from 30 years ago.

The coincidence that I happened to be tackling a computer science problem from 1957 was not lost upon me, and that I am appreciating the solution has applications in modern-day computing. This problem and my attempt at a solution as presented here have impacts onto an unknown size 'hive' type automation.

However, I don't know why mathematicians have such dark backgrounds to their puzzles. It's always "you've been imprisoned on a mountain lair, where you have to guess the colour of your hat before you'll be released, but you can only see the other prisoners feet and have one guess per day". Anyways, it's 1957, and mathematician John Myhill is proposing a problem about robot firing squads.

The Bad Assed Machine Robot

In my picture here, the robots are armed with a ray gun, and they have the obvious radio antennas above their heads. Those don't work for some unknown reason, otherwise, this would be much easier.

If we present the problem today, with 'modern' technology, the solution is rather trivial, and I will address this further down, but it has some interesting historical context.

John Myhill was an English mathematician who at the time was forming maths that then lead to an area called 'Celluar Automation' which in turn was where John Conway formed his 'Game of Life' - something that he is famous for, but feels it wasn't his greatest accomplishment and would rather talk about something else, and the summary of the problem is such:

A row of robots forms a firing squad. They are aware of robots on either side of them, and they have identical programming. When the one on the end is given a command to 'fire when ready', the entire row needs to organise themselves so they all fire at the same time.

I suspect there is some reason they all need to broadside at the same time and some other reason that it's a firing squad and not something more gentle like a robot dance troupe, but here we are.

The problem was passed by word and was originally solved by a pair of mathematicians John McCarthy and Marvin Minsky, but more interestingly it was solved by Eiichi Goto in 1962, and the problem finally published by Edward Moore in 1964. He, in publishing it, makes some interesting observations:

  • Because it has been solved, the problem becomes easier to solve by others (even if they don't know the solution).
  • If you know how to solve it. Don't tell anyone, because that destroys the fun.

The actual problem has a bit more to it. Beyond the first objective of 'fire at the same time:

  • The solution must use a Finite State Machine
  • The robots on the end are 'Generals' - they can have a different program to the robots in the middle because they have to handle the fact they're on the end.
  • The robots state is the only communication to the ones on either side (i.e. there are no special outputs of lights or flags, but instead the position of the robot is the state). This last point is a very important constraint.

The original Goto solution used "thousands of states", but once solved, it became a target to be solved more efficiently with less states.  The Wikipedia page charts the progress of the problem far better than I can restate it. The problem evolves down three main paths:

  • What is the minimum time between the 'fire at will' signal, and them all firing,
  • Is there a state machine which will implement this minimum time? [yes, Goto]
  • What's the minimum number of states to get to a synchronisation?
  • Finally, what's the minimum number of states to get the minimal time?

The latter problem is perhaps one that annoys me - as an engineer, I prefer my programs to be maintainable rather than necessarily short. Optimising a state machine (the equivalent of playing Code Golf) is not a pastime that I enjoy, but rather leads to a more confusing answer.

I would like to address Gotos 'thousands of states' solution - I have struggled to find his original paper (which is referenced from others), but I do wonder if he did list his state machine, or rather a generalised approach and discussed the edge cases showing how many states would be needed for each edge case. As such a solution, he wouldn't have been able to do the simplification, which would have needed a concrete answer, and I'm sure he was more than capable of reducing it down had he the inclination to do so.

Whilst Moore in his paper suggests using paper to solve the problem, I used my head (and to be honest, didn't look at any solutions before I attempted my own). I considered what options I had, what I could use a state machine to do, the nature of how messages propagate through the cells.

Then my process followed this path

  • Develop a state machine simulator, along with a way of configuring it
  • I realised I needed a language to help me define this easier, so wrote a 'compiler' to allow me to define the machine (details below)
  • With a working machine and compiler, I could define a solution to the problem
  • Then an animation to allow me to make the video (and hence these dancing robots).

Finite State Machines

We don't use Finite State Machines in modern technology. We do use 'States' and we often call something a 'State machine' (or at least, I hear it in my circle of friends), but they're not State Machines. We use the term State in modern programming languages to control objects and to turn functionality on and off, but we don't truly use state machines.

So what are state machines, and why did they die out?

There are two types of finite state machines, and the difference is subtle, and often irrelevant on simplistic machines, but more perhaps obvious on larger complex ones, but in both systems, a machine has a limited 'memory' where it can remember its current state and a bunch of defined inputs. These inputs are not necessarily binary but could be any kind of mechanical or analogue inputs. It's not even defined that a state machine is a binary computer but could be any kind of computational device mechanical or (now considered) exotic. Remember these maths are from a time before Transistors dominated computers, indeed Goto the original solver had his research computers that used phased angles of analogue signals to perform calculations.

The machine moves from one state to the next state when a set of inputs match its rules for that particular state - each state has its own rules, and not every state uses all the inputs.

Some state machines are clock-driven (i.e. tests the inputs every tick), which is the type we will be looking at here, but others work more analogue and can work on an edge (e.g. when a signal goes high). Clock driven state machines are easier to think about as each state is for a discrete amount of time.

As mentioned the two main families of state machines are Moore state machines (named after Edward Moore who published the problem in 1964), and Mealy machines (named after George Mealy). Moore machines are easier to understand and build, and are the more common sort, where the outputs are defined by the state the machine is in, where a Mealy machine, the outputs are defined by the last state transition (i.e. leaving a state sets the outputs, not entering one.

Both machines can be drawn as a graph (not a chart).  Simple state machines such as climate controls can be seen here. In this example machine, the input is a value from a thermometer, and the output is a signal to turn on or off a heater, or fan.

Countdown firing

So these are state machines, but what are 'Finite' state machines? - well simply, that the number of states is a countable, describable amount, rather than an abstract number. To give an example, one solution to the problem is to have the robots enter a state one number higher than the robot on the left until it gets to the general on the right, which issues the command to start counting down - as it does so they count down (and trigger the robot on their left to count down), and finally, they all reach 0 at the same time. This is not a finite state machine, as the number of states needs to be effectively infinite: We could argue its a *practical* good example, as a 32 or 64-bit state counter would allow unimaginable numbers of robot firepower, but it does not solve for *any* number of robots. I feel slightly bad for criticising this approach given my solution, which does scale well beyond the MAX_INT of any bit counter but has its failings. It certainly does not implement anywhere near a minimum time for n robots, as the firing will always take max time.

Countdown failure where army is bigger then state machine

State machines are relatively easy to implement using basic logic. If we use binary inputs (and especially if we're flexible on the memory-value of the state to take advantage of Karnaugh maps etc), we can implement state machines using only sets of AND/OR gates.

And why then did they die out? This is because of technology - even where we would use a state machine, it is cheaper and more effective to use something else like an FPGA or a microprocessor. Microprocessors are mass-produced, and therefore a general-purpose embedded computer is cheaper and provides more functionality (and the ability to change) than dedicated electronics of a State Machine. Even systems such a Power Logic Controllers using Ladder Programming which are great for implementing State Machines on are just microprocessors under the hood providing an interpreter on the top of it.

However states are super helpful in modern programming - for instance, in most of my web applications, I have an object called User. This user has a general state attached to it, which defines the functionality available.

States, but not a State Machine

When a user is in 'Good' states, they can log in. Note that this isn't a true state machine because it has other variables (e.g. bad login attempts). Arguably a State machine can be constructed with that both as external storage, as both an output and input, but in this case, it's a conceptual model. When the user is in other states (such as deactivated, or locked), other functions are available, some by the user, some only by an admin. States of objects are powerful, but State machines are limited compared to the power of modern programs.

Modelling a State Machine

This proved to be much more trivial than I had anticipated, mainly by a decision to use regex for the machine rules. The first decision I made was that the object would have two variables: the current state, and the program as a dictionary, with the initialiser able to reset it. Then there would be a single function 'tick' which would take the states of the machines on the left and the right. The Tick function would convert the two inputs into a string of `{left}-{right}` and then this would be compared to each key in the current state's rules - if it matches, the first one that matches the value becomes the new state. If nothing matches, then the state does not change. This prevents me from having to write all the potential states as loopbacks, in effect, there is a rule `.* -> current state` at the end of every state.

class RobotStateMachine():
    _current_state = None
    _machine_code = None
    def __init__(self, machine_code):
        self._machine_code = machine_code
        self._current_state = "0"
    def current_state(self):
        return self._current_state
    def tick(self, left_state, right_state):
        if not self._current_state in self._machine_code:
            # robot is stuck in this state until the end
            # but here for edge cases / programming
        current_logic = self._machine_code[self._current_state]
        target = "%s-%s" % (left_state, right_state)
        found = False
        for key,val in current_logic.items():
            if, target):
                found = True
        if found:
            self._current_state = val
        # if not found, maintain state
    def __str__(self):
        return str(self._current_state)

Predicting an issue with state changes, the 'tick' is done in two phases: firstly I loop over the machines to get their current state and use this as the input to the tick functions, rather than the exact current state. This is done often in electronics by using a form of a buffer such as a flipflop to prevent an open circuit, which can lead to undefined state changes based upon physical distances rather than organised state changes, so the actual machine is done here:

def tick_army(ar):
    states = []
    for machine in ar:
    for machineid in range(len(ar)):
        if machineid == 0:
            left = "-2"
            right = states[1]
        elif machineid == len(ar)-1:
            left= states[machineid-1]
            right = "-2"
            left= states[machineid-1]
            right = states[machineid+1]

I used numbers for most of my states and used the special numbers -1 to indicate firing, and -2 to indicate the edge (which is used only by the general). And a funky debugger to show current states:

def construct_army(ar):
    mystr = ""
    for machine in ar:
        mystr += "%s " % str(machine)
    return mystr

Realising that making changes to the states was painful, I then decided to invent my own language format to allow me to have programs that could be flipped in and out at will. And so, Bad Assed Machine (they are killer robots after all) Script is born:

# BAM Script!
# prototype script file
# comment

    regex 	targetstate
    [2-3]+-/d+   3
    [3-3]+-/d+   4		# Also a comment
    # also a comment

    0   2   # comment
    regex whatever

The language allows me to put both the General (end robots) and Privates (line robots) into the same file with delimiters. Taking some inspiration from assembler and python which uses whitespace, anything tabbed in is a state rule, with the states defined by the lack of leading whitespace. Adding in a comment structure (because anything like this needs comments), allows a program to be defined.

The 'Compiler' (although to call it a compiler is a bit of a stretch), is then written. This can convert it from the flat file into the python dictionary ready to run. Now with a small start up routine I can quickly test state machines:

with open("myprog.bam") as file:
	program =
general_program, private_program = BaMCompile(program)

mid_length = 8
robots = []
for i in range(mid_length):

robots[0]._current_state = "1"

Finally, I wanted a way of visualising my programs as they became more complex. Many years ago (in my dissertation at UEA) I found this wonderful program called Graphviz which allows the rendering of Graphs, and it has wonderful python bindings, so it is trivial to make that work:

def generate_graph(machine):
    dot = Digraph(comment='State Machine')
    for state, rules in main_machine_code.items():
        for rule, value in rules.items():
            dot.edge(str(state), str(value), label=rule)
    dot.render("filename", format="png")))

This allows us to now draw the graphs of the states (and remember if there is no match it stays in the current state, and here are some sample programs graphed out:

It's also relatively trivial Jupyter notebooks it's easy as well without going via an intermediate file - replace the last line of the graph function with: (And put the import near the top)

from IPython.display import display, Image


Because I was going to make a video, I also then worked on an animation, where I built a sprite sheet and provided different arm and leg positions to allow me to demonstrate the 'states' of a robot. The positions are arbitrary, but I did try to match a couple of specific 'end' states to particular hand signals just so I could easier spot them (however all my debugging was done on the console output which let me see the time before and after clearly - in this screen shot we see the animation, but with the state history being printed off on the left.

Historical states on left, with animation on right

Using Jupyter allowed me to rapidly prototype the different states, with a fast print out to debug individual situations. The source code is all available in the invalid entry Github account.

Killing the Fun - Working towards a solution

I'm hoping by this point you've attempted to think of a solution, and if you haven't then you should. Before jumping to the solution, I thought it would be good to demonstrate some message-passing elements and some other tricks.

My first, bad solution. I had done this one in my head, and I knew it was bad before I even programmed it, and it is described above, But just for the animation, I programmed it up. It will work on robots up to 10 long here, and any number below that, but will not work for 'any size' (demonstrated on a 16 robot array below).

So I started constructing different design patterns in my head which would provide me with the tools I needed to solve the problem, and it was only after I had mostly solved it that I found E Moore's original paper which gives some hints on how to solve it.

Passing a signal, then doing it at different speeds

Speed 1 Signal

It's relatively trivial to cause a message to be passed down the line, given the program X, each robot goes into the second state if the robot on the right was in the second state on its previous round. This state machine here, along with the demonstration.

0:  # netural state
    1-\d+   1       # If left hand side is 1, go to 1

Note there is no explicit definition of state 1, but it goes into it because its declared as an exit from state 0.

If we wanted the state to reset after passing, we could add the rule into state 1 as such:

0:  # netural state
    1-\d+   1       # If left hand side is 1, go to 1

1:  # Trigger to the Right, but return to 0 no matter what
    .*      0
A slow (speed 3) signal pass

Passing it at a different speed though is relatively straight forward - in this manner we use an intermediate state to force a delay. We have three states - at rest, delay, and trigger. In the rest state, we are looking to see if there is a trigger on the left, at which point we move to delay. Delay now has a rule that is whatever the inputs, on the next tick we move into the trigger state. This means that the signal goes down the line on every other tick, rather than on every first one.

0:  # netural state
    1-\d+   3       # If left hand side is 1, go to delay sequence

3: # Delay part 1
    .*      2

2: # Delay part 2
    .*      1

1:  # Trigger to the Right, but return to 0 no matter what
    .*      0

Note the left hand part is running a different section of code so only stays on 1 which triggers follow up waves of 3's to be sent across.

Bouncing a signal

Bouncing speed 1 signal

Bouncing a signal also involves the use of an intermediate state, because we don't want to trigger more follow on signals. For this, the end general has a state that looks something like this (which is almost the same as the normal message pass), but then the privates have a state machine on the right; this allows them to pass the bounced signal in the opposite direction. For this example, theres two programs used - the General (which is the ends), and the Privates (the middle). The Privates will pass a message across in either direction (1's going right, 2's going left).

# BAMScript - Bad Assed Machines v1
# Bounce signals


0:  # netural state
    [13]-0      1      # left pulse
    0-[23]      2      # right pulse
    [13]-[23]   3      # colliding pulses

1:  # Fast pulse, from left to Right
    [13]-0      1      # left pulse
    [13]-[23]   3      # colliding pulses
    0-[23]      2      # right pulse
    .*          0      # Anything else, (i.e. 0-0), back to neutral

2:  # Fast Pulse, from right to left
    [13]-0      1      # left pulse
    [13]-[23]   3      # colliding pulses
    0-[23]      2      # right pulse
    .*          0      # Anything else, (i.e. 0-0), back to neutral

3:  # Fast pulse - crossing over both ways
    [13]-0      1      # left pulse
    [13]-[23]   3      # colliding pulses
    0-[23]      2      # right pulse
    .*          0      # Anything else, (i.e. 0-0), back to neutral

# This code works for both ends (interleaved code)
    1--2    2   # Right hand go to 2 - i.e. bounce!
    -2-2    1   # left hand go to 1 - i.e. bounce
1:              # Triggered by kickoff routine or bounce
    .*      0

2:                 # Bounce and return to 0
    .*      0

The program for the private here is a little more complicated then you might expect because this has been designed to handle multiple signals passing through, i.e. no collisions but clear passthroughs.

Now Actually Solving by Working Backwards

To solve it, I first decided what would have to happen for a robot to decide to fire. It needs to know that the neighbours on either side were going to fire on the next round. Secondly, I realised that some robots would be able to fire sooner than others, but had to know that the others wouldn't.

To begin with, I was imagining having some form of structure like an army. Perhaps I was influenced by the military based posing of the question, but I was wondering if (for example), every 10 robots, robots could elect a Sargent that is then giving a final 5 count down (i.e. to the 5 on either side). This would allow a set of finite states as the robots counted (up to 10), but then the problem just goes up one level of how do the sergeants get synchronised. And so my mind went in a loop for a bit of trying different strategies until I realised that every other robot needs to be a sergeant - but, and this was the super important bit, you don't set them up on the first pass, but instead put them in in the form of a binary split.

So the first thing to do was find the midpoint, and mark it, and then start again - because we just keep splitting the robots into two subgroups, until finally, the robots realise they're between two sergeants and that's it, they mark themselves as ready, and everyone fires on the next round.

The problem then is how to find the midpoint, and, the tools above help - we use the signals of different speeds and a bounce to find that point. To cause a collision between two signals moving at different speeds. If we look at how that would work, we know the fastest we can move is 1 cell per tick, i.e. speed 1. That signal has to go all the way across, and back, i.e. 1.5 widths. On the other hand, the slower follow up signal only has to go halfway across (i.e. 0.5 widths). The ratio of distance travelled is 3:1, i.e. the second signal needs to move at 1/3rd the speed, and it will always hit the middle.

This then goes back to Moores paper where he writes:


Whilst he suggests using paper, I found doing it in my head and visualising it to be easier then the Chess grandmasters playing in their head. But thats perhaps because I'm good at electronics and not so good at Chess, but the diagrams begin to look like this (finding the mid point as a signal diagram) - note the shape, because this shape will begin to appear in our state machine outputs later.

In my actual solution, I have a concept of a 'left hand' and a 'right hand' general which are in the state (my sergeants got a promotion somewhere) - these are used instead of a single midpoint, so where the midpoint is found, it's placing a left and right general instead. The generals are promoted because as far as the 'privates' on either side care, they look like the end of the line. The privates no longer care where they are in the total lineup, just are they between two ends (And when they are, they then fire on the next turn).

State machines to find the middle robot are then trivial, and if I print out the robots states over time, you begin to get patterns like this emerging.

There are two edge cases here; either the midpoint happens on a single robot, or it happens between two robots (i.e. there is either an even number of robots or an odd one). And here's where I have to admit something, in my solution, it currently only works for even numbers of robots - and that means all sub-groupings need to be even, which means it only works numbers which are powers of 2. This is solvable (And I attempted to solve it) before with two types of endpoint, however, that solution went very messy and sideways quickly.

Nope. Don't ask

So resetting the project and starting again allows some progress. After finding the middle (and accepting that we're not in the final states yet), we can then bulk out the state machines to send 1 and 3 speed signals both forwards and backwards (by using an intermediate state to trigger only once), and before you know it, we suddenly have this occurring:

The final solution

What is very interesting is the shapes appearing on the left hand side - the first shape is as expected, followed by two more, one reversed, both half the size, and then the sizes half again, and again, and then finally we're in the nearly final state where all the robots know that they're in synch, and boom. Game over.

For a longer sequence (64) see - however I admit I have truncated the states to just the first character of the state to allow it to print nicely.

The final program:

# BAMScript - Bad Assed Machines v1
# Attempt at a solution 
# Works up to midpoint detection on odd/even combos 

0:  # netural state
    ^1-.*       1
    ^3-\d+      3 # left hand is a slow pulse, go to 1 to slow pulse
    8-.*        1
    .*-(7|11)   11 # FIXME

1:  # Fast right trigger
    (4|[LM]HG)-.*        2   # slow right step
    .*-[56]     5   # Fast back
    .*-5        7
    .*          3   # slow right delay
    .*-5        7
    .*          4   # slow right delay 2
4: # Slow forward hold
    .*-5        7   # bouncing wave # FIXME?
    .*          0

5: # Fast back hold
    2-*         8
    4-*         8     # Become a midpoint general
    ^5-*         0
    LHG-.*      1

    # RHG Bounce
    .*          RHG

# these three states may not be a good move
# Here to trigger the bounces
    # R Temp
    .*  RHG
    # L Temp
    .*  LHG

# left hand moves

11:  # fast left
    .*-RHG  12      # Trigger slow wave
    .*-14   12
    1[56]-.*   15

12:  # slow left delay
    .*      13

13:  # slow left delay 2
    .*      14

14:  # Slow left hold
    15-.*   8
    .*      0

15:  # Fast back
    .*-14   7
    .*      0
    # LH bounce
    .*       LHG

    .*  BANG

    # Right hand sub general
    [LR]HG-[LR]HG   -1  # surrounded - everyone fires next turn
    1-.*        6
    #0-LHG       7
    # Left hand sub general
    [LR]HG-[LR]HG   -1  # surrounded - everyone fires next turn
    .*-11   16


# This code works for both ends (interleaved code)
    ^.*--2     RHG
    ^trigger    1         # fake to make graph show right
1:                        # Triggered by kickoff routine
    ^-2-\d+     2         # left hand count up 1
    .*          3
    .*          4
    .*          LHG

6: # RHG Bounce
    .*          RHG

    # LH bounce
    .*       LHG

    # Right hand general
    1-.*           6
    ^[LRM]HG--2    -1  # FIRE!

    # Left hand general
    ^-2-[LRM]HG    -1  # FIRE!
    .*-11   16

    .*  BANG

Looking at other peoples solutions

When I looked at other peoples solutions (which I did after I had found the midpoints but before I had completely solved), the solutions all follow this general process: subdivide and subdivide again, but use various tricks to allow faster solutions. I believe Goto's answer uses ever-increasing delays (factor of 3) signals from either end to find the intermediate points, which shaves time off, and that's the reason for the thousands of states to allow him to double the delay every time. I'm not exactly clear on how he did it, as I mentioned, I haven't been able to find his paper (and I do struggle with some of the formal math proof papers).

In the following diagram, on the left is my two signal solution, but the right hand side has multiple signals, each one slower then the first, showing that whilst the midpoint is found in the same time period, finding the next set is significantly faster, because a second bounce is not needed, its at the speed of the fastest signal. In this manner, the entire system is solved in 2n-2 time. 2n because of the time taken to send a signal all the way across and back, and -2 because the two end don't need to be synchronised in quite the same way.

Improved by multiple slow signals`

Optimising a machine for the fewest states

When it comes to optimising out the final states, the machines can use the same state for more reasons given that the states on either side may be in different situations. Because the entire system is reliable - in that no state will randomly be wrong, and the entire process starts from a known neutral position. The process requires a little bit of skill but can be done. For my own, I think merging the left/right generals into a single state would reduce almost immediately by 6 states (the Right/Left general and also the intermediate states that make them work). This might also then allow me to handle odd-sized elements as this would be come an element.

Real-world applications, and what I learnt

Going back to such a primitive project, and learning to work within the constraints of a system without going 'well let us slap a Raspberry Pi and Arduino in each robot with a Zigbee mesh' allows you to appreciate some of the more interesting technology. Cellular automation (Where each cell is fixed but does not know where it is but knows its neighbours) is only one step away from mesh - where the cells can move around and the neighbours change.

In other places, we are very used to having groups where every item can be enumerated - for example, networks on IPv4 or IPv6, but its interesting to think of networks where there is an unknown number of items, but you might want any to be able to talk to any other item.

Using State Machines in their formal sense, and doing the exercise in my head allowed the workout of some of the old grey matter, and it was also fun to create my own language, even if that ended up looking very assemblerish (And my compiler was a little of an exaggeration to call it a compiler). Reminding myself of how far computers have come, and how it's sometimes nice to formally design systems that can be proved is sometimes refreshing from the doldrums of normal real-world application development. It was also interesting to read about some of these peoples other achievements - Goto's Quantum Flux Parametron has some interesting designs and it might be interesting to build a non-silicon or non-transistor computer at some point.

Also, my solution doesn't work for every answer, but the general process does, and I think with a bit more time and effort (And a few more states) I would be able to fix it for odd number segments.

The animation didn't go completely smoothly - the sprite sheet was a little rushed and some of the frames are out of position, and I had a few difficulties with lining the robots up correctly as a result. So if I did it again, I would try to do that perhaps without my kids climbing over me on an Easter weekend. Apart from that, I had excellent fun which is, of course, the only thing that matters.

If you tried to solve this, I would love to hear what your solution is and whether you implemented it before or after reading the material.