Programmeermethoden 2009
Vierde programmeeropgave
Vier-op-een-rij

Spreekuur in zalen 302 ... 309: maandag 9 tot en met vrijdag 13 november, dinsdag 17 november, dinsdag 24 november, dinsdag 1 december en dinsdag 8 december, van circa 15.30 tot 17.00 uur. En verder op afspraak ...
De werkcolleges van dinsdag 10, dinsdag 17 / donderdag 19 en dinsdag 24 / donderdag 26 november (Qt) zijn speciaal bestemd voor deze opgave. Het werkcollege van donderdag 12 november (en deels dat van dinsdag 10 november) is nog voornamelijk voor de derde programmeeropgave bedoeld.
Let op: het college van dinsdag 24 november (Java en Qt) vindt plaats in het Snellius, zaal 412; de colleges van dinsdagen 1 en 8 december worden als werkcollege / vragenuur in de computerzalen gegeven. Het werkcollege van dinsdag 1 (zalen 403 en 413) en donderdag 3 (zalen 401, 403 en 405) december is voor iedereen, en gaat over oude tentamens.

De bedoeling van de opdracht is om het tweepersoons spel Vier-op-een-rij te programmeren. Deze opdracht kent twee onderdelen:

1. Het spel Vier-op-een-rij programmeren op een m bij n bord (m rijen en n kolommen, beide minstens 1), en een eenvoudige intelligente computertegenstander ontwerpen. Het spel wordt in eerste instantie op een eenvoudige manier afgebeeld.
2. Het spelen van het spel (vaste grootte: 6 hoog en 7 breed) grafisch weergeven met behulp van Qt.

Het spel gaat als volgt. Op een m bij n bord spelen de twee spelers om de beurt een schijfje van hun eigen kleur. Het schijfje wordt in een kolom gespeeld en valt daar naar de laagste nog lege plek. In een volle kolom kan niet meer gespeeld worden. Het spel stopt zodra één van de spelers vier (of meer) van zijn eigen schijfjes direct naast elkaar heeft, en wel horizontaal, verticaal of diagonaal: "vier-op-een-rij"; deze speler wint. Het spel stopt natuurlijk ook als het hele bord vol is. Als geen van beide spelers "vier-op-een-rij" hebben, is de uitslag remise.

Het spel, zoals we het in eerste instantie gaan ontwerpen, moet een aantal keren achter elkaar gespeeld kunnen worden. Bij het begin van elk spel geeft de gebruiker de grootte van het bord op (m bij n, met m hoogstens const int maxrij en n hoogstens const int maxkolom).
Als de gebruiker aan zet is, kan deze een toegestane zet doen, of juist de laatste eigen zet (en meteen de tussenliggende computerzet) terugnemen. De computer doet gedurende een spel ofwel steeds random (toegestane) zetten (optie 1), ofwel steeds zetten volgens een eenvoudige strategie (optie 2). De gebruiker kan tijdens spel steeds opgeven op welk van de twee manieren de computer speelt.
Het is ook mogelijk dat de computer tegen zichzelf speelt. In dat geval kiest de gebruiker voor beide computerspelers een strategie.
Tot slot kan de speler ook telkens het aantal vervolgpartijen opvragen, wat alleen zal werken als dit aantal redelijk beperkt is. Dat is dus overigens niet het aantal vervolgzetten. NB Als deze optie geheel ontbreekt, kost dat 1 punt.

Voor de eenvoudige strategie geldt dat het niet de bedoeling is een boomstructuur met vervolgpartijen op te zetten. Wel moeten alle mogelijk vervolgzetten bekeken worden. Daaruit moet verstandig gekozen worden. Het programma moet in ieder geval winnen als het direct kan winnen, en als dat niet kan zo mogelijk direct verlies voorkomen. Gebruik een eenvoudige evaluatiefunctie om dit tot stand te brengen. De bedoeling is dat de gebruiker ook nog minstens één parameter kan instellen. Zo kan bijvoorbeeld gekeken worden hoeveel nieuwe "drie-op-een-rij"'s ontstaan na een potentiële zet, en of er kansen voor de tegenstander verdwijnen; de parameter kan dan een gewicht zijn voor dit soort maten.

In eerste instantie wordt de stand steeds na elke beurt in een eenvoudig formaat op het scherm getoond. Later wordt Qt gebruikt om een en ander te verfraaien. Een tip is om vroegtijdig met het "niet-grafische programma" rekening te houden bij het ontwerp. Bij de grafische versie moet een speler zijn zetten natuurlijk doorgeven door te klikken met de muis.

Eisen aan de programmatuur

• bord (...): de constructor (initialiseert de membervariabelen).
• beginstand (...): voert de door de gebruiker in te voeren grootte van het bord in.
• drukaf (...): drukt de huidige stand af op het scherm.
• randomzet (...): berekent een random zet. Gebruik de standaardfunctie rand ( ).
• strategiezet (...): bepaalt een zet voor de computer op grond van een of andere eenvoudige strategie; het is absoluut niet de bedoeling om vooruit te rekenen, dus geen boom-algoritmen.
• kieskolom (...): de gebruiker kiest een kolom.
• toegestaan (...): mag een zet?
• doezet (...): voert een gegeven (toegestane) zet uit.
• klaar (...): is het klaar, en wie heeft gewonnen, of is het remise?
• vervolgpartijen (...): rekent recursief het aantal vervolgpartijen uit; dit is overigens de enige plaats in het programma waar recursie gebruikt hoeft te worden.

• zetopstapel (...)
• haalvanstapel (...)
• isstapelleeg (...)

Uiterste inleverdatum:

1. vrijdag 27 november 2009, 17.00 uur: alle niet-grafische files en de UNIX makefile
2. dinsdag 8 december 2009: demonstratie van de interface; maak een afspraak met de docenten

1. Digitaal de C++-code inleveren: stuur een email naar pm@liacs.nl. Doe dit als "tarball": zet alle .cc- en .h-files bij elkaar, en ook de makefile. Geef dan (in Linux) het commando tar cvfz achternamen.tgz *cc *h makefile en stuur achternamen.tgz op.
2. En ook een papieren versie van het voorlopige verslag deponeren in de speciaal daarvoor bestemde witte doos "Programmeermethoden" in de postkamer van Informatica, kamer 156. Overal duidelijk datum en namen van de (maximaal twee) makers vermelden, in het bijzonder als commentaar in de eerste regels van de C++-code.
   Het voorlopige verslag moet alle C++-code en de makefile bevatten. Bij de demo moet het definitieve verslag worden ingeleverd, nu aangevuld met een korte uitleg van het programma; een duidelijke uitleg van de gebruikte strategie; en een tabel met gewerkte uren.

Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
9 november 2009 — http://www.liacs.nl/home/kosters/pm/op4pm09.html