Kunstmatige intelligentie
Programmeeropgave 3 van 2018 — Clobber

Op een rechthoekig m bij n bord bevatten de niet-lege vakjes een witte of zwarte schijf. De beginstand kan willekeurig zijn, of juist regelmatig.
Als een speler aan de beurt is (ze spelen om en om) moet hij/zij met een steen van de eigen kleur een horizontaal of verticaal direct aangrenzende steen van de andere kleur pakken (slaan, "clobberen"). Als een speler niet kan zetten heeft hij/zij verloren, en heeft de ander gewonnnen.

Voor meer achtergronden, zie hier, of lees J. Griebel en J. Uiterwijk, Combining Combinatorial Game Theory with an alpha-beta Solver for Clobber, Proceedings BNAIC 2016, pp. 48-55; link.

Er is voorbeeldcode beschikbaar, waarin diverse functies zitten om het spel te spelen, en zelfs een randomspeler, een "gretige links-boven speler" en een Monte-Carlo speler. De code stelt je in staat om verschillende programma's (zelfs meer dan twee) het spel tegen elkaar te laten spelen. Lees eerst het commentaar bovenin Clobber.cc en bestudeer de drie meegeleverde spelers. Let op: je mag membervariabelen zoals bord in Clobber.cc "public" maken, anders kun je er niet bij vanuit de spelers.

Het is de bedoeling een zoekalgoritme te schrijven dat, gegeven een spelconfiguratie, een zo goed mogelijke zet vindt. We gebruiken hiervoor het minimax-algoritme, met alpha-beta pruning. Er moeten verschillende (member-)functies geschreven worden:

• int evaluatie (short speler) evalueert de huidige positie voor speler (die niet noodzakelijk zelf aan de beurt is!)
  Misschien is het handiger het altijd te bekijken vanuit het standpunt van speler 0, waarbij speler aan de beurt is.
• int minimax (short speler, int diepte, int & dezet) rekent de minimax-waarde voor speler uit, tot en met diepte, en levert een beste zet in bestezet (als diepte = 0, moet het volledig random zijn, bij diepte = 1 worden alleen de kinderen bekeken, etcetera)
• idem: alpha-beta — wat dezelfde waardes zou moeten opleveren
• void slimmezet (int param) doet een slimme zet met alpha-beta; aangenomen mag worden dat er minstens één zet mogelijk is; param is een parameter die (bijvoorbeeld) de diepte aangeeft
• eigen functies naar believen

De eerder genoemde functies mogen worden aangevuld met meer geavanceerde technieken of heuristieken zoals: quiescence search, null-moves, transpositie-tabellen, etc. Ook stellen we interessante evaluatiefuncties op prijs (let op de executiesnelheid; denk: 1 minuut voor circa tien tweepersoons spelletjes random tegen alpha-beta met diepte 6, op een 6 bij 6 bord).

Zoals al opgemerkt, het spel kan ook met meer dan twee spelers gespeeld worden. Doe dus een experiment met drie spelers, en rapporteer daar kort over.

Een paar opmerkingen:

• Beschrijf in het verslag duidelijk hoe de evaluatiefunctie werkt.
• Maak met een experiment aannemelijk dat de geimplementeerde minimax en alpha-beta dezelfde resultaten opleveren.
• Onderzoek het verschil tussen het aantal door minimax en alpha-beta bezochte knopen. Maak een grafiek die dit illustreert.
• Rapporteer over de verhouding tot andere spelers: random, Monte-Carlo, verschillende zoekdieptes, verschillende evaluatie-functies, programma's van collega's, ...
• Rapporteer in het bijzonder over een experiment waarin tegen een programma van iemand anders wordt gespeeld.
• En over een experiment met drie (of meer) spelers.

Deadline: donderdag 26 april 2018, 11:00 uur.
In te leveren: een geprint exemplaar van het verslag (alleen eigen C++-code in de appendix) 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.

27 maart 2018 — http://www.leidenuniv.liacs.nl/~kosterswa/AI/clobber2018.html