Monte Carlo Tree Tic-Tac-Toe játék keresése Java-ban

1. Áttekintés

Ebben a cikkben a Monte Carlo Tree Search (MCTS) algoritmus és alkalmazásai.

Részletesen megvizsgáljuk annak fázisait a Java Tic-Tac-Toe játékának megvalósítása. Megtervezünk egy általános megoldást, amely sok más gyakorlati alkalmazásban is használható, minimális változtatás nélkül.

2. Bevezetés

Egyszerűen fogalmazva: a Monte Carlo fa keresés valószínűségi keresési algoritmus. Ez egy egyedülálló döntéshozó algoritmus, mivel hatékonysága nyitott környezetben, hatalmas lehetőségekkel bír.

Ha már ismeri az olyan játékelméleti algoritmusokat, mint a Minimax, akkor az aktuális állapot kiértékeléséhez funkcióra van szükség, és az optimális lépés megtalálásához számos szintet kell kiszámítania a játékfában.

Sajnos ezt nem lehet megtenni egy olyan játékban, mint a Go, ahol nagy az elágazási tényező (ami millió lehetőségeket eredményez, mivel a fa magassága növekszik), és nehéz jó értékelési funkciót írni annak kiszámításához, hogy a a jelenlegi állapot az.

A Monte Carlo fa keresés Monte Carlo módszert alkalmaz a játékfa keresésre. Mivel a játékállapotok véletlenszerű mintavételén alapul, nem kell minden egyes lehetőségből kijönnie. Továbbá nem feltétlenül igényel értékelést vagy jó heurisztikus funkciókat.

És egy gyors megjegyzés: ez forradalmasította a számítógép Go világát. 2016 márciusa óta elterjedt kutatási témává vált, mivel a Google AlphaGo (MCTS-sel és neurális hálózattal felépítve) megverte Lee Sedolt (a Go világbajnoka).

3. Monte Carlo fa keresési algoritmus

Most vizsgáljuk meg az algoritmus működését. Kezdetben egy keresési fát (játékfát) építünk egy gyökércsomópontgal, majd véletlenszerű bevezetésekkel tovább bővítjük. Ennek során fenntartjuk az egyes csomópontok látogatási és győzelmi számát.

Végül a legígéretesebb statisztikákkal rendelkező csomópontot fogjuk kiválasztani.

Az algoritmus négy fázisból áll; vizsgáljuk meg mindet részletesen.

3.1. Kiválasztás

Ebben a kezdeti fázisban az algoritmus egy gyökércsomópontból indul, és úgy választ ki egy gyermekcsomópontot, hogy az a maximális nyerési arány mellett válassza ki a csomópontot. Arra is szeretnénk ügyelni, hogy minden csomópontnak megfelelő esélyt kapjanak.

Az ötlet az optimális gyermekcsomópontok kiválasztásának folytatása, amíg el nem érjük a fa levélcsomópontját. Egy ilyen gyermekcsomópont kiválasztásának jó módja az UCT (a fákra alkalmazott felső bizalmi kötés) képlet használata:

Amiben

  • wén = a győzelmek száma a én-tharmadik lépés
  • nén = a szimulációk száma a én-tharmadik lépés
  • c = feltárási paraméter (elméletileg egyenlő √2)
  • t = a szülőcsomópont összes szimulációja

A képlet biztosítja, hogy egyetlen állam sem lesz éhezés áldozata, és az ígéretes ágakat is gyakrabban játssza, mint társaikat.

3.2. Terjeszkedés

Amikor már nem alkalmazhatja az UCT-t az utódcsomópont megtalálásához, kibővíti a játékfát azáltal, hogy az összes lehetséges állapotot hozzáfűzi a levélcsomóponthoz.

3.3. Szimuláció

A kibővítés után az algoritmus önkényesen kiválaszt egy gyermekcsomópontot, és egy véletlenszerű játékot szimulál a kiválasztott csomópontból, amíg el nem éri a játék eredményét. Ha a csomópontokat véletlenszerűen vagy félvéletlenszerűen választják ki a játék során, akkor ezt könnyű játéknak nevezzük. Kiválaszthatja a nehéz játékokat is, ha minőségi heurisztikákat vagy értékelési funkciókat ír meg.

3.4. Hátterjedés

Ezt frissítési fázisnak is nevezik. Miután az algoritmus elérte a játék végét, kiértékeli az állapotot, hogy kiderítse, melyik játékos nyert. Felfelé halad a gyökérig, és növeli az összes meglátogatott csomópont látogatási pontszámát. Ezenkívül frissíti az egyes csomópontok győzelmi pontszámát, ha az adott pozícióban lévő játékos megnyerte a játékot.

Az MCTS folyamatosan ismételgeti ezt a négy fázist, amíg bizonyos számú iteráció vagy valamilyen fix idő nem lesz.

Ebben a megközelítésben véletlenszerű mozgások alapján becsüljük meg az egyes csomópontok győztes pontszámát. Tehát nagyobb az iterációk száma, megbízhatóbbá válik a becslés. Az algoritmus-becslések kevésbé pontosak lesznek a keresés kezdetén, és megfelelő idő után folyamatosan javulnak. Ez megint csak a probléma típusától függ.

4. Száraz menet

Itt a csomópontok statisztikákat tartalmaznak, mint az összes látogatás / győzelem pontszám.

5. Végrehajtás

Most valósítsuk meg a Tic-Tac-Toe játékot - a Monte Carlo fa keresési algoritmus segítségével.

Megtervezünk egy általános megoldást az MCTS számára, amely sok más társasjátékhoz is felhasználható. Megnézzük a legtöbb kódot magában a cikkben.

Annak érdekében, hogy a magyarázat éles legyen, előfordulhat, hogy ki kell hagynunk néhány apró részletet (nem különösebben az MCTS-hez kapcsolódóan), de a teljes megvalósítást mindig itt találja.

Mindenekelőtt alapvető megvalósításra van szükségünk Fa és Csomópont osztályok fa keresési funkcióval:

public class Csomópont {State state; Csomópont szülő; List childArray; // seters and getters} public class Tree {Node root; }

Mivel minden csomópontnak megvan a problémájának sajátos állapota, valósítsuk meg a Állapot osztály is:

állami osztály Állami {Igazgatóság; int playerNo; int visitCount; kettős winScore; // a konstruktor, a getterek és a beállítók nyilvános listája getAllPossibleStates () {// az összes lehetséges állapot felsorolását az aktuális állapotból} public void randomPlay () {/ * listát kap az összes lehetséges pozícióról a táblán és véletlenszerűen játszik mozgatás * /}}

Most hajtsuk végre MonteCarloTreeSearch osztály, amely feladata lesz megtalálni a következő legjobb lépést az adott játékpozícióból:

nyilvános osztály MonteCarloTreeSearch {static final int WIN_SCORE = 10; int szint; int ellenfél; public Board findNextMove (Board board, int playerNo) {// meghatároz egy befejezési időt, amely végződési feltételként fog működni ellenfél = 3 - playerNo; Fafa = új Fa (); Csomópont rootNode = tree.getRoot (); rootNode.getState (). setBoard (tábla); rootNode.getState (). setPlayerNo (ellenfél); while (System.currentTimeMillis () 0) {nodeToExplore = ígéretesNode.getRandomChildNode (); } int playoutResult = simulateRandomPlayout (nodeToExplore); backPropogation (nodeToExplore, playoutResult); } Csomópont nyertesNode = gyökérNode.getChildWithMaxScore (); tree.setRoot (nyertesNode); return nyertesNode.getState (). getBoard (); }}

Itt az előre meghatározott időig mind a négy fázist iteráljuk, a végén pedig megbízható statisztikákkal rendelkező fát kapunk, hogy okosan döntsünk.

Most valósítsunk meg módszereket az összes fázisra.

A kiválasztási fázissal kezdjük amely megköveteli az UCT végrehajtását is:

privát csomópont selectPromisingNode (Csomópont rootNode) {Csomópont csomópont = rootNode; while (node.getChildArray (). size ()! = 0) {node = UCT.findBestNodeWithUCT (csomópont); } visszatér csomópont; }
public class UCT {public static double uctValue (int totalVisit, double nodeWinScore, int nodeVisit) {if (nodeVisit == 0) {return Integer.MAX_VALUE; } return ((dupla) nodeWinScore / (double) nodeVisit) + 1,41 * Math.sqrt (Math.log (totalVisit) / (double) nodeVisit); } public static Node findBestNodeWithUCT (Node node) {int parentVisit = node.getState (). getVisitCount (); return Collections.max (node.getChildArray (), Comparator.comparing (c -> uctValue (parentVisit, c.getState (). getWinScore (), c.getState (). getVisitCount ()))); }}

Ez a szakasz egy levélcsomópontot javasol, amelyet a bővítési szakaszban tovább kell bővíteni:

private void expandNode (Csomópont csomópont) {List possibleStates = node.getState (). getAllPossibleStates (); possibleStates.forEach (állapot -> {Csomópont newNode = új Csomópont (állapot); newNode.setParent (csomópont); newNode.getState (). setPlayerNo (node.getState (). getOpponent ()); node.getChildArray (). add (newNode);}); }

Ezután kódot írunk egy véletlenszerű csomópont kiválasztásához és a véletlenszerű játék szimulálásához. Továbbá lesz egy frissítés függvény a pontszám és a látogatások számának terjesztéséhez a levelektől a gyökerekig:

private void backPropogation (Node nodeToExplore, int playerNo) {Node tempNode = nodeToExplore; while (tempNode! = null) {tempNode.getState (). incrementVisit (); if (tempNode.getState (). getPlayerNo () == playerNo) {tempNode.getState (). addScore (WIN_SCORE); } tempNode = tempNode.getParent (); }} private int simulateRandomPlayout (Csomópont csomópont) {Csomópont tempNode = új Csomópont (csomópont); Állapot tempState = tempNode.getState (); int boardStatus = tempState.getBoard (). checkStatus (); if (boardStatus == ellenfél) {tempNode.getParent (). getState (). setWinScore (Integer.MIN_VALUE); visszatérő boardStatus; } while (boardStatus == Board.IN_PROGRESS) {tempState.togglePlayer (); tempState.randomPlay (); boardStatus = tempState.getBoard (). checkStatus (); } return boardStatus; }

Most elkészültünk az MCTS bevezetésével. Csak egy Tic-Tac-Toe-ra van szükségünk Tábla osztály megvalósítása. Figyelje meg, hogy más játékokat kell játszani a megvalósítással; Csak változtatnunk kell Tábla osztály.

public class Board {int [] [] boardValues; public static final int DEFAULT_BOARD_SIZE = 3; nyilvános statikus végső int IN_PROGRESS = -1; nyilvános statikus végső int DRAW = 0; nyilvános statikus végső int P1 = 1; nyilvános statikus végső int P2 = 2; // getters and setters public void performMove (int lejátszó, p pozíció) {this.totalMoves ++; boardValues ​​[p.getX ()] [p.getY ()] = játékos; } public int checkStatus () {/ * Értékelje, hogy megnyerték-e a játékot és visszatérnek-e. Ha döntetlen, akkor return 0 else return -1 * /} public list getEmptyPositions () {int size = this.boardValues.length; List emptyPositions = new ArrayList (); for (int i = 0; i <méret; i ++) {for (int j = 0; j <méret; j ++) {if (boardValues ​​[i] [j] == 0) emptyPositions.add (új pozíció (i, j)); }} return emptyPositions; }}

Most építettünk be egy olyan AI-t, amelyet nem lehet megverni a Tic-Tac-Toe-ben. Írjunk olyan egységet, amely megmutatja, hogy az AI és az AI mindig döntetlent eredményeznek:

@Test public void givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw () {Board board = new Board (); int játékos = Board.P1; int totalMoves = Board.DEFAULT_BOARD_SIZE * Board.DEFAULT_BOARD_SIZE; for (int i = 0; i <totalMoves; i ++) {tábla = mcts.findNextMove (tábla, játékos); if (board.checkStatus ()! = -1) {törés; } játékos = 3 - játékos; } int winStatus = board.checkStatus (); assertEquals (winStatus, Board.DRAW); }

6. Előnyök

  • Nem feltétlenül igényel taktikai ismereteket a játékról
  • Az általános MCTS-megvalósítás tetszőleges számú játékhoz felhasználható, kis módosítással
  • Olyan csomópontokra összpontosít, amelyek nagyobb eséllyel nyerik meg a játékot
  • Alkalmas nagy elágazási tényezővel járó problémákra, mivel nem pazarolja a számításokat az összes lehetséges ágra
  • Az algoritmus megvalósítása nagyon egyszerű
  • A végrehajtás bármikor leállítható, és ez még mindig a következő legjobb állapotot fogja javasolni

7. Hátrány

Ha az MCTS-t alapértelmezésben fejlesztés nélkül használják, akkor lehet, hogy nem javasol ésszerű lépéseket. Ez akkor fordulhat elő, ha a csomópontokat nem látogatják meg megfelelően, ami pontatlan becsléseket eredményez.

Az MCTS azonban bizonyos technikákkal javítható. Tartományspecifikus és tartományfüggetlen technikákat is magában foglal.

A tartományspecifikus technikákban a szimulációs szakasz realisztikusabb játékokat hoz létre, mint sztochasztikus szimulációk. Noha megköveteli a játék specifikus technikáinak és szabályainak ismeretét.

8. Összefoglalás

Első pillantásra nehéz bízni abban, hogy a véletlenszerű döntésekre támaszkodó algoritmus intelligens mesterséges intelligenciához vezethet. Az MCTS átgondolt megvalósítása azonban valóban megoldást kínálhat számunkra, amely sok játékban, valamint döntéshozatali problémákban is használható.

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