Kunstmatige intelligentie
Programmeeropgave 3 van 2020 — Othello

De derde programmeeropgave (in het voorjaar van 2020) behorende bij het vak Kunstmatige intelligentie gaat over het twee-persoons spel Othello. Het is de bedoeling het minimax-algoritme, en ook het alpha-beta-algoritme, te implementeren, voor een geschikte evaluatie-functie.

Op een rechthoekig m bij n bord bevatten de niet-lege vakjes een witte of zwarte schijf. Standaard-Othello is op een 8-bij-8 bord. De beginstand is die zoals in het linker groene plaatje.
Als een speler aan de beurt is (ze spelen om en om) moet hij/zij een steen van de eigen kleur plaatsen, zodanig dat er "geslagen" wordt. Dat laatste betekent dat er één of meer stenen van de tegenstander nu direct ingesloten raken, horizontaal, verticaal of diagonaal; deze klappen allemaal om van kleur na het slaan (zie tweede en derde plaatje, na zetten op plek A). Als je bij Othello niet kunt, moet je passen; als beide spelers niet meer kunnen, stopt het spel, en wint degene met de meeste eigen stenen; remise is hier ook mogelijk, namelijk als beide spelers evenveel stenen hebben. Als het bord vol is, houdt het zeker op, maar het kan ook eerder zijn.

Er is voorbeeldcode [Let op: kleine fout ontdekt en verbeterd, zie aankondiging BlackBoard 10 april 2020] beschikbaar, waarin diverse functies zitten om het spel te spelen, en zelfs een randomspeler, een "gretige links-boven speler" en een Monte Carlo speler. Elke speler zit in een eigen file. De code stelt je in staat om twee verschillende spelers = programma's het spel tegen elkaar te laten spelen. Lees eerst het commentaar en bestudeer de meegeleverde spelers. Wijzig in de file othello.cc alleen daar waar in de code "beginTODO...eindeTODO" staat, om daarmee verschillende spelers aan te roepen. En excuses voor het gebruik van Nederlands en Engels door elkaar.

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. Denk er aan dat er soms gepast moet worden. Er moeten verschillende (member-)functies geschreven worden:

• int evaluate (...) evalueert de huidige positie vanuit het standpunt van speler 0 (BLACK).
• int gametree (..., int depth, int & themove, int & evaluates) rekent de minimax-waarde voor de meegegeven positie uit, tot en met diepte depth (voor zover er nog evalautes beschikbaar zijn), en levert een beste zet in themove (als depth = 1 worden alleen de kinderen bekeken, etcetera); evaluates houdt het (maximale) aantal aanroepen van de functie evaluate bij
• idem: alpha-beta — wat dezelfde waardes zou moeten opleveren als de diepte hetzelfde is (let op: standaard wordt ingeperkt op het aantal aanroepen van de evaluatie-functie)
  Als dit onderdeel ontbreekt, kost dat één punt.
• int volgendeZet ( ) doet een goede (?) zet met bovenstaande methode
• eigen functies naar believen

De eerder genoemde functies mogen natuurlijk worden aangevuld met meer geavanceerde technieken of heuristieken zoals: quiescence search, null-moves, transpositie-tabellen, etc. Ook stellen we interessante evaluatie-functies op prijs. Let ook op de executiesnelheid en rapporteer daarover.

Een paar opmerkingen:

• Beschrijf in het verslag duidelijk hoe de evaluatie-functie 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, dom (= gretig links-boven), Monte Carlo, verschillende zoekdieptes/RESOURCES, verschillende evaluatie-functies, programma's van collega's, parameters van de evaluatie-functie, verschillende bordgroottes, ...
• Rapporteer in het bijzonder over een experiment waarin tegen een programma van iemand anders wordt gespeeld.

Deadline: donderdag 23 april 2020, 11:00 uur.
In te leveren: e-mail met het verslag (alleen eigen C++-code in de appendix) en C++-code. Het verslag moet aan verschillende eisen voldoen.

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

4 maart 2020 — http://www.leidenuniv.liacs.nl/~kosterswa/AI/othello2020.html