mcts

Tutorial algoritma Monte Carlo Tree Search (MCTS) dengan kode Python. Penerapan MCTS untuk membuat AI untuk game sederhana.

Dalam tutorial ini kami akan menjelaskan algoritma Monte Carlo Tree Search dan setiap bagian kodenya. Baru-baru ini kami menerapkan MCTS untuk mengembangkan game kami.

Kode ini bersifat umum dan hanya mengasumsikan keakraban dengan Python dasar. Kami telah menjelaskannya sehubungan dengan permainan kami. Jika Anda ingin menggunakannya untuk proyek atau game Anda, Anda harus sedikit mengubah fungsi yang saya sebutkan di bawah.

Ini link playstore ke gamenya: Sudo Tic Tac Toe.

Aturan permainan kami (mode 1) adalah sebagai berikut:

1. Permainan ini dimainkan pada grid 9 kali 9 seperti Sudoku.
2. Kotak besar berukuran 9 kali 9 ini dibagi menjadi 9 kotak berukuran 3 kali 3 yang lebih kecil (papan lokal).
3. Tujuan permainan ini adalah untuk memenangkan salah satu papan lokal dari 9 papan yang tersedia.
4. Langkah Anda menentukan dewan AI lokal mana yang harus bergerak dan sebaliknya.
5. Misalnya Anda melakukan perpindahan di posisi 1 papan lokal nomor 5. Hal ini akan memaksa AI untuk bergerak di papan lokal nomor 1.
6. Aturan Tic Tac Toe normal diterapkan pada dewan lokal.

Mengapa MCTS?

Seperti yang Anda lihat, game ini memiliki faktor percabangan yang sangat tinggi. Untuk langkah pertama, seluruh papan kosong. Jadi ada 81 tempat kosong. Untuk giliran pertama, ada 81 kemungkinan gerakan. Untuk giliran kedua dengan menerapkan aturan 4 memiliki 8 atau 9 kemungkinan gerakan.

Untuk 2 gerakan pertama ini menghasilkan 81*9 = 729 kemungkinan kombinasi. Dengan demikian jumlah kemungkinan kombinasi meningkat seiring berjalannya permainan, sehingga menghasilkan faktor percabangan yang tinggi. Untuk kedua mode permainan kami, faktor percabangannya sangat tinggi. Untuk game dengan faktor percabangan yang tinggi tidak mungkin menerapkan algoritma minimax. Algoritma MCTS berfungsi untuk permainan semacam ini.

Juga seperti yang bisa kamu lihat dari bermain game, waktu yang dibutuhkan ai untuk bergerak hanya sekitar satu detik. Dengan demikian MCTS berjalan cepat. MCTS telah diterapkan pada kedua mode permainan.

Di bawah ini kami mendemonstrasikan kode MCTS dengan Python. Pertama kita perlu mengimpor numpy dan defaultdict.

 import numpy as np
from collections import defaultdict

Tentukan kelas MCTS seperti yang ditunjukkan di bawah ini.

 class MonteCarloTreeSearchNode ():
    def __init__ ( self , state , parent = None , parent_action = None ):
        self . state = state
        self . parent = parent
        self . parent_action = parent_action
        self . children = []
        self . _number_of_visits = 0
        self . _results = defaultdict ( int )
        self . _results [ 1 ] = 0
        self . _results [ - 1 ] = 0
        self . _untried_actions = None
        self . _untried_actions = self . untried_actions ()
        return

Konstruktor digunakan untuk menginisialisasi variabel berikut.

• state : Untuk permainan kami, ini mewakili status papan. Umumnya status papan diwakili oleh sebuah array. Untuk Tic Tac Toe normal, ini adalah larik 3 kali 3.
• induk : Tidak Ada untuk simpul akar dan untuk simpul lain sama dengan simpul asalnya. Untuk giliran pertama seperti yang Anda lihat dari game, itu adalah Tidak Ada.
• kids : Ini berisi semua tindakan yang mungkin dilakukan dari node saat ini. Untuk giliran kedua dalam permainan kami ini adalah 9 atau 8 tergantung di mana Anda bergerak.
• parent_action : Tidak ada untuk node root dan node lainnya sama dengan tindakan yang dilakukan induknya.
• _number_of_visits : Berapa kali node saat ini dikunjungi
• hasil : Ini kamus
• _untried_actions : Mewakili daftar semua tindakan yang mungkin dilakukan
• tindakan : Gerakan yang harus dilakukan.

Kelas terdiri dari fungsi anggota berikut. Semua fungsi di bawah ini adalah fungsi anggota kecuali fungsi main().

 def untried_actions ( self ):

    self . _untried_actions = self . state . get_legal_actions ()
    return self . _untried_actions

Mengembalikan daftar tindakan yang belum dicoba dari keadaan tertentu. Untuk giliran pertama permainan kami ada 81 kemungkinan tindakan. Untuk turn kedua adalah 8 atau 9. Ini berbeda-beda di permainan kita.

 def q ( self ):
    wins = self . _results [ 1 ]
    loses = self . _results [ - 1 ]
    return wins - loses

Mengembalikan selisih kemenangan - kekalahan

 def n ( self ):
    return self . _number_of_visits

Mengembalikan berapa kali setiap node dikunjungi.

 def expand ( self ):
	
    action = self . _untried_actions . pop ()
    next_state = self . state . move ( action )
    child_node = MonteCarloTreeSearchNode (
		next_state , parent = self , parent_action = action )

    self . children . append ( child_node )
    return child_node 

Dari keadaan sekarang, keadaan selanjutnya dihasilkan tergantung pada tindakan yang dilakukan. Pada langkah ini semua kemungkinan status ditambahkan ke array anak-anak dan node_anak dikembalikan. Status yang dimungkinkan dari status saat ini semuanya ditambahkan ke array anak-anak dan node_anak yang sesuai dengan status ini dikembalikan.

 def is_terminal_node ( self ):
    return self . state . is_game_over ()

Ini digunakan untuk memeriksa apakah node saat ini terminal atau tidak. Node terminal tercapai saat permainan selesai.

 def rollout ( self ):
    current_rollout_state = self . state
    
    while not current_rollout_state . is_game_over ():
        
        possible_moves = current_rollout_state . get_legal_actions ()
        
        action = self . rollout_policy ( possible_moves )
        current_rollout_state = current_rollout_state . move ( action )
    return current_rollout_state . game_result ()

Dari keadaan saat ini, seluruh permainan disimulasikan hingga ada hasil untuk permainan tersebut. Hasil permainan ini dikembalikan. Misalnya jika menghasilkan kemenangan maka hasilnya adalah 1. Sebaliknya -1 jika menghasilkan kekalahan. Dan nilainya 0 jika seri. Jika seluruh permainan disimulasikan secara acak, yaitu pada setiap giliran, gerakan dipilih secara acak dari serangkaian kemungkinan gerakan, ini disebut permainan ringan.

 def backpropagate ( self , result ):
    self . _number_of_visits += 1.
    self . _results [ result ] += 1.
    if self . parent :
        self . parent . backpropagate ( result )

Pada langkah ini semua statistik untuk node diperbarui. Sampai node induk tercapai, jumlah kunjungan setiap node bertambah 1. Jika hasilnya 1 berarti menang, maka kemenangan bertambah 1. Sebaliknya jika hasilnya kalah, maka kalah bertambah 1.

 def is_fully_expanded ( self ):
    return len ( self . _untried_actions ) == 0

Semua tindakan dikeluarkan dari _untried_actions satu per satu. Ketika menjadi kosong, yaitu ketika ukurannya nol, maka ia mengembang sepenuhnya.

 def best_child ( self , c_param = 0.1 ):
    
    choices_weights = [( c . q () / c . n ()) + c_param * np . sqrt (( 2 * np . log ( self . n ()) / c . n ())) for c in self . children ]
    return self . children [ np . argmax ( choices_weights )]

Setelah diperluas sepenuhnya, fungsi ini memilih anak terbaik dari array anak. Suku pertama dalam rumus tersebut berhubungan dengan eksploitasi dan suku kedua berhubungan dengan eksplorasi.

 def rollout_policy ( self , possible_moves ):
    
    return possible_moves [ np . random . randint ( len ( possible_moves ))]

Memilih secara acak sebuah gerakan dari kemungkinan gerakan. Ini adalah contoh permainan acak.

 def _tree_policy ( self ):

    current_node = self
    while not current_node . is_terminal_node ():
        
        if not current_node . is_fully_expanded ():
            return current_node . expand ()
        else :
            current_node = current_node . best_child ()
    return current_node

Memilih node untuk menjalankan peluncuran.

 def best_action ( self ):
    simulation_no = 100
	
	
    for i in range ( simulation_no ):
		
        v = self . _tree_policy ()
        reward = v . rollout ()
        v . backpropagate ( reward )
	
    return self . best_child ( c_param = 0. )

Ini adalah fungsi tindakan terbaik yang mengembalikan node yang sesuai dengan kemungkinan pergerakan terbaik. Langkah ekspansi, simulasi dan backpropagation dilakukan dengan kode di atas.

 def get_legal_actions ( self ): 
    '''
    Modify according to your game or
    needs. Constructs a list of all
    possible states from current state.
    Returns a list.
    ''' 

 def is_game_over ( self ):
    '''
    Modify according to your game or 
    needs. It is the game over condition
    and depends on your game. Returns
    true or false
    ''' 

 def game_result ( self ):
    '''
    Modify according to your game or 
    needs. Returns 1 or 0 or -1 depending
    on your state corresponding to win,
    tie or a loss.
    ''' 

 def move ( self , action ):
    '''
    Modify according to your game or 
    needs. Changes the state of your 
    board with a new value. For a normal
    Tic Tac Toe game, it can be a 3 by 3
    array with all the elements of array
    being 0 initially. 0 means the board 
    position is empty. If you place x in
    row 2 column 3, then it would be some 
    thing like board[2][3] = 1, where 1
    represents that x is placed. Returns 
    the new state after making a move.
    ''' 

 def main ():
    root = MonteCarloTreeSearchNode ( state , None , action )
    selected_node = root . best_action ()
    return 

Ini adalah fungsi utama(). Inisialisasi node root dan panggil fungsi best_action untuk mendapatkan node terbaik. Ini bukan fungsi anggota kelas. Semua fungsi lainnya adalah fungsi anggota kelas.

MCTS terdiri dari 4 langkah:

PILIHAN

Idenya adalah untuk terus memilih simpul anak terbaik hingga kita mencapai simpul daun pada pohon. Cara yang baik untuk memilih simpul anak tersebut adalah dengan menggunakan rumus UCT (Batas Keyakinan Atas yang diterapkan pada pohon):

	wi/ni + c*sqrt(t)/ni

wi = jumlah kemenangan setelah langkah ke-i
ni = jumlah simulasi setelah perpindahan ke-i
c = parameter eksplorasi (secara teoritis sama dengan √2)
t = jumlah total simulasi untuk node induk

EKSPANSI:

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

SIMULASI:

Setelah Ekspansi, algoritme memilih node anak secara sewenang-wenang, dan mensimulasikan seluruh game dari node yang dipilih hingga mencapai status game yang dihasilkan. Jika node dipilih secara acak selama play out, ini disebut light play out. Anda juga dapat memilih permainan berat dengan menulis heuristik berkualitas atau fungsi evaluasi.

PROPAGASI KEMBALI:

Setelah algoritme mencapai akhir permainan, algoritme akan mengevaluasi status untuk mengetahui pemain mana yang menang. Ini melintasi ke atas ke akar dan meningkatkan skor kunjungan untuk semua node yang dikunjungi. Ini juga memperbarui skor kemenangan untuk setiap node jika pemain untuk posisi tersebut telah memenangkan permainan.

MERANCANG GAME ANDA:

Jika Anda berencana membuat game sendiri, Anda harus memikirkan pertanyaan-pertanyaan berikut.

1. Bagaimana Anda mewakili keadaan permainan Anda? Pikirkan tentang keadaan awal dalam permainan kita.
2. Bagaimana kondisi permainan akhir untuk permainan Anda? Bandingkan dengan kondisi permainan akhir permainan kita.
3. Bagaimana Anda mendapatkan tindakan hukum dalam game Anda? Cobalah mendapatkan tindakan hukum untuk langkah pertama permainan kami.

Sudo Tic Tac Toe

Jika Anda memiliki pertanyaan atau saran, jangan ragu untuk menghubungi kami di [email protected]