 |
||||
|
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
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):
- File met main: hoofd.cc.
- Headerfile met klassen: gobord.h.
- Bijbehorende C++-file: gobord.cc.
- En de bijpassende makefile (let op de TABs).
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:
- 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. - 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.
