Voor deze programmeeropgave gaan we het Damspel programmeren, zij het ietwat aangepast. Het is de bedoeling een klasse DamBord 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" damspel gaat als volgt.
Op een 10 bij 10 bord, waarvan de vakjes afwisselend
wit en zwart zijn, wordt gespeeld met 20 witte en 20 zwarte
schijven. Deze staan aan het begin op de zwarte velden:
in de beginstand staan de witte schijven op de 4 onderste rijen,
de zwarte schijven op de 4 bovenste.
Op de onderste rij is het meest linkse veld zwart.
Om de beurt doen de spelers - wit W en zwart
Z geheten - een zet; wit begint. Tijdens een zet wordt
één steen van de eigen kleur diagonaal één plaats
opgeschoven, naar een leeg veld, in de richting van de zijde waar aan het
begin de schijven van de tegenstander stonden.
Bij deze opgave mag ook één vakje recht vooruit
geschoven worden;
elke schijf heeft dus 0, 1, 2 of 3 schuif-mogelijkheden.
Er kan ook geslagen worden: er wordt dan over een schijf van de tegenstander
(die wordt weggehaald) naar een leeg veld er
onmiddellijk achter gesprongen,
eventueel zelfs achteruit, recht vooruit of opzij:
dit heet een slagzet.
In principe kan een steen in maximaal 8 richtingen
(vanzelfsprekend minder bij de randen van het bord)
slaan, dus ook horizontaal en verticaal.
Als er keuze is tussen zetten geldt dat als er een slagzet is,
er een slagzet gedaan moet worden; is die er niet, dan een gewone schuifzet.
Het spel is afgelopen als de speler die aan beurt is niet meer
kan zetten, bijvoorbeeld
omdat hij/zij geen schijven meer heeft: de andere speler heeft dan gewonnen.
Bij deze programmeeropgave komen geen "dammen" voor: een schijf die aan
de andere kant van het bord is gekomen blijft daar staan; alleen opzij of
achteruit slaan mag dan nog. Ook "meerslag" komt niet voor.
We spelen het spel als volgt.
Allereerst mag de menselijke speler zijn/haar kleur kiezen;
de computer speelt dan voor de andere kleur.
Vervolgens mag ook de grootte van het bord gekozen worden:
het aantal rijen m en het aantal kolommen n.
Normaal geldt dus dat m = 10 en n = 10.
Het aantal rijen met witte stenen r in de beginstand
mag ook gekozen worden;
normaal zijn dat er r = 4. Er zijn altijd evenveel rijen met zwarte stenen.
Voor m = 6, n = 7 en r = 2 is de
beginstand:
| Z Z Z |
|Z Z Z Z|
| |
| |
| W W W |
|W W W W|
Per rij staan
in het begin op de zwarte vakjes n/2 witte schijven - voor oneven n naar
boven of beneden afgerond al naar gelang het aantal zwarte vakjes in de rij.
Schrijf een constructor die
een pointerstructuur aanlegt,
waarbij ieder vakje, naast bijvoorbeeld een char als inhoud,
tevens een array met 8 pointers naar
de onmiddellijke buren heeft. Dit is misschien niet zo efficiënt,
maar vraagt wel om precisie.
"Alles wat gebeurt" (kortom, het hele bord) wordt
op een stapel bijgehouden, en zetten kunnen
zelfs herhaald teruggenomen worden.
Hiertoe moeten alle standen worden bijgehouden,
of liever gezegd: zodra de speler zet, wordt de oude stand opgeslagen.
Er moet dus ook 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. Dit onderdeel is zeker niet eenvoudig;
mocht het ontbreken, dan kost dat een halve punt.
Tijdens het spelen moeten de computer en de speler om de beurt een zet doen. Als de computer aan zet is, moet deze een (slag)zet bepalen die aan de bovengemelde (voorrangs)regels voldoet. Als er meerdere geldige zetten zijn, mag het programma daaruit een compleet willekeurige keuze maken, of er altijd dezelfde uit kiezen; liefhebbers mogen een strategie bedenken om een slimme(re) zet te doen; dit is echter niet verplicht. De stand voordat de computer zet en de zetkeuze van de computer moeten - in eenvoudig formaat - op het scherm afgebeeld worden.
Als de speler aan zet is, wordt de stand 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 vervolgpartijen voor de huidige stand laten uitrekenen. Als er een niet toegestane zet wordt geprobeerd, moet de speler natuurlijk opnieuw kiezen. De speler mag altijd zelf vrij kiezen uit de mogelijke (slag)zetten, waarbij slaan - zoals eerder beschreven - voorgaat.
Enkele algemene opmerkingen:
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
7 november 2001 - http://www.liacs.nl/home/kosters/pm/op4pm01.html