streamalism.org

1. Áttekintés

Ebben a cikkben a Minimax algoritmust és alkalmazásait fogjuk megvitatni az AI-ben. Mivel ez egy játékelméleti algoritmus, egy egyszerű játékot fogunk megvalósítani annak használatával.

Megbeszéljük az algoritmus használatának előnyeit és megnézzük, hogyan lehetne javítani rajta.

2. Bevezetés

A Minimax egy döntéshozó algoritmus, jellemzően körökön alapuló, kétjátékos játékokban használják. Az algoritmus célja az optimális következő lépés megtalálása.

Az algoritmusban az egyik játékost maximalizálónak, a másik játékost minimalizálónak nevezik. Ha értékelési pontszámot rendelünk a játéktáblához, az egyik játékos megpróbálja kiválasztani a legnagyobb pontszámú játékállapotot, míg a másik a legkisebb pontszámú állapotot.

Más szavakkal, aA maximalizáló a legmagasabb pontszám elérése érdekében működik, míg a minimalizáló a legalacsonyabb pontszámot próbálja megszerezni a mozgások ellensúlyozásával.

A nulla összegű játékkoncepción alapszik. Zéró összegű játékban a teljes hasznossági pontszám megoszlik a játékosok között. Az egyik játékos pontszámának növekedése a másik játékos pontszámának csökkenését eredményezi. Tehát a teljes pontszám mindig nulla. Ahhoz, hogy az egyik játékos nyerjen, a másiknak veszítenie kell. Ilyen játékok például a sakk, a póker, a dáma, a tic-tac-toe.

Érdekes tény - 1997-ben az IBM sakkjátékos számítógépe, a Deep Blue (a Minimax-szal készült) legyőzte Garri Kaszparovot (a sakk világbajnoka).

3. Minimax algoritmus

Célunk, hogy megtaláljuk a játékos számára a legjobb lépést. Ehhez egyszerűen kiválaszthatjuk a legjobb értékelési ponttal rendelkező csomópontot. A folyamat okosabbá tétele érdekében előre tekinthetünk és értékelhetjük az ellenfél potenciális lépéseit is.

Minden lépésnél annyi lépést tekinthetünk meg előre, ahány számítási teljesítményünk megengedi. Az algoritmus feltételezi, hogy az ellenfél optimálisan játszik.

Technikailag a gyökércsomópontból indulunk ki, és a lehető legjobb csomópontot választjuk. A csomópontokat értékelési pontszámuk alapján értékeljük. Esetünkben az értékelési funkció csak eredmény csomópontokhoz (levelekhez) rendelhet pontszámokat. Ezért rekurzívan pontszámokkal érjük el a leveleket, és visszafelé terjesztjük a pontszámokat.

Vegye figyelembe az alábbi játékfát:

Maximizera gyökércsomóponttal kezdődik és a maximális pontszámmal választja meg a lépést. Sajnos csak a levelek rendelkeznek értékelési pontszámokkal, ezért az algoritmusnak rekurzívan kell elérnie a levélcsomópontokat. Az adott játékfában jelenleg a minimalizátoron van a sor válasszon egy lépést a levélcsomópontok közül, így a minimális pontszámmal rendelkező csomópontok (itt a 3. és 4. csomópont) kiválasztásra kerülnek. Hasonlóan választja a legjobb csomópontokat, amíg el nem éri a gyökércsomópontot.

Most formálisan határozzuk meg az algoritmus lépéseit:

1. Építsd meg a teljes játékfát
2. Értékelje a levelek pontszámait az értékelő funkció segítségével
3. A mentési pontszámok a levelektől a gyökerekig, figyelembe véve a játékos típusát:
   • Max játékos esetén válassza ki a maximális pontszámot elérő gyermeket
   • Min játékos esetén válassza ki a gyermeket a minimális pontszámmal
4. A gyökércsomópontnál válassza ki a maximális értékű csomópontot, és hajtsa végre a megfelelő lépést

4. Végrehajtás

Most hajtsunk végre egy játékot.

A játékban van egy elhalmoz n csontok száma. Mindkét játékosnak muszáj vegyen fel 1,2 vagy 3 csontot viszont. Az a játékos, aki csontokat sem tud elvenni, elveszíti a játékot. Minden játékos optimálisan játszik. Tekintettel a n, írjunk egy AI-t.

A játékszabályok meghatározásához megvalósítjuk GameOfBones osztály:

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

Továbbá szükségünk van a Csomópont és Fa osztályok is:

public class Node {int noOfBones; logikai isMaxPlayer; int pontszám; Sorolja fel a gyermekeket; // seters and getters} public class Tree {Node root; // beállítók és szerelők}

Most megvalósítjuk az algoritmust. Ahhoz, hogy előre nézzen és megtalálja a legjobb lépést, játékfára van szükség. Vezessük be ezt:

nyilvános osztály MiniMax {Fafa; public void constructTree (int noOfBones) {fa = új fa (); Node root = új Node (noOfBones, true); fa.setRoot (gyökér); constructTree (gyökér); } private void constructTree (Node parentNode) {List listofPossibleHeaps = GameOfBones.getPossibleStates (parentNode.getNoOfBones ()); logikai isChildMaxPlayer =! parentNode.isMaxPlayer (); listofPossibleHeaps.forEach (n -> {Csomópont newNode = új Csomópont (n, isChildMaxPlayer); parentNode.addChild (newNode); if (newNode.getNoOfBones ()> 0) {constructTree (newNode);}}); }}

Most megvalósítjuk a checkWin módszer, amely szimulálja a játékot, kiválasztva mindkét játékos számára az optimális lépéseket. A pontszámot a következőkre állítja:

• +1, ha a maximalizáló nyer
• -1, ha a minimalizáló nyer

A checkWin igaz lesz, ha az első játékos (esetünkben - maximalizáló) nyer:

public boolean checkWin () {Csomópont gyökér = tree.getRoot (); checkWin (root); return root.getScore () == 1; } private void checkWin (Csomópont csomópont) {Gyerekek felsorolása = csomópont.getChildren (); logikai isMaxPlayer = csomópont.isMaxPlayer (); children.forEach (gyermek -> {if (child.getNoOfBones () == 0) {child.setScore (isMaxPlayer? 1: -1);} else {checkWin (gyermek);}}); Csomópont bestChild = findBestChild (isMaxPlayer, gyerekek); node.setScore (bestChild.getScore ()); }

Itt a findBestChild A módszer megtalálja a maximális ponttal rendelkező csomópontot, ha egy játékos maximalizáló. Ellenkező esetben a gyermeket a legkisebb pontszámmal adja vissza:

privát csomópont findBestChild (logikai isMaxPlayer, listázza a gyerekeket) {Comparator byScoreComparator = Comparator.comparing (Node :: getScore); return children.stream () .max (isMaxPlayer? byScoreComparator: byScoreComparator.reversed ()) .orElseThrow (NoSuchElementException :: new); }

Végül hajtsunk végre egy tesztesetet néhány értékkel n (a kupacban lévő csontok száma):

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal () {miniMax.constructTree (6); logikai eredmény = miniMax.checkWin (); assertTrue (eredmény); miniMax.constructTree (8); eredmény = miniMax.checkWin (); assertFalse (eredmény); }

5. Fejlesztés

A legtöbb probléma esetében nem kivitelezhető egy teljes játékfa felépítése. A gyakorlatban kidolgozhatunk egy részleges fát (csak előre meghatározott számú szintig szerkeszthetjük a fát).

Ezután végre kell hajtanunk egy értékelési funkció, aminek képesnek kell lennie arra, hogy eldöntse, mennyire jó a jelenlegi állapot a játékos számára.

Még ha nem is építünk teljes vadfákat, időigényes lehet a magas elágazási tényezővel rendelkező játékok mozgásának kiszámítása.

Szerencsére van egy lehetőség az optimális lépés megtalálásához, minden csomópont feltárása nélkül a vad fa. Néhány ágat kihagyhatunk néhány szabály betartásával, és ez nem befolyásolja a végeredményt. Ezt a folyamatot hívjákmetszés. Az alfa – béta metszés a minimax algoritmus egyik elterjedt változata.

6. Következtetés

A Minimax algoritmus az egyik legnépszerűbb algoritmus a számítógépes társasjátékok számára. Széles körben alkalmazzák a soron alapuló játékokat. Jó választás lehet, ha a játékosoknak teljes információval rendelkeznek a játékról.

Lehet, hogy nem a legjobb választás a kivételesen magas elágazási tényezővel rendelkező játékokhoz (pl. GO játék). Ennek ellenére a megfelelő megvalósítás miatt elég intelligens mesterséges intelligencia lehet.

Mint mindig, az algoritmus teljes kódja megtalálható a GitHub oldalon.