streamalism.org

1. Pregled

U ovom ćemo članku razgovarati o algoritmu Minimax i njegovim primjenama u AI. Kako se radi o algoritmu teorije igara, implementirat ćemo jednostavnu igru ​​pomoću njega.

Također ćemo razgovarati o prednostima upotrebe algoritma i vidjeti kako se može poboljšati.

2. Uvod

Minimax je algoritam za donošenje odluka, obično se koristi u igrama s dva igrača smještene u potezu. Cilj algoritma je pronaći optimalni sljedeći potez.

U algoritmu se jedan igrač naziva maksimalizatorom, a drugi igrač minimizatorom. Ako igraćoj ploči dodijelimo ocjenu, jedan igrač pokušava odabrati stanje igre s maksimalnim brojem bodova, dok drugi odabire stanje s minimalnim rezultatom.

Drugim riječima, themaximizer radi na postizanju najveće ocjene, dok minimizer pokušava dobiti najnižu ocjenu pokušavajući kontrirati poteze.

Temelji se na konceptu igre s nultim zbrojem. U igri s nultim zbrojem ukupni rezultat korisnosti podijeljen je između igrača. Povećanje rezultata jednog igrača rezultira smanjenjem rezultata drugog igrača. Dakle, ukupni rezultat uvijek je nula. Da bi jedan igrač pobijedio, drugi mora izgubiti. Primjeri takvih igara su šah, poker, dame, tik-takti.

Zanimljiva činjenica - 1997. godine IBM-ovo računalo za igranje šaha Deep Blue (izgrađeno s Minimaxom) pobijedilo je Garryja Kasparova (svjetskog prvaka u šahu).

3. Minimax algoritam

Cilj nam je pronaći najbolji potez za igrača. Da bismo to učinili, možemo samo odabrati čvor s najboljom ocjenom. Da bismo proces učinili pametnijim, također možemo gledati naprijed i procijeniti poteze potencijalnih protivnika.

Za svaki potez možemo gledati unaprijed onoliko poteza koliko nam dopušta naša računarska snaga. Algoritam pretpostavlja da protivnik igra optimalno.

Tehnički započinjemo s korijenskim čvorom i biramo najbolji mogući čvor. Čvorove procjenjujemo na temelju njihovih ocjena. U našem slučaju, funkcija procjene može dodijeliti ocjene samo rezultatim čvorovima (listovima). Stoga rekurzivno dosežemo lišće s bodovima i natrag širimo rezultate.

Razmotrite donje stablo igre:

Maksimizatorzapočinje korijenskim čvorom i odabire potez s maksimalnim brojem bodova. Nažalost, samo listovi imaju ocjene s njima, pa algoritam mora rekurzivno doći do čvorova lista. U danom stablu igara trenutno je red na minimizeru odaberite potez iz čvorova lista, tako da će biti odabrani čvorovi s minimalnim rezultatima (ovdje, čvor 3 i 4). Slično nastavlja s odabirom najboljih čvorova, sve dok ne dođe do korijenskog čvora.

Ajmo sada formalno definirati korake algoritma:

1. Izgradite cjelovito stablo igre
2. Ocjenjujte ocjene za lišće pomoću funkcije procjene
3. Rezervne ocjene od lišća do korijena, s obzirom na vrstu igrača:
   • Za max igrača odaberite dijete s maksimalnim rezultatom
   • Za min igrača odaberite dijete s minimalnim rezultatom
4. Na korijenskom čvoru odaberite čvor s maksimalnom vrijednošću i izvedite odgovarajući pomak

4. Provedba

A sad, implementirajmo igru.

U igri imamo gomila sa n broj kostiju. Oba igrača moraju pokupite 1,2 ili 3 kosti zauzvrat. Igrač koji ne može uzeti kosti gubi igru. Svaki igrač igra optimalno. S obzirom na vrijednost n, napišimo AI.

Da bismo definirali pravila igre, provest ćemo ih GameOfBones razred:

class GameOfBones {statički popis getPossibleStates (int noOfBonesInHeap) {return IntStream.rangeClosed (1, 3) .boxed () .map (i -> noOfBonesInHeap - i) .filter (newHeapCount -> newHeapCount> = 0) .collect (Collectors izlistati()); }}

Nadalje, također nam je potrebna implementacija za Čvor i Drvo tečajevi:

čvor javne klase {int noOfBones; logički isMaxPlayer; int rezultat; Popis djece; // postavljači i getteri} drvo javne klase {Node root; // postavljači i dobivači}

Sada ćemo implementirati algoritam. Potrebno je stablo igre da gleda unaprijed i pronađe najbolji potez. Primijenimo to:

javna klasa MiniMax {stablo stabla; javna praznina constructTree (int noOfBones) {stablo = novo stablo (); Korijen čvora = novi čvor (noOfBones, točno); tree.setRoot (korijen); constructTree (korijen); } private void constructTree (Node parentNode) {List 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);}}); }}

Sada ćemo implementirati checkWin metoda koja će simulirati play out, odabirom optimalnih poteza za oba igrača. Rezultat postavlja na:

• +1, ako maximizer pobijedi
• -1, ako minimizer pobijedi

The checkWin vratit će se istinito ako pobijedi prvi igrač (u našem slučaju - maksimalizator):

javna logička provjeraWin () {Čvor korijena = stablo.getRoot (); checkWin (korijen); vratiti root.getScore () == 1; } private void checkWin (čvor čvora) {Popis djece = node.getChildren (); boolean isMaxPlayer = node.isMaxPlayer (); kids.forEach (child -> {if (child.getNoOfBones () == 0) {child.setScore (isMaxPlayer? 1: -1);} else {checkWin (dijete);}}); Čvor bestChild = findBestChild (isMaxPlayer, djeca); node.setScore (bestChild.getScore ()); }

Evo, findBestChild metoda pronalazi čvor s maksimalnim rezultatom ako je igrač maksimalizator. Inače, djetetu vraća minimalni rezultat:

privatni čvor findBestChild (logički isMaxPlayer, popis djece) {Comparator byScoreComparator = Comparator.comparing (Node :: getScore); vratiti children.stream () .max (isMaxPlayer? byScoreComparator: byScoreComparator.reversed ()) .orElseThrow (NoSuchElementException :: novo); }

Na kraju, provedimo testni slučaj s nekim vrijednostima od n (broj kostiju na hrpi):

@Test javna praznina givenMiniMax_whenCheckWin_thenComputeOptimal () {miniMax.constructTree (6); logički rezultat = miniMax.checkWin (); assertTrue (rezultat); miniMax.constructTree (8); rezultat = miniMax.checkWin (); assertFalse (rezultat); }

5. Poboljšanje

Za većinu problema nije izvedivo izraditi cijelo stablo igara. U praksi možemo razviti djelomično stablo (konstruirati stablo samo do unaprijed određenog broja razina).

Tada ćemo morati implementirati funkcija procjene, koja bi trebala moći odlučiti koliko je trenutno stanje dobro za igrača.

Čak i ako ne izgradimo cjelovita stabla igara, izračunavanje poteza za igre s visokim faktorom grananja može potrajati.

Srećom, postoji mogućnost pronalaska optimalnog poteza, bez istraživanja svakog čvora stabla igre. Neke grane možemo preskočiti slijedeći neka pravila i to neće utjecati na konačni rezultat. Taj se proces nazivaobrezivanje. Alfa-beta rezidba prevladava varijanta algoritma minimax.

6. Zaključak

Minimax algoritam jedan je od najpopularnijih algoritama za računalne igre na ploči. Široko se primjenjuje zauzvrat bazirane igre. To može biti dobar izbor kada igrači imaju potpune informacije o igri.

Možda nije najbolji izbor za igre s izuzetno visokim faktorom grananja (npr. Igra GO). Ipak, s obzirom na pravilnu implementaciju, to može biti prilično pametan AI.

Kao i uvijek, cjelovit kôd algoritma možete pronaći na GitHubu.