De grote opdracht: Boter, kaas & eieren
Het spel: Link | Broncode: Link
Dit is de vervangende grote opdracht van periode 2 die ik samen met meneer Meftah uitkoos. Een goede werkende AI maken was iets compleet nieuws voor mij, en ik had ook over deze opdracht weer serieuze twijfels of het wel zou lukken. Ik begon met het opzoeken van informatie over hoe dat nou gaat, een AI maken. Ik kwam al gauw het Minimax algoritme tegen (Wikipedia: Minimax), wat veel gebruikt wordt voor spellen als Boter kaas & eieren, maar bijvoorbeeld ook voor schaken. Ik heb het artikel meerdere keren doorgelezen en snapte de grote lijnen in het algoritme. Of in ieder geval: er begon zich een idee te vormen in mijn hoofd over hoe ik dit aan moest gaan pakken.
Het begin
De eerste stap die ik zette is vaststellen hoe het programma er ongeveer uit moest komen te zien. Hiervoor heb ik een stuk pseudocode geschreven, waarin ik de hoofdlus van het spel beknopt beschrijf en een beetje uitdiep wat er allemaal moet gebeuren. Dit was de pseudocode. Toen ik min of meer meer tevreden was over de pseudocode (ik begreep het Minimax algoritme nog niet door en door, dus ik verwachtte dat er nog een hoop zou veranderen wanneer ik daadwerkelijk zou beginnen met het programmeren van het spel), realiseerde ik me wat. Dit zou me nooit of te nimmer gaan lukken in QBasic. De ideeen die zich in mijn hoofd hadden gevormd hadden redelijk geavanceerde datastructuren nodig om te werken, en pointers zijn volgens mij al helemaal een no-go in QBasic. Je kan mijn versie van boter, kaas & eieren zeker namaken in QBasic, en hoogstwaarschijnlijk ook met minder code dan ik het heb gemaakt. Maar het zou voor mij gewoon simpelweg onpraktisch zijn om het in QBasic te maken. Een kort overleg met meneer Meftah later was ik overgestapt op C++ en kon het echte werk beginnen.
De PSD's
Voor de goede orde heb ik ook nog 3 PSD's gemaakt. Ze zijn misschien een beetje anders dan de pseudocode. Dat is zo omdat toen ik de pseudocode schreef nog niet 100% door had hoe het MiniMax algoritme precies werkte. Toen ik de PSD's schreef begreep ik het wel 100%, dus zijn de PSD's eigenlijk beter.
- PSD van het spel.
- PSD van de fucntie die node functies maakt en ze analyseert. Dit is kortgezegd de AI.
- PSD van de functie die spelsituaties evalueert en herkend of er iemand wint of niet.
Structuur
Mijn stappenplan zag er zo uit:
- Een systeem te maken dat makkelijk kan rekenen en communiceren met spelsituaties
- Het spel uitwerken tot het punt dat je zetten kan doen, maar de computer nog geen zetten terug hoeft te/kan doen. Hierin moet een AI makkelijk te implementeren zijn
- De AI erin verwerken zodat het spel leuk wordt
Zo gezegd, zo gedaan. De eerste twee stappen waren prima te doen. Wat ik bij dit gedeelte geleerd heb is vooral structuur aanbrengen in een programma. Vroeger was mijn programmastructuur nogal rommelig, maar bij dit project heb ik erg mijn best gedaan om alles netjes en gestructureerd te houden. Ik had hier in de latere stadia van het ontwikkelen van het spel een heleboel profijt van, omdat ik door de goede structuur bijna kon voorspellen hoe sommige functies eruit zagen en hoe ze werkten, waardoor het programmeren een prettig zetje in de rug kreeg. Daarna moest ik bezig met de AI. Het maken van de AI in het spel bleek reuze mee te vallen, want ik had verwacht dat het heel erg veel moeite zou kosten. Maar als ik erop terugkijk zie ik dat het me meer tijd heeft gekost om het algoritme echt te begrijpen dan om het om te zetten in regeltjes code. Ik zal hier kort uitleggen wat het Minimax algoritme nou eigenlijk doet.
Minimax: hoe werkt het
Het Minimax algoritme werkt vanuit een paar principes:
- Beide spelers hebben volledig inzicht in de situatie. Dit is van toepassing op boter kaas en eieren, maar ook op bijvoorbeeld schaken: beide spelers hebben alle informatie over alle stukken. Dit gaat bijvoorbeeld niet op bij een kaartspel: je weet niet wat de ander in zijn hand heeft, en dit geld ook voor je tegenstander.
- Er komt geen toeval voor bij het spel. Dit is het geval voor voor boter kaas en eieren, maar bijvoorbeeld niet voor mens erger je niet. Voor mens erger je niet zou je dus moeilijk tot niet een minimax algoritme kunnen maken.
- Beide spelers proberen hun verlies te minimaliseren, oftewel hun winst te maximaliseren. De computer zou jou dus nooit laten winnen, maar op z'n minst gelijk laten spelen. En dat alleen als het niet anders kan.
- Beide spelers maken geen fouten. Oftewel, het algoritme zal altijd rekenen met worst case scenario. Als de tegenstander van de computer dus wel fouten maakt, zal de computer redelijk genadeloos zijn.
Hoe het algoritme werkt is eigenlijk heel simpel. Hij evalueert de spelsituatie op dit moment. Dit doet hij door op de achtergrond alle mogelijke zetten te maken, en dan elke zet onafhankelijk te evalueren. Vervolgens maakt hij van elke zet die hij op de achtergrond gemaakt heeft, alle mogelijke zetten die erna kunnen komen. En zo gaat het maar door, totdat hij alle mogelijke speluitkomsten van de spelsituatie op dit moment berekend heeft. Vervolgens kiest hij de zet die de minste kans heeft om een winst voor de ander te worden. Hier gaan natuurlijk nog heel veel andere vergelijkingen en bewerking aan vooraf, maar dit is het ongeveer in een notendop.
Mijn mening over de opdracht
Ik heb verder van geen enkele bron regels code gepikt, of dingen gekopieerd. Ik heb het hele project zelf getypt en bedacht. Het enige wat ik heb gedaan is slechts het algoritme van dat op het internet beschreven stond toepassen, wat opzich wel pittig was. Tuurlijk is mijn manier niet de beste en zeker niet de meest optimale, maar voor een klein spelletje zoals boter kaas & eieren is het prima. Al met al vond ik dit een hele leuke opdracht, en is het eigenlijk de eerste waar ik moeite voor moet doen en ook nog wat geleerd heb.
Bronnen
Om dit programma te maken heb ik vier bronnen gebruikt:
- Het nederlandse Wikipedia artikel over het Minimax algoritme - Hier heb ik de basis van het algoritme opgepikt.
- Het engelse Wikipedia artikel over het Minimax algoritme - Het nederlandse artikel ging niet diep genoeg in op het algoritme, dus heb ik me verder ingelezen op het onderwerp met het engelse artikel.
- Een voorbeeld van de implementatie van het Minimax algoritme met Boter, kaas & eieren - Om te kijken of het uberhaupt wel kon. Er staan ook wat leuke wetenswaardigheidjes op de pagina.
- Voor de spelsituatie-evaluatie functie - Ik had helemaal geen ervaring met AI's, laat staan het Minimax algoritme. Dus toen ik las dat ik waarschijnlijk een spelsituatie-evaluatie functie nodig zou hebben heb ik er maar gewoon eentje opgezocht op internet, en hem gevonden op deze pagina. Ik heb niet verder gelezen dan de eerste paragraaf ("Formulating Game Playing as Search"), dus alles wat erna komt heb ik pas gelezen toen ik klaar was met het spel.
- Gratis PSD maker - Met dit programma heb ik de PSD's gemaakt.