Kunstmatige intelligentie
Programmeeropgave 3 van 2016 — Tablut

De derde programmeeropgave behorende bij het vak Kunstmatige intelligentie gaat over het spel Tablut. Hierin strijden twee legers tegen elkaar op een rechthoekig 9×9 bord. Het witte leger probeert zijn koning te laten ontsnappen door hem naar de rand van het bord te bewegen. Het zwarte leger probeert de witte koning te slaan. Alle stukken bewegen zoals de toren in schaken. Het slaan van stukken gaat volgens het zogenaamde custodial capture principe. Kijk allereerst hier voor een uitgebreide beschrijving van de spelregels. En speel een spelletje. Voor een korte presentatie, en een programma voor het werkcollege van 29 maart 2016, zie hier.

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 binnen iterative deepening.
Gebruik het Tablut framework (versie februari 2014) 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 de evaluatiefunctie moet rekening gehouden worden met de asymmetrische doelen van beide spelers. Voor wit kan bijvoorbeeld de afstand van de koning tot de rand van het bord belangrijk zijn. Houd niet alleen rekening met het beschikbare materiaal, maar ook een aantal dynamische zaken zoals mobiliteit, pionstructuur, etc.
• negamax(…) (in search.cc): het negamax-algoritme. Dit 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: 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 er is rekening gehouden met de asymmetrische doelen van beide spelers.
• Onderzoek het verschil tussen het aantal door nega/minimax en alpha-beta bezochte knopen. Maak een aantal grafieken (met het aantal bezochte knopen) tot 7-ply diep vanaf de beginconfiguratie.

Met het referee programma kunnen twee programma's tegen elkaar spelen. Om tussentijds een idee te krijgen hoe goed je programma is, kan je (vanaf een NUWD computer) in de map /vol/share/groups/liacs/scratch/2016Tablut/ executables plaatsen en dus jouw programma tegen een programma van een collega te laten spelen.
Na de deadline zal er een competitie worden gehouden tussen alle ingeleverde programma's.

Het is ook mogelijk je eigen programma ./engine tegen Sigtyr (van de website) te laten spelen (vanaf een NUWD computer). Bijvoorbeeld: ./referee -b './engine -d 7 -t 5000' -w '/vol/share/groups/liacs/scratch/2016Tablut/sigtyr -d 11 -t 5000'
Hierbij staat -b/w voor de speler (wit/zwart), -d voor de maximale zoekdiepte en -t voor de maximale rekentijd per zet, in millisecondes. Let op de quotes.

Deadline: dinsdag 19 april 2016
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.

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

22 maart 2016 — http://www.leidenuniv.liacs.nl/~kosterswa/AI/tablut2016.html