Ken's POTW
Firing Squad
N soldiers stand in a row, shoulder to shoulder, facing the same direction.
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
Mail to Ken