|
| Contest | Langton's Ant |
| Due Date | February 16, 2002 |
| Prize | Your choice of one of the books I have in stock (approximately $50 value), you pay postage (about $3 in the US). |
The Science of Discworld
talks about Langton's Ant. The idea is a tiny ant is sitting in the middle of a grid of squares that
are either black or white. There are only three rules. During each round:
- Turn:
- If the ant is on a white square, turn right.
- If the ant is on a black square, turn left.
- Switch the color of the ant's current square.
- Move forward one square.
The contest is to build a Langton's Ant simulator. Possible features:
- Start and stop the ant.
- Display the grid at different scales (in case the ant wanders far away).
- Save the current situation including the grid and the ant's position and direction.
- Reload a situation and run from there.
- Save an image of the grid.
- Run displaying the round number without showing the grid (for extra speed to run a lot of rounds).
The "standard" start position is an all white board. For extra credit, also allow the user to select a checkerboard or other interesting initial board patterns (random, white with a block of black, and so forth).
The ant shows three distinct types of behavior over time. To see the third type of behavior, you need to be able to run the ant for more than 10,000 rounds so be sure your program can run that long.
Langton's Ant shows three distinct "behaviors." Initially it seems to move with a purpose, building itself
a little nest. After a while, the ant makes a bigger and bigger nest and gives the nest a rather chaotic structure.
After about 10,000 moves, the ant starts building a "highway" moving away from the nest.
Simple Rules, Complex Behavior
One moral of Langton's Ant is that a small set of simple rules can lead to apparently complex behavior. This has
some interesting philosophical consequences. The world around us is filled with apparently complex processes and
behaviors. It is possible that at least some of these are due to very simple "rules" even if those rules are not
easy to see. A colony of real ants shows complex behaviors but an ant's brain cannot be very complex. Each ant must
operate on a relatively simple set of "rules" yet somehow together they form a complex society.
Similarly you can build a quite realistic model of weather behavior using a few simple rules. Weather is not
only complex but it is also chaotic so predicting its behavior is extremely difficult.
Just because something is governed by a simple set of rules doesn't mean you can easily discover those rules.
Looking at Langton's Ant from any distance, it would be hard to deduce its three rules of movement.
This also doesn't mean that complex behavior cannot come from complex rules. Even apparently simple behavior can
come from complex rules.
The Halting Problem
Langton's Ant also demonstrates an important computer science concept: the halting problem. Suppose you have
a computer program (like the Ant's "program"). The problem is to determine whether the program eventually halts.
Knowing the Langton's Ant rules, you probably would not guess that the ant would eventually end up building a
"highway" away from its "nest." Even if you ran the ant simulation, you would probably not suspect that result
initially. If you got tired of watching the ant, you might stop well before the 10,000 moves needed to see the
highway develop.
The halting problem applies to a more general class of programs and there are several programs that pose quite a puzzle.
For example, you can build a program that evaluates logical expressions and determines whether they are true.
Unfortunately the algorithm doesn't necessarily ever halt. If the logical statement is true, the program will
eventually fins out. If it is not true, however, the program may run forever. So the question is, after 10,000
steps, do you assume the statement is false? Or do you run 100,000 steps? 1,000,000? It's easy to tell that some
programs eventually halt (for example, Windows), but for others there is no way to be sure until they actually do halt.
Computability theory deals with this and other problems that ask, "Can something be computed?" The related
field complexity theory asks, "How long does it take to compute something?" These are two of my favorite
fields of computer science research.
Turing Machines
If you enjoyed working with Langton's Ant, you may also be interested in Turing machines.
A Turing machine is a hypothetical computer with rules about as simple as those used by Langton's Ant.
One simple form of machine reads an infinite tape. Each cell in the tape contains a 0 or 1.
When it reads a value, the machine checks its rules to see what to do. The rules tell the machine
whether to make the cell a 0 or 1, whether to move left or right on the tape, and what state to move
into next. The states determine which rules apply at any given point. Other kinds of Turing machines
use "machines" with features such as multiple tape heads and multiple tapes.
These simple machines are extremely powerful and with the right set of rules it can perform addition, multiplication,
exponentiation, and all sorts of other mathematical operations (if you like this stuff, it's fun to build a Turing
machine simulator and then watch it run programs for exponentiation). With a little work, you can show that some kinds
of Turing machines are just as powerful as a Pentium 4. Turing machines let you study other kinds of computability issues.
The solutions submitted for this contest were outstanding. Each had its own set of great features.
Erno had the only .NET solution and his program is written in C#. Unfortunately I couldn't get it to run.
It's probably my fault for not building the components correctly or something but I don't have time to figure it out.
If you have time to give this solution a try, let me know how it works out.
Mike's program lets you start and stop the ant, run the simulation at different speeds, record the ant's position
so you can resume running later.
Its coolest feature is the ability to save the ant's movements into a movie file! You can adjust the number of
frames per second so the movie can actually run much faster than the ant simulation.
The program's one drawback is that its fastest speed is relatively slow. That makes it hard to run past the
10,000 or so rounds you need to pass to see the ant's third type of behavior.
Neil's solution followed the KISS (Keep It Simple Stupid) strategy. The code is very simple and easy to understand.
That lets the program run very quickly which is a big advantage if you want to run for 10,000 iterations.
The program provides fewer options than the others so you cannot save or load the ant's state, change speed, alter
the grid size, and so forth. The program runs long enough for you to see the "highway" appear and then stops.
It shows the ant's behaviors quite elegantly, though it does limit future research.
Richard's program has several very nice features. It lets you change the ant's speed, save and restore board
positions, save the board in a bitmap, and change the grid size. The program has a nice menu system with shortcut
keys and a toolbar. That alone is worth some study if you haven't built toolbars before.
The program's coolest feature is the ability to run more than one ant on the board at the same time. As the ants
build their nests, they eventually bump into each other. After that, who knows what will happen. Will they eventually
start building highways like the single ant? Perhaps. But what if they start in a different position? Or facing
different directions?
This really drives home the computability problem. Given only two ants in particular positions facing given directions,
will they eventually start building highways? Will they eventually repeat a board pattern and enter an infinite loop?
Will they build a huge joint nest and stay inside it forever? There's really no way to know until it happens.
Yaron's solution also lets you resize the grid and run multiple ants. It provides a Fast Forward mode that lets
you run the simulation without displaying any output. This mode is extremely fast so you can easily run
100,000 steps or more. This is very useful for exploring the halting problem (or in this case the "highway problem"
might be a better name) for unusual situations like multiple ants.
Yaron also included a nice instruction file in RTF format. Documentation is usually not the first thing on a
developer's mind but it is often more important than the code in the long run. Without documentation even the
most worthwhile program may become unmaintainable long before its usefulness ends.
I prefer Richard's user interface and his solution has a couple features that would be nice here. For example,
in Yaron's program you need to create each ant by hand. It would be nice to be able to make 10 random or equally
spaced ants without needing to build each individually.
As usual, selecting a winner is hard because all of the solutions were excellent and each has its advantages and
disadvantages. The choice is so close that I'm going to pick two winners: Richard Moss for his great interface features
and Yaron Budowski for his outstanding flexibility and speed.
Congratulations everyone!
| 
