Colloquium Berto Booijink

Dit jaar gaat CoVer ook de afstudeercolloquia van haar leden promoten. Zodoende kunnen leden een duidelijker beeld krijgen van het onderzoek aan het eigen instituut. Wil je meer van de colloquia weten? Kijk dan op www.ai.rug.nl/nl/colloquia

Deze week: Berto Booijink - \"Strategie Evolutie en Resolutie Deductie in Diplomacy\"

Toelichting bij dit colloquium:
Diplomacy is een strategisch spel waarbij zeven spelers proberen Europa te veroveren. De spelers hebben legers en vloten tot hun beschikking om dit doel te bereiken. Ze onthullen telkens gelijktijdig welke zetten ze met hun materieel willen doen. Alle zetten samen bepalen welke zetten daadwerkelijk worden uitgevoerd; zetten kunnen elkaar verhinderen of juist ondersteunen.

Speltheorie is het onderzoeksgebied binnen de kunstmatige intelligentie dat zich bezig houdt met de wisselwerking tussen mensen. Gezelschapsspellen vormen een perfect domein voor dergelijk onderzoek. Spellen met grote zoekruimten zijn met name interressant. Diplomacy overtreft zelfs Go wat dit betreft, waardoor het klassieke zoekalgoritmen geen enkele kans laat. Slimmere technieken zijn nodig om Diplomacy te doorgronden.

Ik heb een implementatie gemaakt van een Diplomacy-speler, gebaseerd op een genetisch algoritme dat strategieen evolueert. Hij past voortdurend zijn plannen aan voor de situaties die hij verwacht tegen te komen, continu rekening houdend met de mogelijke tegenwerkingen van anderen. Ook heb ik een algoritme geschreven dat de zetten van alle spelers verwerkt door middel van logische deductie. Het stelt mijn speler in staat gevolgen van mogelijke zetten voor hemzelf en zijn tegenspelers te voorzien.

Simulatie heeft uitgewezen dat de vervaardigde speler significant beter presteert dan willekeurig spelende tegenstanders.