Firing Squad

The first soldier on the right is the drummer. Every second, the drummer gives a beat, heard by all the soldiers. On that beat, the soldiers modify their state based solely upon their current state and the state of their nearest neighbors. (Perhaps the state of a soldier is noticeable by their posture, stance, or some other visual clue.)

Currently, all the soldiers are in a quiescent state, awaiting orders.

The first soldier on the left is the General. The General changes his state to give the command "Fire!" Each second, the command is passed on, perhaps in both directions as needed. Some time later, all N soldiers fire at the same time.

- How could this occur? I'm only looking for a theoretical answer here. What would the algorithm be to get them all to fire at the same time?
- Each soldier is an agent, with its own rules for state-changes. Obviously, the General and the drummer will have special rules, since they have only one neighbor, but the rest should share the same set of rules. Can you determine a rule set (a state machine) for the General, drummer, and soldiers? How many states are needed? Can the state machines work for any N?

Source: Homework problem in a CompSci Agents course at Stanford University, Fall, 1991.

Solution:

Received May 6, 1997 from Robert A. Pease (author of several

[I haven't checked it completely but it seems to answer both questions above. I'd be interested if anyone does write a program to test this and if there are any discrepancies for particular values of N.]

Hello, Ken, Here's a solution to your PUZZLE with the General and the Drummer. I think this one's really easy. It reminds me of a dual-slope or triple-slope ADC. THE GENERAL has to do some planning, before the time of the Attack, just as a real General does. See below. The DRUMMER has to keep beating the drum, one beat per second, uniformly, or at the required rate. It would be wise if he keeps on beating all the time, even when there are no orders to be passed. (Although the general might arrange for a BACKUP who can substitute in so the Drummer can go to the John before his work becomes critical.) The DRUMMER must also pass the ORDER on to his left or right, per the procedure as stated below for the men. The INFANTRYMEN have simple tasks: 1. Pass the ORDER: If the man receives an ORDER on the left, he must pass it to the man on the right, on the next drum beat, for a delay of exactly one drum beat. If he cannot pass it to the right, because there is no-one there, he must pass it back to the left. (If he receives orders on the RIGHT, then VICE VERSA of above.) 2. Count. The first time he gets an ORDER, he must COUNT until he gets the ORDER back again. Then he must REMEMBER that count, N. 3. The THIRD time he gets the order, he must start counting DOWN from (N/2 + 1). When his count gets to ZERO, he must FIRE. (Note, if he whispers his countdown out loud, he can hear his comrades on each side, counting down just the same.) The GENERAL must send out the first ORDER at a suitable early time before the ATTACK. He must count the number of Drum beats M until he gets the ORDER repeated back, on the Left (ML) and on the Right (MR). He must remember these counts. (an Odd number, each.) When he is ready to call an attack at time T, he must send out the ORDER to the left at a time t = T - ML/2 -1/2. He must likewise send out an ORDER to the right at a time t = T - MR/2 - 1/2. After that delay, everybody will fire at time = T. (Option, everybody counts down from N/2 + 2) for best precision. Start sending out the orders to start firing at t = T - M/2 -1.5 ) It's hard to think of any procedure much simpler (or quicker) than that. Any good software writer could write that one. Even I could write that one - in BASIC. Best regards/ rap

Mail to Ken