Kunstmatige intelligentie
Programmeeropgave 3 van 2015 — Jungle

De derde programmeeropgave behorende bij het vak Kunstmatige intelligentie gaat over het spel Jungle. Hierin is het de bedoeling om een stuk op een speciaal vakje (den) van een rechthoekig 7×9 bord te krijgen door deze in orthogonale richting te bewegen. Ieder stuk heeft een rang (1 rat; 2 kat; 3 wolf; 4 hond; 5 luipaard; 6 tijger; 7 leeuw; 8 olifant) en kan een stuk van de tegenstander slaan indien dat stuk dezelfde of een lagere rang heeft (vergelijk: Stratego). De stukken kunnen zich niet door het water bewegen met uitzondering van de rat, die, hoewel hij de laagste rang heeft, de olifant kan slaan. De leeuw en de tijger kunnen over het water springen. De vakjes rond de den zijn traps. Een vijandelijk stuk wordt daarin tot de laagste rang gedegradeerd. Kijk ook hier (versie 23mrt2015) voor een uitgebreide beschrijving van de spelregels.

Het is de bedoeling een zoekalgoritme te schrijven dat, gegeven een spelconfiguratie, een zo goed mogelijke zet vindt. We gebruiken hiervoor twee varianten van het minimax algoritme: negamax en alpha-beta pruning.
Gebruik het Jungle framework (versie: 5mrt2013) van de website. Binnen het framework moeten tenminste drie functies worden geschreven:

• evaluate() (in evaluation.cc): dit is de evaluatiefunctie voor een spelconfiguratie. Deze functie wordt door zowel negamax als de alpha-beta functie gebruikt om een heuristische waarde te bepalen van de huidige stand op het bord.
  Binnen deze functie moeten minimaal twee factoren aan bod komen: de (relatieve) waarde van de in het spel zijnde stukken en de afstand van een/alle/sommige stuk(ken) tot het doel.
• negamax(…) (in search.cc): het negamax-algoritme. Deze is in principe hetzelfde als de klassieke minimax-functie waarbij gebruik wordt gemaakt van de zero-sum eigenschap: max(a, b) = -min(-a, -b).
• alphabeta(…) (in search.cc): alpha-beta pruning. Deze functie probeert het aantal bezochte knopen van negamax wat te beperken door in de zoekboom te snoeien indien dit mogelijk is.

De eerder genoemde functies mogen eventueel ook worden aangevuld met meer geavanceerde technieken of heuristieken zoals: iterative deepening, quiescence search, null-move pruning, transposition tables, etc. Ook stellen we interessante evaluatiefuncties op prijs (let op de executiesnelheid).

• Beschrijf in het verslag duidelijk hoe de evaluatiefunctie werkt aan de hand van voorbeelden waaruit blijkt dat zowel de relatieve waarde van de stukken als hun positie op het bord (ten opzichte van het doel) bepalend is.
• Onderzoek het verschil tussen het aantal door negamax en alpha-beta bezochte knopen. Maak een aantal grafieken (met het aantal bezochte knopen/bladeren) tot 7-ply diep vanaf de beginconfiguratie.
• Bereken voor beide methoden de branching factor en relateer deze aan de theoretische branching factor van alpha-beta en maak wederom een grafiek.

Met contest.sh kunnen twee programma's tegen elkaar spelen. Na de deadline zal er een competitie worden gehouden tussen alle ingeleverde programma's. Een punt van het cijfer wordt bepaald door de uitslag van de onderlinge competitie.

Het is ook mogelijk je eigen programma tegen Bagheera (van de website) te laten spelen (vanaf een computer binnen het LIACS en met ssh).
Bijvoorbeeld: ./contest.sh '/home/jvis/public_html/doushouqi/bin/bagheera -w -d 11 -t 5' './jungle b 7' (let op het verschil in de argumenten).

Deadline: dinsdag 21 april 2015.
In te leveren: een geprint exemplaar van het verslag tijdens het college, en de C++-code van het programma naar onderstaand adres. Het verslag moet aan verschillende eisen voldoen.

Vragen en/of opmerkingen kunnen worden gestuurd naar: w.a.kosters@liacs.leidenuniv.nl.

23 maart 2015 — http://www.liacs.leidenuniv.nl/~kosterswa/AI/jungle2015.html