cursus Inleiding Adaptieve Systemen Opleiding Kunstmatige Intelligentie 2020-21



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

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 antRL
    Still chaos after 1.000.000 stepsRLR
    Immediately a simple highwayLLR
    A straight highway to the rightRRLLLRRRLRRR
    A broad highway, 45 degreesRRLRLLRLRR
    568.000 steps before highway emergesLLLLLLRRLRRR
    A highway that is not a multiple of 45 degreesRLRLRLLRLR
    A curvy highway to the leftLLRRRLRLRLLR
    Some way to fill a sectorRRLRLRR
    Some other way to fill a sectorRRLLLRLLLRRR
    White upper cone fillerRRLLLRRRRRLR
    Left lower plane fillerRRLRLLRRRRRR
    Some way to fill the whole planeRRLRR
    Fill the whole plane, connect with highwaysLRRRRRLLR
    Fill the whole plane, with spiraling highwayLRRRRLLLRRR
    Your brain (from above)LLRR
    Your brain (from above), connected to an ICRLLR
    Professor's brain (from above)LLLLLLRRRRRR
    Professor's brain connected to an ICRRRLLLLLLRRR
    Complicated constructionRRRRLRRRLLRR
    Biffled highwayRLLLLRRRLLLR
    Overheating reactorRRLRLLLRRRR
    Extending square domainLLRLLLRRRRR
    Persian carpetLRLRLLLLLLLR
    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 900 en -900, maar tussen vooraf opgegeven hoekparen waar verder geen beperking op ligt behalve dat zij veelvouden van 450 zijn. Dus bv. de mier laten kiezen tussen -2250 en 3150. (Dat zijn beiden veelvouden van 450.) 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.

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 ------------------------------------
In de infotab staat onder FEATURES welke twee onderdelen (bij 1-puntsfeatures) of onderdeel (bij een 2-puntsfeature) worden/wordt voorgedragen als extra feature. Uiteraard mogen meerdere features worden geïmplementeerd, echter deze dingen dan niet mee. Deze voorwaarde is nog eens herhaald bij de inlevervoorwaarden op de practicumpagina.

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) .


*Naast de algemene randvoorwaarden voor de programmeeropdrachten en de algemene randvoorwaarden voor de programmeeropdrachten die specifiek in Netlogo worden uitgevoerd. Zie de pagina met clausules.


Laatst gewijzigd op vrijdag 05 maart 2021, om 12:41 uur ——— translate to ru, ro, or en ——— Auteur(s): Gerard Vreeswijk