Serendip is an independent site partnering with faculty at multiple colleges and universities around the world. Happy exploring!

You are here

Home » Blogs » Variation on Langton's Ant

Variation on Langton's Ant

By Leslie McTavish
February 16, 2006 - 12:26
Leslie McTavish's picture
Projects: 
Emergence 361
Here is the model with two of Langton's ants

Comments

Leslie McTavish's picture

Submitted by Leslie McTavish on February 17, 2006 - 07:38

You don't have to wait that for that long for something to happen. If you start them off closer together they won't even get as far as constructing their roads before they bump into each other and start to back track over the others path, eventually returning to each others starting positions. Then they start the process all over again.
PaulGrobstein's picture

Submitted by PaulGrobstein on February 16, 2006 - 13:39

Magnificent. Is indeed that each ant cleans up the trail of the other ant. And so they end up at each other's starting point. And so they are actually "in synch" throughout the entire dance. Now THAT was certainly not "intended" by Langton when he created the instructions. Anbody have a good suggestion about why it happens? It MUST have to do with their being a configuration that effectively "reverses" the ant, no? So, one might be able to get a single ant to do it by changing its heading (and possibly displacing it slightly)?
PaulGrobstein's picture

Submitted by PaulGrobstein on February 16, 2006 - 15:56

Another way to think about it .... there is an odd sort of symmetry involved here, two things starting at different places but doing exactly the same things at the outset and then interacting with each others traces in the same environment using exactly the same set of rules. Is there some kind of symmetry preserved the entire time? Does the oscillation between two mirror symmetric states on a long period follow necessarily from that? What happens with odd numbers of ants? Even numbers greater than two?
PaulGrobstein's picture

Submitted by PaulGrobstein on February 17, 2006 - 17:12

Its not in fact as symmetric as I thought. Try starting one ant at x=0, y=0, and the other at x=0, y=4. You get the two in inverted postions pretty quickly (~2000 moves, before any roads) but they return to their original positions after a much smaller number of moves. Ergo, when in the inverted postion, one or both must be sitting on a colored square instead of an uncolored one. Probably both, since the situation is (I think) symmetric enough so that there is no reason for it to be one or the other.
PaulGrobstein's picture

Submitted by PaulGrobstein on February 17, 2006 - 21:47

Intended to post this shortly after the above but had a completing obligation. Noticed that Leslie included controls for ant orientation. So should have said for the above the one ant had initial heading 180 and the other 90. And intended to say this further complicates the "symmetry" way of thinking about this, as per above. Then went off to dinner, over which, actually several hours later, the following ...
PaulGrobstein's picture

Submitted by PaulGrobstein on February 17, 2006 - 22:22

Leslie's implementation, like The World of Langton's Ant has a finite number of locations (since it wraps) and a finite number of possible ant locations (for any finite number of ants) and therefore a finite number of states. Hence, after a finite number of iterations, it MUST repeat, since it must move into a state it has been in before and it is deterministic; therefore having necessarily reached a state a state it has been in before it must do again do what it did before when it was in that state. This accounts for the fact that a two ant situation repeats itself. It does NOT by itself account for the fact that the two ant situation ultimately goes back to the original state, passing through a "symmetric minimal state" on the way. That's still going to take some work, but my guess is that the algorithm has, for some reason, the effect of precluding any state repetition until one reaches the "symmetric minimal state". The analysis DOES, however, allow one to conclude that after a sufficient number of iterations, the one ant situation will, in the wrapping condition, also cycle. My conjecture is that situation too, given enough iterations, will ALSO pass through a symmetric minimal state. My further conjecture, for reasons elaborated below, is that, contra intuition, increasing the number of ants will actually decrease rather than increase the number of interations necessary to return to the original state. No deterministic algorithm followed by an ant can increase the number of possible states of the world of Langton's ant, and most will decrease it (some number of states cannot be reached using that algorithm). A big part of what is "surprising" about the two ant finding is that it cycles much more rapidly than one would have thought given one's sense of the aimlessness of the movement.. In fact, though, the deterministic algorithm VERY much reduces the number of possible states and therefore decreases the time it takes for the world to return to a state it has been in before. More ants will (I think) still more restrict the number of possible states and therefore decrease the time it takes for cycling to appear. No, NOT yet clearly accounting for the dramatic "erasure" phenomenon, but it does yield something perhaps equally interesting in its own right. Any finite deterministic world will cycle (for the simple reasons given at the outset). This sets some interesting and reasonably well-defined limits on the viability of "digital determinism". The maximum cycle time relates both to the size of the universe and to the algorithm used to go from one interation to the next. Given that there has been no observable cycling in the universe over fifteen billion years either the combination of the two yields more possible states than can have been explored over that period or there is no deterministic algorithm.
Doug Blank's picture

Submitted by Doug Blank on February 18, 2006 - 09:08

This space, like all of the CA spaces we have explored, is indeed finite. In this case, it is exactly 2 ^ (140 * 100) (two to the power of width times height of the board). That's pretty big. About: 2629900367325311780389341293440721322227771551581731834551032514983937 8426924171214498611343414712256174026289516946119523811775624467731770 4982104228572381561212835383679294290422948158152103995789000997628676 8995605962323461209749088319239573407993173341507124798549810785096438 7704126118743710024142029229260847390992841110518849094712483395520224 8744332100580637003124978589491701695101808522061144843988133835134392 6371348231118779507236126800515720925873045677951105291646555977456234 9391766686776418778862562643080722537226180483775757692465100405435762 0509329318741181910302634590696915593034823530153709878779890484879296 3392301112263542115718822716200103130152819302838623158490769778399951 7504561397654107162767284461987773185780788248073616394445546448020436 6826389362507650345097862743477536825185737660772096012005787655040340 1268300956546122905571549328959920046056277988837550161552617827935649 1324907632232575540800893224321210813954335005463793982547895511586457 9828008151366973217156309375261794492221838351346755841787461956930463 5800199722522584746512259680136082497281444971743825563074561082526031 8084402220397293576471865293287285780643586223527835550741425330830246 0895923907550669237900634542848067408226046188724428808270623931372529 8976008440535592826897679446829067287601700532625435414303538585646760 7485488880967386375435169930458312631299355183936167481633482683690263 8988247747907218828567459135627245585690901082233494426017513437437450 6065667582101786154189831488356113720152356859721185554982249389519000 1521526275891417350791465165370599281375736761195526120614754600889050 2789281477959095303190149250968082178459572180060041398557654197699926 1454325818515912956511161027877536900281321389839133815068660598450356 6675509237961925926505414997222258476658252774325639486440948905895925 8511157809244889757489729059857104856687703650301577046137206267229068 0776019663174044512112272892727887007286503040499455776483279871646231 0000874816700461907902019180579143889332126045711482225507973302310101 0863073670147484190556813422050853921435708168321378455723960331769908 4456014060600058775176341948422676275506848959590920174153281192446937 8193996196783156670833187469863612364973261643287684226943681930423645 7575085952737686167748921194450944987730620397476605664783305777748249 0348456618849632950066406390360032102464538632033808809485141750606692 0915429662809787249994883198552628409846537884618102224137419646264171 7502794537067729051885641975472020828764687565865530333975926092825932 3917161288964180621115960609642946050894280464851290495817670282495080 3702623034919386269783075187196964002597914724957869594918933588400196 2338893140682509823431283076620933048883456675115155462413209734504001 6307204314593840478185730940548486584654591409903055689286232266993547 3310925375285878852925193765981347025535461051911590798215975134019564 9711580795222387676475047121576965232737615114755253957597707815729239 3731312892564116118034679126022981440519348934139082181374530911957028 5077663686740238808071011481380555692220980993865590350483159648904366 9336632105608061026734199822904422939462549317030021122411931713883622 6934342863506458440693755033583081458521135855125620257570365123060829 4111142568338289286398171366596040690738104832467961098196876579533304 4165113293745159204745140043258518543947733834839066171415664096031329 6065599397083831475771969947781996730167806610264472929237224506141573 2499213045991711368707985711528854857689088186848460937500025109110059 1939225144364623867640694682641627464807665789387787689831730056348581 5471083725647664980987460647820500280715390778988420376200985566906933 6237558193900981651081044472131226536462149611359802618695988423686368 8099019836470414246949514271345503502536416933499943904297965854102816 9335283749149109245363366721928253680684257443450774798160206778004504 7007035183606958737702087752751354576665897950971682003721388740895555 9931679863269431038050962802251853710848275433057116675899294898777773 7745666234906385546596571572240985553095457648473983532685246856477550 3861419835445020939839730724038115818701048150085351166074881391365179 8097170556607931135475307632200291474771586044913722975022506963202321 801281720549376 if I remember correctly. :) This number is accurate, by the way. So the fact that it is finite doesn't explain too much. That is, being finite doesn't necessarily limit the possibilities. Now, not all of these states may be accessible by the rules (and starting state) of Langton's Ants. I don't think you can make accurate predictions on whether additional ants will increase or decrease the steps before looping. Also, there is no reason to think that the third ant would start the cleanup phase at the same time as the other two. Many questions... very generative... much surprise... unpredictable... reminds me of something...
PaulGrobstein's picture

Submitted by PaulGrobstein on February 18, 2006 - 11:10

Life, maybe? And a world in which intuitions, further explored, are at least as good, perhaps better than "accurate predictions"? So long as they are used "to extend the possibilities of thought"? I can always use another cup of coffee/hamburger. Leslie? What's the answer for three ants? four? And what about the idea that we're imposing our own frameworks on the ant(s), as we did with "aimless" and "purpose", that there really isn't any "clean up" phase as distinct from any other behaviors? Can we get at that question somehow?
Kathy Maffei's picture

Submitted by Kathy Maffei on February 19, 2006 - 14:08

For example, I noticed with my model that changing the screen dimensions made a big difference in the interaction of ants who progressed across the screen wraps. Obviously, they meet at different places and behave accordingly. If you download my model, try the 3rd "Things To Try" with 4 ants, then modify the screen dimensions and try it again, you'll see some big differences in how the 4 ants interact.
Doug Blank's picture

Submitted by Doug Blank on February 19, 2006 - 14:45

It also seems to matter where the four ants start. Try putting two right next to each other. Then two above and below each other. What will happen? What if they are mirror images of each other in terms of direction? You can make oscillators. Can you make a two-ant glider or road-builder? Very nice model!
Kathy Maffei's picture

Submitted by Kathy Maffei on February 20, 2006 - 12:30

My spouse spent a few hours playing with this model yesterday - it was funny listening to his oohs and ahhs in the next room, he was rather excited every time he made an interesting pattern - and I remember he was particularly happy with the behavior of 4 ants in a square configuration at 5 patches off center: (0,5) @ 0 degrees (5,0) @ 90 degrees (0,-5) @ 180 degrees (-5,0) @ 270 degrees They perform a nice little ballet - lots of symmetry.
Kathy Maffei's picture

Submitted by Kathy Maffei on February 20, 2006 - 13:52

Woo-hoo! I watched that 4 ant pattern long enough and it's pretty cool. The 4 ants dance in a flower pattern for awhile, and then create a wavy circle around it, all four circling around making the circle larger & larger until they hit the screen edges and bump one another, which reverses them. They go back the way they came, circling in reverse making the circle smaller & smaller until it returns to the center shape and erases it until all four ants are at their original positions (ok, I don't remember which colors were at which points, but there were 4 ants at the same points) and then they start over. So, this is a starting configuration which clearly demonstrates the reversal phenomenon with 4 ants.
Kathy Maffei's picture

Submitted by Kathy Maffei on February 19, 2006 - 14:00

Last week I set out to create a version of Langton's Ant that resolves the parallel processing concerns. In each step, all ants are asked to determine their next move, and then all ants are asked to perform those moves. This way, we can be sure that during each step no ant is affecting the environment before another has a chance to evaluate. I'm not sure how this will affect the results you're seeing. I also see the same erasing behavior, so it might not have made much of a difference. Also, some of the questions I see here might be explored with my model since it allows any number of ants to be wherever you place them at whatever heading you like. I found some really nifty behaviors that can be reproduced by following the "Things To Try" section. For example, one ant starting at 120 degrees will immediately make a snake-like road. And some configurations of ants will perform ant-ballets with symmetrical designs and such. I recommend using colors.
PaulGrobstein's picture

Submitted by PaulGrobstein on February 19, 2006 - 18:25

Alright, alright, is looking already like my effort to make sense of this in abstractions may not make it (have tried three ants and isn't looking good). So, another tack. Can anybody reorient/reposition an ant so that it backs back over and erases its trail? If so, the two ant situation may simply be one in which there is (for some reason?) a very high likelihood of both ants coming on the trail of the other in the right configuration?
Leslie McTavish's picture

Submitted by Leslie McTavish on February 20, 2006 - 08:50

I have been trying different scenarios trying to make some sense of what is happening. So far, this is what I believe. One ant will never backtrack. Two ants will eventually. In the three ant world two may potentially meet and back track, but by the time they grow back again the third ant has created obstacles that prevent them from backtracking again. Four ants, usually just makes a mess. But as Kathy pointed out this may change by increasing the size of their world.. but then they just have enough space to do what they would in a smaller world with just only two ants. I had thought that the backtracking starts when the two ants occupy the same space on the board because I noticed that if I divided the number of moves they took to return to starting positions in half, the ants did occupy the same space at approximately that point. I added an option to the model to halt when this happens, and found that they crossed paths multiple times. Now I'm wondering if they reverse direction when they meet. Another odd thing that happens sometimes is that only one ant will go off to make a road, but they will both eventually return to the start position. This means that they don't have to have followed the same pattern in order to return to the beginning at the same time.
Doug Blank's picture

Submitted by Doug Blank on February 20, 2006 - 10:27

"This means that they don't have to have followed the same pattern in order to return to the beginning at the same time." Another way to say this is that they don't have to be symmetric, but the reversal may indeed be caused by their head-to-head encounter (e.g., their "crash" --- need some good jargon for this new multi-ant field :).
Kathy Maffei's picture

Submitted by Kathy Maffei on February 20, 2006 - 12:37

It's interesting to compare models - when I place two ants in each model at the same coordinates (say, 0,4 and 0,-4) both heading 0, I see very different behavior in each model. In the few configurations I tried, only one of Leslie's ants built roads at a time, while in mine, often both ants were building roads at once. Part or all of the reason is likely the parallel computing issue - that Leslie's ants evaluate & act one at a time. But as I was noticing with my model, screen dimensions affected performance as well, but I didn't expect it to do so while the ants were still in the center - not crossing the screen wrap.