Pencarian Pohon Monte Carlo untuk Game Tic-Tac-Toe di Jawa

1. Ikhtisar

Pada artikel ini, kita akan menjelajahi algoritma Monte Carlo Tree Search (MCTS) dan aplikasinya.

Kami akan melihat tahapannya secara detail dengan mengimplementasikan permainan Tic-Tac-Toe di Java . Kami akan merancang solusi umum yang dapat digunakan di banyak aplikasi praktis lainnya, dengan sedikit perubahan.

2. Pendahuluan

Sederhananya, pencarian pohon Monte Carlo adalah algoritma pencarian probabilistik. Ini adalah algoritme pengambilan keputusan yang unik karena efisiensinya di lingkungan terbuka dengan banyak kemungkinan.

Jika Anda sudah terbiasa dengan algoritme teori permainan seperti Minimax, ini memerlukan fungsi untuk mengevaluasi keadaan saat ini, dan harus menghitung banyak level dalam pohon permainan untuk menemukan gerakan yang optimal.

Sayangnya, hal ini tidak mungkin dilakukan dalam game seperti Go yang memiliki faktor percabangan yang tinggi (menghasilkan jutaan kemungkinan seiring bertambahnya ketinggian pohon), dan sulit untuk menulis fungsi evaluasi yang baik untuk menghitung seberapa baik keadaan saat ini.

Pencarian pohon Monte Carlo menerapkan metode Monte Carlo untuk pencarian pohon permainan. Karena didasarkan pada pengambilan sampel acak dari status permainan, ia tidak perlu memaksa keluar dari setiap kemungkinan. Juga, tidak perlu kita menulis evaluasi atau fungsi heuristik yang baik.

Dan, catatan singkat - ini merevolusi dunia komputer Go. Sejak Maret 2016, Ini telah menjadi topik penelitian yang lazim karena AlphaGo Google (dibangun dengan MCTS dan jaringan saraf) mengalahkan Lee Sedol (juara dunia di Go).

3. Algoritma Pencarian Pohon Monte Carlo

Sekarang, mari kita jelajahi cara kerja algoritme. Awalnya, kita akan membangun pohon lookahead (pohon permainan) dengan simpul akar, dan kemudian kita akan terus mengembangkannya dengan peluncuran acak. Dalam prosesnya, kami akan mempertahankan jumlah kunjungan dan jumlah kemenangan untuk setiap node.

Pada akhirnya, kami akan memilih node dengan statistik paling menjanjikan.

Algoritma ini terdiri dari empat fase; mari kita jelajahi semuanya secara mendetail.

3.1. Pilihan

Pada fase awal ini, algoritme dimulai dengan node root dan memilih node turunan sedemikian rupa sehingga mengambil node dengan tingkat kemenangan maksimum. Kami juga ingin memastikan bahwa setiap node diberikan kesempatan yang adil.

Idenya adalah untuk terus memilih simpul anak yang optimal sampai kita mencapai simpul daun dari pohon. Cara yang baik untuk memilih simpul anak adalah dengan menggunakan rumus UCT (Upper Confidence Bound diterapkan ke pohon):

Di mana

  • w i = jumlah kemenangan setelah gerakan ke- i
  • n i = jumlah simulasi setelah gerakan ke- i
  • c = parameter eksplorasi (secara teoritis sama dengan √2)
  • t = jumlah total simulasi untuk node induk

Formula tersebut memastikan bahwa tidak ada negara bagian yang akan menjadi korban kelaparan dan juga memainkan cabang yang menjanjikan lebih sering daripada rekan-rekan mereka.

3.2. Ekspansi

Ketika tidak dapat lagi menerapkan UCT untuk menemukan simpul penerus, ia memperluas pohon permainan dengan menambahkan semua kemungkinan status dari simpul daun.

3.3. Simulasi

Setelah Ekspansi, algoritme memilih node turunan secara sewenang-wenang, dan ini mensimulasikan game yang diacak dari node yang dipilih hingga mencapai status game yang dihasilkan. Jika node dipilih secara acak atau semi-acak selama permainan, itu disebut permainan ringan. Anda juga dapat memilih permainan berat dengan menulis heuristik kualitas atau fungsi evaluasi.

3.4. Propagasi mundur

Ini juga dikenal sebagai fase pembaruan. Setelah algoritme mencapai akhir permainan, algoritme mengevaluasi status untuk mencari tahu pemain mana yang menang. Ini melintasi ke atas ke root dan meningkatkan skor kunjungan untuk semua node yang dikunjungi. Itu juga memperbarui skor kemenangan untuk setiap node jika pemain untuk posisi itu telah memenangkan permainan.

MCTS terus mengulangi keempat fase ini hingga sejumlah iterasi tetap atau jumlah waktu tetap.

Dalam pendekatan ini, kami memperkirakan skor kemenangan untuk setiap node berdasarkan gerakan acak. Semakin tinggi jumlah iterasi, estimasi menjadi lebih andal. Perkiraan algoritme akan kurang akurat di awal pencarian dan terus meningkat setelah waktu yang cukup. Sekali lagi, ini sepenuhnya tergantung pada jenis masalahnya.

4. Lari Kering

Di sini, node berisi statistik sebagai total kunjungan / skor kemenangan.

5. Implementasi

Sekarang, mari terapkan permainan Tic-Tac-Toe - menggunakan algoritme penelusuran pohon Monte Carlo.

Kami akan merancang solusi umum untuk MCTS yang dapat digunakan untuk banyak permainan papan lainnya juga. Kami akan melihat sebagian besar kode di artikel itu sendiri.

Meskipun untuk membuat penjelasannya jelas, kami mungkin harus melewatkan beberapa detail kecil (tidak terlalu terkait dengan MCTS), tetapi Anda selalu dapat menemukan penerapan lengkapnya di sini.

Pertama-tama, kita membutuhkan implementasi dasar untuk kelas Tree and Node agar memiliki fungsi pencarian pohon:

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

Karena setiap node akan memiliki status masalah tertentu, mari kita implementasikan kelas State juga:

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

Sekilas, sulit dipercaya bahwa algoritme yang mengandalkan pilihan acak dapat menghasilkan AI yang cerdas. Namun, implementasi MCTS yang bijaksana memang dapat memberi kami solusi yang dapat digunakan dalam banyak permainan serta dalam masalah pengambilan keputusan.

Seperti biasa, kode lengkap untuk algoritme dapat ditemukan di GitHub.