Programmeermethoden 1999
Vierde programmeeropgave - Go-bang

De vierde programmeeropgave van het vak Programmeermethoden in het najaar van 1999 heet Go-bang; zie ook de WWW-bladzijde van het tiende werkcollege (met hints!), en lees geregeld deze pagina op WWW.

Voor deze programmeeropgave gaan we het spel Go-bang 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 afdrukken, spelerzet en computerzet. Uiteraard heeft deze klasse ook een constructor en een destructor. Verder moeten gedane zetten met behulp van een stapel ongedaan gemaakt kunnen worden.

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. Wit 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 Go-bang mag de speler die aan de beurt is zijn/haar schijf steeds op een willekeurige plaats neerleggen, dus niet noodzakelijk onderin een kolom.

We spelen het spel als volgt. Allereerst mag de speler zijn/haar kleur kiezen; de computer speelt dan voor de andere kleur. Daarna kiest de speler de strategie van de computer. De computer kan naar keuze van de speler namelijk op één van twee nivo's spelen:

  1. Zet volledig willekeurig - gebruik een eigen randomgenerator.
  2. Eerst een meteen winnende zet doen (als die er is), anders die zet kiezen die voorkomt dat de tegenstander de volgende beurt wint - als dat kan, en anders willekeurig zetten. Het kost één punt als deze strategie ontbreekt.
Liefhebbers mogen hier natuurlijk hun eigen creativiteit inzetten. Tot slot mag ook de grootte van het bord gekozen worden: het aantal rijen m en het aantal kolommen n. Normaal geldt dus dat m=6 en n=7.
Als de speler aan zet is, wordt de stand -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.

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: linksboven, middenboven, rechtsboven, rechts, rechtsonder, middenonder, linksonder en links. 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 tussenstanden moeten op een stapel worden bijgehouden, en spelerzetten kunnen daarmee zelfs herhaald teruggenomen worden. Hiertoe moeten dus alle standen (en niet de zetten) worden onthouden, of liever gezegd: zodra de speler zet, wordt de oude stand opgeslagen. Er moet dus een memberfunctie kopieer gemaakt worden, die de gehele pointerstructuur kopieert!
Verder dient er een recursieve memberfunctie vervolg geschreven te worden die gegeven een zekere stand 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 halve punt.

Enkele algemene opmerkingen:

Uiterste inleverdatum: voor voltijdstudenten: vrijdag 10 december 1999, 17.00 uur; voor deeltijdstudenten: vrijdag 17 december 1999. In te leveren: schijfje met de C++-files en de makefile (of het programma en de makefile per email aan de nakijker (dagstudenten: hoen@liacs.nl; avondstudenten: kosters@liacs.nl) sturen) en listing op papier; beide in de bak in de metalen boekenkast achterin de gang bij de Indyzaal. Overal duidelijk de datum en de namen van de makers vermelden. Te gebruiken compiler: als het maar C++ is.
Normering: layout 1; commentaar 2; modulariteit en OOP 3; werking 4.

Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.

9 november 1999 - http://www.liacs.nl/home/kosters/pm/op4pm99.html