Programmeermethoden 2013
Vierde programmeeropgave: Gomoku

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

Spreekuur in zalen 302 ... 309: dinsdag 19, woensdag 20, donderdag 21, dinsdag 26, donderdag 28 november, dinsdag 3, woensdag 4, donderdag 5 (?) en vrijdag 6 december 2013, van circa 15:30 tot 17:00 uur.
Extra vragenuur: dinsdagmiddag 26 november 2013, 13:45-17:00 uur (op 26 en 27 november is er geen college).

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 zetten met behulp van een stapel ongedaan gemaakt kunnen worden.

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, en niet-gebruik van onderstaand viertal heeft geen invloed op het cijfer. De files zijn (zie verderop voor gebruik met Code::Blocks):

Het "normale" 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 naast elkaar, in plaats van vier, is winnend.

We spelen het spel als volgt. Allereerst mag de speler zijn/haar kleur kiezen; de ``computer'' speelt dan voor de andere kleur, en zet volledig willekeurig (gebruik random ( ) uit <cstdlib>). 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. Er moet ook een mogelijkheid zijn om het programma tegen zichzelf te laten spelen. Tot slot mag ook de grootte van het bord gekozen worden: het aantal rijen m en het aantal kolommen n. Bij Vier-op-een-rij geldt dus dat m = 6 en n = 7.
Als de speler aan zet is, wordt de stand, oftewel de bordpositie, —in eenvoudig formaat— op het scherm getoond, en kan de speler zijn/haar zet doen, of juist de laatste eigen zet (en meteen de tussenliggende computerzet) terugnemen, of het aantal mogelijke vervolgpartijen voor de huidige stand laten uitrekenen. Als er een reeds bezette plek wordt gekozen, moet de speler natuurlijk opnieuw kiezen. En er is uiteraard een functie die bepaalt of het spel is afgelopen, en of er dan iemand (wie?) gewonnen heeft.

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, rechtsonder, middenonder, linksonder, links 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 spelerzetten kunnen daarmee teruggenomen worden. Zodra een speler zet, wordt de zet, bestaande uit een tweetal gehele getallen, opgeslagen.
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. Dit onderdeel is zeker niet eenvoudig; mocht het ontbreken, dan kost dat een punt.
Tip: controleer het antwoord door het te vergelijken met Boter-kaas-en-eieren (3-op-een-rij op een 3 bij 3 bord), 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) bevat de klasse-definitie voor gobord, en de derde (zeg gobord.cc) bevat de functies uit die klasse. Evenzo zijn er files stapel.h en stapel.cc. Maak ook een makefile.
Code::Blocks-gebruikers: doe dit gedeelte 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 regels. Denk aan het infoblokje.

Uiterste inleverdatum: vrijdag 6 december 2013, 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 C++-files en de makefile digitaal in! Noem de file gobord.cc hier bij voorkeur zoiets als simongarfunkelgobord4.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" in de postkamer van Informatica, kamer 156 van het Snellius-gebouw.
    BinnenhofI&E-studenten (Den Haag) mogen de pdf-versie per email meesturen.
     

    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 Dev-C++ 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; verslag 1; commentaar 1; modulariteit (OOP, functies) 3; werking 4. Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde: www.liacs.nl/home/kosters/pm/op4pm.php.