Kunstmatige intelligentie
Programmeeropgave 3 van 2024 — A*

Er is voorbeeldcode [versie 14 maart 2024; 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 parameters, 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, 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 dubbele getallen zijn!

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 waarin diverse getallen in de puzzel hetzelfde zijn, zoals in dubbel3.txt.
• Sta ook diagonale zetten toe. De parameter k moet dan tussen 0 en 7, grenzen inbegrepen, lopen. En uiteraard moeten de functies movepossible en domove worden aangepast. En de heuristieken, die moeten admissibel zijn!
  Let op: je mag ook zelf een andere interessante zet-variant kiezen.
• Pas de gegeven functies aan — met uitleg in het verslag.

Deadline: woensdag 17 april 2024, 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.

13 maart 2024 — http://www.leidenuniv.liacs.nl/~kosterswa/AI/aster2024.html