The Bug is in the Nature of Reality

tart8

Today’s edition of Occupy Math is about the horrors of debugging code in the form of a story that explains why mathematical thinking is sometimes deeply valuable. We are going to look at a marvelous code bug! One of Occupy Math’s core research areas is bioinformatics. Clicking the link will give you the collective wisdom of Wikipedia on bioinformatics, but Occupy Math thinks of it as “digging biologists out from under big piles of data”. Occupy Math’s first bioinformatics project was with the Schnable lab, figuring out what the DNA sequences of the genes of corn were. When formatting a bunch of of gene-sequencer output for submission to GenBank and NCBI, Occupy Math created simple code that absolutely would not work. Two weeks later, in consultation with his biological collaborators, Occupy Math learned that the problem was not in his code. The sequencing center had sent over someone else’s chicken sequences and so the critical genetic marker in the sequencing constructs from the Schnable lab corn data wasn’t there. Frustration sometimes yields wisdom, in this case:

The problem may not be in your code. Also debug the data!

At this point, readers may be wondering what the odd animation at the beginning of the article is. If you could not see what it could possibly have to do with corn genomics, good for you! It is entirely unrelated. The picture is an animation of evolved virtual robots. Their job is to push boxes so that as many sides of boxes are against the wall as possible. These robots were created with an evolutionary algorithm, using a super-simple digital form of Darwin’s theory of evolution to program robots. The robots shown are about half-way to full competence — their moves are clearly not random, but they leave a lot left to do at the end of the animation. Occupy Math has worked on a variety of these virtual robotics problems, because they are difficult (but not impossible) test problems for improving his evolutionary computation chops.

Another task set for the virtual robots is pushing the boxes all together; we call this the builder task. To drive evolution, we need a measure of how well the virtual robots are doing. For the builder task, this is the number of pairs of adjacent boxes when the robots use up their allotment of time. The robots can push one box but they cannot push two. This means that the builder task involves some fairly sophisticated planning to avoid creating obstructions that prevent pushing all the boxes together. It is the builder task that caused Occupy Math to discover the wonderful bug.

glowworm

For the builder problem we need starting configurations. The bug arises in the code for generating those starting configurations — before the robots do anything; the bug doesn’t even involve the robots. The picture above is an example of the kind of problem we might set the robot. It obeys some important rules:

  1. Since the robot’s score is based on pairs of adjacent boxes (not including diagonals), we start with no two adjacent boxes: no free points.
  2. The robot cannot pull boxes away from walls, so boxes on walls would create a preferred direction for the robot, a sort of hint, so we start with boxes away from the walls.
  3. If there are too many boxes, creating obstructions is really easy and the robots will probably not be able to evolve, so we keep the number of boxes relatively small. The number of boxes may be increased after the robots have evolved to some degree.

So where is the wonderful bug?

A large number of different starting configurations are needed for training robots via evolution. Occupy Math used the following algorithm to create starting configurations for the builder problem:

  • Clear the board.
  • Repeat
    • Pick a random square until you get one with nothing adjacent to it.
    • Put the box there.
  • Until all the boxes are placed

Generating (sort of) random numbers is a property of most programming environments, so this is a pretty simple algorithm. Occupy Math then ran a bunch of experiments with different sized boards and different numbers of boxes. The bug was this. Occasionally — after running evolution for a couple of hours — the algorithm would freeze.

The code that maintains the virtual world where the bots live is pretty complicated, and Occupy Math spent a lot of time checking it. He found and fixed a few minor bugs and inefficiencies — but nothing that would cause the freeze. Checking the bot-world code was a bit dumb of Occupy Math, because the freeze only happened for a very small number of board sizes and for particular numbers of boxes — always the largest number of boxes for that board size. This makes it seem unlikely that it was anything in the world code causing the problem. Time for the reveal. If you say a box “covers” the squares adjacent to it, then the box-placing algorithm is looking for uncovered squares — that is, places we can put a box without breaking the rules. Some of the squares in the example box above are covered multiple times so there is some variation in how efficiently a placement of boxes covers squares. Here is what happened.

For the smallest example that froze, there was a one-in-a-million super-efficient way to place the boxes so that the first eleven (of twelve) boxes covered everything.

This means that Occupy Math’s code was stuck in an infinite loop, generating random positions in a search for an uncovered position that did not exist. This is a good-news bad-news situation. The bad news is that there was no bug in Occupy Math’s code — or at least no bug that caused this problem. The good news was that there was some new mathematics concerning the creation of builder boards. It turns out that this problem is a special case of the dominating set problem in graph theory. Once you notice the problem exists, mathematical analysis quickly leads you to this picture.

crossesImagine we place a box in the center of each cross. The cross-shaped domains are the areas one box covers. If you pack them in the fashion shown, then boxes placed as the center of each cross cover everything without double-covering anything. The cross-shaped domains are the most efficient possible way to cover (two dimensional) space with boxes. For any finite board, you use the board like a cookie cutter on a large field of packed crosses — including the most cross-centers you can — and then repair the edges as best you can. For any board size this is a simple, finite search problem. Problem solved! The letters, numbers, and stars are in the diagram to support three paragraphs of argumentation (not shown) that Occupy Math did to mathematically prove the proposition that this is an optimal way of covering space with boxes.

Here is the beauty: the bug in Occupy Math’s code was in the nature of reality.

Think about that for a moment. The code froze — that meant that it had a bug. Unlike the chicken-corn mix-up from the beginning of the article, the bug wasn’t in the data, because this code works without input data. There was a law of nature that prevented the code from working. In this case, debugging the code meant that Occupy Math had to prove theorems about boxes covering space and, from this, learn the boundaries of the possible for the builder problem. In addition to being beautiful, this sets the weirdness dial to eleven for debugging code.

There were mechanical ways of fixing this bug without mathematics. Occupy Math could have simply checked to see if there were no uncovered squares left and restarted the box-placement algorithm when it got stuck. The problem with this is that, as more boxes were added, the number of restarts needed would grow, and the code would become mysteriously slower. The point where no configuration would work would also create an infinite loop of restarts at some point.

Using mathematics to understand what happened is certainly a more elegant approach.

The problem with using an elegant mathematical approach to solving code problems like this is that most programs that train people how to code avoid mathematics or ignore it. At best they have courses enumerating some of the math that is clearly, directly useful in coding. The view that math is a useless form of torture is as pervasive as it is false. Occupy Math has characterized this blog as a fable drawn from his own experience — but it is not an isolated incident. Medieval alchemists tried to turn lead into gold, something utterly beyond their capabilities (no atomic physics). Worse, when science did manage to make gold from lead by nuclear transmutation, it was so costly that it was not worth the trouble. Plus the gold was radioactive. Learning mathematics coveys a mental agility that enables problem solving and helps us detect and avoid the impossible before we waste too much time and too many resources on it.

To be fair, people that do coding are focused on solving problems and meeting deadlines. It took Occupy Math several months (and help from a couple of students) to work out the cross-based mathematics that established how many boxes were too many for the builder problem. When you are focused on solutions, instead of on problems, you’re not going to notice obscure features of reality, showing a substantial difference between the mathematical attitude toward problems and the coding attitude. This is not to say one attitude is superior — and they can both exist in a single individual.

Occupy Math thinks math can benefit almost everyone — but to enjoy most of the benefits only some of us need to acquire the skills. A good intermediate goal would be to admire rather than ridicule those who are taking the trouble to hone their talents, to create room for mathematicians to grow and flourish. Occupy Math has frequently touched on the problems of women and minorities in mathematics, but even the least discriminated groups still mock those among them that study and enjoy math. Occupy Math urges you not to be a part of this! Do you have any stories about math helping to solve a problem or about being mocked because you like math? Please comment or tweet!

I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s