streamalism.org

1. Pregled

U ovom ćemo članku istražiti Algoritam pretraživanja stabla Monte Carlo (MCTS) i njegove primjene.

Detaljno ćemo razmotriti njegove faze do implementirajući igru ​​Tic-Tac-Toe na Javi. Osmislit ćemo opće rješenje koje bi se moglo koristiti u mnogim drugim praktičnim primjenama, uz minimalne promjene.

2. Uvod

Jednostavno rečeno, traženje stabla Monte Carlo vjerojatni je algoritam pretraživanja. To je jedinstveni algoritam donošenja odluka zbog svoje učinkovitosti u otvorenim okruženjima s ogromnom količinom mogućnosti.

Ako ste već upoznati s algoritmima teorije igara kao što je Minimax, potrebna mu je funkcija za procjenu trenutnog stanja i mora izračunati mnogo razina u stablu igara kako bi pronašla optimalni potez.

Nažalost, to nije izvedivo u igri poput Go u kojoj postoji visok faktor grananja (što rezultira milijunima mogućnosti kako se visina stabla povećava), a teško je napisati dobru funkciju procjene kako bi se izračunalo koliko je dobar trenutno stanje je.

Pretraživanje stabla Monte Carlo primjenjuje metodu Monte Carlo na pretraživanje stabla igre. Kako se temelji na slučajnom uzorkovanju stanja igre, ne treba grubo forsirati svaku mogućnost. Također, ne zahtijeva nužno da napišemo ocjenu ili dobre heurističke funkcije.

I kratka napomena - revolucionirao je svijet računala Go. Od ožujka 2016. godine postala je prevladavajuća tema istraživanja jer je Googleov AlphaGo (izgrađen s MCTS-om i neuronskom mrežom) pobijedio Leeja Sedola (svjetskog prvaka u Go-u).

3. Algoritam pretraživanja stabla Monte Carlo

Sada, istražimo kako algoritam radi. U početku ćemo graditi lookahead stablo (stablo igre) s korijenskim čvorom, a zatim ćemo ga nastaviti širiti slučajnim predstavljanjima. U tom ćemo procesu održavati broj posjeta i broj pobjeda za svaki čvor.

Na kraju ćemo odabrati čvor s najperspektivnijim statistikama.

Algoritam se sastoji od četiri faze; istražimo ih sve u detalje.

3.1. Izbor

U ovoj početnoj fazi algoritam započinje s korijenskim čvorom i odabire podređeni čvor tako da odabere čvor s maksimalnom stopom dobitka. Također želimo biti sigurni da se svakom čvoru pruža poštena šansa.

Ideja je nastaviti s odabirom optimalnih podređenih čvorova dok ne dođemo do lisnog čvora stabla. Dobar način za odabir takvog podređenog čvora je upotreba UCT (gornja granica povjerenja primijenjena na stabla):

U kojem

• w_ja = broj pobjeda nakon ja-ti potez
• n_ja = broj simulacija nakon ja-ti potez
• c = parametar istraživanja (teoretski jednak √2)
• t = ukupan broj simulacija za nadređeni čvor

Formula osigurava da niti jedna država neće biti žrtva gladi, a igra i obećavajuće grane češće od svojih kolega.

3.2. Proširenje

Kad više ne može primijeniti UCT za pronalaženje čvora nasljednika, proširuje stablo igre dodavanjem svih mogućih stanja iz čvora lista.

3.3. Simulacija

Nakon proširenja, algoritam proizvoljno odabire podređeni čvor i simulira randomiziranu igru ​​odabranog čvora sve dok ne dosegne rezultirajuće stanje igre. Ako se čvorovi odaberu nasumično ili polu-nasumično tijekom play out-a, to se naziva light play out. Također se možete odlučiti za tešku igru ​​pisanjem kvalitetne heuristike ili funkcija procjene.

3.4. Povratno razmnožavanje

To je također poznato kao faza ažuriranja. Jednom kada algoritam dođe do kraja igre, procjenjuje stanje kako bi utvrdio koji je igrač pobijedio. Prelazi prema korijenu i povećava rezultat posjeta za sve posjećene čvorove. Također ažurira rezultat pobjede za svaki čvor ako je igrač na toj poziciji pobijedio u razigravanju.

MCTS ponavlja ove četiri faze sve do određenog broja ponavljanja ili određenog vremena.

U ovom pristupu procjenjujemo dobitni rezultat za svaki čvor na temelju slučajnih poteza. Dakle, što je veći broj ponavljanja, procjena postaje pouzdanija. Procjene algoritma bit će manje precizne na početku pretraživanja i poboljšavat će se nakon dovoljnog vremena. Opet, to ovisi isključivo o vrsti problema.

4. Suho trčanje

Ovdje čvorovi sadrže statistiku kao ukupan broj posjeta / pobjeda.

5. Provedba

Ajmo sada implementirati igru ​​Tic-Tac-Toe - koristeći algoritam pretraživanja stabla Monte Carlo.

Osmislit ćemo generalizirano rješenje za MCTS koje se može koristiti i za mnoge druge društvene igre. Pogledat ćemo većinu koda u samom članku.

Iako da bi objašnjenje postalo oštro, možda ćemo morati preskočiti neke manje detalje (koji nisu osobito povezani s MCTS-om), ali cjelovitu provedbu uvijek možete pronaći ovdje.

Prije svega, trebamo osnovnu implementaciju za Drvo i Čvor klase kako bi imali funkcionalnost pretraživanja stabla:

čvor javne klase {državno stanje; Nadređeni čvor; Popis childArray; // postavljači i getteri} drvo javne klase {Node root; }

Kako će svaki čvor imati određeno stanje problema, provedimo a država razred također:

državna klasa {odbor odbora; int playerNo; int visitCount; dvostruki winScore; // kopiraj konstruktor, gettere i postavljače javni popis getAllPossibleStates () {// gradi popis svih mogućih stanja iz trenutnog stanja} public void randomPlay () {/ * dobiti popis svih mogućih pozicija na ploči i igrati nasumično premjesti * /}}

Sad, krenimo MonteCarloTreeSearch klase, koja će biti odgovorna za pronalaženje sljedećeg najboljeg poteza s dane pozicije igre:

javna klasa MonteCarloTreeSearch {static final int WIN_SCORE = 10; int razina; int protivnik; javni Board findNextMove (Board board, int playerNo) {// definirajte vrijeme završetka koje će djelovati kao završni uvjet protivnika = 3 - playerNo; Stablo drveta = novo stablo (); Čvor rootNode = tree.getRoot (); rootNode.getState (). setBoard (ploča); rootNode.getState (). setPlayerNo (protivnik); while (System.currentTimeMillis () 0) {nodeToExplore = promisingNode.getRandomChildNode (); } int playoutResult = simulateRandomPlayout (nodeToExplore); backPropogation (nodeToExplore, playoutResult); } Čvor dobitnikNode = rootNode.getChildWithMaxScore (); tree.setRoot (winnerNode); vratiti returnNode.getState (). getBoard (); }}

Ovdje stalno ponavljamo sve četiri faze do unaprijed određenog vremena, a na kraju dobivamo stablo s pouzdanom statistikom za pametnu odluku.

Sada, provedimo metode za sve faze.

Krenut ćemo s fazom odabira što zahtijeva i provedbu UCT-a:

private Node selectPromisingNode (Node rootNode) {Node node = rootNode; while (node.getChildArray (). size ()! = 0) {node = UCT.findBestNodeWithUCT (čvor); } povratni čvor; }

javna klasa UCT {javni statički dvostruki uctValue (int totalVisit, dvostruki nodeWinScore, int nodeVisit) {if (nodeVisit == 0) {return Integer.MAX_VALUE; } return ((dvostruki) nodeWinScore / (dvostruki) nodeVisit) + 1,41 * Math.sqrt (Math.log (totalVisit) / (double) nodeVisit); } javni statički čvor findBestNodeWithUCT (čvor čvora) {int parentVisit = node.getState (). getVisitCount (); vratiti Collections.max (node.getChildArray (), Comparator.comparing (c -> uctValue (parentVisit, c.getState (). getWinScore (), c.getState (). getVisitCount ())))); }}

Ova faza preporučuje lisni čvor koji bi se trebao dalje proširiti u fazi širenja:

private void expandNode (čvor čvora) {Lista possibleStates = node.getState (). getAllPossibleStates (); possibleStates.forEach (state -> {Node newNode = new Node (state); newNode.setParent (node); newNode.getState (). setPlayerNo (node.getState (). getOpponent ()); node.getChildArray (). add (noviČvor);}); }

Dalje, pišemo kod da bi odabrali slučajni čvor i simulirali slučajno odigravanje iz njega. Također, imat ćemo i ažuriranje funkcija za širenje rezultata i broja posjeta počevši od lista do korijena:

private void backPropogation (Čvor nodeToExplore, int playerNo) {Čvor tempNode = nodeToExplore; while (tempNode! = null) {tempNode.getState (). incrementVisit (); if (tempNode.getState (). getPlayerNo () == playerNo) {tempNode.getState (). addScore (WIN_SCORE); } tempNode = tempNode.getParent (); }} private int simulateRandomPlayout (čvor čvora) {čvor tempNode = novi čvor (čvor); Stanje tempState = tempNode.getState (); int boardStatus = tempState.getBoard (). checkStatus (); if (boardStatus == protivnik) {tempNode.getParent (). getState (). setWinScore (Integer.MIN_VALUE); povratna pločaStatus; } while (boardStatus == Board.IN_PROGRESS) {tempState.togglePlayer (); tempState.randomPlay (); boardStatus = tempState.getBoard (). checkStatus (); } return boardStatus; }

Sad smo završili s implementacijom MCTS-a. Sve što trebamo je posebno Tic-Tac-Toe Odbor provedba razreda. Primijetite da igranje drugih igara s našom implementacijom; Samo se trebamo promijeniti Odbor razred.

javni razred Board {int [] [] boardValues; javni statički konačni int DEFAULT_BOARD_SIZE = 3; javni statički konačni int IN_PROGRESS = -1; javni statički konačni int DRAW = 0; javni statički konačni int P1 = 1; javni statički konačni int P2 = 2; // getteri i postavljači public void performMove (int player, Position p) {this.totalMoves ++; boardValues ​​[p.getX ()] [p.getY ()] = igrač; } public int checkStatus () {/ * Procijenite je li igra pobijeđena i vraćen je pobjednik. Ako je izvlačenje return 0 else return -1 * /} javni popis getEmptyPositions () {int size = this.boardValues.length; Popis emptyPositions = novi ArrayList (); for (int i = 0; i <size; i ++) {for (int j = 0; j <size; j ++) {if (boardValues ​​[i] [j] == 0) emptyPositions.add (novi položaj (i, j)); }} return emptyPositions; }}

Upravo smo implementirali AI koji se ne može pobijediti u Tic-Tac-Toe. Napišimo slučaj jedinice koji pokazuje da će AI nasuprot AI uvijek rezultirati neriješenim rezultatom:

@Test javna praznina givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw () {Board board = new Board (); int igrač = Board.P1; int totalMoves = Board.DEFAULT_BOARD_SIZE * Board.DEFAULT_BOARD_SIZE; for (int i = 0; i <totalMoves; i ++) {ploča = mcts.findNextMove (ploča, igrač); if (board.checkStatus ()! = -1) {break; } igrač = 3 - igrač; } int winStatus = board.checkStatus (); assertEquals (winStatus, Board.DRAW); }

6. Prednosti

• Ne zahtijeva nužno nikakvo taktičko znanje o igri
• Općenita implementacija MCTS-a može se ponovno koristiti za bilo koji broj igara s malo izmjena
• Fokusira se na čvorove s većim izgledima za pobjedu u igri
• Pogodno za probleme s visokim faktorom grananja jer ne troši proračune na svim mogućim granama
• Algoritam je vrlo jednostavan za primjenu
• Izvršenje se može zaustaviti u bilo kojem trenutku i još će predložiti sljedeće najbolje izračunato stanje do sada

7. nedostatak

Ako se MCTS koristi u osnovnom obliku bez ikakvih poboljšanja, možda neće predložiti razumne poteze. Može se dogoditi ako se čvorovi ne posjete na odgovarajući način što rezultira netočnim procjenama.

Međutim, MCTS se može poboljšati pomoću nekih tehnika. Uključuje tehnike specifične za domenu, kao i tehnike neovisne o domeni.

U tehnikama specifičnim za područje, faza simulacije daje realističnija igranja umjesto stohastičkih simulacija. Iako zahtijeva poznavanje tehnika i pravila specifičnih za igru.

8. Sažetak

Na prvi pogled teško je vjerovati da algoritam koji se oslanja na slučajne izbore može dovesti do pametne AI. Međutim, promišljena primjena MCTS-a zaista nam može pružiti rješenje koje se može koristiti u mnogim igrama, kao i u problemima donošenja odluka.

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