streamalism.org

1. Oversigt

I denne artikel skal vi udforske Monte Carlo Tree Search (MCTS) algoritme og dets applikationer.

Vi vil se på dens faser i detaljer ved implementering af spillet Tic-Tac-Toe i Java. Vi designer en generel løsning, der kan bruges i mange andre praktiske anvendelser med minimale ændringer.

2. Introduktion

Kort sagt, Monte Carlo-træsøgning er en sandsynlig søgealgoritme. Det er en unik beslutningstagningsalgoritme på grund af dens effektivitet i åbne miljøer med enorme muligheder.

Hvis du allerede er bekendt med spilteori-algoritmer som Minimax, kræver det en funktion for at evaluere den aktuelle tilstand, og den skal beregne mange niveauer i spilletræet for at finde det optimale træk.

Desværre er det ikke muligt at gøre det i et spil som Go, hvor der er høj forgreningsfaktor (hvilket resulterer i millioner af muligheder, når træets højde øges), og det er svært at skrive en god evalueringsfunktion for at beregne, hvor god den er nuværende tilstand er.

Monte Carlo-træsøgning anvender Monte Carlo-metoden til spilletræssøgningen. Da det er baseret på tilfældig prøveudtagning af spiltilstande, behøver det ikke brute force sig vej ud af hver mulighed. Det kræver heller ikke nødvendigvis, at vi skriver en evaluering eller gode heuristiske funktioner.

Og en hurtig sidebemærkning - den revolutionerede computeren Go's verden. Siden marts 2016 er det blevet et udbredt forskningsemne, da Googles AlphaGo (bygget med MCTS og neuralt netværk) slog Lee Sedol (verdensmesteren i Go).

3. Algoritme til Monte Carlo-træsøgning

Lad os nu undersøge, hvordan algoritmen fungerer. Oprindeligt bygger vi et lookahead-træ (spiltræ) med en rodnode, og derefter fortsætter vi med at udvide det med tilfældige udrulninger. I processen opretholder vi antallet af besøg og antallet af vinder for hver node.

I sidste ende skal vi vælge den node med mest lovende statistik.

Algoritmen består af fire faser; lad os udforske dem alle i detaljer.

3.1. Udvælgelse

I denne indledende fase starter algoritmen med en rodnode og vælger en undernode, så den vælger noden med maksimal gevinsthastighed. Vi ønsker også at sikre, at hver knude får en rimelig chance.

Ideen er at fortsætte med at vælge optimale barneknuder, indtil vi når træets bladknude. En god måde at vælge en sådan barneknude på er at bruge formlen UCT (Upper Confidence Bound anvendt på træer):

Hvori

• w_jeg = antal sejre efter jeg-th træk
• n_jeg = antal simuleringer efter jeg-th træk
• c = udforskningsparameter (teoretisk lig √2)
• t = samlet antal simuleringer for den overordnede node

Formlen sikrer, at ingen stat bliver offer for sult, og den spiller også lovende grene oftere end deres kolleger.

3.2. Udvidelse

Når det ikke længere kan anvende UCT for at finde efterfølgernoden, udvider det spilletræet ved at tilføje alle mulige tilstande fra bladnoden.

3.3. Simulation

Efter udvidelse vælger algoritmen et underordnet knudepunkt vilkårligt, og det simulerer et randomiseret spil fra det valgte knudepunkt, indtil det når den resulterende tilstand af spillet. Hvis noder vælges tilfældigt eller semi-tilfældigt under afspilningen, kaldes det let afspilning. Du kan også vælge kraftig afspilning ved at skrive kvalitetsheuristikker eller evalueringsfunktioner.

3.4. Backpropagation

Dette er også kendt som en opdateringsfase. Når algoritmen når slutningen af ​​spillet, evaluerer den tilstanden for at finde ud af, hvilken spiller der har vundet. Det krydser opad til roden og stigninger i besøgsscore for alle besøgte noder. Det opdaterer også gevinstscore for hver node, hvis spilleren til den position har vundet playout.

MCTS gentager disse fire faser indtil et fast antal gentagelser eller et bestemt tidsrum.

I denne tilgang estimerer vi vinderscore for hver node baseret på tilfældige træk. Så højere antallet af iterationer, mere pålideligt bliver estimatet. Algoritmestimaterne vil være mindre nøjagtige i starten af ​​en søgning og fortsætte med at forbedre efter tilstrækkelig tid. Igen afhænger det udelukkende af typen af ​​problemet.

4. Tørkørsel

Her indeholder noder statistik som total besøg / vind-score.

5. Implementering

Lad os nu implementere et spil Tic-Tac-Toe - ved hjælp af Monte Carlo-træ-søgealgoritme.

Vi designer en generaliseret løsning til MCTS, som også kan bruges til mange andre brætspil. Vi ser på det meste af koden i selve artiklen.

Skønt for at gøre forklaringen skarp, skal vi muligvis springe nogle mindre detaljer over (ikke særlig relateret til MCTS), men du kan altid finde den komplette implementering her.

Først og fremmest har vi brug for en grundlæggende implementering til Træ og Node klasser for at have en træsøgningsfunktionalitet:

offentlig klasse Node {State state; Nodeforælder; Liste barnArray; // setters og getters} public class Tree {Node rod; }

Da hver knude har en bestemt tilstand af problemet, lad os implementere en Stat klasse også:

offentlig klasse State {Board board; int playerNo; int visitCount; dobbelt winScore; // kopi konstruktør, getters og setters offentlige Liste getAllPossibleStates () {// konstruerer en liste over alle mulige tilstande fra nuværende tilstand} offentlig ugyldig randomPlay () {/ * få en liste over alle mulige positioner på tavlen og spil en tilfældig bevæge sig */ } }

Lad os nu implementere MonteCarloTreeSearch klasse, som er ansvarlig for at finde det næstbedste træk fra den givne spilposition:

offentlig klasse MonteCarloTreeSearch {statisk endelig int WIN_SCORE = 10; int niveau; int modstander; public Board findNextMove (Board board, int playerNo) {// definer en sluttid, der fungerer som en afsluttende tilstand modstander = 3 - playerNo; Trætræ = nyt træ (); Node rootNode = tree.getRoot (); rootNode.getState (). setBoard (bord); rootNode.getState (). setPlayerNo (modstander); mens (System.currentTimeMillis () 0) {nodeToExplore = promisingNode.getRandomChildNode (); } int playoutResult = simulateRandomPlayout (nodeToExplore); backPropogation (nodeToExplore, playoutResult); } Node winnerNode = rootNode.getChildWithMaxScore (); tree.setRoot (vinderNode); returner winnerNode.getState (). getBoard (); }}

Her fortsætter vi med at gentage over alle de fire faser indtil det foruddefinerede tidspunkt, og i slutningen får vi et træ med pålidelige statistikker til at tage en smart beslutning.

Lad os nu implementere metoder til alle faser.

Vi starter med udvælgelsesfasen hvilket også kræver UCT-implementering:

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

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 fase anbefaler en bladknude, som skal udvides yderligere i ekspansionsfasen:

privat ugyldigt expandNode (Node-node) {Liste muligStates = node.getState (). getAllPossibleStates (); possibleStates.forEach (state -> {Node newNode = new Node (state); newNode.setParent (node); newNode.getState (). setPlayerNo (node.getState (). getOpponent ()); node.getChildArray (). add (newNode);}); }

Dernæst skriver vi kode for at vælge en tilfældig node og simulere en tilfældig afspilning fra den. Vi vil også have en opdatering funktion til at udbrede score og besøgstælling startende fra blad til rod:

privat ugyldigt 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 = ny Node (node); Tilstand tempState = tempNode.getState (); int boardStatus = tempState.getBoard (). checkStatus (); hvis (boardStatus == modstander) {tempNode.getParent (). getState (). setWinScore (Integer.MIN_VALUE); retur bordStatus; } mens (boardStatus == Board.IN_PROGRESS) {tempState.togglePlayer (); tempState.randomPlay (); boardStatus = tempState.getBoard (). checkStatus (); } returbrætStatus; }

Nu er vi færdige med implementeringen af ​​MCTS. Alt, hvad vi har brug for, er en Tic-Tac-Toe-bestemt Bestyrelse klasseimplementering. Bemærk, at for at spille andre spil med vores implementering; Vi skal bare ændre Bestyrelse klasse.

public class Board {int [] [] boardValues; offentlig statisk endelig int DEFAULT_BOARD_SIZE = 3; offentlig statisk endelig int IN_PROGRESS = -1; offentlig statisk endelig int DRAW = 0; offentlig statisk endelig int P1 = 1; offentlig statisk endelig int P2 = 2; // getters og setters public void performMove (int player, Position p) {this.totalMoves ++; boardValues ​​[p.getX ()] [p.getY ()] = spiller; } public int checkStatus () {/ * Evaluer, om spillet er vundet og returner vinder. Hvis det er tegne returnere 0 andet returnere -1 * /} offentlig liste getEmptyPositions () {int størrelse = this.boardValues.length; Liste tomPositioner = ny ArrayList (); for (int i = 0; i <størrelse; i ++) {for (int j = 0; j <størrelse; j ++) {hvis (boardValues ​​[i] [j] == 0) emptyPositions.add (ny position (i, j)); }} returner tommePositioner; }}

Vi har lige implementeret en AI, som ikke kan slå i Tic-Tac-Toe. Lad os skrive en enhedssag, der viser, at AI vs. AI altid vil resultere i uafgjort:

@Test offentlig ugyldighed givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw () {Board board = new Board (); int player = 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. Fordele

• Det kræver ikke nødvendigvis nogen taktisk viden om spillet
• En generel MCTS-implementering kan genbruges til et hvilket som helst antal spil med lille ændring
• Fokuserer på noder med større chancer for at vinde spillet
• Velegnet til problemer med høj forgreningsfaktor, da det ikke spilder beregninger på alle mulige grene
• Algoritme er meget ligetil at implementere
• Eksekvering kan stoppes til enhver tid, og det vil stadig antyde den hidtil bedste beregnede tilstand

7. Ulempe

Hvis MCTS bruges i sin grundform uden forbedringer, foreslår det muligvis ikke rimelige træk. Det kan ske, hvis noder ikke besøges tilstrækkeligt, hvilket resulterer i unøjagtige estimater.

MCTS kan dog forbedres ved hjælp af nogle teknikker. Det involverer domænespecifikke såvel som domæneuafhængige teknikker.

I domænespecifikke teknikker producerer simuleringsfasen mere realistiske play outs snarere end stokastiske simuleringer. Selvom det kræver kendskab til spilspecifikke teknikker og regler.

8. Resume

Ved første øjekast er det svært at stole på, at en algoritme, der er afhængig af tilfældige valg, kan føre til smart AI. Imidlertid kan tankevækkende implementering af MCTS faktisk give os en løsning, der kan bruges i mange spil såvel som i beslutningsproblemer.

Som altid kan den komplette kode til algoritmen findes på GitHub.