Kunstmatige intelligentie
Programmeeropgave 3 van 2023 — A*

Er is voorbeeldcode [versie 22 maart 2023; er komen wellicht nog aanpassingen of verbeteringen] beschikbaar, waarin al diverse functies zitten; deze code moet als basis gebruikt worden, maar wijzigingen zijn toegestaan. Lees eerst het commentaar bovenaan het programma; let erop dat sommige puzzels echt niet oplosbaar zijn, en sommige andere niet met de gekozen parametersi, zoals de grootte van het geheugen. Een voorbeeldaanroep is: ./puzzle drie.txt 25 50000 1 2 2 100 0 123, waarbij 100 maal een puzzel gebaseerd op de file drie.txt (zie onder) wordt opgelost, met als random seed 123 en maximaal geheugen 50000. De maximale lengte van een oplossing is hier (in zekere zin) 25, en de 0 betekent dat er weinig geprint wordt (een 1 levert veel uitvoer). Tot slot betekent 1 2 2 dat de puzzel misschien echt niet oplosbaar is (de 1; bij 2 altijd wel oplosbaar), dat heuristiek 2 wordt gebruikt (de som van de Manhattan-afstanden; ook 0 en 1 zijn al beschikbaar) en dat methode 2 wordt gebruikt (dat is A*, 1 levert best first en 3 is IDA*). Let op de maximale grootte van de puzzel (constante MAX).
Er zijn diverse voorbeeldfiles met puzzels: twee.txt, drie.txt (maximaal 31 zetten voor oplosbare puzzels), vier.txt, abc.txt, impossible.txt, strange.txt, cirkel.txt, dubbel3.txt en dubbel4.txt, De eerste regel bevat steeds hoogte en breedte van de puzzel, daarna per rij de getallen. Er is in iedere puzzel precies één nul, die het lege vakje representeert. Een zet bestaat uit het verwisselen van de nul met een direct horizontaal of verticaal aangrenzend getal. Verder kunnen er "zwarte" = geblokkeerde vakjes zijn, aangegeven met het getal 99. En dubbele getallen!

Wat is de bedoeling?

• Voer experimenten uit met de verschillende instellingen van het programma en de (ook eigen) voorbeeldfiles, en rapporteer daarover.
• Kijk in het bijzonder naar geheugengebruik en runtime bij de drie methoden. Hoeveel knopen worden er ge-expandeerd (voeg zelf tellers toe)?
• IDA* blijft nu maar doorgaan als er geen oplossing is en de limiet erg hoog is. Repareer dit. (Hint: voorkom direct terugzetten.)
• Door in de scramble2-functie wat minder vaak random te schuiven, ontstaan wellicht eenvoudiger puzzels. Experimenteer hiermee.
• Schrijf verder een eigen betere heuristische functie voor puzzels als abc.txt, waarin zwarte vakjes (wellicht op speciale plekken) staan.
• Onderzoek de situatie waarin diverse getallen in de puzzel hetzelfde zijn, zoals in dubbel3.txt.
• Verbeter eventueel de gegeven functies — met uitleg in het verslag.

Deadline: woensdag 26 april 2023, 13:15 uur.
In te leveren: een geprint exemplaar van het verslag (alleen eigen C++-code in de appendix) tijdens het college, en de volledige C++-code via Brightspace => Assignments. Het verslag moet aan verschillende eisen voldoen.

Vragen en/of opmerkingen kunnen worden gestuurd naar: aicollege@liacs.leidenuniv.nl.

22 maart 2023 — http://www.leidenuniv.liacs.nl/~kosterswa/AI/aster2023.html