Prakticum KI deel 2

In deel 3 gaan we een eenvoudig spelletje implementeren met behulp van het minimax-algorithme.

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 een programma dat de rol van een van de spelers van Kalah overneemt. Gebruik hiervoor het minimax-algorithme. Gebruik als statische evaluatiefunctie het aantal steentjes uit de eigen Kalah minus dat uit de vijandelijke Kalah. Zorg dat je kunt instellen hoeveel beurten er vooruit wordt gedacht.

Inleveren:

De programmalisting met een kort verslagje kan je inleveren per email: zo dus.