Introduksjon til Minimax-algoritme med en Java-implementering

1. Oversikt

I denne artikkelen skal vi diskutere Minimax-algoritmen og dens applikasjoner i AI. Siden det er en algoritme for spillteori, implementerer vi et enkelt spill ved hjelp av det.

Vi vil også diskutere fordelene ved å bruke algoritmen og se hvordan den kan forbedres.

2. Introduksjon

Minimax er en beslutningsalgoritme, vanligvis brukt i et turbasert tospillerspill. Målet med algoritmen er å finne det optimale neste trekket.

I algoritmen kalles den ene spilleren for maksimering, og den andre spilleren for en minimizer. Hvis vi tildeler en evalueringspoeng til spillbrettet, prøver den ene spilleren å velge en spilltilstand med maksimumscore, mens den andre velger en tilstand med minimumscore.

Med andre ord, demaximizer jobber for å få høyest poengsum, mens minimizer prøver får lavest poengsum ved å prøve å motvirke trekk.

Det er basert på null-sum spillkonseptet. I et nullsumsspill blir den totale nytteverdien delt mellom spillerne. En økning i en spillers poengsum resulterer i reduksjon i en annen spillers poengsum. Så den totale poengsummen er alltid null. For at en spiller skal vinne, må den andre tape. Eksempler på slike spill er sjakk, poker, brikker, tic-tac-toe.

Et interessant faktum - i 1997 beseiret IBMs sjakk-spillende datamaskin Deep Blue (bygget med Minimax) Garry Kasparov (verdensmesteren i sjakk).

3. Minimax algoritme

Målet vårt er å finne det beste trekket for spilleren. For å gjøre det kan vi bare velge noden med best vurderingspoeng. For å gjøre prosessen smartere, kan vi også se fremover og evaluere potensielle motstanders trekk.

For hvert trekk kan vi se fremover så mange trekk som vår datakraft tillater. Algoritmen forutsetter at motstanderen spiller optimalt.

Teknisk sett starter vi med rotnoden og velger best mulig node. Vi evaluerer noder basert på deres evalueringspoeng. I vårt tilfelle kan evalueringsfunksjonen tildele score til kun resultatnoder (blader). Derfor når vi rekursivt blader med poengsummer og forplanter poengene tilbake.

Vurder spilltreet nedenfor:

Maximizerstarter med rotnoden og velger trekket med maks poengsum. Dessverre er det bare blader som har evalueringspoeng, og dermed må algoritmen nå bladnoder rekursivt. I det gitte spilletreet er det for øyeblikket minimizerens tur til velg et trekk fra bladnodene, slik at nodene med minimumscore (her, node 3 og 4) blir valgt. Det fortsetter å velge de beste nodene på samme måte til den når rotnoden.

La oss nå formelt definere trinn i algoritmen:

  1. Konstruer hele spilletreet
  2. Evaluer poeng for blader ved hjelp av evalueringsfunksjonen
  3. Sikkerhetskopier fra blader til rot, med tanke på spillertypen:
    • For maks spiller, velg barnet med maks poengsum
    • For min spiller, velg barnet med minimum poengsum
  4. På rotnoden velger du noden med maks verdi og utfører den tilsvarende flyttingen

4. Gjennomføring

La oss nå implementere et spill.

I spillet har vi en haug med n antall bein. Begge spillerne må plukk opp 1,2 eller 3 bein i sin tur. En spiller som ikke kan ta bein, mister spillet. Hver spiller spiller optimalt. Gitt verdien av n, la oss skrive en AI.

For å definere spillereglene vil vi implementere GameOfBones klasse:

class GameOfBones {static List getPossibleStates (int noOfBonesInHeap) {return IntStream.rangeClosed (1, 3) .boxed () .map (i -> noOfBonesInHeap - i) .filter (newHeapCount -> newHeapCount> = 0) .collect (Collectors. å liste opp()); }}

Videre trenger vi også implementeringen for Node og Tre klasser også:

offentlig klasse Node {int noOfBones; boolsk isMaxPlayer; int score; Liste barn; // setters and getters} public class Tree {Node root; // setters og getters}

Nå implementerer vi algoritmen. Det krever et spilletre for å se fremover og finne det beste trekket. La oss implementere det:

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

Nå skal vi implementere checkWin metode som vil simulere en play out, ved å velge optimale trekk for begge spillerne. Det setter poengsummen til:

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

De checkWin vil være sant hvis den første spilleren (i vårt tilfelle - maksimalisering) vinner:

offentlig boolsk checkWin () {Node root = tree.getRoot (); checkWin (rot); returner root.getScore () == 1; } private void checkWin (Node node) {List child = 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, barn); node.setScore (bestChild.getScore ()); }

Her, den findBestChild metoden finner noden med maksimal poengsum hvis en spiller er en maksimering. Ellers returnerer det barnet med minst poengsum:

privat Node findBestChild (boolsk isMaxPlayer, liste barn) {Comparator byScoreComparator = Comparator.comparing (Node :: getScore); returner childs.stream () .max (isMaxPlayer? byScoreComparator: byScoreComparator.reversed ()) .orElseThrow (NoSuchElementException :: ny); }

Til slutt, la oss implementere en testtilfelle med noen verdier av n (antall bein i en haug):

@Test offentlig ugyldig 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 av problemene er det ikke mulig å konstruere et helt viltre. I praksis kan vi utvikle et delvis tre (konstruer treet til et forhåndsdefinert antall nivåer).

Da må vi implementere en evalueringsfunksjon, som skal kunne bestemme hvor god den nåværende tilstanden er for spilleren.

Selv om vi ikke bygger komplette spilltrær, kan det være tidkrevende å beregne trekk for spill med høy forgreningsfaktor.

Heldigvis er det et alternativ for å finne det optimale trekket uten å utforske hver node av spilletreet. Vi kan hoppe over noen grener ved å følge noen regler, og det vil ikke påvirke det endelige resultatet. Denne prosessen kallesbeskjæring. Alfa-beta beskjæring er en utbredt variant av minimax algoritme.

6. Konklusjon

Minimax algoritme er en av de mest populære algoritmene for brettspill. Det brukes mye i turbaserte spill. Det kan være et godt valg når spillerne har fullstendig informasjon om spillet.

Det er kanskje ikke det beste valget for spill med eksepsjonelt høy forgreningsfaktor (f.eks. GO of game). Likevel, gitt en riktig implementering, kan det være en ganske smart AI.

Som alltid kan den komplette koden for algoritmen finnes på GitHub.