Programmeermethoden 2005
Vierde programmeeropgave — Het Kat en Muis

We bekijken het spel Kat en Muis, dat normaliter gespeeld wordt op een 8 bij 8 schaakbord, met linksboven een zwart veld en dus rechtsonder ook. Vier katten nemen het op tegen één muis. Bij aanvang van het spel staan de vier katten (hier de witte stenen) op de zwarte vakjes op de bovenste rij. Op de onderste rij staat de muis (een zwarte steen) op het zwarte vak ongeveer in het midden. Zie onderstaand plaatje.

Wij zullen het spel wat algemener spelen, namelijk op een m bij n bord (met m en n even en minstens 2), met de muis en de n/2 katten in de beginsituatie in de onderste, respectievelijk bovenste rij geplaatst zoals in de versie op het 8 bij 8 bord.
De spelregels zijn eenvoudig. Er zijn twee spelers, in dit geval de gebruiker en de computer. De gebruiker speelt met de muis (zwart) en de computer met de katten (wit). Ze doen om de beurt een zet waarbij ze een steen van de eigen kleur verschuiven. Stenen mogen alleen diagonaal, met stapgrootte 1, verplaatst worden. Wit mag alleen vooruit zetten (naar beneden dus) en zwart mag zowel vooruit (naar boven) als achteruit (naar beneden). Het spel is afgelopen zodra (1) zwart de overkant bereikt (zij heeft dan gewonnen) of (2) zodra een van de twee spelers niet meer kan zetten (deze heeft dan verloren). Zwart (de gebruiker) mag altijd beginnen.
Het spel moet een aantal keren achter elkaar gespeeld kunnen worden. Bij het begin van elk spel geeft de gebruiker de grootte van het bord op (m bij n, met m hoogstens const int maxrij en n hoogstens const int maxkolom).
Als de gebruiker aan zet is, kan deze een toegestane zet doen, of juist de laatste eigen zet (en meteen de tussenliggende computerzet) terugnemen. Voor dit laatste gebruiken we een stapel (stack). Een toegestane zet betekent uiteraard dat diagonaal geschoven wordt naar een leeg buurvakje.
De computer doet gedurende een spel ofwel steeds random zetten (optie 1), ofwel steeds zetten volgens een of andere strategie (optie 2). De gebruiker moet voor het spel begint opgeven op welk van de twee manieren de computer speelt.
In eerste instantie (Stap 1 tot en met 4) wordt de stand steeds in een eenvoudig formaat op het scherm getoond, later (Stap 5) wordt Visual C++ gebruikt om een en ander te verfraaien.

Enkele aanwijzingen

1. Schrijf eerst een programma dat de gebruiker en de computer om de beurt een zet laat doen, waarbij de computer telkens random zet. Er moet altijd gecontroleerd worden of een door de gebruiker ingevoerde zet een toegestane zet is. Zo niet, dan moet de speler een nieuwe zet invoeren. Het programma moet na elke zet van zwart controleren of deze heeft gewonnen (de overkant heeft bereikt). Zo ja, dan stopt het spel met de mededeling dat de gebruiker heeft gewonnen. Verder moet natuurlijk worden gecontroleerd of de speler die aan de beurt is nog wel een zet kan doen. Zo niet dan is het spel ook afgelopen en wordt afgedrukt wie er heeft gewonnen.
   De random zet van de computer wordt als volgt bepaald. Eerst wordt berekend hoeveel toegestane zetten er mogelijk zijn, zeg toegestaan, en vervolgens wordt random bepaald welke van die toegestaan zetten de computer doet. Hier kun je bijvoorbeeld de randomgenerator uit het dictaat voor gebruiken.
   Schrijf een klasse bord waarin een spelsituatie is opgeslagen. Dit kan bijvoorbeeld middels een (groot genoeg) tweedimensionaal array. Bovendien moeten objecten van de klasse bord de speler die aan de beurt is bevatten, alsmede de actuele grootte van het bord. De klasse bord bevat verder methoden/memberfuncties (eventuele parameters en returnwaarden moet je zelf invullen) zoals:
   • bord(...): de constructor (initialiseert de membervariabelen).
   • beginstand(...): voert de door de gebruiker in te voeren grootte van het bord in en zet de stenen op de juiste beginposities.
   • toegestanezet(...): controleert of een gegeven zet is toegestaan.
   • drukaf(...): drukt de huidige stand af op het scherm.
   • randomzet(...): berekent een random zet voor de computer.
   • strategiezetzet(...): bepaalt een zet voor de computer op grond van een of andere strategie (zie Stap 4).
   • doezet(...): voert een gegeven toegestane zet uit.
2. Breid het door jou geschreven programma zodanig uit dat de gebruiker, wanneer hij aan de beurt is, ook ervoor kan kiezen zijn laatst gedane zet (en meteen de tussenliggende computerzet) terug te nemen. Na het terugzetten is de gebruiker opnieuw aan de beurt. Er kunnen zo dus ook meerdere zetten van de speler achter elkaar teruggenomen worden. Om zetten terug te kunnen nemen moeten tussenstanden op een stapel (stack) worden bijgehouden. Dat betekent dus dat alle voorgaande standen waarin de gebruiker aan de beurt is moeten worden onthouden. Zodra de speler zet, wordt daartoe steeds de oude stand boven op de stapel gezet. Schrijf hiervoor een geschikte klasse stapel, met in elk geval memberfuncties zetopstapel(...), haalvanstapel(...) en isstapelleeg(...).
3. Splits het programma op in een bestand waarin main() staat, een bestand waarin de implementatie van klasse bord staat, en een header file met daarin de definitie van deze klasse (zonder implementatie). Hetzelfde voor de klasse stapel. De bedoeling is dat het programma in eerste instantie (zonder grafisch interfase) ook onder Unix werkt. Schrijf daartoe een Makefile voor deze files zodanig dat de .cc bestanden apart worden gecompileerd en uiteindelijk worden samengevoegd ("gelinkt") tot een executeerbaar programma.
4. Breid het programma nu zodanig uit dat de computer behalve random zetten (optie 1) ook betere zetten, volgens een of andere strategie (optie 2), kan doen. Wit doet dan, afhankelijk van de stand, een zet volgens een of meer vuistregels, dus zonder zetten vooruit te kijken. Je kunt hierbij bijvoorbeeld denken aan een combinatie van: (1) houd de katten (witte stenen) zoveel mogelijk op hooguit twee verschillende aangrenzende rijen, (2) probeer elke kat zo dicht mogelijk bij zijn oorspronkelijke kolom te houden en (3) doe de zet die het verst van de muis verwijderd is. Probeer zelf een zo goed mogelijke strategie voor wit te bedenken. Het bedenken en implementeren van een goede strategie levert maximaal 2 punten op (zie de normering): hoe beter de strategie (en implementatie), hoe meer punten je ervoor krijgt. Geef in het commentaar boven de betreffende functie duidelijk aan wat de strategie doet.
   Het handigst is het om een aparte functie (geen memberfunctie) te schrijven waarin het spel daadwerkelijk gespeeld wordt. Deze functie kan dan weer memberfuncties van bord en stapel voor bijvoorbeeld het bepalen van een goede computerzet en het (ont)stapelen bij (terug)zetten door de gebruiker. Deze functie wordt dan in \verb+main+ aangeroepen zolang de gebruiker het spel wil spelen. Bij het begin van elk spel kan de gebruiker kiezen of de computer random speelt (optie 1) of volgens een strategie (optie 2).
5. Schrijf een grafische interface voor het spel Kat en Muis met behulp van Visual C++. Een speler moet het spel tegen de computer kunnen spelen. De computer controleert wanneer gewonnen is en door wie, etc. Het spel wordt nu standaard gespeeld op een 8 bij 8 bord. Om het spel weer te geven gebruiken we een 8 bij 8 rooster met witte en zwarte vakjes als een schaakbord. Het spel begint met de standaard startopstelling. De gebruiker kan een zet doen door bijvoorbeeld op het vakje met de muis te klikken en vervolgens op een ander vakje. Niet-toegestane zetten worden niet geaccepteerd: de speler moet dan opnieuw een zet aangeven. Na de zet van de gebruiker doet meteen de computer (de katten) een zet. Deze zet kan random zijn of volgens een strategie. Zorg daartoe voor een button waarmee je aangeeft of de computer random of volgens de strategie speelt. Tijdens het spel kan de gebruiker door op deze knop te klikken de speelwijze veranderen. Geef in de button aan wat de huidige speelwijze is. Deze knop kan dus op en neer toggelen tussen de twee verschillende speelwijzen. Verder moet er een knop zijn waarmee de gebruiker een zet terugneemt. Zorg tevens voor een startknop: als de gebruiker hierop klikt begint een nieuw spel en wordt de beginopstelling dus weer op het scherm gezet. Het spel kan zo herhaald gespeeld worden. Maak ook een tekstvakje waarin gemeld wordt wie er gewonnen heeft na afloop van een spel.

Uiterste inleverdatum: vrijdag 2 december 2005, 17.00 uur (Stap 1 tot en met 4) en vrijdag 9 december 2005, 17.00 uur: het geheel.
Manier van inleveren:

• Op vrijdag 2 december moeten Stap 1 tot en met 4 klaar zijn en dient het bijbehorende werkende programma te worden ingeleverd. De rest volgt een week later.
• Email aan de hoofdnakijker pm@liacs.nl sturen. Zorg er voor dat je {\em alleen} de programma-code inlevert en niet de executables. Je kunt ofwel alle bestanden apart "attachen", of er (onder UNIX) een enkel tar-bestand van maken (waarschijnlijk makkelijker). Met tar kun je vanaf een UNIX systeem meerdere bestanden in één file stoppen. Als bijvoorbeeld je bestanden staan in directory ./opdracht4/, dan kun je deze directory, alle bestanden in deze directory, en alle subdirectories en hun bestanden in deze directory in één tar-bestand (bijvoorbeeld genaamd opdracht4.tar) stoppen door middel van het volgende commando: tar cvf opdracht4.tar opdracht4/. Nogmaals: zorg ervoor dat deze directories alleen programma-code bestanden bevatten. Stuur dit tar-bestand als attachment naar pm@liacs.nl.
• En ook een listing (in totaal twee versies!) op papier deponeren in de daarvoor bestemde doos "Programmeermethoden" in de postkamer, kamer 156. Overal duidelijk datum en namen van de makers vermelden, in het bijzonder in de eerste regels van de C++-code.

Te gebruiken compiler: C++, maar het programma zonder grafisch interface moet ook op een Linux-machine (met g++) draaien. Voor het grafische programma gebruik je bij voorkeur Visual C++.
Normering: layout 1; commentaar 1,5; modulariteit 1,5; werking niet-grafisch 4; werking grafisch 2.
Eventuele aanvullingen en verbeteringen: lees deze WWW-bladzijde.

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

7 november 2005 — http://www.liacs.nl/home/kosters/pm/op4pm05.html