Kunstmatige intelligentie
Programmeeropgave 3 van 2022 — A*

schuiven maar De derde programmeeropgave (in het voorjaar van 2022) behorende bij het vak Kunstmatige intelligentie gaat over schuifpuzzels zoals de 15-puzzel. We gaan daartoe algoritmen als A* in C++ programmeren. Zie de colleges over Zoeken (sheets 18, 19 en 20) en over Gericht zoeken. Daar zijn ook video's van.

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 30 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 30, 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?

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