The Concept of Ant Hills

by David E. Schwartz

As many of you know, I am deeply involved in artificial intelligence research. In 1995, a friend related a story he had read in a book about artificial life. Let me relate that story to you as I remembered it at the time. [The punch line here is that when I read the book myself a year later, my memory of the actual story was not even close. Still, I like my version of the story better and I’m doing the writing.]

In the early days of computers (1960s) a graduate student at M.I.T. got the bright idea to create a computer maze and some computer ants. He wanted to "breed" a strain of these "cyber ants" that could learn how to run through the maze. In simplistic definition, a cyber ant is comprised of a strand of DNA 250 characters long. This DNA is actually a set of rules for negotiating a maze.

Ant DNA: 12131 23321 44121 12111 13112 12132 11311… 31112

Imagine that the above DNA is encoded as follows:

1=move forward one square
2=turn right 90 degrees
3=turn left 90 degrees
4=turn around (180 degrees)

Thus, our ant above translates to:

1= move forward
2= turn right
1= move forward
1= move forward
3= turn left
1= move forward
2= turn right

… and so on.

His program created 500 ants randomly (i.e. just a string of numbers between 1 and 4) then ran the ants through the computer maze. It then kept the 20 ants that went the farthest into the maze and killed the other 480 ants. This is a straightforward example of the Darwinian approach to natural selection, with the most fit ants surviving to pass their genes on to future generations. This was the first generation.

In the next generation, the 20 survivors of the first generation were "bred" together. This breeding process consisted of:

1. Draw two ants at random ("A" and "B")

2. Choose a point in the DNA at random (i.e. generate a number between 1 and 250)

3. Take the leftmost part of "ant A" and the rightmost part of "ant B" (as broken at the random point) and put them together to create "ant C."

This process was repeated 480 times, until the "hill" population was back up to 500. Then the maze running process was repeated to determine the "top 20" ants again. This was the next generation.

As each generation passed, the most successful ants would live and get an opportunity to pass their "genes" on to the next generation. Through this process, the ant hill would, theoretically, improve.

Well, it worked. Eventually, our hero wound up with a breed of ants that could zip through that maze with ease.

Draw an analogy to horse racing here. Imagine that each ant is a system for selecting horses and the maze is a group of races drawn from a database. Of course, the dna strand for a horse selection system could be much more complex (i.e. longer).

Back to our hero. He tells a friend of his at the University of Arizona about his ants. The friend is intrigued, to say the least. He decides to get into this maze-running stuff.

However, he approaches it from a little different angle. He builds an ant hill, but instead of one maze, he builds three mazes. He runs his ants against maze number one, applies the natural selection rules, breeds, and moves on to maze number two for the second generation. Again he runs them into the maze, kills off all but 20, and breeds. Same thing with maze number three, then cycles back to maze number one again.

After doing this for some period of time, he calls the friend at M.I.T. and says, "Let’s have a contest. Send me your ants." Our hero sends him his ants. (How does one send cyber ants? In a box? In a plastic bag? Frozen?)

The Arizona guy creates a "fresh" maze for the contest, a maze that neither hill has seen. Then he runs both teams through the maze.

Now, let's see how intuitive you are. Which ant hill does best? In comparing the two ant hills, remember that the M.I.T. ants are older, and have been honing their skills against the M.I.T. maze for months. The Arizona ants are younger, but have been looking at three different mazes

The M.I.T. ants

The Arizona ants

After the contest, our east coast hero says, "Let’s repeat the contest here. Send me your ants." (Do you suppose that there is a quarantine period when sending cyber ants?)

So, now the Arizona ants are facing the original M.I.T. maze in a contest with the original M.I.T. ants. Who wins this round?

The M.I.T. ants

The Arizona ants

Let’s draw another analogy to horse racing here. Picture a handicapper studying the same group of races over and over, looking for a system that beats them. Is it any wonder that his system usually falls flat when tried against a "fresh" sample of live races?

While the size of the sample may help, it really doesn’t make much difference. If the M.I.T. ants had been facing a maze of giant proportions, they would still have developed a maze-running system that was designed to address their specific maze. They are doomed to being "home team" ants.

In looking for an analogy to the Az. ants, envision a handicapper that has a large group of races (say 1,000), and draws a subset of these (say 200) at random. He studies against the first sample of 200 races for "awhile" then draws a new subset and studies some more. He continues the process until his approach is performing well against almost every subset he draws.

Back to Boston. Fresh off a victory in the Massachusetts Maze Contest, our hero says, "Let’s have a new contest. I’ll create a new maze and we’ll let our ants run 1,000 generations through it and see whose do best."

So now we are going to test the ants abilities to learn rather than just test what they already know. Who wins this time?

The M.I.T. ants

The Arizona ants

The Az. ants are more likely to learn faster because their strategy for going through a maze is not dependant upon "tricks" but rather upon more general skills. They are more likely to have developed some subset "assemblies" that address specific problems faced in maze running. For example, instead of, "Always turn right at the big tree," they are more likely to have a rule that says, "A turn may be necessary after a big tree."

Time for another analogy to racing. When a handicapper looks at the same sample of races over and over, he finds tricks (rules) that get the most important races right. ("Got to find a way to get that $43 winner.") Remember that the size of the sample has little impact on this. No matter how you slice it, a retrofit is still a retrofit.

So, how does one test against past races? Build several systems using whatever ideas you may have. Grab some races. Test each system against the races. Rank the systems’ performance against this sample. Keep a "score-to-date" for each system. Grab some more races and test again. Continue this process. Periodically (i.e. after every so many tests) rank the systems by "score-to-date" and discard the weakest systems. Then replace those weak systems with new systems created by looking at what the most successful of your systems have in common (A good system plus a good system could produce a better-than-good system.) Repeat the process over and over.

Once you think you have learned enough to play, grab some races from a database you haven’t trained against and test your top systems against this sample. Repeat the process several times, noting not just "performance-to-date," but also the performance against the individual samples. This will give you a chance to get a feel for what normal is for the systems. It will also show you how often your best systems "go bad."

As you can imagine, applying these concepts manually can be very time consuming. A computer does help, but it really does take more than simply buying a whiz-bang piece of A.I. software. There is a commitment necessary to the application of artificial intelligence that goes beyond the level most players are prepared for. While A.I. can produce meaningful understanding of what has happened in the past, it is the future that really counts in the wagering arena. The software cannot do it alone.