Opdracht 1: Langton's mier

Inleiding

In 1986 publiceerde Christopher G. Langton een artikel getiteld Studying artificial life with cellular automata. In dit artikel werden verschillende cellulaire automaten besproken, maar veel van wat er in het artikel aan de orde kwam lijkt een beetje vergeten. Wat het artikel achteraf gezien bijzonder maakt, is dat er min of meer terloops een nieuw type cellulaire automaat werd geïntroduceerd. In deze automaat wordt de toestandsverandering van cellen geïnduceerd (teweeg gebracht) door een virtuele mier die over de cellen loopt. Langton noemde deze mier in zijn artikel een virtual ant, maar later werd deze mier toch vooral bekend als Langton's ant. Anders dan in Langton's originele artikel is de mier op talloze andere plekken beschreven, waaronder Wikipedia en TCBoN (Flake). Op veel van deze plekken worden meteen ook mogelijke generalisaties beschreven: meerdere mieren, een rooster met meer dan twee toestanden, meerdere toestanden per mier, en ga zo maar door.

Motivatie

Het speciale van Langton's (originele) mier is dat een eenvoudige regel, afhankelijk van de startconfiguratie (i.e., welke roostercellen in het begin “aan” staan), complexe patronen kan voortbrengen. Er is weinig bekend over het lange-termijngedrag van Langton's mier. Eén van de zeldzame resultaten is een stelling van Cohen en Kong die zegt dat het spoor van Langton's mier onbegrensd moet zijn. Deze stelling bezit een vernuftig bewijs, zie hiervoor bijvoorbeeld het artikel The Industrious Ant van David Gale (1993). Flake's boek bezit een prachtige en zelden beschreven variatie op Cohen en Kong's stelling, namelijk de stelling dat één individuele mier zijn eigen spoor niet kan inverteren (i.e., uitwissen), uiteraard gevolgd door een bewijs.

Echter, het meest bekende “feit” t.a.v. Langton's mier is een vermoeden, genaamd het snelweg-vermoeden. Dit vermoeden stelt dat, voor iedere eindige startconfiguratie (i.e., eindig veel cellen “aan”), Langton's mier op den duur altijd een snelweg zal bouwen. Tot op heden is dit vermoeden bewezen noch weerlegd en zelfs de meest begaafde wiskundigen hebben voorzover ik weet geen idee welke technieken toepasbaar zouden kunnen zijn om dit vermoeden te bewijzen. (Hoewel: zie Alexei Bondal's lezing “Langton's ant period”. Deze lezing is state-of-the-art. Halverwege zijn lezing zegt Bondal iets over semi-invarianten en dalende entropie als bewijstechnieken, maar dat zijn duidelijk nog vage intuïties.) In die zin lijkt het snelweg-vermoeden wel op het mysterieuze vermoeden van Collatz (ook wel: het 3x+1 vermoeden). Beiden vermoedens gaan over de vraag of een zwaar recursieve iteratie convergeert naar een triviale cyclus (1, 4, 2, 1 voor Collatz, en de 104-highway cyclus voor Langton's mier). Over het vermoeden van Collatz merkte de grote wiskundige Paul Erdös ooit op dat de wiskunde misschien nog niet klaar is voor dergelijke problemen, dat wil zeggen, dat de wiskunde vandaag de dag wellicht nog het gereedschap ontbeert om dergelijke problemen aan te pakken. Wie de kracht en de reikwijdte van de wiskunde een beetje kent (ik niet hoor! 😉) beseft dat dit een zware en daarom een spectaculaire bewering is.

Hoewel de theorievorming ten aanzien van Langton's mier dus erg moeizaam verloopt, is het programmeren ervan bijzonder eenvoudig.

Globale omschrijving

Programmeer een veralgemeniseerde versie van Langton's mier waarbij cellen meer dan twee toestanden kunnen aannemen. Bekijk verder Aldo Cavini Benedetti's Youtube uitleg. (Deze uitleg bevat een caveat. Zie daarvoor de section “Bronnen”, onderaan.)

Werking

• Vooraf aan elke animatie (of: run, of: episode) wordt het aantal mogelijk toestanden 2 ≤ N ≤ 12 per cel vastgesteld. Voor de originele versie van Langton's mier geldt N=2.
• Toestanden worden geteld vanaf nul. Toestanden bezitten een eigen kleur: toestand 0 is wit, toestand 1 is rood, toestand 2 is lichtgroen, etc:

  

  In Netlogo zijn de kleurcodes van deze cellen resp. white, red, lime, cyan, yellow, 126, 3, brown, 52, blue, 43, en 124. Van deze kleurcodes mag niet worden afgeweken.
• Cellen met toestand nul die niet door een mier werden bezocht worden niet wit, maar grijs (Netlogo kleurcode “gray”) gekleurd. Op deze manier kan goed worden gezien welke cellen al werden belopen door een mier (wit, rood, lichtgroen, ...) en welke niet (grijs).
• Vooraf aan elke animatie wordt bepaald welke kant de mier zal afslaan bij welke toestand: links of rechts. Bijvoorbeeld, met N=3 zijn er drie mogelijke toestanden per cel, te weten 0, 1 en 2 (grijs/wit, rood, en lichtgroen). We moeten dan voor elke toestand vooraf aan elke animatie opgeven welke kant de mier zal afslaan, bijvoorbeeld naar links bij wit, naar rechts bij rood, en naar links bij lichtgroen. Deze laatst gegeven informatie kan voor het gemak worden afgekort tot de string LRL. Zo betekent bijvoorbeeld de string RLRRL dat patches in 5 verschillende toestanden kunnen verkeren (wit t/m geel), en dat de mier bij wit rechtsaf slaat, bij rood linksaf, bij lichtgroen rechts-, bij lichtblauw rechts-, en bij geel linksaf.
• Dat links- en rechtsaf slaan gaat als volgt. Een mier komt op een patch (cel), leest de toestand van die patch en draait dan, afhankelijk van de waarde van die toestand, 90⁰ naar links of naar rechts. Vervolgens wordt de toestand van die cel met één opgehoogt. De cel verandert bij elk bezoek dus van kleur. Lichtblauw gaat naar geel, geel gaat naar magenta, magenta gaat naar donkergrijs, enzovoort. Als de oude toestand-waarde gelijk was aan de maximum toestand-waarde N-1, dan is de nieuwe toestand-waarde niet N, maar 0. Toestand-ophoging vindt dus modulo N plaats. Daarna stapt de mier (na dus te zijn gedraaid) naar het midden van de volgende patch.

• Bijvoorbeeld, als de toestand-string van de situatie hiernaast gelijk is aan RLL, dan zal de mier in de situatie hiernaast de volgende stap naar rechts draaien, immers wit representeert toestand 0 en het karakter op index 0 van RLL is gelijk aan R. De witte patch waarop de mier staat zal toestand 0+1 aannemen, dus rood kleuren, en vervolgens zal de mier naar de groene cel wandelen. (Voor ons is dat de groene cel rechts van de mier, immers de mier was naar rechts gedraaid.) De mier staat nu op de groene cel en wijst naar het oosten. In een volgende stap zal de mier naar links draaien, de groene cel wit kleuren en daarna uiteraard weer een stap naar voren zetten.
• De LR-instructiestring van Langton's mier, dat wil zeggen van de originele mier, is dan gelijk aan RL (“white is right, red is left”). Het rooster kent in dat geval dan dus alleen maar grijze, witte en rode cellen.

Randvoorwaarden

Hier staat wat moet.* Bij afwijking van randvoorwaarden worden punten in mindering gebracht. Het voldoen aan de randvoorwaarden levert in ieder geval het cijfer acht op. Om een cijfer hoger dan een acht te halen dien je één of meer extra features te hebben geïmplementeerd.

1. Bij aanvang wijst de mier naar het Noorden.
2. In je uiteindelijke uitwerking moeten de absolute waarden van de minimum/maximum x/y patch-coördinaten gelijk zijn aan 140. De patch-grootte moet gelijk zijn aan 2. (Wel is het aan te raden om bij het ontwikkelen van je app een kleiner veld met grotere patches te nemen. Netlogo staat bij aanvang al op en klein veld met grote patches.)
3. De gebruiker moet zelf een LR-string kunnen opgeven.
4. De app kan zelf ook een willekeurige LR-string genereren als de gebruiker dat wil. Lengte ten minste 2 en ten hoogste 12.
5. Het volgende gedrag moet middels een Netlogo “chooser” (dit is een Netlogo widget) kunnen worden opgeroepen. (De namen heb ik zelf verzonnen, ik hoop dat ze aanspreken.)

   Langton's ant RL Still chaos after 1.000.000 steps RLR Immediately a simple highway LLR A straight highway to the right RRLLLRRRLRRR A broad highway, 45 degrees RRLRLLRLRR 568.000 steps before highway emerges LLLLLLRRLRRR A highway that is not a multiple of 45 degrees RLRLRLLRLR A curvy highway to the left LLRRRLRLRLLR Some way to fill a sector RRLRLRR Some other way to fill a sector RRLLLRLLLRRR White upper cone filler RRLLLRRRRRLR Left lower plane filler RRLRLLRRRRRR Some way to fill the whole plane RRLRR Fill the whole plane, connect with highways LRRRRRLLR Fill the whole plane, with spiraling highway LRRRRLLLRRR Your brain (from above) LLRR Your brain (from above), connected to an IC RLLR Professor's brain (from above) LLLLLLRRRRRR Professor's brain connected to an IC RRRLLLLLLRRR Complicated construction RRRRLRRRLLRR Biffled highway RLLLLRRRLLLR Overheating reactor RRLRLLLRRRR Extending square domain LLRLLLRRRRR Persian carpet LRLRLLLLLLLR Other carpet (skew) LLRRLRRRRRRR

   Waarden, exclusief gebruikers-input en random-gegenereerde keuze, in Netlogo syntax (handig voor copy-paste 😉): [ ["Langton's ant" "RL"] ["Still chaos after 1.000.000 steps" "RLR"] ["Immediately a simple highway" "LLR"] ["A straight highway to the right" "RRLLLRRRLRRR"] ["A broad highway, 45 degrees" "RRLRLLRLRR"] ["568.000 steps before highway emerges" "LLLLLLRRLRRR"] ["A highway that is not a multiple of 45 degrees" "RLRLRLLRLR"] ["A curvy highway to the left" "LLRRRLRLRLLR"] ["Some way to fill a sector" "RRLRLRR"] ["Some other way to fill a sector" "RRLLLRLLLRRR"] ["White upper cone filler" "RRLLLRRRRRLR"] ["Left lower plane filler" "RRLRLLRRRRRR"] ["Some way to fill the whole plane" "RRLRR"] ["Fill the whole plane, connect with highways" "LRRRRRLLR"] ["Fill the whole plane, with spiraling highway" "LRRRRLLLRRR"] ["Your brain (from above)" "LLRR"] ["Your brain (from above), connected to an IC" "RLLR"] ["Professor's brain (from above)" "LLLLLLRRRRRR"] ["Professor's brain connected to an IC" "RRRLLLLLLRRR"] ["Complicated construction" "RRRRLRRRLLRR"] ["Biffled highway" "RLLLLRRRLLLR"] ["Overheating reactor" "RRLRLLLRRRR"] ["Extending square domain" "LLRLLLRRRRR"] ["Persian carpet" "LRLRLLLLLLLR"] ["Other carpet (skew)" "LLRRLRRRRRRR"] ]

6. Voer een tick uit na elke zet (“move”). Dit is belangrijk om de animatie desgewenst snel te kunnen laten lopen. Netlogo kiest dan namelijk automatisch voor een repaint na elke tik, of een repaint na elke zoveel tikken.
7. De mier mag niet over de randen lopen. Als de mier dat toch dreigt te doen, wordt de animatie stopgezet.

Aanwijzingen

1. Zorg er voor dat je mier zich in de juiste richting beweegt. De originele versie van Langton's mier, bijvoorbeeld, zal in de eerste vier stappen met de klok mee bewegen. Bij start-oriëntatie Noord ontwikkelt de snelweg zich dan op den duur in het 3e kwadrant (het zuid-westen).
2. De waarde van N kan worden afgeleid van de toestand-string (de LR-string). Pas dit idee toe in je app.
3. Gebruik bij voorkeur het imperatief move-to patch-ahead 1 om naar de volgende patch te lopen. Dit plaatst je mier met zekerheid in het midden van de volgende patch. Het imperatief forward 1 doet dat ook, maar dan relatief t.o.v. de mier. Op deze manier kan het gebeuren dat na een groot aantal iteraties de mier niet meer op midden van patches staat.

Extra

Extra punten kunnen worden verdient door het aanbrengen van één of meer van de volgende features.

1. Startwaarden (+1) Geef de gebruiker de mogelijkheid om cellen willekeurige begin-waarden te geven in een straal radius van patch (0, 0). Interessant gedrag kan al worden opgeroepen door slechts een klein deel van de initialisatie-schijf te vullen met toestanden ongelijk nul. Daarom kent de initialisatie bovendien een parameter density (dichtheid), die aangeeft hoe groot de kans is dat een cel (op de initialisatie-schijf) bij initialisatie gezet wordt op een toestand ongelijk nul.
2. Heat map (+1) Hou het aantal bezoeken (“visits”) per cel bij. Kleur na afloop cellen blauw (Netlogo: sky) als deze niet bezocht werden. Kleur de cellen anders in een spectrum wat loopt van wit naar rood naar donkerrood tot zwart met behulp van het Netlogo primitief scale-color. Wit betekent dat de cel relatief vaak bezocht werd.
3. Alternatieve hoeken (+1) Laat de mier niet kiezen tussen 90⁰ en -90⁰, maar tussen vooraf opgegeven hoekparen waar verder geen beperking op ligt behalve dat zij veelvouden van 45⁰ zijn. Dus bv. de mier laten kiezen tussen -225⁰ en 315⁰. (Dat zijn beiden veelvouden van 45⁰.) Creëer in dit verband ook twee sliders met stapgrootte 45: één voor hoek L, en één voor hoek R.
4. Backtrack (+1) Langton's mier is, in tegenstelling tot de meeste cellulaire automaten, tijd-reversibel. Maak het mogelijk dat de gebruiker de mier vraagt één of meer stapjes terug te doen (wellicht doorlopend tot aan t=0). (De mier kan overigens verder dan t=0 in de tijd terug gaan...) Let er op dat een cel tijdig op grijs wordt terug gezet als dat moet. Ook als de mier daarna weer vooruit loopt! (Hint: gebruik daarvoor per cel het aantal bezoeken.)
5. Meerdere mieren (+2) Laat zien dat meerdere mieren elkaar kunnen begrenzen tot een eindige omgeving (nooit mogelijk bij één mier). Laat zien dat meerdere mieren elkaars snelwegen kunnen afbreken. Om nakijken te vergemakkelijken moet dit gedrag makkelijk terug op te roepen zijn via één enkele button die de mier en de cellen op de juiste manier initialiseert.
6. Highway detectie (+2) (Doe dit alleen voor Langton's mier.) Houd bij welke bewegingen de mier maakt en stop de animatie als de mier verzeild in een cyclus ter lengte 104. Maak ook een extra button waarmee de mier voortdurend opstart in een random omgeving (zie “Extra”, onderdeel “Startwaarden”.) bij de detectie van een snelweg. Als het snelweg-vermoeden waar is zou je app eeuwig moeten runnen.

Snippets

Haal er uit wat je handig lijkt. Het is niet verplicht deze code te gebruiken.

• Om patches te initialiseren:

  ask patches [ set state 0 set pcolor gray ]
  

• Om een globale kleurenlijst aan te leggen:

  globals [ colours ... ]
  
  set colours [ white red lime cyan yellow 126 3 brown 52 blue 43 124 ]
  

• Om een globale instructie-tabel aan te leggen:

  extensions [ table ]
  
  globals [ instruction-table ... ]
  
  set instruction-table table:from-list [
     ["Langton's ant" "LR"]
     ["Still chaos after 1.000.000 iterations" "RRL"]
     ["..."] ["..."]
     ...
  ]
  
  set state-sequence table:get instruction-table my-choice
  

  waarbij my-choice dan gebruikers-input is, bijvoorbeeld uit een Netlogo widget van het type “chooser”.
• Om een lijst te comprimeren naar een string:

  to-report to-string [ l ]
    report reduce [ [?1 ?2] -> word ?1 ?2 ] l
  end
  

• Om een willekeurige LR-string te genereren:

  let random-length 2 + random 10
  let random-sequence to-string n-values random-length [ one-of ["L" "R"] ]
  

• Twee condities om te controleren of gebruikers-invoer correct is:

  remove "L" remove "R" my-state-sequence = ""
  

  2 <= length my-state-sequence and length my-state-sequence <= 12
  

• Om voorzichtig een move te doen kan Netlogo's imperatief carefully worden gebruikt. Dit werkt hetzelfde als throw en catch in andere talen:

  carefully [
    <doe een stap>
  ] [
    ; als <doe een stap> faalt:
    set bumped? true
  ]
  

• Om na een bezoek de volgende toestand te bepalen:

  set state (state + 1) mod N

Nakijkmodel

Het volgende nakijkmodel zal worden gebruikt.

   ------------------------------------------------------

    1. gratis punt
    2. GUI (widgets thematisch gerangschikt, netjes uitgelijnd, handig benoemd,
            veel gebruikte widgets hebben shortcuts, ..)

    3. werkt in grote lijnen
    4. werkt 100% correct (interpretatie LR strings, oriëntatie mier,
       stop-conditie, conform randvoorwaarden kleuring, veldgrootte)

    5. code syntax (organisatie, leesbaarheid)
    6. code semantiek (vnl. executiesnelheid, maar dat zit in deze opdracht al snel goed)

    7. documentatie in de code (op plekken waar dat nodig is en helpt, niet redundant)
    8. documentatie in de tab (zinvol en netjes georganiseerd), aanwezigheid *.png

   ----- cijfer acht ------------------------------------

    9. best of extra feature
   10. "

   ----- cijfer tien ------------------------------------

Bronnen

1. Studying artificial life with cellular automata, C.G. Langton, 1986. In: Physica D: Nonlinear Phenomena, Vol. 22(1-3), pp. 120-149.
2. Langton's ant, engelstalige Wikipedia
3. Section Virtual Ants, Gary Flake, 1998. In: The computational beauty of nature: Computer explorations of fractals, chaos, complex systems, and adaptation, MIT Press, Cambridge, MA.
4. The Industrious Ant D. Gale, 1993. In: The Mathematical Intelligencer, Vol 15(2), pp. 54-58.
5. Aldo Cavini Benedetti's uitleg op Youtube (locale MP4). Zie ook zijn Flickr-pagina. Benedetti's mieralgoritme werkt iets anders dan Langton's officiële algoritme. In Benedetti's algoritme verandert de mier bij aankomst op een cel eerst de toestand van die cel. Pas daarna draait de mier op basis van de nieuwe toestand naar links of naar rechts. Daarom zijn Benedetti's LR-instructierijen anders dan onze LR-instructierijen. Benedetti's instructierijnen kunnen worden verkregen uit de onze door het laatste karakter van onze instructierij vooraan te zetten. Deze verschuiving is een gevolg van de premature toestandophoging in Benedetti's algoritme.
6. Langton's ant period. Lezing van de Russische wiskundige Alexei Bondal in het kader van het colloquium “Random geometry”, 12 September 2014, Moskou. Abstract: “We describe the famous cellular automaton called Langton's ant, as well as its generalizations, and present some conjectures and results on its behavior” (locale MP4) .