streamalism.org

1. Overzicht

In dit artikel gaan we de Monte Carlo Tree Search (MCTS) -algoritme en zijn toepassingen.

We zullen de fasen in detail bekijken door het implementeren van het spel Tic-Tac-Toe in Java. We zullen een algemene oplossing ontwerpen die kan worden gebruikt in vele andere praktische toepassingen, met minimale wijzigingen.

2. Inleiding

Simpel gezegd, Monte Carlo-boomzoekopdrachten zijn een probabilistisch zoekalgoritme. Het is een uniek besluitvormingsalgoritme vanwege zijn efficiëntie in open omgevingen met enorm veel mogelijkheden.

Als je al bekend bent met speltheorie-algoritmen zoals Minimax, dan heeft het een functie nodig om de huidige toestand te evalueren, en het moet veel niveaus in de spelboom berekenen om de optimale zet te vinden.

Helaas is het niet haalbaar om dit te doen in een spel als Go waarin er een hoge vertakkingsfactor is (resulterend in miljoenen mogelijkheden naarmate de hoogte van de boom toeneemt), en het is moeilijk om een ​​goede evaluatiefunctie te schrijven om te berekenen hoe goed de huidige staat is.

Monte Carlo-boomonderzoek past de Monte Carlo-methode toe op het zoeken in de spelboom. Omdat het is gebaseerd op willekeurige steekproeven van gamestatussen, hoeft het niet met brute kracht uit elke mogelijkheid te komen. Het vereist ook niet noodzakelijk dat we een evaluatie of goede heuristische functies schrijven.

En, een korte kanttekening: het heeft een revolutie teweeggebracht in de wereld van computer Go. Sinds maart 2016 is het een veel voorkomend onderzoeksonderwerp geworden toen Google's AlphaGo (gebouwd met MCTS en neuraal netwerk) Lee Sedol (de wereldkampioen in Go) versloeg.

3. Monte Carlo Tree Search-algoritme

Laten we nu eens kijken hoe het algoritme werkt. In eerste instantie zullen we een lookahead-boom (gameboom) bouwen met een hoofdknooppunt, en daarna blijven we het uitbreiden met willekeurige uitrol. Tijdens het proces houden we het aantal bezoeken en het aantal winsten bij voor elk knooppunt.

Uiteindelijk gaan we het knooppunt selecteren met de meest veelbelovende statistieken.

Het algoritme bestaat uit vier fasen; laten we ze allemaal in detail bekijken.

3.1. Selectie

In deze beginfase begint het algoritme met een rootknooppunt en selecteert een kindknooppunt zodanig dat het het knooppunt met maximale winstpercentage kiest. We willen er ook voor zorgen dat elk knooppunt een eerlijke kans krijgt.

Het idee is om optimale onderliggende knooppunten te blijven selecteren totdat we de bladknoop van de boom bereiken. Een goede manier om zo'n kindknooppunt te selecteren, is door de UCT-formule (Upper Confidence Bound toegepast op bomen) te gebruiken:

Waarin

• w_ik = aantal overwinningen na de ik-de zet
• n_ik = aantal simulaties na de ik-de zet
• c = verkenningsparameter (theoretisch gelijk aan √2)
• t = totaal aantal simulaties voor het bovenliggende knooppunt

De formule zorgt ervoor dat geen enkele staat het slachtoffer wordt van uithongering en speelt ook vaker op veelbelovende takken dan hun tegenhangers.

3.2. Uitbreiding

Wanneer het UCT niet langer kan toepassen om het opvolgknooppunt te vinden, breidt het de spelboom uit door alle mogelijke toestanden van het bladknooppunt toe te voegen.

3.3. Simulatie

Na de uitbreiding kiest het algoritme willekeurig een kindknooppunt en simuleert het een willekeurig spel van het geselecteerde knooppunt totdat het de resulterende staat van het spel bereikt. Als knooppunten willekeurig of semi-willekeurig worden gekozen tijdens het uitspelen, wordt dit light play out genoemd. U kunt ook kiezen voor zware play-out door kwaliteitsheuristieken of evaluatiefuncties te schrijven.

3.4. Backpropagation

Dit wordt ook wel een updatefase genoemd. Zodra het algoritme het einde van het spel bereikt, evalueert het de staat om erachter te komen welke speler heeft gewonnen. Het gaat omhoog naar de root en verhoogt de bezoekscore voor alle bezochte knooppunten. Het werkt ook de winscore voor elk knooppunt bij als de speler voor die positie de play-out heeft gewonnen.

MCTS blijft deze vier fasen herhalen tot een bepaald aantal iteraties of een vaste hoeveelheid tijd.

Bij deze benadering schatten we de winnende score voor elk knooppunt op basis van willekeurige bewegingen. Dus hoe hoger het aantal iteraties, hoe betrouwbaarder de schatting wordt. De algoritme-schattingen zullen aan het begin van een zoekopdracht minder nauwkeurig zijn en na voldoende tijd blijven verbeteren. Nogmaals, het hangt alleen af ​​van het type probleem.

4. Drooglopen

Hier bevatten knooppunten statistieken als totale bezoeken / overwinningsscore.

5. Implementatie

Laten we nu een spelletje Tic-Tac-Toe implementeren - met behulp van het Monte Carlo-boomzoekalgoritme.

We zullen een algemene oplossing voor MCTS ontwerpen die ook voor veel andere bordspellen kan worden gebruikt. We zullen de meeste code in het artikel zelf bekijken.

Hoewel om de uitleg helder te maken, kunnen we enkele kleine details overslaan (niet specifiek gerelateerd aan MCTS), maar u kunt hier altijd de volledige implementatie vinden.

Allereerst hebben we een basisimplementatie nodig voor Boom en Knooppunt klassen om een ​​boomzoekfunctie te hebben:

openbare klasse Node {State state; Bovenliggende knooppunt; Lijst childArray; // setters and getters} public class Tree {Node root; }

Aangezien elk knooppunt een bepaalde toestand van het probleem heeft, implementeren we een Staat klasse ook:

openbare klasse Staat {Board board; int playerNo; int visitCount; dubbele winScore; // kopieer constructor, getters en setters openbare lijst getAllPossibleStates () {// stelt een lijst samen van alle mogelijke toestanden van de huidige staat} public void randomPlay () {/ * verkrijg een lijst met alle mogelijke posities op het bord en speel een willekeurige Actie */ } }

Laten we nu implementeren MonteCarloTreeSearch klasse, die verantwoordelijk is voor het vinden van de volgende beste zet vanaf de gegeven spelpositie:

openbare klasse MonteCarloTreeSearch {statische finale int WIN_SCORE = 10; int niveau; int tegenstander; public Board findNextMove (Board board, int playerNo) {// definieer een eindtijd die zal fungeren als een beëindigende voorwaarde tegenstander = 3 - playerNo; Tree tree = nieuwe Tree (); Knooppunt rootNode = tree.getRoot (); rootNode.getState (). setBoard (bord); rootNode.getState (). setPlayerNo (tegenstander); while (System.currentTimeMillis () 0) {nodeToExplore = promisingNode.getRandomChildNode (); } int playoutResult = simulateRandomPlayout (nodeToExplore); backPropogation (nodeToExplore, playoutResult); } Knooppunt winnerNode = rootNode.getChildWithMaxScore (); tree.setRoot (winnerNode); return winnerNode.getState (). getBoard (); }}

Hier blijven we alle vier fasen herhalen tot de vooraf gedefinieerde tijd, en aan het einde krijgen we een boom met betrouwbare statistieken om een ​​slimme beslissing te nemen.

Laten we nu methoden implementeren voor alle fasen.

We beginnen met de selectiefase die ook UCT-implementatie vereist:

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

openbare klasse UCT {openbare statische dubbele uctValue (int totalVisit, dubbele nodeWinScore, int nodeVisit) {if (nodeVisit == 0) {return Integer.MAX_VALUE; } return ((dubbel) nodeWinScore / (dubbel) nodeVisit) + 1,41 * Math.sqrt (Math.log (totalVisit) / (dubbel) nodeVisit); } openbare statische 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 ()))); }}

Deze fase beveelt een leaf-node aan die in de uitbreidingsfase verder moet worden uitgebreid:

private void expandNode (Knooppunt knooppunt) {Lijst mogelijkeStaten = knooppunt.getState (). getAllPossibleStates (); PossibleStates.forEach (state -> {Node newNode = new Node (state); newNode.setParent (node); newNode.getState (). setPlayerNo (node.getState (). getOpponent ()); node.getChildArray (). add (newNode);}); }

Vervolgens schrijven we code om een ​​willekeurig knooppunt te kiezen en daaruit een willekeurig spel te simuleren. We zullen ook een bijwerken functie om de score en het aantal bezoeken te verspreiden, beginnend van blad tot wortel:

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 (Node node) {Node tempNode = new Node (node); Staat tempState = tempNode.getState (); int boardStatus = tempState.getBoard (). checkStatus (); if (boardStatus == tegenstander) {tempNode.getParent (). getState (). setWinScore (Integer.MIN_VALUE); terugkeer boardStatus; } while (boardStatus == Board.IN_PROGRESS) {tempState.togglePlayer (); tempState.randomPlay (); boardStatus = tempState.getBoard (). checkStatus (); } return boardStatus; }

Nu zijn we klaar met de implementatie van MCTS. Alles wat we nodig hebben, is een Tic-Tac-Toe-specifiek Bord klasse implementatie. Merk op dat om andere spellen te spelen met onze implementatie; We moeten gewoon veranderen Bord klasse.

openbare klasse Board {int [] [] boardValues; openbare statische laatste int DEFAULT_BOARD_SIZE = 3; openbare statische finale int IN_PROGRESS = -1; openbare statische definitieve int DRAW = 0; openbare statische finale int P1 = 1; openbare statische finale int P2 = 2; // getters en setters public void performMove (int player, Position p) {this.totalMoves ++; boardValues ​​[p.getX ()] [p.getY ()] = speler; } public int checkStatus () {/ * Evalueer of de game is gewonnen en geef de winnaar terug. Als het draw is retourneer 0, anders retourneer -1 * /} openbare lijst getEmptyPositions () {int size = this.boardValues.length; Lijst emptyPositions = nieuwe ArrayList (); for (int i = 0; i <size; i ++) {for (int j = 0; j <size; j ++) {if (boardValues ​​[i] [j] == 0) emptyPositions.add (nieuwe positie (i, j)); }} return emptyPositions; }}

We hebben zojuist een AI geïmplementeerd die niet te verslaan is in Tic-Tac-Toe. Laten we een eenheidscasus schrijven die aantoont dat AI versus AI altijd zal resulteren in een gelijkspel:

@Test openbare leegte gegevenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw () {Board board = nieuw 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); if (board.checkStatus ()! = -1) {pauze; } player = 3 - speler; } int winStatus = board.checkStatus (); assertEquals (winStatus, Board.DRAW); }

6. Voordelen

• Het vereist niet per se tactische kennis over het spel
• Een algemene MCTS-implementatie kan met weinig aanpassingen worden hergebruikt voor een willekeurig aantal games
• Richt zich op knooppunten met een grotere kans om het spel te winnen
• Geschikt voor problemen met een hoge vertakkingsfactor, omdat het geen berekeningen op alle mogelijke takken verspilt
• Algoritme is heel eenvoudig te implementeren
• De uitvoering kan op elk gewenst moment worden gestopt en het zal nog steeds de volgende beste status voorstellen die tot nu toe is berekend

7. Nadeel

Als MCTS in zijn basisvorm zonder enige verbeteringen wordt gebruikt, kan het zijn dat het geen redelijke zetten suggereert. Het kan gebeuren als knooppunten niet voldoende worden bezocht, wat resulteert in onnauwkeurige schattingen.

MCTS kan echter met enkele technieken worden verbeterd. Het omvat zowel domeinspecifieke als domeinonafhankelijke technieken.

In domeinspecifieke technieken produceert de simulatiefase meer realistische play-outs in plaats van stochastische simulaties. Het vereist echter kennis van spelspecifieke technieken en regels.

8. Samenvatting

Op het eerste gezicht is het moeilijk te vertrouwen dat een algoritme dat vertrouwt op willekeurige keuzes, kan leiden tot slimme AI. Een doordachte implementatie van MCTS kan ons echter wel een oplossing bieden die zowel in veel games als bij besluitvormingsproblemen kan worden gebruikt.

Zoals altijd is de volledige code voor het algoritme te vinden op GitHub.