Търсене на дърво в Монте Карло за игра Tic-Tac-Toe в Java

1. Общ преглед

В тази статия ще изследваме алгоритъма за търсене на дървета в Монте Карло (MCTS) и неговите приложения.

Ще разгледаме подробно фазите му, като внедрим играта на Tic-Tac-Toe в Java . Ще проектираме общо решение, което може да се използва в много други практически приложения, с минимални промени.

2. Въведение

Просто казано, търсенето на дърво в Монте Карло е вероятностен алгоритъм за търсене. Това е уникален алгоритъм за вземане на решения поради своята ефективност в отворени среди с огромно количество възможности.

Ако вече сте запознати с алгоритмите на теорията на игрите като Minimax, тя изисква функция за оценка на текущото състояние и трябва да изчисли много нива в дървото на играта, за да намери оптималния ход.

За съжаление не е възможно да се направи това в игра като Go, в която има висок коефициент на разклонение (което води до милиони възможности с увеличаване на височината на дървото) и е трудно да се напише добра функция за оценка, за да се изчисли колко добра е текущото състояние е.

Търсене на дърво в Монте Карло прилага метода на Монте Карло към търсенето на дървото на играта. Тъй като се основава на произволно вземане на проби от състояния на играта, не е необходимо да се насилва изходът от всяка възможност. Освен това не е задължително да пишем оценка или добри евристични функции.

И една бърза странична бележка - тя революционизира света на компютърната Go. От март 2016 г. това се превърна в преобладаваща изследователска тема, тъй като AlphaGo на Google (изграден с MCTS и невронна мрежа) победи Lee Sedol (световния шампион в Go).

3. Алгоритъм за търсене на дървета в Монте Карло

Сега нека разгледаме как работи алгоритъмът. Първоначално ще изградим дърво lookahead (дърво на играта) с корен възел и след това ще продължим да го разширяваме с произволни пускания. В процеса ще поддържаме броя на посещенията и броя на печалбите за всеки възел.

В крайна сметка ще изберем възела с най-обещаващи статистически данни.

Алгоритъмът се състои от четири фази; нека да ги изследваме подробно.

3.1. Избор

В тази начална фаза алгоритъмът започва с корен възел и избира дъщерен възел, така че да избере възела с максимална степен на печалба. Също така искаме да се уверим, че всеки възел има справедлив шанс.

Идеята е да продължим да избираме оптимални дъщерни възли, докато стигнем до листния възел на дървото. Един добър начин да изберете такъв дъщерен възел е да използвате формула UCT (Upper Configuration Bound, приложена към дървета):

В който

  • w i = брой победи след i- тия ход
  • n i = брой симулации след i- ия ход
  • c = параметър за проучване (теоретично равен на √2)
  • t = общ брой симулации за родителския възел

Формулата гарантира, че никоя държава няма да стане жертва на глад и също така играе обещаващи клонове по-често от своите колеги.

3.2. Разширяване

Когато вече не може да приложи UCT за намиране на наследник възел, той разширява дървото на играта, като добавя всички възможни състояния от листния възел.

3.3. Симулация

След Разширяване, алгоритъмът избира произволен детски възел и симулира рандомизирана игра от избрания възел, докато достигне полученото състояние на играта. Ако възлите се избират произволно или полуслучайно по време на игра, това се нарича лека игра. Можете също така да изберете тежка игра, като напишете качествена евристика или функции за оценка.

3.4. Обратно размножаване

Това е известно и като фаза на актуализация. След като алгоритъмът достигне края на играта, той оценява състоянието, за да разбере кой играч е спечелил. Той преминава нагоре към корена и увеличава резултата от посещението за всички посетени възли. Той също така актуализира резултата за победа за всеки възел, ако играчът от тази позиция е спечелил играта.

MCTS продължава да повтаря тези четири фази до някакъв фиксиран брой итерации или някакъв фиксиран период от време.

При този подход ние оценяваме печеливш резултат за всеки възел въз основа на произволни ходове. Така че колкото по-голям е броят на итерациите, толкова по-надеждна става оценката. Оценките на алгоритъма ще бъдат по-малко точни в началото на търсенето и ще продължат да се подобряват след достатъчно време. Отново зависи само от вида на проблема.

4. Сухо бягане

Тук възлите съдържат статистика като общ брой посещения / спечелен резултат.

5. Изпълнение

Сега, нека внедрим игра на Tic-Tac-Toe - използвайки алгоритъма за търсене на дърво в Монте Карло.

Ще проектираме обобщено решение за MCTS, което може да се използва и за много други настолни игри. Ще разгледаме по-голямата част от кода в самата статия.

Въпреки че, за да направим обяснението ясно, може да се наложи да пропуснем някои незначителни подробности (не особено свързани с MCTS), но винаги можете да намерите пълното изпълнение тук.

На първо място, ние се нуждаем от основно изпълнение за класовете Tree и Node , за да имаме функционалност за търсене на дърво:

public class Node { State state; Node parent; List childArray; // setters and getters } public class Tree { Node root; }

Както всеки възел ще има определено състояние на проблема, нека да приложи държавна клас, както и:

public class State { Board board; int playerNo; int visitCount; double winScore; // copy constructor, getters, and setters public List getAllPossibleStates() { // constructs a list of all possible states from current state } public void randomPlay() { /* get a list of all possible positions on the board and play a random move */ } }

Now, let's implement MonteCarloTreeSearch class, which will be responsible for finding the next best move from the given game position:

public class MonteCarloTreeSearch { static final int WIN_SCORE = 10; int level; int opponent; public Board findNextMove(Board board, int playerNo) { // define an end time which will act as a terminating condition opponent = 3 - playerNo; Tree tree = new Tree(); Node rootNode = tree.getRoot(); rootNode.getState().setBoard(board); rootNode.getState().setPlayerNo(opponent); while (System.currentTimeMillis()  0) { nodeToExplore = promisingNode.getRandomChildNode(); } int playoutResult = simulateRandomPlayout(nodeToExplore); backPropogation(nodeToExplore, playoutResult); } Node winnerNode = rootNode.getChildWithMaxScore(); tree.setRoot(winnerNode); return winnerNode.getState().getBoard(); } }

Here, we keep iterating over all of the four phases until the predefined time, and at the end, we get a tree with reliable statistics to make a smart decision.

Now, let's implement methods for all the phases.

We will start with the selection phase which requires UCT implementation as well:

private Node selectPromisingNode(Node rootNode) { Node node = rootNode; while (node.getChildArray().size() != 0) { node = UCT.findBestNodeWithUCT(node); } return node; }
public class UCT { public static double uctValue( int totalVisit, double nodeWinScore, int nodeVisit) { if (nodeVisit == 0) { return Integer.MAX_VALUE; } return ((double) nodeWinScore / (double) nodeVisit) + 1.41 * Math.sqrt(Math.log(totalVisit) / (double) nodeVisit); } public static 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()))); } }

This phase recommends a leaf node which should be expanded further in the expansion phase:

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); }); }

Next, we write code to pick a random node and simulate a random play out from it. Also, we will have an update function to propagate score and visit count starting from leaf to root:

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

Now we are done with the implementation of MCTS. All we need is a Tic-Tac-Toe particular Board class implementation. Notice that to play other games with our implementation; We just need to change Board class.

public class Board { int[][] boardValues; public static final int DEFAULT_BOARD_SIZE = 3; public static final int IN_PROGRESS = -1; public static final int DRAW = 0; public static final int P1 = 1; public static final int P2 = 2; // getters and setters public void performMove(int player, Position p) { this.totalMoves++; boardValues[p.getX()][p.getY()] = player; } public int checkStatus() { /* Evaluate whether the game is won and return winner. If it is draw return 0 else return -1 */ } public List getEmptyPositions() { int size = this.boardValues.length; List emptyPositions = new 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)); } } return emptyPositions; } }

We just implemented an AI which can not be beaten in Tic-Tac-Toe. Let's write a unit case which demonstrates that AI vs. AI will always result in a draw:

@Test public void 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); if (board.checkStatus() != -1) { break; } player = 3 - player; } int winStatus = board.checkStatus(); assertEquals(winStatus, Board.DRAW); }

6. Advantages

  • It does not necessarily require any tactical knowledge about the game
  • A general MCTS implementation can be reused for any number of games with little modification
  • Focuses on nodes with higher chances of winning the game
  • Suitable for problems with high branching factor as it does not waste computations on all possible branches
  • Algorithm is very straightforward to implement
  • Execution can be stopped at any given time, and it will still suggest the next best state computed so far

7. Drawback

If MCTS is used in its basic form without any improvements, it may fail to suggest reasonable moves. It may happen if nodes are not visited adequately which results in inaccurate estimates.

However, MCTS can be improved using some techniques. It involves domain specific as well as domain-independent techniques.

In domain specific techniques, simulation stage produces more realistic play outs rather than stochastic simulations. Though it requires knowledge of game specific techniques and rules.

8. Summary

На пръв поглед е трудно да се доверим, че алгоритъмът, разчитащ на произволни избори, може да доведе до интелигентен ИИ. Внимателното внедряване на MCTS обаче наистина може да ни предостави решение, което може да се използва в много игри, както и при проблеми при вземането на решения.

Както винаги, пълният код на алгоритъма може да бъде намерен в GitHub.