De eerste programmeeropgave (in het voorjaar van 2010) 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, waarbij een Monte Carlo methode wordt gebruikt.
Voor meer informatie over Tetris:
hier,
daar (in PDF)
en
Tetris (wiki).
Gebruik het C++-voorbeeldprogramma van de website. Dit genereert random Tetris-stukken, die naar beneden vallen. Geheel gevulde regels verdwijnen. Je algoritme moet het zolang mogelijk hier tegen volhouden — als er (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. Eventueel mag je informatie over het volgende stuk gebruiken — pas hiertoe het programma zelf aan.
Gebruik nu een drietal AI-componenten:
in een gegeven situatie s doe
voor alle mogelijke zetten i = 1, 2, ...
doe in een kopie van de situatie s zet i, leidende tot toestand s(i)
herhaal k keer
bereken de "waarde" van s(i) door het spel snel uit te spelen
met strategie EEN of TWEE
bepaal gemiddelde
kies beste zet
Dit is de Monte Carlo methode; een achtergrondartikel, voor de liefhebbers, staat hier:
artikel.
Wat is de "beste" zet? Laten we afspreken dat het belangrijkste is het
zo lang mogelijk vol te houden. En dat we dus die zet kiezen waarbij dit
gemiddeld zo goed mogelijk is.
Probeer dit zo simpel mogelijk te programmeren.
Deadline: dinsdag 23 februari 2010.
In te leveren: een geprint exemplaar van het verslag
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: kosters@liacs.nl.
29 januari 2010 — http://www.liacs.nl/home/kosters/AI/teet2010.html