Alternatieve Opdracht

We gaan een eenvoudig spelletje implementeren met behulp van het minimax-algoritme. Deze opdracht mag je maken in plaats van opdrachten 4 en 5, maar vergt wel programmeerervaring. Ook kan deze opdracht, vanwege zijn grootte, niet door de compensatieopdracht worden vervangen. Denk dus goed na voor je hieraan begint (zijn er nog lezers?).
De interface van het onderstaande spel hoeft niet denderend te zijn, maar wel overzichtelijk. Het gaat ons uiteraard voornamelijk om de code en de functionaliteit. De keuze voor de taal is redelijk vrij; C++, java, pascal.... Laat ons gelijk weten wat je van plan bent, dan kunnen wij je vertellen of we het ook kunnen nakijken.

Kalah: de spelregels

Kalah is een afrikaans bordspelletje, waarin gebruik gemaakt wordt van een "bord", dat bestaat uit 14 kuiltjes: 12 kleine kuiltjes, en 2 grote kuilen, de "Kalahs". In elk van deze kuiltjes kan een aantal steentjes liggen. Bij het begin van het spel zijn beide Kalah's leeg, en ligt in elk klein kuiltje een zelfde aantal. Dit aantal kan varieren van 3 tot 8, hoe meer steentjes, des te langer het spel duurt en gecompliceerder het is.

Beginsituatie met drie steentjes

Zoals te zien is, zijn de kuiltjes in een soort rechthoek geplaatst. Elke speler heeft zes kleine kuiltjes en een Kalah. Doel van het spel is om zoveel mogelijk steentjes in je eigen kalah te krijgen. Het spel is dan ook afgelopen als een van beide spelers meer dan de helft van het totale aantal steentjes in zijn Kalah heeft.

Het doen van zetten

Spelers doen om de beurt een zet. Een zet bestaat uit het z.g. zaaien. Dit doe je door een van je eigen kleine kuiltjes leeg te halen, en deze over de andere kuiltjes uit te zaaien. Het zaaien begint bij het kuiltje direct rechts van de beginkuil, en gaat verder tegen de klok in. Dit is inclusief je eigen kleine kuiltjes, je eigen kalah en de kleine kuiltjes van de tegenstander, maar exclusief de Kalah van je tegenstander. Een voorbeeld:

In deze situatie kiest speler 1 kuiltje zes om te zaaien. Hij begint met 1 in zijn eigen kalah te gooien, vervolgens 1 in elk van de tegenstanders kleine kuiltjes, en tenslotte in de kleine kuiltjes van hemzelf, eindigend in zijn eigen kalah. De bordsituatie is vervolgens:

Merk op dat er in de Kalah's alleen maar steentjes bijkomen, aangezien je niet vanuit de kalah kunt zaaien.

Speciale zetten

Bij het zaaien kan er sprake zijn van twee speciale gevallen. Deze hebben beide betrekking op het laatste steentje dat je zaait.

Het eerste speciale geval is als het laatste steentje in een van je eigen kleine kuiltjes terecht komt, nadat je ook eerst in je tegenstanders kuiltjes hebt gezaaid. Indien het kuiltje waar je uitkomt niet leeg is, pak je de inhoud van dit kuiltje en zaai je hiermee verder (inclusief het ene steentje van de vorige "zaaiing").

Een voorbeeld:

Als je hier kuiltje 6 speelt, dan kom je uit in kuiltje 3 aan je eigen kant, en zaai je hiermee verder. Het resultaat is:

Het tweede speciale geval is, als het laatste steentje in een klein kuiltje van je tegenstander terecht komt. Indien met dit steentje het totaal aantal steentjes in dat kuiltje op 2 of 3 komt, mag je de inhoud van dat kuiltje in je eigen Kalah gooien. Indien het kuiltje direct ervoor ook 2 of 3 steentjes bevat, mag je die ook in je Kalah gooien enzovoort. Het is dus in theorie mogelijk in een zet al je tegenstanders kleine kuiltjes te legen!

Een voorbeeld van zo'n meervoudige "slag":

Als je hier kuiltje 6 leegt, kom je uit in het vierde kuiltje van je tegenstander, dat daarmee twee steentjes bevat. Deze mag je in je kalah gooien. Het kuiltje ervoor bevat echter 3 steentjes, dus die mag ook in de kalah, evenals die daarvoor met 2 steentjes. Eindresulaat:

Einde van het spel

Het spel is beeindigd indien een van beide spelers meer dan de helft van de steentjes in zijn bezit heeft. Indien een speler niet meer kan zetten omdat al zijn kleine kuiltjes leeg zijn, mag de andere speler wat hij nog in zijn kleine kuiltjes heeft in zijn Kalah gooien, en wint degene met de meeste steentjes.

Opdracht

Schrijf allereerst een programma waarmee twee menselijke spelers het spel kunnen spelen, en lever dit uiterlijk vrijdag 12 maart in. Hierna ga je het programma uitbreiden zodat het spel een rol van een speler kan overnemen. Zorg dus ook dat er twee computerspelers tegen elkaar kunnen spelen. Gebruik hiervoor het minimax-algorithme. Gebruik als statische evaluatiefunctie bijvoorbeeld het aantal steentjes uit de eigen Kalah minus dat uit de vijandelijke Kalah. Zorg ook dat je kunt instellen hoeveel beurten er vooruit wordt gedacht.

Inleveren:

Lever je code in, voorzien van commentaar!! (Onvoldoende commentaar zorgt ervoor dat je een onvoldoende krijgt. duh). Lever ook een gecompileerd programma in, dat scheelt ons weer.