streamalism.org

1. Oversigt

I denne artikel vil vi diskutere Minimax-algoritme og dens applikationer i AI. Da det er en algoritme til spilteori, implementerer vi et simpelt spil ved hjælp af det.

Vi diskuterer også fordelene ved at bruge algoritmen og se, hvordan den kan forbedres.

2. Introduktion

Minimax er en beslutningsalgoritme, bruges typisk i et turbaseret tospiller-spil. Målet med algoritmen er at finde det optimale næste træk.

I algoritmen kaldes den ene spiller maksimering, og den anden spiller er en minimizer. Hvis vi tildeler en evalueringsscore til spillebrættet, prøver den ene spiller at vælge en spiltilstand med den maksimale score, mens den anden vælger en tilstand med den mindste score.

Med andre ord, detmaximizer arbejder for at få den højeste score, mens minimizer forsøger få den laveste score ved at prøve at modvirke træk.

Det er baseret på nul-sum-spilkonceptet. I et nul-sum-spil er den samlede nytte score fordelt på spillerne. En stigning i en spillers score resulterer i faldet i en anden spillers score. Så den samlede score er altid nul. For at en spiller skal vinde, skal den anden tabe. Eksempler på sådanne spil er skak, poker, brikker, tic-tac-toe.

En interessant kendsgerning - i 1997 besejrede IBMs skakspilende computer Deep Blue (bygget med Minimax) Garry Kasparov (verdensmesteren i skak).

3. Minimax algoritme

Vores mål er at finde det bedste træk for spilleren. For at gøre det kan vi bare vælge den node med den bedste vurderingsscore. For at gøre processen smartere kan vi også se fremad og evaluere potentielle modstanders bevægelser.

For hvert træk kan vi se fremad så mange træk som vores computerkraft tillader. Algoritmen antager, at modstanderen spiller optimalt.

Teknisk set starter vi med rodnoden og vælger den bedst mulige node. Vi evaluerer noder ud fra deres evalueringsscorer. I vores tilfælde kan evalueringsfunktionen tildele scores til kun resultatknudepunkter (blade). Derfor når vi rekursivt blade med scoringer, og spredes tilbage.

Overvej nedenstående spilletræ:

Maximizerstarter med rodnoden og vælger træk med den maksimale score. Desværre har kun blade evalueringsscorer med sig, og derfor skal algoritmen nå bladknuderne rekursivt. I det givne spiltræ er det i øjeblikket minimizerens tur til vælg et træk fra bladknudepunkterne, så knudepunkterne med minimumscores (her, node 3 og 4) bliver valgt. Det fortsætter med at vælge de bedste noder på samme måde, indtil det når rodnoden.

Lad os nu formelt definere trin i algoritmen:

1. Konstruer det komplette spiltræ
2. Evaluer scoringer for blade ved hjælp af evalueringsfunktionen
3. Back-up scorer fra blade til rod i betragtning af spillertypen:
   • For maks. Spiller skal du vælge barnet med den maksimale score
   • For min-spiller skal du vælge barnet med minimumscore
4. På rodnoden skal du vælge noden med den maksimale værdi og udføre det tilsvarende træk

4. Implementering

Lad os nu implementere et spil.

I spillet har vi en bunke med n antal knogler. Begge spillere skal afhente 1,2 eller 3 knogler efter deres tur. En spiller, der ikke kan tage knogler, mister spillet. Hver spiller spiller optimalt. I betragtning af værdien af n, lad os skrive en AI.

For at definere spillereglerne implementerer vi GameOfBones klasse:

klasse GameOfBones {statisk liste getPossibleStates (int noOfBonesInHeap) {return IntStream.rangeClosed (1, 3) .boxed () .map (i -> noOfBonesInHeap - i) .filter (newHeapCount -> newHeapCount> = 0) .collect (Collectors. toList ()); }}

Desuden har vi også brug for implementeringen til Node og Træ klasser også:

offentlig klasse Node {int noOfBones; boolsk isMaxPlayer; int score; Liste børn; // setters og getters} public class Tree {Node rod; // settere og getters}

Nu implementerer vi algoritmen. Det kræver et spiltræ at se fremad og finde det bedste træk. Lad os implementere det:

offentlig klasse MiniMax {Tree tree; public void constructTree (int noOfBones) {tree = new Tree (); Node rod = ny node (noOfBones, sand); tree.setRoot (rod); constructTree (rod); } privat ugyldigt constructTree (Node parentNode) {List listofPossibleHeaps = GameOfBones.getPossibleStates (parentNode.getNoOfBones ()); boolsk isChildMaxPlayer =! parentNode.isMaxPlayer (); listofPossibleHeaps.forEach (n -> {Node newNode = ny node (n, isChildMaxPlayer); parentNode.addChild (newNode); hvis (newNode.getNoOfBones ()> 0) {constructTree (newNode);}}); }}

Nu implementerer vi checkWin metode, der simulerer en play-out ved at vælge optimale træk for begge spillere. Det sætter scoren til:

• +1, hvis maksimerer vinder
• -1, hvis minimizer vinder

Det checkWin returnerer sandt, hvis den første spiller (i vores tilfælde - maksimering) vinder:

public boolean checkWin () {Node root = tree.getRoot (); checkWin (rod); returner root.getScore () == 1; } privat ugyldig checkWin (Node-node) {List børn = node.getChildren (); boolsk isMaxPlayer = node.isMaxPlayer (); children.forEach (child -> {if (child.getNoOfBones () == 0) {child.setScore (isMaxPlayer? 1: -1);} else {checkWin (child);}}); Node bestChild = findBestChild (isMaxPlayer, børn); node.setScore (bestChild.getScore ()); }

Her, den findBestChild metode finder noden med den maksimale score, hvis en spiller er en maksimering. Ellers returnerer det barnet med den mindste score:

privat Node findBestChild (boolsk isMaxPlayer, liste børn) {Comparator byScoreComparator = Comparator.comparing (Node :: getScore); returnere børn.stream () .max (isMaxPlayer? byScoreComparator: byScoreComparator.reversed ()) .orElseThrow (NoSuchElementException :: new); }

Lad os endelig implementere en test case med nogle værdier på n (antallet af knogler i en bunke):

@Test offentlig ugyldighed givenMiniMax_whenCheckWin_thenComputeOptimal () {miniMax.constructTree (6); boolsk resultat = miniMax.checkWin (); assertTrue (resultat); miniMax.constructTree (8); resultat = miniMax.checkWin (); assertFalse (resultat); }

5. Forbedring

For de fleste af problemerne er det ikke muligt at konstruere et helt spiltræ. I praksis kan vi udvikle et delvis træ (konstruer træet til et foruddefineret antal niveauer).

Derefter bliver vi nødt til at implementere en evalueringsfunktion, som skal være i stand til at afgøre, hvor god den aktuelle tilstand er for spilleren.

Selvom vi ikke bygger komplette spiltræer, kan det være tidskrævende at beregne træk til spil med høj forgreningsfaktor.

Heldigvis er der en mulighed for at finde det optimale træk uden at udforske hver knude af spilletræet. Vi kan springe nogle grene over ved at følge nogle regler, og det påvirker ikke det endelige resultat. Denne proces kaldesbeskæring. Alfa-beta beskæring er en udbredt variant af minimax algoritme.

6. Konklusion

Minimax algoritme er en af ​​de mest populære algoritmer til computerspil. Det anvendes bredt i turbaserede spil. Det kan være et godt valg, når spillerne har komplet information om spillet.

Det er muligvis ikke det bedste valg til spil med en usædvanlig høj forgreningsfaktor (f.eks. GO-spil). Ikke desto mindre, givet en ordentlig implementering, kan det være en ret smart AI.

Som altid kan den komplette kode til algoritmen findes på GitHub.