Kunstmatige intelligentie
Programmeeropgave 3 van 2022 — A*

Er is voorbeeldcode [versie 22 maart 2022; 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. Een voorbeeldaanroep is: ./puzzle drie.txt 25 1 2 2 100 0 123, waarbij 100 maal een verschoven puzzel gebaseerd op drie.txt wordt opgelost, met als random seed 123. De maximale lengte, of de limiet bij IDA*, van een oplossing is hier 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) en de maximale grootte van de "frontier" (constante MEMORY).
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 voor het lege vakje staat. Een zet bestaat uit het verwisselen van de nul met een direct horizontaal of verticaal aangrenzend getal. Verder kunnen er "zwarte" of geblokkeerde vakjes zijn, aangegeven met het getal 99.

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 A* versus IDA*.
• 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 20 april 2022, 14:00 uur.
In te leveren: een geprint exemplaar van het verslag (alleen eigen C++-code in de appendix) tijdens het college, en een e-mail met de volledige C++-code naar onderstaand adres. Het verslag moet aan verschillende eisen voldoen.

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

21 maart 2022 — http://www.leidenuniv.liacs.nl/~kosterswa/AI/aster2022.html