Kunstmatige intelligentie
Programmeeropgave 1 van 2021 — Tetris

Tetris De eerste programmeeropgave (in het voorjaar van 2021) behorende bij het vak Kunstmatige intelligentie gaat over het eenpersoons spel Tetris. Het is de bedoeling een eenvoudig programma te schrijven dat dit spel speelt. Er mag hierbij maximaal één zet vooruit gekeken worden. (Dus: wat gebeurt er als het huidige stuk op verschillende manieren valt?) Het is niet de bedoeling een (zelf)lerend programma te maken. Wat wel de bedoeling is: enerzijds zien hoeveel moeite het kost met menselijke regels beter te gaan spelen, anderzijds verbaasd erover zijn dat een programma, dat niets begrijpt, het toch heel goed kan.
Voor meer informatie over Tetris: hier, daar (in PDF) en Tetris (wiki).

Bekijk ook de bijbehorende video (1/3), video (2/3) en video (3/3).

We gebruiken de programmeertaal C++, zoals behandeld bij het college Programmeermethoden. Daar staan ook video's, bijvoorbeeld over het installeren van een C++-compiler (Code::Blocks). Bij de eerste opgave hoef je niet zo heel veel van C++ te weten, vraag eventueel hulp.

Gebruik het C++-voorbeeldprogramma van de website, dat een random spelletje Tetris speelt. Het programma genereert random Tetris-stukken, die naar beneden vallen in een put. Geheel gevulde regels verdwijnen. Je algoritme moet het zolang mogelijk hier tegen volhouden — als er namelijk (gedeeltes van) stukken boven de rand van de "put" uitsteken stopt het proces. Het enige wat het programma moet doen is het kiezen van 1. de oriëntatie van het huidige stuk en 2. de kolommen waarin het stuk valt (positie). Er mag — in tegenstelling tot bij het "echte" spel — daarna niet meer geroteerd of geschoven worden. Informatie over het volgende stuk mag niet gebruikt worden. Er mag hooguit één zet vooruit gekeken worden, dat wil zeggen: je mag kijken wat er gebeurt als je het huidige stuk op alle mogelijke manieren zou laten vallen.

Gebruik nu een drietal AI-componenten:

Laat deze drie spelers spelen, en rapporteer de bevindingen. Kortom: maak diverse simulaties. Varieer onder meer de grootte van het bord, bijvoorbeeld tussen 5 en 20, en toon de resultaten in een grafiek. Er mag vrijelijk —met bronvermelding— gebruik gemaakt worden van de voorbeeld-code. Voeg zeker niet meer dan 200 regels toe!
Er wordt niet gevraagd om een programma dat aan alle software engineering standaards voldoet. Houd het programma dus eenvoudig — maar wel netjes!

Gebruik bijvoorbeeld gnuplot om voor het verslag enkele grafieken te plotten. Een ander plot-programma mag ook.
Je kunt gnuplot onder Windows eenvoudig installeren van hier (download versie 5.2.8, bijvoorbeeld). Binnen gnuplot moet je misschien het "loadpath" goed zetten, met zoiets als gunplot> set loadpath "C:\\JeMap\\" om de files die je wilt plotten te kunnen vinden.
In Ubuntu is het ook eenvoudig te installeren. Op internet staat alles en meer over gnuplot, bijvoorbeeld daar (Wayback machine).
Zie het laatste gedeelte (ongeveer van minuut 8 tot 12) van deze video voor wat meer uitleg.

De resultaten van je experimenten moet je onder andere weergeven in een grafiek. 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". En dan het resulterende PDF-plaatje in je LaTeX-file binnenhalen.
Als je een file met resultaten hebt (zeg iets.uit; twee getallen per regel):
     1 24
     2 31
     3 56
     4 7

kun je deze eenvoudig met gnuplot in een grafiek printen met plot "iets.uit" with lines.

Deadline: dinsdag 23 februari 2021, 17:00 uur.
Stuur als tweetal een e-mail naar aicollege@liacs.leidenuniv.nl , met als twee attachments het (met LaTeX gemaakte) verslag in PDF-formaat en de C++-code van het programma. Het verslag moet aan verschillende eisen voldoen. Geef in de appendix van het verslag alleen de wijzigingen / aanvullingen op de bestaande voorbeeld-code. Probeer 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: aicollege@liacs.leidenuniv.nl.

10 december 2020 — http://www.liacs.leidenuniv.nl/~kosterswa/AI/teet2021.html