Bob's Portfolio

Kunstmatige Intelligentie

Keuzeonderwerp V6 periode 1

Voor het keuzeonderwerp van periode 1 van V6 ga ik mij richten op 2 gebieden die wat met Kunstmatige Intelligentie te maken hebben, namelijk het maken van doolhoven en hoe de computer de weg kan vinden in deze doolhoven. Om dit project tot een goed einde te brengen heb ik me gehouden aan dit stappenplan:

  1. Orienteren op het gebied van doolhoven en padvind-algoritmes
  2. Algoritmen uitwerken en vaststellen wat het eindproduct (een goed afgewerkt werkend programma) nodig heeft om te kunnen functioneren.
  3. Het programmeren van het programma.

Het programma Maze+ inclusief bronbestanden en designsheet kun je hier downloaden. Als je geinteresseerd bent in de ontwikkeling van het programma kun je hieronder verderlezen.

De Orientatie

Het eerste wat ik deed was meer opzoeken over het onderwerp. Ik had al eerder hier en daar wat gelezen over doolhoven en het oplossen ervan, maar veel wist ik nog niet. Ik wist al wel dat je doolhoven grofweg kan indelen in twee categorieen: perfecte doolhoven en niet-perfecte doolhoven. Perfecte doolhoven hebben maar 1 ingang en 1 uitgang. Elk punt in het doolhof is te bereiken vanaf een ander punt, en er is altijd maar 1 weg om van A naar B te komen, wat ook automatische de kortste is. Ik had hier en daar al wat algoritmes bekeken voor dit type doolhoven, dus ik besloot mezelf uitsluitend te richten op deze algoritmes. Uiteindelijk heb ik deze 3 algoritmes uitgekozen: Prim's algoritme, het Hunt & Kill algoritme & het binaire algoritme. Ik ging ook nog zelf een algoritme maken voor een ideetje dat ik had: het muurgroeier-algoritme. Toen moest ik ook nog een pad-vind algoritme zoeken. Na een tijdje zoeken moest ik kiezen tussen deze twee algoritmes: het A* algoritme & Dijkstra's algoritme. Ik koos voor Dijkstra's algoritme, omdat het ietsje makkelijker te implementeren is, en bovendien gaat het A* er een beetje vanuit dat er een bepaalde logica zit in doolhoven, wat over het algemeen niet zo is waardoor je het dus als een mindere goede keus zou kunnen beschouwen.

Algoritmes uitwerken en programma vaststellen

Ik begon met het uitwerken van de algoritmes. Ik zal hieronder beschrijven hoe elk algoritme werkt.

Hunt & Kill

Het Hunt&Kill is het algoritme met de meest (naar mijn mening) interessante naam. Het algoritme is gebaseerd op dat van de recursive backtracker, en is redelijk snel met geheugengebruik recht evenredig met de grootte van het doolhof. Nadeel is dat het niet altijd redelijk interessante doolhoven produceerd, maar dat hoeft geen probleem te zijn. Als je van bovenaf het doolhof bekijkt is hij makkelijk, maar als je er zelf in zit is hij erg moeilijk.

Binair

Bij een project voor informatica kan een subtiele referentie naar de binaire aard van de computer natuurlijk niet vergeten worden. Het binaire algoritme is het simpelst van alle algoritmes. Het is het snelst, en gebruikt geheugen recht evenredig aan de grootte van het doolhof. Nadeel is alleen: de doolhoven zijn echt heel erg simpel. Gelukkig heb ik de complexiteit van doolhoven niet als criteria gesteld.

Prim's

Hoe de doolhoven van Prim's algoritme gegenereerd worden vind ik een mooi proces. Het algoritme verspreid zich als een soort virus over het veld. Het is makkelijk om te begrijpen, maar minder makkelijk om te implementeren. Dit kom omdat je bij het genereren van dit doolhoof gebruik maakt van een dynamische lijst. Dit is een lijst waar je vrij elementen aan toe kunt voegen en uit weg kunt halen. Voordeel is dat het dus een erg dynamisch doolhoof wordt, maar het heeft ook een nadeel. Het bijhouden en bewerken van een dergelijke lijst kost vooral als hij langer wordt erg veel moeite. Het is dus een van de 2 algoritmes die ik heb uitgekozen die niet geheugenloos is. Bovendien zijn de doolhoven redelijk makkelijk op te lossen, als je ze weer van bovenaf bekijkt. Het is verder redelijk snel, en gebruikt geheugen exponentieel aan de grootte van het doolhof.

Mijn eigen creatie: het Muurgroeier-algoritme

Met dit algoritme werd ik een keer op een ochtend in m'n hoofd wakker. Ik weet niet of ik het volledig zelf heb bedacht, mogelijkheid is dat ik hem een keer op internet langs heb zien komen maar dat later weer vergeten ben. Het was een leuk algoritme om uit te werken en te implementeren, al had ik het niet altijd naar mijn zin tijdens het implementeren. Dit algoritme is namelijk een algoritme dat werkt op het principe van het plaatsen van muren. De andere algoritmes werken precies vanuit het tegenovergestelde principe: het weghalen van muren. Ik heb het systeem om doolhoven op te slaan in het geheugen dus ook georienteerd op het benaderen van individuele cellen, en niet van individuele muren. Dat zorgde ervoor dat mijn systeem soms terugvocht: bepaalde denkstappen die ik in het algoritme kon maken moesten bij het implementeren met een omweg. Resultaat hiervan is een stuk in mijn programma met een hoop zoals ik het noem "dirty coding": weinig functies en objecten, maar veel losse variabelen en "handwerk" (in plaats van iets om te zetten in een functie het copy-pasten van code en de variabelen daarin veranderen). Gelukkig is het me uiteindelijk wel gelukt. Van dit algoritme heb ik uiteindelijk het meeste geleerd.

Dijkstra's

Toen moest ik als laatste een padvind-algoritme zoeken. Na wat googlen en rondstruinen op wikipedia had ik mijn keuzelijstje vernauwd tot twee keuzes: Dijkstra's algoritme & het A*-algoritme. Ik was eerst van plan het A*-algoritme te gebruiken, maar hier heb ik later van afgezien. Dit was om bepaalde redenen. Ten eerste omdat het A* algoritme veel rekening houdt met afstanden en de vorm van de omgeving. Dit heeft bij de meeste doolhoven geen toegevoegd waarde, aangezien er maar een pad is (het kortste) en de doolhoven altijd zo goed als willekeurig zijn waardoor er geen bedoeling zit in de paden en je de afstanden dus ook niet in kan schatten (wat een onderdeel is van het A*-algoritme). Ten tweede was het A*-algoritme ook wat moeilijker om te implementeren omdat er meerdere dynamische lijsten aan te pas kwamen, waar ik een beetje tegenop zag. Ten derde vond ik het gevolg van het A*-algoritme maar niets: verlies van snelheid door meerdere dynamische lijsten. Daarom heb ik alles meegenomen maar voor Dijkstra's gekozen, omdat ik gewoon een simpel en snel algoritme nodig had.

Voor wie het algoritme niet snapt heb ik nog een extra voorbeeld. Stel je voor, je begint bij het beginhokje. Dan zet je op alle omliggende hokjes een bordje met een pijl, en laat alle pijlen wijzen naar het beginhokje. Dan kies je vervolgens een van die hokjes, en zet je op alle hokjes die om dat hokje heenliggen (waar nog geen bordjes op staan) bordjes met pijlen erop, die je allemaal naar het hokje laat wijzen waar je nu opstaat. Dit blijf je doordoen totdat je uiteindelijk op het hokje komt dat je als bestemming had vastgesteld. Als je vanaf hier terug wilt komen naar het startpunt hoef je vervolgens alleen maar de pijlen te volgen! En zo vind je dan het juiste pad. Dit pad is (in mijn geval) automatisch ook het kortste, omdat het allemaal perfecte doolhoven zijn.

Merk op dat de beschrijvingen van de algoritmes niet optimaal en een beetje versimpeld zijn. Het eindresultaat is hetzelfde, maar deze zullen waarschijnlijk een stuk langzamer zijn. Ze leveren echter hetzelfde resultaat als de algoritmes die ik daadwerkelijk gebruikt heb in mijn programma.

Programma vaststellen

Voordat ik begon met programmeren ging ik eerst vaststellen wat ik allemaal nodig had voor het programma. Deze zou ik dan vantevoren eerst gaan maken, en later allemaal combineren in het uiteindelijke programma. Wat had ik nodig?

Zo zag mijn "boodschappenlijstje" (ook wel designsheet genoemd) eruit. De originele designsheet is bijgevoegd met het Maze+ programma, als iemand er belangstelling voor heeft. Merk wel op dat het originele document niet mooi ingedeeld is. Het was voor mij puur een lijst om bij te kunnen houden wat er moest gebeuren, wat ik nog nodig had of hoe ik iets aan moest pakken.

Het programmeren

En toen moest ik beginnen met het daadwerkelijk programmeren van het programma, wat heerlijk soepel ging (op het muurgroei algoritme na...). Voor het knoppensysteem had ik al gauw een kandidaat, namelijk een knoppensysteem dat ik had geschreven voor een eerder projectje, wat ik met een paar aanpassingen ook kon gebruiken voor dit project. Het spelsituatie-systeem was ook snel gevonden, dat had ik namelijk eerder ook al geschreven voor een ander project, en kon ik ook (met ietwat meer aanpassingen) gebruiken voor dit project. Om te kunnen schrijven naar het scherm en input van de gebruiker (muis, rood kruisje rechtsboven) te verkijgen heb ik gebruik gemaakt van de SDL engine. SDL staat voor Simple Directmedia Layer. Het is een zoals de naam al zegt simpele engine die ik al vaker gebruikt heb. Hij is lichtgewicht en crossplatform met bovendien een erg grote community, waardoor ik als ik een probleem heb vaak makkelijk een oplossing kan vinden. Het selectievakjesysteem en het doolhof opslagsysteem waren twee niet al te moeilijke maar leuke uitdagingen. Bij beiden heb ik mijn vaardigheid om objectgeorienteerd te programmeren weer verbeterd. Ik maakte er voor mijzelf een uitdaging van door zo min mogelijk globale variabelen te gebruiken, en het is me gelukt om het te beperken tot 3 globale variabelen. Het programmeren van dit programma had me zonder late avonden waarschijnlijk rond de 2 a 3 weken gekost. Ik heb er echter, in verband met een druk schema, uiteindelijk een week aan besteed.

Evaluatie

Wat ging er goed, wat ging er mis? Iets waar ik bij dit project heel erg tevreden over ben is het werk vooraf. Als ik soms met een eigen projectje bezig ben doe ik dingen vaak uit de losse pols. Ik begin gewoon met typen en uiteindelijk kom ik er wel. Niet de mooiste manier, maar het werkt. Hier heb ik dat anders aangepakt: ik heb precies vantevoren vastgesteld wat ik ging doen en hoe ik dat ging doen, waardoor ik bijna nooit met vraagtekens zat (wat ik normaal wel veel heb). Iets anders waar ik echt trots op ben is de object-georienteerdheid van dit progamma. Ik heb veel dingen als "object" benaderd, wat een redelijk nieuw concept voor mij is, waardoor ik bugs razendsnel kon opsporen, systemen en algoritmen makkelijk met elkaar kon combineren en de algehele ontwikkelingssnelheid veel hoger lag dan normaal. Helaas ging niet alles goed. Ik ben namelijk ook veel te laat begonnen met het programmeren, waardoor ik in tijdnood kwam en veel late avonden heb moeten maken om het af te krijgen. Daarnaast kwam het idee voor een zelfgemaakt algoritme ook wat later, wat heel erg veel tijd gekost heeft. Daar had ik misschien beter van af kunnen zien.

Al met al vond ik dit een superleuk project om te maken. Ik heb me goed verdiept in de stof, me goed voorbereid op het programmeren van het programma zelf en (snelheids)grenzen verlegd bij het programmeren. Ik hoop dat jullie net zoveel plezier hebben van het eindresultaat als ik had van het maken van dit programma! :-)