sinds de komst van kunstmatige intelligentie (AI) is het spelen van games een van de meest interessante toepassingen van AI.De eerste schaakprogramma ‘ s werden geschreven door Claude Shannon en Alan Turing in 1950, bijna zodra de computers programmeerbaar werden.
spellen zoals Schaken, tic-tac-toe en Go zijn interessant omdat ze een pure abstractie van de competitie tussen de twee legers bieden.
het is deze abstractie die het spel een aantrekkelijk gebied maakt voor AI-onderzoek.
in dit artikel gaan we door de basisprincipes van het MiniMax algoritme samen met de werking van het algoritme.
we zullen ook kijken naar de optimalisatie van het MiniMax algoritme, alpha-beta snoeien.
Wat is het MiniMax-algoritme?
Minimax is een recursief algoritme dat wordt gebruikt om een optimale zet voor een speler te kiezen, ervan uitgaande dat de andere speler ook optimaal speelt.
het wordt gebruikt in spellen zoals tic-tac-toe, go, chess, Isola, checkers en vele andere spellen met twee spelers.
dergelijke spellen worden spellen met perfecte informatie genoemd omdat het mogelijk is om alle mogelijke zetten van een bepaald spel te zien.
er kunnen spellen met twee spelers zijn die geen perfecte informatie bevatten, zoals Scrabble omdat de zet van de tegenstander niet voorspeld kan worden.
het is vergelijkbaar met hoe we denken als we een spel spelen:” als ik deze zet maak, dan kan mijn tegenstander alleen deze zetten maken, ” enzovoort.
Minimax wordt zo genoemd omdat het helpt bij het minimaliseren van het verlies wanneer de andere speler kiest voor de strategie met het maximale verlies.
terminologie
- spelstructuur: het is een structuur in de vorm van een boom die bestaat uit alle mogelijke zetten waarmee u van een toestand van het spel naar de volgende toestand kunt gaan.
een spel kan worden gedefinieerd als een zoekprobleem met de volgende componenten:
- initiële status: Het bevat de positie van het bord en toont wiens zet het is.
- Opvolgfunctie: Het bepaalt wat de legale zetten een speler kan maken zijn.
- Terminalstatus: het is de positie van het bord wanneer het spel voorbij is.
- Utility function: het is een functie die een numerieke waarde toekent aan de uitkomst van een spel. Bijvoorbeeld, in schaken of tic-tac-toe, de uitkomst is ofwel een overwinning, een verlies, of een gelijkspel, en deze kunnen worden weergegeven door de waarden +1, -1, of 0, respectievelijk. Er zijn spellen die een veel groter bereik van mogelijke uitkomsten hebben; bijvoorbeeld, de hulpprogramma ‘ s in backgammon variëren van +192 tot -192. Een utility-functie kan ook een payoff-functie worden genoemd.
Hoe werkt het algoritme?
er zijn twee spelers betrokken bij een spel, genaamd MIN en MAX. De speler MAX probeert de hoogst mogelijke score te krijgen en MIN probeert de laagst mogelijke score te krijgen, dat wil zeggen, MIN en MAX proberen tegenover elkaar te handelen.
het algemene proces van het MiniMax-algoritme is als volgt:
Stap 1: genereer eerst de volledige spelstructuur vanaf de huidige positie van het spel tot aan de terminalstatus. Zo ziet de spelboom eruit voor het spel tic-tac-toe.
laat ons de gedefinieerde terminologie in termen van het bovenstaande diagram begrijpen.
- de initiële status is de eerste laag die bepaalt dat het bord leeg is. het is de beurt aan MAX om te spelen.
- Opvolgfunctie geeft alle mogelijke opvolgbewegingen weer. Het is gedefinieerd voor alle lagen in de boom.
- Terminalstatus is de laatste laag van de boom die de uiteindelijke status toont, dat wil zeggen of de speler MAX wint, verliest of banden heeft met de tegenstander.
- Utilities in dit geval zijn de terminaltoestanden 1, 0 en -1 zoals eerder besproken, en ze kunnen ook worden gebruikt om de utilities van de andere knooppunten te bepalen.
Stap 2: Pas de utility-functie toe om de nutswaarden voor alle terminalstaten te krijgen.
Stap 3: Bepaal de hulpprogramma ’s van de hogere knooppunten met behulp van de hulpprogramma’ s van de terminalknooppunten. Bijvoorbeeld, in het diagram hieronder, hebben we de hulpprogramma ‘ s voor de terminaltoestanden geschreven in de vierkanten.
laten we het hulpprogramma berekenen voor het linker knooppunt (rood) van de laag boven de terminal. Aangezien het de beweging van de speler MIN, zullen we het minimum van alle hulpprogramma ‘ s te kiezen. Voor dit geval moeten we min{3, 5, 10} evalueren, waarvan we zeker weten dat het 3 is. Dus het hulpprogramma voor de rode knoop is 3.
op dezelfde manier zullen we voor de groene knoop in dezelfde laag min{2,2} moeten evalueren, wat 2 is.
Stap 4: Bereken de nutswaarden met behulp van bladeren overwegen een laag per keer tot de wortel van de boom.
Stap 5: uiteindelijk bereiken alle back-upwaarden de wortel van de boom, d.w.z. het bovenste punt. Op dat moment moet MAX de hoogste waarde kiezen.
in ons voorbeeld hebben we slechts 3 lagen, dus we bereikten meteen de root, maar in echte spellen zullen er veel meer lagen en knopen zijn. Dus moeten we max{3,2} evalueren, wat 3 is.
daarom is de beste openingszet voor MAX de linker knoop(of de rode). Deze zet wordt de minimax beslissing genoemd omdat het het nut maximaliseert volgens de aanname dat de tegenstander ook optimaal speelt om het te minimaliseren.
samenvattend,
Minimax Decision = MAX{MIN{3,5,10}, MIN{2,2}}
= MAX{3,2}
= 3
Psuedocode:
function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue
optimalisatie
Spellenbomen zijn over het algemeen zeer tijdrovend om te bouwen, en het is alleen voor eenvoudige spellen dat het in korte tijd kan worden gegenereerd.
als er\ (b\) juridische stappen zijn, d.w.z., \(b\) knooppunten op elk punt en de maximale diepte van de boom is \(m\), de tijdscomplexiteit van het minimaxalgoritme is van de orde \(b^m (O(b^m))\).
om deze situatie te beteugelen, zijn er een paar optimalisaties die aan het algoritme kunnen worden toegevoegd.
gelukkig is het haalbaar om de werkelijke minimax beslissing te vinden zonder zelfs maar naar elk knooppunt van de spelboom te kijken. Daarom elimineren we knooppunten uit de boom zonder te analyseren, en dit proces heet snoeien.
Alpha-beta snoeien
de methode die we in dit artikel gaan bekijken heet alpha-beta snoeien.
als we alpha-beta snoeien toepassen op een standaard minimax algoritme, geeft het dezelfde beweging terug als de standaard, maar het verwijdert (snoeit) alle knooppunten die mogelijk geen invloed hebben op de uiteindelijke beslissing.
laat ons eerst de intuã tie achter dit begrijpen en dan zullen we het algoritme formaliseren. Stel dat we de volgende wildboom hebben:
in dit geval,
Minimax Decision = MAX{MIN{3,5,10}, MIN{2,a, b}, MIN{2,7,3}}
= MAX{3, c,2}
= 3
je zou verrast zijn!
Hoe kunnen we het maximum berekenen met een ontbrekende waarde? Dit is de truc. MIN{2, a, b} zou zeker kleiner zijn dan of gelijk aan 2, d.w.z. c<=2 en dus moet MAX{3, c,2} 3 zijn.
de vraag is nu of we echt c moeten berekenen? Natuurlijk niet.
we hadden tot een conclusie kunnen komen zonder naar die knooppunten te kijken. En dit is waar alfa-beta snoeien in beeld komt.
enkele definities:
Alfa: het is de beste keuze tot nu toe voor de speler MAX. We willen hier de hoogst mogelijke waarde krijgen.
bèta: Het is de beste keuze tot nu toe voor MIN,en het moet de laagst mogelijke waarde.
opmerking: elk knooppunt moet zijn alfa-en bètawaarden bijhouden. Alpha kan alleen worden bijgewerkt wanneer het MAX ’s beurt is en, op dezelfde manier, beta kan alleen worden bijgewerkt wanneer het Min’ s kans.
Hoe werkt alfa-beta snoeien?
- initialiseer alpha = – oneindigheid en beta = oneindigheid als de slechtst mogelijke gevallen. De voorwaarde om een knoop te snoeien is wanneer alpha groter dan of gelijk aan beta wordt.
- begin met het toewijzen van de beginwaarden van alpha en beta aan root en aangezien Alfa minder is dan beta snoeien we het niet.
- dragen deze waarden van alfa en bèta naar de onderliggende knoop aan de linkerkant. En nu vanuit de nutswaarde van de terminalstatus, zullen we de waarden van alpha en be bijwerken, zodat we de waarde van beta niet hoeven bij te werken. Nogmaals, we snoeien niet omdat de conditie hetzelfde blijft. Ook het derde kindknooppunt. En dan terugdraaien naar de root zetten we alpha = 3 in omdat dat de minimale waarde is die alpha kan hebben.
- nu, alpha = 3 en beta = oneindigheid aan de wortel. Dus we snoeien niet. Door dit naar het middenknooppunt te brengen, en min{2, oneindigheid} te berekenen, krijgen we alpha = 3 en beta = 2.
- snoei de tweede en derde kindknoop omdat Alfa nu groter is dan bèta.
- Alfa aan de wortel blijft 3 omdat het groter is dan 2. Evalueer MIN{oneindigheid, 2}=2 door dit naar de meest rechtse kinderknoop te brengen. Update beta naar 2 en alpha blijft 3.
- snoei de tweede en derde kindknoop omdat Alfa nu groter is dan bèta.
- vandaar, krijgen we 3, 2, 2 op de linker, midden, en rechts min knooppunten, respectievelijk. En het berekenen van MAX{3,2,2}, krijgen we 3. Daarom, zonder zelfs maar te kijken naar vier bladeren konden we correct de minimax beslissing te vinden.
Pseudocode (bron: NPTEL cursus):
evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha
conclusie
spellen zijn erg aantrekkelijk en het schrijven van spelprogramma ‘ s is misschien nog spannender. Wat Grand Prix racen is voor de auto-industrie, spel spelen is AI.
net zoals we niet verwachten dat een raceauto perfect op een hobbelige weg rijdt, moeten we ook niet verwachten dat algoritmes voor het spelen van games perfect zijn voor elke situatie.
het MiniMax-algoritme ook. Het is misschien niet de beste oplossing voor allerlei computerspellen die AI moeten hebben.
maar gegeven een goede implementatie, kan het een harde concurrent creëren.