Bob's Portfolio

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.

Structuur

Mijn stappenplan zag er zo uit:

  1. Een systeem te maken dat makkelijk kan rekenen en communiceren met spelsituaties
  2. 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
  3. 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:

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: