streamalism.org

1. Oversikt

I denne artikkelen skal vi utforske Monte Carlo Tree Search (MCTS) algoritme og dets applikasjoner.

Vi vil se på fasene i detalj innen implementering av spillet Tic-Tac-Toe i Java. Vi designer en generell løsning som kan brukes i mange andre praktiske bruksområder, med minimale endringer.

2. Introduksjon

Enkelt sagt, Monte Carlo-treesøk er en sannsynlig søkealgoritme. Det er en unik beslutningsalgoritme på grunn av effektiviteten i åpne miljøer med enorme muligheter.

Hvis du allerede er kjent med spillteori-algoritmer som Minimax, krever det en funksjon for å evaluere den nåværende tilstanden, og den må beregne mange nivåer i spilletreet for å finne det optimale trekket.

Dessverre er det ikke mulig å gjøre det i et spill som Go der det er høy forgreningsfaktor (noe som resulterer i millioner av muligheter når høyden på treet øker), og det er vanskelig å skrive en god evalueringsfunksjon for å beregne hvor god nåværende tilstand er.

Monte Carlo-treesøk bruker Monte Carlo-metoden på spilletreet. Siden det er basert på tilfeldig utvalg av spilltilstander, trenger det ikke å tøffe seg ut av hver mulighet. Dessuten krever det ikke nødvendigvis at vi skriver en evaluering eller gode heuristiske funksjoner.

Og en kort sidemerknad - den revolusjonerte datamaskinens Go-verden. Siden mars 2016 har det blitt et utbredt forskningstema da Googles AlphaGo (bygget med MCTS og nevrale nettverk) slo Lee Sedol (verdensmesteren i Go).

3. Monte Carlo-treesøkalgoritme

La oss nå utforske hvordan algoritmen fungerer. I utgangspunktet bygger vi et lookahead-tre (spilltre) med en rotnode, og deretter utvider vi det med tilfeldige utrullinger. I prosessen vil vi opprettholde besøkstall og vinnertall for hver node.

Til slutt skal vi velge noden med mest lovende statistikk.

Algoritmen består av fire faser; la oss utforske dem alle i detalj.

3.1. Utvalg

I denne innledende fasen starter algoritmen med en rotnode og velger en undernode slik at den plukker noden med maksimal vinningsgrad. Vi vil også sørge for at hver node får en god sjanse.

Tanken er å fortsette å velge optimale barnenoder til vi når bladknuten til treet. En god måte å velge en slik underordnet node er å bruke formelen UCT (Upper Confidence Bound applied to trees):

I hvilken

• w_Jeg = antall seire etter Jeg-te trekk
• n_Jeg = antall simuleringer etter Jeg-te trekk
• c = leteparameter (teoretisk lik √2)
• t = totalt antall simuleringer for foreldrenoden

Formelen sikrer at ingen stater blir utsatt for sult, og den spiller også lovende grener oftere enn deres kolleger.

3.2. Ekspansjon

Når den ikke lenger kan bruke UCT for å finne etterfølgernoden, utvider den spilletreet ved å legge til alle mulige tilstander fra bladnoden.

3.3. Simulering

Etter utvidelse velger algoritmen en barnekode vilkårlig, og den simulerer et randomisert spill fra valgt node til det når den resulterende tilstanden til spillet. Hvis noder blir valgt tilfeldig eller semi-tilfeldig under spillingen, kalles det light play out. Du kan også velge tungt spill ved å skrive kvalitetsheuristikk eller evalueringsfunksjoner.

3.4. Backpropagation

Dette er også kjent som en oppdateringsfase. Når algoritmen når slutten av spillet, evaluerer den staten for å finne ut hvilken spiller som har vunnet. Den krysser oppover til roten og trinn for besøk for alle besøkte noder. Den oppdaterer også gevinstpoeng for hver node hvis spilleren for den posisjonen har vunnet playout.

MCTS fortsetter å gjenta disse fire fasene til et fast antall gjentakelser eller noe fast tid.

I denne tilnærmingen estimerer vi vinnerscore for hver node basert på tilfeldige trekk. Så høyere antall iterasjoner, mer pålitelig blir estimatet. Algoritmestimatene vil være mindre nøyaktige i begynnelsen av et søk og fortsette å forbedres etter tilstrekkelig tid. Igjen avhenger det bare av typen problem.

4. Dry Run

Her inneholder noder statistikk som totalt besøk / vinn-poengsum.

5. Implementering

La oss nå implementere et spill Tic-Tac-Toe - ved hjelp av Monte Carlo-treesøkalgoritmen.

Vi designer en generalisert løsning for MCTS som også kan brukes til mange andre brettspill. Vi tar en titt på det meste av koden i selve artikkelen.

Selv om forklaringen blir skarp, må vi kanskje hoppe over noen mindre detaljer (ikke spesielt relatert til MCTS), men du kan alltid finne den komplette implementeringen her.

Først av alt trenger vi en grunnleggende implementering for Tre og Node klasser for å ha en treesøkfunksjonalitet:

offentlig klasse Node {State state; Node foreldre; Liste barnArray; // setters and getters} public class Tree {Node root; }

Siden hver node vil ha en bestemt tilstand av problemet, la oss implementere en Stat klasse også:

offentlig klasse State {Board board; int-spiller Nei; int visitCount; dobbelt vinnescore; // copy constructor, getters, and setters public List getAllPossibleStates () {// konstruerer en liste over alle mulige tilstander fra nåværende tilstand} public void randomPlay () {/ * få en liste over alle mulige posisjoner på tavlen og spill en random bevege seg */ } }

La oss nå implementere MonteCarloTreeSearch klasse, som vil være ansvarlig for å finne det neste beste trekket fra den gitte spillposisjonen:

offentlig klasse MonteCarloTreeSearch {statisk slutt int WIN_SCORE = 10; int nivå; int motstander; public Board findNextMove (Board board, int playerNo) {// definer en sluttid som vil fungere som en avslutningstilstand motstander = 3 - playerNo; Tree tree = new Tree (); Node rootNode = tree.getRoot (); rootNode.getState (). setBoard (bord); rootNode.getState (). setPlayerNo (motstander); mens (System.currentTimeMillis () 0) {nodeToExplore = promisingNode.getRandomChildNode (); } int playoutResult = simulateRandomPlayout (nodeToExplore); backPropogation (nodeToExplore, playoutResult); } Node winnerNode = rootNode.getChildWithMaxScore (); tree.setRoot (winnerNode); returner winnerNode.getState (). getBoard (); }}

Her fortsetter vi å itere over alle de fire fasene til den forhåndsdefinerte tiden, og til slutt får vi et tre med pålitelig statistikk for å ta en smart beslutning.

La oss nå implementere metoder for alle fasene.

Vi starter med utvelgelsesfasen som også krever UCT-implementering:

privat Node selectPromisingNode (Node rootNode) {Node node = rootNode; mens (node.getChildArray (). størrelse ()! = 0) {node = UCT.findBestNodeWithUCT (node); } retur node; }

offentlig klasse UCT {public static double uctValue (int totalVisit, double nodeWinScore, int nodeVisit) {if (nodeVisit == 0) {return Integer.MAX_VALUE; } returner ((dobbelt) nodeWinScore / (dobbelt) nodeVisit) + 1,41 * Math.sqrt (Math.log (totalVisit) / (dobbelt) nodeVisit); } offentlig statisk Node findBestNodeWithUCT (Node node) {int parentVisit = node.getState (). getVisitCount (); returner Collections.max (node.getChildArray (), Comparator.comparing (c -> uctValue (parentVisit, c.getState (). getWinScore (), c.getState (). getVisitCount ()))); }}

Denne fasen anbefaler en bladnode som bør utvides ytterligere i utvidelsesfasen:

private void expandNode (Node node) {List possibleStates = node.getState (). getAllPossibleStates (); possibleStates.forEach (state -> {Node newNode = new Node (state); newNode.setParent (node); newNode.getState (). setPlayerNo (node.getState (). getOpponent ()); node.getChildArray (). add (newNode);}); }

Deretter skriver vi kode for å velge en tilfeldig node og simulere en tilfeldig avspilling fra den. Vi vil også ha en Oppdater funksjon for å forplante poengsum og besøkstall fra blad til rot:

privat ugyldig backPropogation (Node nodeToExplore, int playerNo) {Node tempNode = nodeToExplore; mens (tempNode! = null) {tempNode.getState (). incrementVisit (); hvis (tempNode.getState (). getPlayerNo () == playerNo) {tempNode.getState (). addScore (WIN_SCORE); } tempNode = tempNode.getParent (); }} private int simulateRandomPlayout (Node node) {Node tempNode = new Node (node); State tempState = tempNode.getState (); int boardStatus = tempState.getBoard (). checkStatus (); hvis (boardStatus == motstander) {tempNode.getParent (). getState (). setWinScore (Integer.MIN_VALUE); retur bordStatus; } mens (boardStatus == Board.IN_PROGRESS) {tempState.togglePlayer (); tempState.randomPlay (); boardStatus = tempState.getBoard (). checkStatus (); } returbrettStatus; }

Nå er vi ferdige med implementeringen av MCTS. Alt vi trenger er en spesiell Tic-Tac-Toe Borde klasseimplementering. Legg merke til at å spille andre spill med implementeringen vår; Vi trenger bare å endre oss Borde klasse.

public class Board {int [] [] boardValues; offentlig statisk finale int DEFAULT_BOARD_SIZE = 3; offentlig statisk finale int IN_PROGRESS = -1; offentlig statisk slutt int DRAW = 0; offentlig statisk endelig int P1 = 1; offentlig statisk sluttint P2 = 2; // getters and setters public void performMove (int player, Position p) {this.totalMoves ++; boardValues ​​[p.getX ()] [p.getY ()] = spiller; } public int checkStatus () {/ * Evaluer om spillet er vunnet og returner vinneren. Hvis det er uavgjort, returner 0 annet tilbake -1 * /} offentlig liste getEmptyPositions () {int size = this.boardValues.length; Liste tomme posisjoner = ny ArrayList (); for (int i = 0; i <size; i ++) {for (int j = 0; j <size; j ++) {if (boardValues ​​[i] [j] == 0) emptyPositions.add (new Position (i, j)); }} returner tomme posisjoner; }}

Vi implementerte nettopp en AI som ikke kan bli slått i Tic-Tac-Toe. La oss skrive en enhetssak som demonstrerer at AI mot AI alltid vil resultere i uavgjort:

@Test offentlig ugyldighet givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw () {Board board = new Board (); int-spiller = Board.P1; int totalMoves = Board.DEFAULT_BOARD_SIZE * Board.DEFAULT_BOARD_SIZE; for (int i = 0; i <totalMoves; i ++) {board = mcts.findNextMove (board, player); hvis (board.checkStatus ()! = -1) {pause; } spiller = 3 - spiller; } int winStatus = board.checkStatus (); assertEquals (winStatus, Board.DRAW); }

6. Fordeler

• Det krever ikke nødvendigvis noen taktisk kunnskap om spillet
• En generell MCTS-implementering kan gjenbrukes for et hvilket som helst antall spill med liten modifikasjon
• Fokuserer på noder med større sjanser for å vinne spillet
• Egnet for problemer med høy forgreningsfaktor, da det ikke kaster bort beregninger på alle mulige grener
• Algoritme er veldig grei å implementere
• Utførelsen kan stoppes når som helst, og det vil fremdeles antyde den nest beste tilstanden som er beregnet så langt

7. Ulempe

Hvis MCTS brukes i sin grunnleggende form uten forbedringer, kan det hende at den ikke foreslår rimelige grep. Det kan skje hvis noder ikke besøkes tilstrekkelig, noe som resulterer i unøyaktige estimater.

Imidlertid kan MCTS forbedres ved hjelp av noen teknikker. Det involverer domenespesifikke så vel som domeneavhengige teknikker.

I domenespesifikke teknikker produserer simuleringsstadiet mer realistiske play outs i stedet for stokastiske simuleringer. Selv om det krever kunnskap om spillspesifikke teknikker og regler.

8. Oppsummering

Ved første øyekast er det vanskelig å stole på at en algoritme som stoler på tilfeldige valg kan føre til smart AI. Imidlertid kan gjennomtenkt implementering av MCTS virkelig gi oss en løsning som kan brukes i mange spill så vel som i beslutningsproblemer.

Som alltid kan den komplette koden for algoritmen finnes på GitHub.