Reinforcement Learning: Bermain Tic-Tac-Toe

Reinforcement Learning: Bermain Tic-Tac-Toe

Mendefinisikan Environment

Environment adalah class di mana Agent akan berinteraksi dengannya. Class ini juga bertujuan untuk menggambar papan TTT di layar, termasuk juga mendefinisikan status apakah permainan sudah berakhir atau tidak.

Dalam membuat class Environment kita perlu beberapa methods di dalamnya, antara lain:

  • __init__() = digunakan untuk mendefinisikan beberapa variabel di dalam class ini.
  • kosong(i, j) = digunakan untuk memberikan informasi jika kotaknya masih kosong.
  • reward(symbol) = digunakan untuk memberikan reward kepada Agent dengan simbol tertentu (apakah X atau O).
  • akses_state() = Sudah dijelaskan di bagian sebelumnya, yaitu digunakan untuk mendefinisikan semua state (3 pangkat 9).
  • game_over() = memberikan nilai True atau False. Intinya adalah method ini berguna untuk memberitahu sistem bahwa permainan telah berakhir (bernilai True jika sudah berakhir).
  • draw_board() = sesuai namanya maka method ini berguna untuk menggambar papan TTT di layar.

Sekarang kita akan bahas satu demi satu:

class Environment:
    def __init__(self):
        self.board = np.zeros((dimensi, dimensi))
        self.x = -1 
        self.o = 1 
        self.winner = None
        self.ended = False
        self.num_states = 3**(dimensi*dimensi)

    def kosong(self, i, j):
        return self.board[i,j] == 0

    def reward(self, sym):
        if not self.game_over():
            return 0

        return 1 if self.winner == sym else 0

    def akses_state(self):
        k = 0
        h = 0
        for i in range(dimensi):
            for j in range(dimensi):
                if self.board[i,j] == 0:
                    v = 0
                elif self.board[i,j] == self.x:
                    v = 1
                elif self.board[i,j] == self.o:
                    v = 2
                h += (3**k) * v
                k += 1
        return h

    def game_over(self, proses_rekalkulasi=False):
        if not proses_rekalkulasi and self.ended:
            return self.ended
    
        for i in range(dimensi):
            for player in (self.x, self.o):
                if self.board[i].sum() == player*dimensi:
                    self.winner = player
                    self.ended = True
                    return True

        for j in range(dimensi):
            for player in (self.x, self.o):
                if self.board[:,j].sum() == player*dimensi:
                    self.winner = player
                    self.ended = True
                    return True

        for player in (self.x, self.o):
            if self.board.trace() == player*dimensi:
                self.winner = player
                self.ended = True
                return True
            if np.fliplr(self.board).trace() == player*dimensi:
                self.winner = player
                self.ended = True
                return True
        
        if np.all((self.board == 0) == False):
            self.winner = None
            self.ended = True
            return True

        self.winner = None
        return False

    def is_draw(self):
        return self.ended and self.winner is None

  # Contoh papan TTT
  # -------------
  # | x |   |   |
  # -------------
  # |   |   |   |
  # -------------
  # |   |   | o |
  # -------------
    def menampilkan_board(self):
        for i in range(dimensi):
            print("-------------")
            for j in range(dimensi):
                print("  ", end="")
                if self.board[i,j] == self.x:
                    print("x ", end="")
                elif self.board[i,j] == self.o:
                    print("o ", end="")
                else:
                    print("  ", end="")
            print("")
        print("-------------")

Penjelasan:

  • Line 1 mendefinisikan nama class Environment.
  • Line 2 mendefinisikan nama method __init__. Metode init digunakan untuk mendefinisikan nilai parameter awal yang nanti akan digunakan oleh fungsi-fungsi di line selanjutnya.
  • Line 3 mengisi papan dengan nilai 0 ukuran 3 x 3. Karena kotak kosong bernilai nol, maka kita gunakan nilai -1 untuk simbol X dan nilai 1 untuk simbol O.
  • Line 4 menandai (inisiasi) kotak dengan simbol X dengan angka -1. Mengapa memilih angka -1? Karena akan berguna saat mendefinisikan method game_over nanti.
  • Line 5 menandai (inisiasi) kotak dengan simbol O dengan angka 1. Mengapa memilih angka 1? Karena akan berguna saat mendefinisikan method game_over nanti.
  • Line 6 menunjukkan status awal pemenang saat memulai permainan adalah None (tidak ada).
  • Line 7 menunjukkan status awal bahwa permainan belum berakhir (karena baru mulai) dengan tipe boolean bernilai False.
  • Line 8 menunjukkan jumlah state nya adalah 3 pangkat 9.
  • Line 10-11 mendefinisikan method kosong.
  • Line 13-15 mendefinisikan method reward.
  • Line 19-32 mendefinisikan method akses_state (sudah dibahas sebelumnya).
  • Line 34 mendefinisikan method game_over dengan attribute default proses_rekalkulasi = False.
  • Line 35-36 digunakan untuk membuat jalan pintas memberitahu kepada sistem bahwa game sudah berakhir saat menjalankan fungsi akses_state_end_winner.
  • Line 38-43 adalah melakukan pengecekan berdasarkan baris. Karena kita memiliki nilai X = -1, dan O = 1, maka jika kita berhasil membuat tiga simbol sejajar jumlah X pasti -3, dan jumlah 0 adalah 3. Karenanya, dengan menggunakan fungsi sum() kita bisa mendapatkan jumlah nilai simbol di baris tersebut. Jika sudah berakhir (game_over) maka kita kembalikan nilai True ke sistem.
  • Line 45-50 mirip dengan line 38-43 namun kali ini untuk kolom.
  • Line 52-60 adalah untuk mencari tiga simbol secara diagonal. Untuk bisa melakukannya, kita gunakan fungsi trace() yang akan menjumlahkan secara diagonal (konsepnya mirip dengan pembahasan di atasnya).
  • Line 53-56 dari kiri atas ke kanan bawah.
  • Line 57-60 dari kanan atas ke kiri bawah.
  • Line 62-65 adalah untuk mengecek apakah permainan beakhir seri (draw). Caranya adalah cukup mengecek apakah semua kotak berisi dengan angka (bukan nol).
  • Line 67-68 menyatakan bahwa jika semua perintah dari line 35-65 tidak ada yang terpenuhi (tidak tereksekusi), maka kita set winner = None dan mengembalikan status False ke sistem, karena permainan belum selesai.
  • Line 70-71 digunakan (dipanggil) untuk menjelaskan bahwa saat ini permainan berakhir seri (draw).
  • Line 73-80 adalah ilustrasi papan TTT untuk gambaran kita.
  • Line 81-93 adalah method yang bertujuan sesuai namanya yaitu menampilkan_board.

Mendefinisikan Agent

Sekarang kita akan mendefinisikan class dengan nama Agent. Class ini merupakan kunci dari AI kita, di mana ia akan bermain layaknya robot kecerdasan buatan, dan ia akan berinteraksi dengan lingkungannya (Environment). Agent akan bergerak berdasarkan V(s), sehingga kunci kecerdasan dia berasal dari V(s).

Dalam membuat class Agent kita perlu beberapa methods di dalamnya, antara lain:

  • __init__() = Digunakan untuk mendefinisikan (inisiasi) beberapa parameter awal di class ini.
  • setV(V) = Menginisiasi (mendefinisikan) value function.
  • set_symbol(symbol) = Digunakan agar Agent bisa memakai salah satu simbol (X atau O).
  • set_verbose(b) = Mencetak informasi ke layar jika parameter verbose diset keTrue.
  • reset_history() = Digunakan untuk melakukan tracking state history untuk setiap episode. Ketika 1 episode selesai kita tidak memerlukan state history-nya dan akan mulai episode baru di awal.
  • take_action(env) = Digunakan agar Agent bisa melakukan action (berjalan memilih kotak TTT).
  • update_state_history(s) = Sesuai namanya untuk meng-update state history.
  • update(env) = Melakukan update Environment.

Sekarang kita akan bahas satu demi satu:

class Agent:
    def __init__(self, eps=0.1, alpha=0.5):
        self.eps = eps 
        self.alpha = alpha 
        self.verbose = False
        self.state_history = []
  
    def setV(self, V):
        self.V = V

    def set_symbol(self, sym):
        self.sym = sym

    def set_verbose(self, v):
        self.verbose = v

    def reset_history(self):
        self.state_history = []

    def mulai_jalan(self, env):
        r = np.random.rand()
        best_state = None
        if r < self.eps:
            if self.verbose:
                print("Memilih action secara random")

            kemungkinan_pergerakan = []
            for i in range(dimensi):
                for j in range(dimensi):
                    if env.kosong(i, j):
                        kemungkinan_pergerakan.append((i, j))
            idx = np.random.choice(len(kemungkinan_pergerakan))
            pergerakan_selanjutnya = kemungkinan_pergerakan[idx]
        else:
            pos2value = {}
            pergerakan_selanjutnya = None
            best_value = -1
            for i in range(dimensi):
                for j in range(dimensi):
                    if env.kosong(i, j):
                        env.board[i,j] = self.sym
                        state = env.akses_state()
                        env.board[i,j] = 0 
                        pos2value[(i,j)] = self.V[state]
                        if self.V[state] > best_value:
                            best_value = self.V[state]
                            best_state = state
                            pergerakan_selanjutnya = (i, j)
            if self.verbose:
                print("Memilih action berdasarkan epsilon greedy")
                for i in range(dimensi):
                    print("------------------")
                    for j in range(dimensi):
                        if env.kosong(i, j):
                            print(" %.2f|" % pos2value[(i,j)], end="")
                        else:
                            print("  ", end="")
                            if env.board[i,j] == env.x:
                                print("x  |", end="")
                            elif env.board[i,j] == env.o:
                                print("o  |", end="")
                            else:
                                print("   |", end="")
                    print("")
                print("------------------")
        env.board[pergerakan_selanjutnya[0], pergerakan_selanjutnya[1]] = self.sym

    def update_state(self, s):
        self.state_history.append(s)

    def update(self, env):
        reward = env.reward(self.sym)
        target = reward
        for prev in reversed(self.state_history):
            value = self.V[prev] + self.alpha*(target - self.V[prev])
            self.V[prev] = value
            target = value
        self.reset_history()

Penjelasan:

  • Line 1 mendefinisikan nama class Agent.
  • Line 2 mendefinisikan method __init__ di mana ia memerlukan 2 input yaitu epsilon (eps) dan alpha. Epsilon yang dimaksud adalah koefisien epsilon greedy. Kita set nilai defaultnya adalah 0.1, tentu saja pembaca bisa merubahnya. Paramater alpha yang dimaksud adalah learning rate. Umumnya orang banyak memakai nilai 0.5 untuk parameter ini.

Apa itu epsilon greedy? Untuk mereview silakan baca kembali artikel saya di link ini.

  • Line 3-6 adalah nilai masing-masing attributes di method __init__. Kita set verbose dengan nilai False. Verbose ini digunakan untuk mencetak informasi di layar jika diperlukan. Pembaca bisa saja merubah namanya menjadi selain verbose, namun istilah ini sudah umum dipakai di dunia ML. Kemudian, state_history kita set kosong di awal.
  • Line 8-18 mendefinisikan attributes setV, set_symbol, set_verbose dan reset_history.
  • Line 21 mendefinisiksn variabel r secara random yang nantinya akan menentukan apakah Agent berjalan secara random atau sesuai epsilon greedy. Jika nilainya lebih kecil dari eps maka ia akan berjalan random, jika lebih maka sebaliknya.
  • Line 22 mendefinisikan bahwa belum ada best_state secara default.
  • Line 24-33 adalah langkah yang diambil oleh Agent jika nilai r lebih kecil dari eps. Dia akan mencetak di layar, memberitahu kita bahwa Agent bergerak secara random. Kemudian ia akan mendata semua kemungkinan pergerakan yang ada dan memilih salah satunya secara random menggunakan attribute pergerakan_selanjutnya.
  • Line 35-48 sangat mirip dengan line 24-33 tapi kali ini Agent bergerak berdasarkan epsilon greedy. Kita akan melakukan looping ke seluruh posisi (kotak) di papan (board) TTT. Kemudian akan kita cek apakah kotaknya kosong atau tidak. Jika kotaknya kosong kita cek nilai (value) nya. Jika nilai kotak tadi lebih besar dari nilai terbesar yang ada, maka kita akan mengganti nilai terbesar (best_value) dan posisi terbaik (best_state) sebelumnya dengan nilai dan state dari kotak tersebut. Dengan demikian, Agent akan bergerak (pergerakan_selanjutnya) ke posisi yang terbaik.
  • Line 35 dan line 65 digunakan untuk melakukan mapping sekaligus mencetak papan jika verbose bernilai True. Dua lines ini berkaitan dengan line 49-55. Line 35 menggunakan dictionary di python.
  • Line 66 untuk mengisi board dengan simbol X atau O.
  • Line 68-69 digunakan untuk mengupdate state_history.
  • Line 71-78 adalah method untuk mengupdate reward dan value function di sisi Agent (review lagi formula value function dan bagaimana Agent memilih langkah dengan mengupdate V(s) secara mundur) di artikel ini.

Mendefinisikan Pemain (Human)

Class Human jauh lebih mudah dipahami, karena class ini merepresentasikan kita sebagai lawan tanding dari AI. Setiap line dalam class ini sudah langsung bisa menjelaskan maksud dan tujuannya.

class Human:
    def __init__(self):
        pass

    def set_symbol(self, sym):
        self.sym = sym

    def mulai_jalan(self, env):
        while True:
            move = input("Masukkan koordinat di papan i,j untuk pergerakan selanjutnya (i,j=0-2): ")
            i, j = move.split(',')
            i = int(i)
            j = int(j)
            if env.kosong(i, j):
                env.board[i,j] = self.sym
                break

    def update(self, env):
        pass

    def update_state(self, s):
        pass

Script Utama (AI Mulai Pertama)

Sekarang kita akan membahas bagaimana permainan TTT ini berlangsung. Hal yang perlu dipahami adalah kita ingin melatih AI dengan cara bermain melawan dirinya sendiri sebanyak 20 ribu kali! Dengan harapan ia akan benar-benar menjadi pemain yang sangat handal.

if __name__ == '__main__':
    p1 = Agent()
    p2 = Agent()

    env = Environment()
    state_winner_triples = akses_state_end_winner(env)

    Vx = awal_V_x(env, state_winner_triples)
    p1.setV(Vx)
    Vo = awal_V_o(env, state_winner_triples)
    p2.setV(Vo)

    p1.set_symbol(env.x)
    p2.set_symbol(env.o)

    T = 20000
    for t in range(T):
        if t % 200 == 0:
            print(t)
        bermain(p1, p2, Environment())

    human = Human()
    human.set_symbol(env.o)
    while True:
        p1.set_verbose(True)
        bermain(p1, human, Environment(), draw=2)
        jawaban = input("Ingin bermain lagi? [Y/n]: ")
        if jawaban and jawaban.lower()[0] == 'n':
            break

Penjelasan:

  • Line 1 digunakan untuk memberitahu kepada sistem bahwa ini akan jadi perintah utama (if __name__ == ‘__main__’).
  • Line 2 dan 3 memberikan perintah bahwa pemain 1 dan 2 adalah Agent AI itu sendiri. Artinya AI akan melawan dirinya sendiri dengan tujuan untuk belajar mengevaluasi langkah-langkahnya.
  • Line 5 mendefinisikan variabel env sebagai representasi dari class Environment.
  • Line 6 mendefinisikan variabel state_winner_triples sebagai representasi dari fungsi akses_state_end_winner dengan attribute env.
  • Line 8 mendefinisikan variabel Vx sebagai representasi dari fungsi awal_V_x dengan attributes env, dan state_winner_triples. Line 10 adalah untuk Vo.
  • Line 9 adalah untuk menginisiasi value function Vx untuk pemain pertama, dan line 11 adalah Vy untuk pemain kedua.
  • Line 13 menugaskan pemain pertama untuk menggunakan simbol X, dan line 14 menugaskan pemain kedua menggunakan simbol O.
  • Line 16 mendefinisikan variabel T di mana kita ingin melatih Agent bermain sebanyak 20 ribu kali.
  • Line 17-20 adalah untuk menjalankan fungsi bermain sehingga Agent bisa bermain sebanyak 20 ribu kali.
  • Line 22 mendefinisikan variabel human sebagai representasi dari class Human.
  • Line 23 mendefinisikan bahwa Human akan menggunakan simbol O. Tentu saja pembaca bisa menggantinya dengan simbol X jika diinginkan.
  • Line 24-29 adalah eksekusi permainan dengan menggunakan While loop. Looping ini akan berhenti jika kita memilih untuk tidak melanjutkan permainan setelah ada pemenang atau draw dengan memasukkan nilai n di console (layar).
  • Line 25 mensetting set_verbose untuk p1 dengan nilai True.
  • Line 26 memulai permainan di mana AI (p1) akan mulai lebih dahulu. Tentu saja kita bisa membaliknya sehingga Human akan mulai lebih dahulu (kita bahas nanti). Kita tulis draw = 2 jika AI mulai dahulu, dan draw = 1 jika Human mulai dahulu.
  • Line 27 mendefinisikan variabel jawaban di mana kita akan memasukkan n ke layar untuk berhenti.
  • Line 28-29 adalah perintah jika jawabannya n maka programnya akan berhenti.

Dengan script ini maka AI akan mulai bermain lebih dahulu sebanyak 20 ribu kali.


Human Mulai Pertama

Jika ingin kita bermain pertama, maka ubah scriptnya menjadi seperti ini:

if __name__ == '__main__':
    p1 = Agent()
    p2 = Agent()

    env = Environment()
    state_winner_triples = akses_state_end_winner(env)

    Vx = awal_V_x(env, state_winner_triples)
    p1.setV(Vx)
    Vo = awal_V_o(env, state_winner_triples)
    p2.setV(Vo)

    p1.set_symbol(env.x)
    p2.set_symbol(env.o)

    T = 20000
    for t in range(T):
        if t % 200 == 0:
            print(t)
        bermain(p1, p2, Environment())

    human = Human()
    human.set_symbol(env.x)
    while True:
        p2.set_verbose(True)
        bermain(human, p2, Environment(), draw=1)
        jawaban = input("Ingin bermain lagi? [Y/n]: ")
        if jawaban and jawaban.lower()[0] == 'n':
            break

Untuk melanjutkan membaca silakan klik tombol halaman selanjutnya di bawah ini.

Bagikan artikel ini:

Pages: 1 2 3 4 5

1
Leave a Reply

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Anton Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Anton
Guest
Anton

mantapppp… Langsung praktekin.!!