Kunstmatige intelligentie
Programmeeropgave 1 van 2016 — Schaken
De eerste programmeeropgave (in het voorjaar van 2016) 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 (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.
Een idee is bijvoorbeeld het volgende.
Loop alle mogelijkheden 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 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 meteen geslagen?
- 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.
Noem in het verslag ook andere aanpakken, bijvoorbeeld
de eindspel-database, met referenties.
Laat dus de drie spelers spelen, en rapporteer de bevindingen
(gemiddeldes, standaard-deviaties, grafieken).
De zwarte speler speelt in principe altijd random.
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!
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 1 maart 2016;
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.
26 januari 2016 — http://www.liacs.leidenuniv.nl/~kosterswa/AI/schaak2016.html