Kunstmatige intelligentie
Programmeeropgave 1 van 2017 — Clobber

Op een rechthoekig m bij n bord bevatten de niet-lege vakjes een witte of zwarte schijf, en in de versie met meer spelers een "schijf" met 0, 1, 2, ... De beginstand kan willekeurig zijn, of regelmatig.
Als een speler aan de beurt is (ze spelen om en om: wit-zwart-wit-... of 0-1-2-3-0-1-2-...) moet hij/zij met een steen van de eigen kleur een horizontaal of verticaal direct aangrenzende steen van de/een andere kleur pakken (slaan). Als een speler niet kan zetten moet hij/zij passen. Bij de tweepersoons versie: zodra een speler past, heeft de ander gewonnnen. Bij de meerpersoons versie: als alle spelers moeten passen heeft de laatste die een zet deed gewonnen. (Overigens: als hier een speler moet passen, kan hij/zij nooit meer.)

Een leuke recente publicatie over Clobber: J. Griebel en J. Uiterwijk, Combining Combinatorial Game Theory with an alpha-beta Solver for Clobber, Proceedings BNAIC 2016, pp. 48-55; link.

Gebruik het Clobber-voorbeeldprogramma van de website.

Bestudeer nu AI-spelers voor drie (of meer) spelers:

• EEN: speelt volledig random, zie voorbeeld-code. (Tip: kies optie 66 voor MC-speler, dan speelt iedereen random.)
• TWEE: bedenk zelf een (eenvoudige) strategie. Vul daartoe voorbeeld-code aan met een geschikte functie.
  Een idee is bijvoorbeeld het volgende. Loop alle mogelijkheden af, speel per mogelijkheid in een kopie van het bord de betreffende zet (via clobber kopie = *this;), beoordeel de stand, en selecteer tot slot de "beste" zet. Denk niet verder vooruit. Kijk bijvoorbeeld naar het aantal mogelijke zetten voor de andere spelers. Of: hoeveel "actieve" stenen heeft de huidige speler nog, al dan niet "gedekt"?
• DRIE: idem, maar nu met Monte Carlo.
  Speel voor alle mogelijke zetten een aantal random spelletjes (zeg 1000; met gebruik van de random-speler), en kies daaruit de "beste". Zie verder de voorbeeld-code.

Tip voor gnuplot: maak een plot-file plot.gpi met daarin bijvoorbeeld
     # plot-file voor gnuplot
     set xrange [0:10]
     set yrange [17:42]
     set xlabel "iets"
     set ylabel "iets anders"
     set terminal jpeg
     set output "file.jpg"
     plot "mijnfile.txt" using 1:2 with lines notitle
en roep deze binnen gnuplot aan met load "plot.gpi". Uiteraard moet de file mijnfile.txt op iedere regel twee getallen hebben: de x- en y-coordinaat van het punt dat geplot gaat worden.
Op internet staat alles en meer over gnuplot, bijvoorbeeld hier of [wie heeft deze geweldige site weggehaald?] daar (Wayback machine).

Deadline: dinsdag 23 februari 2017, 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.

21 november 2016 — http://www.liacs.leidenuniv.nl/~kosterswa/AI/clobber2017.html