 |
||||
|
Programmeermethoden 2016
Vierde programmeeropgave: Gomoku
De vierde programmeeropgave van het vak
Programmeermethoden
in het najaar van 2016
heet Gomoku;
zie ook het
elfde werkcollege,
en lees geregeld deze pagina op WWW.
Spreekuur in zalen 302 ... 309:
dinsdag 15, donderdag 17,
dinsdag 22, donderdag 24,
dinsdag 29 november, donderdag 1,
dinsdag 6, donderdag 8 en vrijdag 9 december 2016, van circa
15:30 tot 17:00 uur. (Vrijdag zelfs vanaf circa 11;15 uur.)
Voor I&E-studenten (Den Haag)
is er een vragenuur in zaal Paleistuin op donderdag 8 december 2016, vanaf circa 14:45 uur.
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 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; niet-gebruik van onderstaand viertal heeft geen invloed op het cijfer. De files zijn (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 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 (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 spelerzetten 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 (nog) 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 9 december 2016, 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 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" in de postkamer
van Informatica, kamer 156 van het Snellius-gebouw.
I&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.
