streamalism.org

1. Overzicht

In dit artikel gaan we het Minimax-algoritme en zijn toepassingen in AI bespreken. Omdat het een speltheorie-algoritme is, zullen we er een eenvoudig spel mee implementeren.

We bespreken ook de voordelen van het gebruik van het algoritme en kijken hoe het kan worden verbeterd.

2. Inleiding

Minimax is een besluitvormingsalgoritme, meestal gebruikt in turn-based games voor twee spelers. Het doel van het algoritme is om de optimale volgende zet te vinden.

In het algoritme wordt de ene speler de maximizer genoemd en de andere speler is een minimizer. Als we een evaluatiescore aan het speelbord toekennen, probeert de ene speler een speltoestand met de maximale score te kiezen, terwijl de andere een staat met de minimumscore kiest.

Met andere woorden, demaximizer werkt om de hoogste score te halen, terwijl de minimizer de laagste score probeert te halen door zetten te proberen tegen te gaan.

Het is gebaseerd op het zero-sum game-concept. In een zero-sum-game wordt de totale utility-score over de spelers verdeeld. Een verhoging van de score van een speler resulteert in een verlaging van de score van een andere speler. De totale score is dus altijd nul. Om de ene speler te laten winnen, moet de andere verliezen. Voorbeelden van dergelijke spellen zijn schaken, poker, dammen, boter-kaas-en-eieren.

Een interessant feit: in 1997 versloeg IBM's schaakcomputer Deep Blue (gebouwd met Minimax) Garry Kasparov (de wereldkampioen schaken).

3. Minimax-algoritme

Ons doel is om de beste zet voor de speler te vinden. Om dit te doen, kunnen we gewoon het knooppunt met de beste evaluatiescore kiezen. Om het proces slimmer te maken, kunnen we ook vooruit kijken en mogelijke zetten van de tegenstander evalueren.

Voor elke zet kunnen we zoveel zetten vooruitkijken als onze rekenkracht toelaat. Het algoritme gaat ervan uit dat de tegenstander optimaal speelt.

Technisch gezien beginnen we met het rootknooppunt en kiezen we het best mogelijke knooppunt. We evalueren knooppunten op basis van hun evaluatiescores. In ons geval kan de evaluatiefunctie scores toewijzen aan alleen resultaatknooppunten (bladeren). Daarom bereiken we recursief bladeren met scores en verspreiden we de scores terug.

Beschouw de onderstaande spelboom:

Maximizerbegint met het hoofdknooppunt en kiest de zet met de maximale score. Helaas hebben alleen bladeren evaluatiescores bij zich, en daarom moet het algoritme de bladknooppunten recursief bereiken. In de gegeven spelboom is het momenteel de beurt aan de minimizer kies een zet uit de bladknooppunten, dus de knooppunten met minimale scores (hier knooppunt 3 en 4) worden geselecteerd. Het blijft op dezelfde manier de beste knooppunten kiezen, totdat het het hoofdknooppunt bereikt.

Laten we nu formeel de stappen van het algoritme definiëren:

1. Construeer de volledige spelboom
2. Evalueer scores voor bladeren met behulp van de evaluatiefunctie
3. Back-upscores van blad tot wortel, rekening houdend met het type speler:
   • Selecteer voor de maximale speler het kind met de maximale score
   • Selecteer voor minspeler het kind met de minimumscore
4. Kies bij het hoofdknooppunt het knooppunt met de maximale waarde en voer de bijbehorende verplaatsing uit

4. Implementatie

Laten we nu een spel implementeren.

In het spel hebben we een ophopen met n aantal botten. Beide spelers moeten raap 1,2 of 3 botten op in hun beurt. Een speler die geen botten kan pakken, verliest het spel. Elke speler speelt optimaal. Gezien de waarde van n, laten we een AI schrijven.

Om de regels van het spel te definiëren, zullen we implementeren GameOfBones klasse:

class GameOfBones {statische lijst getPossibleStates (int noOfBonesInHeap) {retourneer IntStream.rangeClosed (1, 3) .boxed () .map (i -> noOfBonesInHeap - i) .filter (newHeapCount -> newHeapCount> = 0) .collect (Collectors. toList ()); }}

Verder hebben we ook de implementatie nodig voor Knooppunt en Boom lessen ook:

openbare klasse Node {int noOfBones; boolean isMaxPlayer; int score; Lijst kinderen; // setters and getters} public class Tree {Node root; // setters en getters}

Nu gaan we het algoritme implementeren. Het vereist een spelboom om vooruit te kijken en de beste zet te vinden. Laten we dat implementeren:

openbare klasse MiniMax {Boomstructuur; openbare void constructTree (int noOfBones) {tree = new Tree (); Knooppunt root = nieuw knooppunt (noOfBones, true); tree.setRoot (root); constructTree (root); } private void constructTree (Node parentNode) {ListofPossibleHeaps = GameOfBones.getPossibleStates (parentNode.getNoOfBones ()); boolean isChildMaxPlayer =! parentNode.isMaxPlayer (); listofPossibleHeaps.forEach (n -> {Node newNode = new Node (n, isChildMaxPlayer); parentNode.addChild (newNode); if (newNode.getNoOfBones ()> 0) {constructTree (newNode);}}); }}

Nu gaan we het checkWin methode die een play-out simuleert, door optimale zetten voor beide spelers te selecteren. Het stelt de score in op:

• +1, als maximizer wint
• -1, als minimizer wint

De checkWin zal true retourneren als de eerste speler (in ons geval - maximizer) wint:

openbare boolean checkWin () {Node root = tree.getRoot (); checkWin (root); return root.getScore () == 1; } private void checkWin (Node node) {List children = node.getChildren (); boolean isMaxPlayer = node.isMaxPlayer (); children.forEach (child -> {if (child.getNoOfBones () == 0) {child.setScore (isMaxPlayer? 1: -1);} else {checkWin (child);}}); Knooppunt bestChild = findBestChild (isMaxPlayer, kinderen); node.setScore (bestChild.getScore ()); }

Hier de findBestChild methode vindt het knooppunt met de maximale score als een speler een maximalisator is. Anders retourneert het het kind met de minimumscore:

private Node findBestChild (boolean isMaxPlayer, List kinderen) {Comparator byScoreComparator = Comparator.comparing (Node :: getScore); return children.stream () .max (isMaxPlayer? byScoreComparator: byScoreComparator.reversed ()) .orElseThrow (NoSuchElementException :: new); }

Laten we tot slot een testcase implementeren met enkele waarden van n (het aantal botten in een hoop):

@Test openbare leegte gegevenMiniMax_whenCheckWin_thenComputeOptimal () {miniMax.constructTree (6); booleaans resultaat = miniMax.checkWin (); assertTrue (resultaat); miniMax.constructTree (8); resultaat = miniMax.checkWin (); assertFalse (resultaat); }

5. Verbetering

Voor de meeste problemen is het niet haalbaar om een ​​volledige gameboom te maken. In de praktijk kunnen we een gedeeltelijke boom ontwikkelen (bouw de boom slechts tot een vooraf bepaald aantal niveaus).

Dan zullen we een evaluatiefunctie, die moeten kunnen beslissen hoe goed de huidige staat is voor de speler.

Zelfs als we geen complete spelbomen bouwen, kan het tijdrovend zijn om zetten te berekenen voor spellen met een hoge vertakkingsfactor.

Gelukkig is er een optie om de optimale zet te vinden, zonder elk knooppunt te verkennen van de spelboom. We kunnen enkele vertakkingen overslaan door enkele regels te volgen, en dit heeft geen invloed op het uiteindelijke resultaat. Dit proces heetsnoeien. Alpha-beta-snoeien is een veel voorkomende variant van het minimax-algoritme.

6. Conclusie

Het Minimax-algoritme is een van de meest populaire algoritmen voor computerbordspellen. Het wordt veel toegepast in turn-based games. Het kan een goede keuze zijn als spelers volledige informatie over het spel hebben.

Het is misschien niet de beste keuze voor de spellen met een uitzonderlijk hoge vertakkingsfactor (bijvoorbeeld Game of GO). Desalniettemin kan het, gezien een goede implementatie, een behoorlijk slimme AI zijn.

Zoals altijd is de volledige code voor het algoritme te vinden op GitHub.