Programmeermethoden 2019
Vierde programmeeropgave: Gomoku

De vierde programmeeropgave van het vak Programmeermethoden in het najaar van 2019 heet Gomoku; zie ook het elfde werkcollege, en lees geregeld deze pagina op WWW.

Spreekuur in zalen 302 ... 309: Aansluitend op de werkcolleges van maandag en donderdag, in de computerzalen.

De opgave

van wikipedia Voor deze programmeeropgave gaan we het spel Gomoku programmeren, dat verdacht veel lijkt op het bekende Vier-op-een-rij. Het is de bedoeling een klasse gobord te maken, die onder meer memberfuncties heeft als drukaf, menszet en randomzet. Uiteraard heeft deze klasse ook een constructor en een destructor. Verder moeten gedane menselijke zetten met behulp van een stapel ongedaan gemaakt kunnen worden, kan het aantal vervolgpartijen worden uitgerekend, en kunnen wat statistieken worden gegenereerd.

De mogelijkheid bestaat om gebruik te maken van een aantal voorbeeldfiles, van waaruit de opgave stap voor stap kan worden gedaan. Je kunt ook je eigen files met andere functies maken, maar gesplitst moet er worden; niet-gebruik van onderstaand viertal heeft geen invloed op het cijfer. De files zijn allereerst (zie verderop voor gebruik met Code::Blocks, op eigen risico):

Het wellicht meer bekende spel Vier-op-een-rij gaat als volgt. Op een 6 bij 7 bord wordt gespeeld met witte en zwarte schijfjes. Om de beurt leggen de spelers —wit W en zwart Z geheten— een schijfje met hun eigen kleur op een nog leeg vakje, en wel op het onderste lege veld uit een kolom naar keuze. Als een kolom vol is, kan hierin niet meer een schijfje gelegd worden. Zwart mag altijd beginnen. Het spel is afgelopen als het bord vol is, of als één der spelers gewonnen heeft. Een speler wint als er minstens vier stenen van zijn kleur direct horizontaal naast elkaar staan, of verticaal, of diagonaal. Bij Gomoku mag de speler die aan de beurt is zijn/haar schijf steeds op een willekeurige lege plaats neerleggen, dus niet noodzakelijk onderin een kolom. En vijf (of meer) naast elkaar, in plaats van vier, is winnend.

We spelen het spel als volgt. Allereerst mag gekozen worden of de eerste speler een mens of computer is, en idem voor de tweede speler. De "computer" zet volledig willekeurig (gebruik random ( ) uit <cstdlib>; denk aan srand ( )). (Liefhebbers mogen hier natuurlijk hun eigen creativiteit inzetten, door bijvoorbeeld in de buurt van eerdere stenen te zetten, of door (dreigen) te winnen als dat kan.) Daarna mag de grootte van het bord gekozen worden: het aantal rijen m en het aantal kolommen n, en met hoeveel h op een rij er gewonnen wordt. Boter-kaas-en-eieren heeft m = n = h = 3. En tot slot moet er gekozen worden hoeveel spelletjes er gespeeld worden als de computer tegen zichzelf speelt. In dat geval moet er een eenvoudige statistiek worden afgedrukt, bijvoorbeeld hoevaak de beide spelers gewonnnen hebben of remise behaalden, en hoeveel spelletjes er 0,1,2,... zetten duurden.
Als een speler aan zet is, en er precies één spelletje gespeeld moet worden, wordt de stand, oftewel de bordpositie, —in eenvoudig formaat— op het scherm getoond, en kan de menselijke speler zijn/haar zet doen, of juist de laatste eigen zet (en meteen de tussenliggende zet van de tegenstander) terugnemen, of het aantal mogelijke vervolgpartijen voor de huidige stand laten uitrekenen. Als er een reeds bezette plek wordt geselecteerd, moet de speler natuurlijk opnieuw kiezen. Computerzetten worden steeds direct gedaan. En er is uiteraard een functie die bepaalt of het spel is afgelopen, en of er dan iemand (wie?) gewonnen heeft. Het aantal gedane zetten wordt ook steeds getoond. Houd dit, na ieder spel, in een array bij, zodat na afloop eenvoudig kan worden geprint hoeveel spelletjes z zetten duurden (z = 0, 1, ..., m*n), zie onder.

Schrijf een constructor voor de klasse gobord die een pointerstructuur aanlegt, waarbij ieder vakje, naast bijvoorbeeld een char als inhoud, tevens een array met 8 pointers naar de onmiddellijke buren heeft: middenboven (0), rechtsboven (1), rechts (2), rechtsonder (3), middenonder (4), linksonder (5), links (6) en linksboven (7). De vakjes aan de randen bevatten uiteraard diverse NULL-pointers. Het bord is dus niet een m bij n array, maar een zeer ingewikkelde pointerstructuur.

Alle zetten moeten op een stapel worden bijgehouden, en menselijke zetten kunnen daarmee teruggenomen worden. Zodra een speler zet, wordt de zet, bestaande uit een tweetal gehele getallen, opgeslagen. Dit onderdeel is zeker niet eenvoudig; mocht het ontbreken, dan kost dat een punt.
Verder dient er een recursieve memberfunctie vervolg geschreven te worden die gegeven een zekere stand (bordpositie) het totale aantal mogelijke vervolgpartijen, dat overigens erg groot kan zijn, uitrekent. Hiervoor moeten alle mogelijke zetten van beide spelers doorgerekend worden. Ook dit onderdeel is zeker niet eenvoudig; mocht het ontbreken, dan kost dat een halve punt. Tip: controleer het antwoord door het te vergelijken met Boter-kaas-en-eieren, vanuit de beginpositie: 255168. Als je hier 5-op-een-rij speelt, is het antwoord 9! = 362880. Algemeen: als er nog v plekken over zijn, zijn er maximaal v! vervolgpartijen.

Het is de bedoeling om een vijftal files te produceren: de eerste bevat main en het menutje, de tweede (zeg gobord.h, zie boven) bevat de klasse-definitie voor gobord, en de derde (zeg gobord.cc, zie boven) bevat de functies uit die klasse. Evenzo zijn er files stapel.h en stapel.cc. Maak ook een makefile.
Code::Blocks-gebruikers: doe deze opgave liever op een Linux-machine. Maar het kan wel: open een nieuw project via "File -- New project -- Empty project", vul wat in, en voeg de drie files toe via "Project -- Add files", en daarna het project compileren op de gebruikelijke manier. Of, op eigen risco, lees over projecten.

Opmerkingen
Gebruik geschikte (member)functies. Bij deze opgave mogen wederom bij elke functie (zelfs main) tussen begin-{ en eind-} hooguit circa 30 niet al te volle regels staan! Elke functie dient van commentaar voorzien te zijn. Let op goed parametergebruik: alle parameters, met uitzondering van membervariabelen, in de heading doorgeven, en de variabele-declaraties zowel bij main als bij de andere functies aan het begin. De enige te gebruiken headerfile is in principe iostream. Zeer ruwe indicatie voor de lengte van de gezamenlijke C++-files: 500 tot 600 regels. Denk aan het infoblokje.

Uiterste inleverdatum: maandag 9 december 2019, 17:00 uur.
Manier van inleveren:

  1. Digitaal de C++-code inleveren: stuur een email naar pm@liacs.leidenuniv.nl.
    Stuur geen executable's, lever alleen de vijf (of drie) C++-files en de makefile digitaal in! Noem de file gobord.cc hier bij voorkeur zoiets als garfunkelsimongobord4.cc, dit voor de opdracht van het duo Simon-Garfunkel, en analoog de andere files. De laatst voor de deadline ingeleverde versie wordt nagekeken.
  2. En ook een papieren versie van het verslag (inclusief de C++-code van alle files, en de makefile) deponeren in de speciaal daarvoor bestemde doos "Programmeermethoden" bij kamer 159 van het Snellius-gebouw.
    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 verslag (uiteraard weer in LaTeX, zie de eerdere opgaven) moet het volgende bevatten: een zeer korte beschrijving van het programma, een beschrijving van punten waarop het programma faalt (indien van toepassing), en een tabel met gewerkte uren, uitgesplitst per week en per persoon. En een referentie betreffende Gomoku. En een grafiek (zie het bijbehorende werkcollege voor tips) waarin staat hoe lang het duurt voor de random speler, spelend tegen zichzelf, wint — op borden van verschillende grootte.
Te gebruiken compiler: als hij maar C++ vertaalt; het programma moet in principe zowel op een Linux-machine (met g++) als onder Visual C++ of Code::Blocks draaien. Test dus in principe op beide systemen! Het programma wordt doorgaans nagekeken met behulp van de compiler die (uiteraard) in het commentaar bovenin het programma vermeld staat. Normering: layout 1; experiment 1; verslag 1; commentaar 1; modulariteit (OOP, functies) 2; werking 4. Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde: www.liacs.leidenuniv.nl/~kosterswa/pm/op4pm.php.