streamalism.org

1. Prehľad

V tomto článku sa chystáme preskúmať Algoritmus vyhľadávania stromov Monte Carlo (MCTS) a jeho aplikácií.

Jeho fázam sa podrobne pozrieme do implementácia hry Tic-Tac-Toe v Jave. Navrhneme všeobecné riešenie, ktoré by bolo možné s minimálnymi zmenami použiť v mnohých ďalších praktických aplikáciách.

2. Úvod

Jednoducho povedané, vyhľadávanie stromov v Monte Carle je pravdepodobnostný vyhľadávací algoritmus. Je to jedinečný rozhodovací algoritmus vďaka svojej účinnosti v otvorených prostrediach s obrovským množstvom možností.

Ak ste už oboznámení s algoritmami teórie hier, ako je Minimax, vyžaduje si funkciu na vyhodnotenie aktuálneho stavu a musí vypočítať veľa úrovní v strome hry, aby našiel optimálny pohyb.

Bohužiaľ to nie je možné urobiť v hre ako Go, v ktorej je vysoký faktor rozvetvenia (čo vedie k miliónom možností, ako sa zvyšuje výška stromu), a je ťažké napísať dobrú hodnotiacu funkciu na výpočet toho, aká dobrá súčasný stav je.

Pri hľadaní stromu Monte Carlo sa pri hľadaní stromu hry použije metóda Monte Carlo. Pretože je založený na náhodnom vzorkovaní stavov hry, nemusí si cestu z každej možnosti vybíjať hrubou silou. Tiež to nevyhnutne nevyžaduje, aby sme napísali hodnotenie alebo dobré heuristické funkcie.

A ešte krátka poznámka - priniesla revolúciu vo svete počítačov Go. Od marca 2016 sa stala prevládajúcou témou výskumu, pretože AlphaGo spoločnosti Google (postavené na MCTS a neurónovej sieti) porazili Lee Sedola (majster sveta v Go).

3. Algoritmus vyhľadávania stromu Monte Carlo

Poďme teraz preskúmať, ako algoritmus funguje. Spočiatku postavíme vyhľadávací strom (herný strom) s koreňovým uzlom a potom ho neustále rozširujeme náhodnými zavedeniami. V tomto procese budeme udržiavať počet návštev a počet výhier pre každý uzol.

Nakoniec vyberieme uzol s najsľubnejšou štatistikou.

Algoritmus pozostáva zo štyroch fáz; poďme ich preskúmať podrobne.

3.1. Výber

V tejto počiatočnej fáze algoritmus začína koreňovým uzlom a vyberie podradený uzol tak, aby vybral uzol s maximálnou mierou výhry. Chceme tiež zaistiť, aby každý uzol dostal spravodlivú šancu.

Myšlienkou je stále vyberať optimálne podriadené uzly, kým sa nedostaneme k listovému uzlu stromu. Dobrým spôsobom, ako vybrať takýto podradený uzol, je použiť vzorec UCT (Upper Confidence Bound applied to trees):

V ktorom

• w_i = počet výhier po i-th ťah
• n_i = počet simulácií po i-th ťah
• c = parameter skúmania (teoreticky rovný √2)
• t = celkový počet simulácií pre nadradený uzol

Vzorec zaisťuje, že žiadny štát nebude obeťou hladu, a tiež hrá nádejné odvetvia častejšie ako ich náprotivky.

3.2. Expanzia

Keď už nemôže použiť UCT na nájdenie nástupníckeho uzla, rozšíri herný strom pripojením všetkých možných stavov z listového uzla.

3.3. Simulácia

Po rozšírení algoritmus ľubovoľne vyberie podradený uzol a simuluje randomizovanú hru z vybraného uzla, kým nedosiahne výsledný stav hry. Ak sú uzly vybrané náhodne alebo čiastočne náhodne počas hrania, nazýva sa to ľahké hranie. Môžete sa tiež rozhodnúť pre náročné hranie napísaním kvalitnej heuristiky alebo hodnotiacich funkcií.

3.4. Spätné šírenie

Toto sa nazýva aj fáza aktualizácie. Akonáhle algoritmus dosiahne koniec hry, vyhodnotí stav a zistí, ktorý hráč vyhral. Prechádza hore ku koreňu a zvyšuje skóre návštevnosti pre všetky navštívené uzly. Aktualizuje tiež skóre víťazstva pre každý uzol, ak hráč na tejto pozícii vyhral playout.

MCTS neustále opakuje tieto štyri fázy, kým nedosiahne určitý pevný počet iterácií alebo určitý pevný čas.

V tomto prístupe odhadujeme výherné skóre pre každý uzol na základe náhodných ťahov. Čím vyšší je počet iterácií, tým spoľahlivejší je odhad. Odhady algoritmu budú na začiatku vyhľadávania menej presné a po dostatočnom čase sa budú naďalej zlepšovať. Závisí to opäť iba od typu problému.

4. Beh na sucho

Tu uzly obsahujú štatistiku ako celkové skóre návštev / výhier.

5. Implementácia

Teraz poďme implementovať hru Tic-Tac-Toe - pomocou algoritmu vyhľadávania stromov Monte Carlo.

Navrhneme zovšeobecnené riešenie pre MCTS, ktoré je možné využiť aj pre mnoho ďalších stolových hier. Na väčšinu kódu sa pozrieme v samotnom článku.

Aj keď je vysvetlenie ostré, možno budeme musieť preskočiť niektoré drobné podrobnosti (nijako zvlášť sa netýka MCTS), ale tu nájdete vždy úplnú implementáciu.

Najskôr potrebujeme základnú implementáciu pre Strom a Uzol triedy, aby mali funkciu vyhľadávania stromu:

public class Uzol {State state; Uzol rodič; Zoznam childArray; // setters and getters} public class Tree {Node root; }

Pretože každý uzol bude mať konkrétny stav problému, implementujme a Štát trieda tiež:

public class State {Board Board; int playerNo; int visitCount; dvojité winScore; // kopírovať konštruktor, getry a nastavovače public List getAllPossibleStates () {// vytvorí zoznam všetkých možných stavov z aktuálneho stavu} public void randomPlay () {/ * získa zoznam všetkých možných pozícií na doske a prehrá random presunúť * /}}

Teraz poďme implementovať MonteCarloTreeSearch trieda, ktorá bude zodpovedná za nájdenie ďalšieho najlepšieho ťahu z danej hernej pozície:

verejná trieda MonteCarloTreeSearch {statické konečné int WIN_SCORE = 10; úroveň int; int oponent; public Board findNextMove (Board board, int playerNo) {// definuje čas ukončenia, ktorý bude slúžiť ako konečná podmienka oponent = 3 - playerNo; Strom stromu = nový Strom (); Uzol rootNode = tree.getRoot (); rootNode.getState (). setBoard (doska); rootNode.getState (). setPlayerNo (súper); while (System.currentTimeMillis () 0) {nodeToExplore = promisingNode.getRandomChildNode (); } int playoutResult = simulateRandomPlayout (nodeToExplore); backPropogation (nodeToExplore, playoutResult); } Uzol winnerNode = rootNode.getChildWithMaxScore (); tree.setRoot (winnerNode); návrat winnerNode.getState (). getBoard (); }}

Tu pokračujeme v iterácii všetkých štyroch fáz až do vopred určeného času a na konci dostaneme strom so spoľahlivými štatistikami, aby sme sa mohli inteligentne rozhodnúť.

Teraz poďme implementovať metódy pre všetky fázy.

Začneme fázou výberu ktorý tiež vyžaduje implementáciu UCT:

private Node selectPromisingNode (Node rootNode) {Uzol uzol = rootNode; while (node.getChildArray (). size ()! = 0) {node = UCT.findBestNodeWithUCT (node); } návratový uzol; }

public class UCT {public static double uctValue (int totalVisit, double nodeWinScore, int nodeVisit) {if (nodeVisit == 0) {return Integer.MAX_VALUE; } návrat ((double) nodeWinScore / (double) nodeVisit) + 1,41 * Math.sqrt (Math.log (totalVisit) / (double) nodeVisit); } verejný statický uzol findBestNodeWithUCT (uzol uzla) {int parentVisit = node.getState (). getVisitCount (); vrátiť Collections.max (node.getChildArray (), Comparator.comparing (c -> uctValue (parentVisit, c.getState (). getWinScore (), c.getState (). getVisitCount ()))); }}

Táto fáza odporúča listový uzol, ktorý by sa mal vo fáze rozširovania ďalej rozširovať:

private void expandNode (uzol uzla) {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);}); }

Ďalej napíšeme kód, aby sme vybrali náhodný uzol a simulovali z neho náhodné prehrávanie. Tiež budeme mať aktualizovať funkcia na šírenie skóre a počtu návštev od listu po koreň:

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 (uzol uzla) {uzol tempNode = nový uzol (uzol); State tempState = tempNode.getState (); int boardStatus = tempState.getBoard (). checkStatus (); if (boardStatus == oponent) {tempNode.getParent (). getState (). setWinScore (Integer.MIN_VALUE); návratová doskaStatus; } while (boardStatus == Board.IN_PROGRESS) {tempState.togglePlayer (); tempState.randomPlay (); boardStatus = tempState.getBoard (). checkStatus (); } vrátiť boardStatus; }

Teraz sme skončili s implementáciou MCTS. Všetko, čo potrebujeme, je predovšetkým Tic-Tac-Toe Doska triedna implementácia. Upozorňujeme, že s našou implementáciou môžete hrať aj ďalšie hry; Musíme sa len zmeniť Doska trieda.

public class Board {int [] [] boardValues; public static final int DEFAULT_BOARD_SIZE = 3; verejný statický konečný int IN_PROGRESS = -1; public static final int DRAW = 0; verejný statický konečný int P1 = 1; verejný statický konečný int P2 = 2; // getters and setters public void performMove (int player, Position p) {this.totalMoves ++; boardValues ​​[p.getX ()] [p.getY ()] = hráč; } public int checkStatus () {/ * Vyhodnoťte, či je hra vyhraná, a vráťte víťaza. Ak je to draw return 0 else return -1 * /} public List getEmptyPositions () {int size = this.boardValues.length; Zoznam emptyPositions = new ArrayList (); for (int i = 0; i <size; i ++) {for (int j = 0; j <size; j ++) {if (boardValues ​​[i] [j] == 0) emptyPositions.add (nová pozícia (i, j)); }} return emptyPositions; }}

Práve sme implementovali AI, ktorú v Tic-Tac-Toe nemožno poraziť. Napíšme prípad jednotky, ktorý demonštruje, že AI vs. AI bude mať vždy za následok remízu:

@Test public void givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw () {Board board = new Board (); int hráč = Board.P1; int totalMoves = Board.DEFAULT_BOARD_SIZE * Board.DEFAULT_BOARD_SIZE; for (int i = 0; i <totalMoves; i ++) {board = mcts.findNextMove (doska, prehrávač); if (board.checkStatus ()! = -1) {break; } hráč = 3 - hráč; } int winStatus = board.checkStatus (); assertEquals (winStatus, Board.DRAW); }

6. Výhody

• To nevyhnutne nevyžaduje žiadne taktické znalosti o hre
• Všeobecnú implementáciu MCTS možno s malými úpravami opätovne použiť na ľubovoľný počet hier
• Zameriava sa na uzly s vyššou pravdepodobnosťou výhry v hre
• Vhodné pre problémy s vysokým faktorom vetvenia, pretože neplytvá výpočtami na všetkých možných vetvách
• Algoritmus sa implementuje veľmi jednoducho
• Spustenie je možné kedykoľvek zastaviť a bude stále navrhovať ďalší najlepší vypočítaný stav

7. Nevýhoda

Ak sa MCTS používa v základnej podobe bez akýchkoľvek vylepšení, môže zlyhať v navrhovaní rozumných krokov. Môže sa to stať, ak uzly nie sú dostatočne navštevované, čo vedie k nepresným odhadom.

MCTS sa však dá vylepšiť použitím niektorých techník. Zahŕňa to techniky špecifické pre doménu, ako aj techniky nezávislé od domény.

V technikách špecifických pre doménu produkuje fáza simulácie realistickejšie hry než stochastické simulácie. Aj keď to vyžaduje znalosť herných postupov a pravidiel.

8. Zhrnutie

Na prvý pohľad je ťažké uveriť, že algoritmus spoliehajúci sa na náhodné voľby môže viesť k inteligentnej AI. Premyslená implementácia MCTS nám však skutočne môže poskytnúť riešenie, ktoré je možné použiť v mnohých hrách, ako aj pri rozhodovacích problémoch.

Úplný kód algoritmu nájdete ako vždy na GitHub.