Úvod do algoritmu Minimax s implementáciou Java

1. Prehľad

V tomto článku sa budeme zaoberať algoritmom Minimax a jeho aplikáciami v AI. Pretože ide o algoritmus teórie hier, implementujeme pomocou neho jednoduchú hru.

Budeme tiež diskutovať o výhodách použitia algoritmu a uvidíme, ako sa dá vylepšiť.

2. Úvod

Minimax je rozhodovací algoritmus, sa zvyčajne používa v ťahových hrách pre dvoch hráčov. Cieľom algoritmu je nájsť optimálny ďalší krok.

V algoritme sa jeden hráč nazýva maximalizátor a druhý hráč minimalizátor. Ak hernému plánu pridelíme hodnotiace skóre, jeden hráč sa pokúsi zvoliť stav hry s maximálnym skóre, zatiaľ čo druhý zvolí stav s minimálnym skóre.

Inými slovami, themaximalizátor pracuje na dosiahnutí najvyššieho skóre, zatiaľ čo minimalizátor sa snaží dosiahnuť najnižšie skóre pokusom o protiútoky.

Vychádza z herného konceptu s nulovým súčtom. V hre s nulovým súčtom sa celkové skóre úžitku rozdelí medzi hráčov. Výsledkom zvýšenia skóre jedného hráča je zníženie skóre iného hráča. Celkové skóre je teda vždy nulové. Aby jeden hráč vyhral, ​​musí druhý prehrať. Príklady takýchto hier sú šach, poker, dáma, piškvorky.

Zaujímavý fakt - v roku 1997 porazil šachový počítač IBM Deep Blue (vyrobený s Minimaxom) Garryho Kasparova (majstra sveta v šachu).

3. Minimaxový algoritmus

Naším cieľom je nájsť pre hráča najlepší krok. Aby sme tak mohli urobiť, môžeme si len zvoliť uzol s najlepším hodnotiacim skóre. Aby bol proces inteligentnejší, môžeme sa tiež pozerať dopredu a hodnotiť potenciálne ťahy súpera.

Na každý pohyb sa môžeme pozerať dopredu s toľkými pohybmi, koľko nám umožňuje náš výpočtový výkon. Algoritmus predpokladá, že súper hrá optimálne.

Technicky začneme od koreňového uzla a vyberieme najlepší možný uzol. Uzly hodnotíme na základe ich hodnotiacich skóre. V našom prípade môže funkcia vyhodnotenia priradiť skóre iba k uzlom výsledku (listy). Preto rekurzívne dosiahneme listy so skóre a späť skóre spropagujeme.

Zvážte nasledujúci herný strom:

Maximalizátorzačína koreňovým uzlom a zvolí ťah s maximálnym skóre. Iba listy majú, bohužiaľ, hodnotenie skóre so sebou, a preto musí algoritmus dosiahnuť uzly listov rekurzívne. V danom strome hier je momentálne na rade minimalizátor vyberte presun z uzlov listu, takže sa vyberú uzly s minimálnym skóre (tu, uzol 3 a 4). Stále vyberá najlepšie uzly, kým sa nedostane ku koreňovému uzlu.

Teraz formálne definujme kroky algoritmu:

  1. Postavte si kompletný herný strom
  2. Vyhodnoťte skóre listov pomocou hodnotiacej funkcie
  3. Záložné skóre od listov po koreň, berúc do úvahy typ hráča:
    • Pre maximálneho hráča vyberte dieťa s maximálnym počtom bodov
    • Pre najmenšieho hráča vyberte dieťa s minimálnym skóre
  4. V koreňovom uzle vyberte uzol s maximálnou hodnotou a vykonajte zodpovedajúci ťah

4. Implementácia

Teraz poďme implementovať hru.

V hre máme a halda s n počet kostí. Obaja hráči musia vyzdvihnúť 1,2 alebo 3 kosti podľa ich poradia. Hráč, ktorý si nemôže vziať žiadne kosti, prehráva. Každý hráč hrá optimálne. Vzhľadom na hodnotu n, napíšme AI.

Aby sme definovali pravidlá hry, budeme ich implementovať GameOfBones trieda:

trieda GameOfBones {statický zoznam getPossibleStates (int noOfBonesInHeap) {návrat IntStream.rangeClosed (1, 3) .boxed () .map (i -> noOfBonesInHeap - i) .filter (newHeapCount -> newHeapCount> = 0) .collect (Collectors. listovať()); }}

Ďalej tiež potrebujeme implementáciu pre Uzol a Strom triedy tiež:

verejná trieda Uzol {int noOfBones; boolean isMaxPlayer; int skóre; Zoznam detí; // setters and getters} public class Tree {Node root; // zakladatelia a prijímači}

Teraz implementujeme algoritmus. Vyžaduje to herný strom, aby ste sa dívali dopredu a našli najlepší krok. Implementujme to:

verejná trieda MiniMax {Strom stromu; public void constructTree (int noOfBones) {strom = nový strom (); Koreň uzla = nový uzol (noOfBones, true); tree.setRoot (root); constructTree (root); } 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);}}); }}

Teraz implementujeme checkWin metóda, ktorá bude simulovať rozohrávku výberom optimálnych pohybov pre oboch hráčov. Nastavuje skóre na:

  • +1, ak vyhrá maximalizátor
  • -1, ak vyhráva minimalizátor

The checkWin vráti true, ak vyhrá prvý hráč (v našom prípade - maximalizátor):

public boolean checkWin () {root uzla = tree.getRoot (); checkWin (root); návrat root.getScore () == 1; } private void checkWin (uzol uzla) {List children = node.getChildren (); boolean isMaxPlayer = node.isMaxPlayer (); children.forEach (child -> {if (child.getNoOfBones () == 0) {child.setScore (isMaxPlayer? 1: -1);} else {checkWin (child);}}); Uzol bestChild = findBestChild (isMaxPlayer, deti); node.setScore (bestChild.getScore ()); }

Tu je findBestChild metóda nájde uzol s maximálnym skóre, ak je hráč maximalizátorom. V opačnom prípade vráti dieťa s minimálnym skóre:

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

Na záver poďme implementovať testovací prípad s niektorými hodnotami n (počet kostí v kope):

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal () {miniMax.constructTree (6); boolovský výsledok = miniMax.checkWin (); assertTrue (výsledok); miniMax.constructTree (8); výsledok = miniMax.checkWin (); assertFalse (výsledok); }

5. Zlepšenie

Pre väčšinu problémov nie je možné zostaviť celý herný strom. V praxi môžeme vytvoriť čiastočný strom (skonštruovať strom iba na vopred určený počet úrovní).

Potom budeme musieť implementovať hodnotiaca funkcia, ktorý by mal byť schopný rozhodnúť, aký dobrý je aktuálny stav pre hráča.

Aj keď nebudeme stavať úplné hracie stromy, môže byť časovo náročné počítať pohyby pre hry s vysokým faktorom rozvetvenia.

Našťastie existuje možnosť nájsť optimálny pohyb bez preskúmania každého uzla herného stromu. Niektoré pobočky môžeme preskočiť podľa niektorých pravidiel a nebude to mať vplyv na konečný výsledok. Tento proces sa nazývaprerezávanie. Prerezávanie alfa-beta je prevládajúcou variantou algoritmu minimax.

6. Záver

Algoritmus Minimax je jedným z najpopulárnejších algoritmov pre počítačové stolové hry. Je široko používaný v ťahových hrách. Môže to byť dobrá voľba, keď majú hráči úplné informácie o hre.

Pre hry s mimoriadne vysokým faktorom rozvetvenia (napr. Hra GO) to nemusí byť najlepšia voľba. Avšak pri správnej implementácii to môže byť celkom inteligentná AI.

Úplný kód algoritmu nájdete ako vždy na GitHub.


$config[zx-auto] not found$config[zx-overlay] not found