Kunstmatige intelligentie
Programmeeropgave 1 van 2019 — Schaken

De eerste programmeeropgave (in het voorjaar van 2019) behorende bij het vak Kunstmatige intelligentie gaat over het spel schaken. Het is de bedoeling een eenvoudig programma te schrijven dat een klein gedeelte van dit spel zo goed mogelijk speelt. We bekijken alleen de situatie waarbij een witte dame of toren (WQ) en witte koning (WK) proberen een eenzame zwarte koning (BK) mat te zetten. Een eindspel dus.

Gebruik het C++-voorbeeldprogramma van de website.

Maak nu een drietal AI-spelers voor wit:

EEN: speelt volledig random, zie voorbeeld-code.
TWEE: bedenk zelf een (eenvoudige) strategie. Vul daartoe voorbeeld-code aan met een geschikte functie. Je mag maar één zet vooruit kijken!
Een idee is bijvoorbeeld het volgende. Loop alle mogelijkheden van een positie af, speel per mogelijkheid in een kopie van het bord de betreffende zet (via Board kopie = *this;), beoordeel de zet, en selecteer tot slot de "beste" zet. Denk dus niet verder vooruit.
Wat is de grootte van de rechthoek waarin de zwarte koning kan bewegen? Hoeveel mogelijke zetten heeft de zwarte koning? Staat de zwarte koning aan de rand? Hoe dicht staan de witte stukken bij elkaar? Hoe dicht staan de witte en zwarte stukken bij elkaar? Wordt de dame/toren als dat kan meteen geslagen door de zwarte speler? (In de functie randomblackmove staat hiervoor een optie. (*))
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 hints bovenaan voorbeeld-code.

Probeer dit zo simpel mogelijk te programmeren. Er zijn eenvoudige systemen om de zwarte koning mat te zetten, maar de bedoeling van deze opgave is om zelf heuristieken te verzinnen en daarover een verslag te schrijven. Is er verschil tussen dame en toren? Noem in het verslag ook andere aanpakken, bijvoorbeeld met een eindspel-database of met "deep learning", met referenties.
Laat dus de drie spelers spelen, en rapporteer de bevindingen (gemiddeldes, standaard-deviaties, grafieken). De zwarte speler speelt in principe altijd random of met (*). Kortom: maak diverse simulaties; varieer onder meer de grootte van het bord. Er mag vrijelijk —met bronvermelding— gebruik gemaakt worden van de voorbeeld-code.
Er wordt niet gevraagd om een programma dat aan alle software engineering standaards voldoet. Houd het programma dus eenvoudig — maar wel netjes!

Gebruik gnuplot om voor het verslag enkele grafieken te plotten.
Tips: 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"
     plot "mijnfile.txt" using 1:2 with lines notitle
en roep deze binnen gnuplot aan met load "plot.gpi". Gebruik de export-mogelijkheden om pdf-uitvoer te genereren.
Als je een file met resultaten hebt (zeg iets.uit; twee getallen per regel: de x- en y-coordinaten van een punt):
     1 24      2 31      3 56      4 7
kun je deze eenvoudig met gnuplot in een grafiek printen met plot "iets.uit" with lines.
Op internet staat alles en meer over gnuplot, bijvoorbeeld hier of daar.

Deadline: donderdag 28 februari 2019, 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. Probeer in het verslag ook kort een relatie te leggen met de theorie zoals die behandeld is tijdens de colleges.

Er is een klein skelet voor de verslagen: verslag.tex, dat deze PDF-versie op kan leveren. Zie ook diverse opmerkingen.

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

22 januari 2019 — http://www.liacs.leidenuniv.nl/~kosterswa/AI/schaak2019.html

Kunstmatige intelligentieProgrammeeropgave 1 van 2019 — Schaken

Kunstmatige intelligentie
Programmeeropgave 1 van 2019 — Schaken