Reinforcement Learning: Bermain Tic-Tac-Toe

Reinforcement Learning: Bermain Tic-Tac-Toe

Sebelum kita melakukan programming di Python, kita harus paham dulu bahwa kita akan bermain dengan OOP (object oriented programming) dan mendefinisikan beberapa classes. Kita perlu sebuah objek (class) yang berperan sebagai agent (pemain AI), sebuah objek sebagai human (kita sebagai manusia), dan sebuah objek sebagai environment (lingkungan termasuk user interface). Dengan demikian kita memiliki 3 classes. Setelah itu kita definisikan beberapa fungsi di script kita seperti fungsi untuk update, fungsi untuk bermain, dan lain-lain.

Langkah selanjutnya dalam membuat script RL adalah kita harus memahami kerangkanya (outline) nya, yaitu bagaimana objek satu dengan yang lainnya saling berinteraski.


Mendefinisikan Fungsi: bermain

Kita memiliki class dengan nama Agent, di mana ia akan berinteraksi dengan Environment. Untuk bisa berinteraksi, maka kita definisikan sebuah fungsi dengan nama bermain. Fungsinya adalah sebagai berikut:

def bermain(p1, p2, env, draw=False):
    pemain_saat_ini = None
    while not env.game_over():
        if pemain_saat_ini == p1:
            pemain_saat_ini = p2
        else:
            pemain_saat_ini = p1
        if draw:
            if draw == 1 and pemain_saat_ini == p1:
                env.menampilkan_board()
            if draw == 2 and pemain_saat_ini == p2:
                env.menampilkan_board()
        pemain_saat_ini.mulai_jalan(env)
        state = env.akses_state()
        p1.update_state(state)
        p2.update_state(state)
    if draw:
        env.menampilkan_board()
    p1.update(env)
    p2.update(env)

Penjelasan:

  • Line 1 kita mendefinisikan fungsi dengan nama bermain, di mana ia memerlukan 4 attributes yaitu p1, p2, env, dan draw dengan nilai default-nya adalah False. Ada dua pemain di sini, yaitu p1 dan p2. Sementara env yang dimaksud di sini adalah Environment.

Perlu dipahami bahwa ketika kita mendefinisikan attributes di dalam sebuah fungsi bisa jadi attributes yang ditulis tidak didefinisikan di dalam fungsi tempat ia dipanggil (dieksekusi). Sebagai contoh, attribute env, game_over, mulai_jalan, akses_state, update_state, menampilkan_board dan update tidak kita definisikan di fungsi bermain; mereka didefinisikan di fungsi atau class lain, dan semuanya terakumulasi saat ingin dieksekusi di bagian akhir nanti.

Yang ingin saya katakan adalah (khususnya jika pembaca sangat baru di programming), ketika mengeksekusi perintah utama (main script) nantinya, maka script ini akan jalan tanpa masalah jika semua attributes yang dia panggil juga sudah didefinisikan. Jika tidak, maka ia akan error.

Ikuti saja dulu, nanti akan mudah ketika melihat semua script nya secara keseluruhan.

  • Line 2 kita definisikan sebuah variabel dengan nama pemain_saat_ini dengan nilai default adalah None. Artinya variabel ini adalah variabel kosong yang nantinya diisi dnegan nilai di line selanjutnya.
  • Line 3 menggunakan While loop, di mana kita ingin agar ia terus melakukan looping (terus bermain) selama permainan belum selesai (game_over).
  • Line 4-16 adalah perintah yang berada di dalam While loop.
  • Line 4-7 memastikan bahwa p1 akan selalu mulai lebih dahulu dibandingkan p2. Caranya adalah dengan menggunakan IF ELSE. Perintah ini juga memastikan bahwa pemain selalu bergantian. Jika p1 sudah selesai, maka sekarang giliran p2.
  • Line 8-12 bertujuan untuk menampilkan papan TTT (tic-tac-toe) yang sudah diisi dan siapa yang mengisinya, apakah p1 atau p2. Itu semua dilakukan jika kondisinya drawi (seri), artinya tidak ada yang menang dan kalah.
  • Line 13 adalah perintah agar pemain yang sedang aktif (apakah p1 atau p2) melakukan action dengan cara menjalankan fungsi mulai_jalan.
  • Line 14-16 bertujuan untuk melakukan update pada state yang ada di Environment.
  • Line 14 mendefinisikan variabel state di mana ia akan diisi oleh state Environment yang ada saat ini.
  • Line 15 adalah perintah di mana state akan diupdate oleh p1 dengan cara menjalankan fungsi update_state.
  • Line 16 sama seperti line 15, namun dilakukan oleh p2.
  • Line 17-18 adalah perintah untuk menampilkan papan TTT jika kondisinya drawi (seri).
  • Line 19 dan 20 adalah perintah untuk melakukan update di value function yang dimiliki oleh masing-masing pemain. Ini adalah saat di mana setiap pemain melakukan update untuk bisa menentukan mana langkah yang terbaik. Line 19 adalah untuk p1 dan line 20 untuk p2.

Mendefinisikan State

Sekarang kita harus bisa mendefinisikan state dalam permainan TTT ini. Seperti kita ketahui, bahwa TTT memiliki 9 kotak (cell) berukuran 3×3. Kemudian setiap kotak ini bisa diisi dengan 3 kemungkinan, yaitu X, O atau kosong (_). Dengan demikian, jika 9 kotak kita tulis sejajar, maka kombinasinya tampak sebagai berikut:

X X X X X X X X X = 9 kali X

OOOOOOOOO = 9 kali O

_ _ _ _ _ _ _ _ _ = 9 kali _

Jika kita hitung jumlah kombinasinya maka akan didapat sebanyak 3x3x3x3x3x3x3x3x3 (atau 3 pangkat 9) yaitu sebanyak 19683 kemungkinan.

Untuk permasalahan permainan TTT yang masih sederhana, kita akan menyimpan 19683 kemungkinan ini di memory dengan menggunakan numpy array. Tentunya dalam kenyataan tidak mungkin semua kemungkinan ini akan terjadi (tidak mungkin semua kotak diisi X misalnya) karena ada 2 pemain di sini (p1 dan p2). Jadi walaupun ada banyak kemungkinan sebanyak 19683, hal ini tidak akan memengaruhi script kita (algoritma) secara keseluruhan. Semua kemungkinan ini tidak akan muncul di state, sehingga kita tidak perlu khawatir.

Sekarang kita tahu bahwa setiap kotak bisa diisi 3 pilihan (X, O, atau _). Dengan demikian, kita bisa membuat fungsinya agar Agent bisa mengakses state-nya. Perlu diingat bahwa total kita memiliki 19683 states.

Karena kita memiliki 3 pilihan, maka penulisan state mirip seperti merubah angka binary ke decimal dengan menjumlahkan setiap perkalian antara nilai binary dengan 2 pangkat nilai binary-nya, dituliskan sebagai berikut:

Formula binary ke decimal
Formula binary ke decimal

di mana koefisien b diisi dengan 0 atau 1 (binary) hanya terdiri dari pilihan angka 0 dan 1).

Lalu apa hubungannya dengan kasus kita? Karena kita memiliki 3 pilihan, maka angka 2 cukup diganti angka 3, di mana koefisien b : pilihan kosong (_) adalah 0, pilihan X adalah 1, dan pilihan O adalah 2. Dengan demikian formulanya menjadi:

Formula pengisian state untuk TTT

Kita akan membuat fungsinya dengan nama akses_state. Berikut adalah fungsinya:

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

Penjelasan:

  • Line 1 mendefinisikan fungsinya dengan nama akses_state.
  • Line 2 mendefinisikan variabel k dengan nilai 0 yang nantinya akan diupdate di line bawahanya. Variabel k ini berfungsi sebagai counter.
  • Line 3 mendefinisikan variabel h dengan nilai 0 yang nantinya akan diupdate di line bawahnya. Variabel h ini berfungsi untuk melakukan update nilai state-nya.
  • Line 4-13 melakukan looping dengan menggunakan for loop.
  • Line 4 memulai looping dengan melakukan iterasi sepanjang ukuran dimensi kolomnya (dalam hal ini 3). Variabel dimensi didefinisikan di luar fungsi ini.
  • Line 5 adalah kelanjutan dari line 4, di mana kita akan memulai looping lagi (sebagai tambahan) sepanjang ukuran dimensi barisnya (3 baris).
  • Line 6-7 adalah pengisian state bernilai 0 jika ia adalah kotak kosong.
  • Line 8-9 adalah pengisian state bernilai 1 jika ia adalah kotak diisi dengan simbol X.
  • Line 10-11 adalah pengisian state bernilai 2 jika ia adalah kotak diisi dengan simbol O.
  • Line 12 adalah h, di mana ia mewakili nilai state nya (seperti koefisien b dalam formula di atas).
  • Line 13 adalah k, di mana ia mewakili counter (seperti N dalam formula di atas).
  • Line 14 mengembalikan nilai h ke sistem agar bisa diakses oleh Agent nantinya.

Mendefinisikan Value Function

Dalam permainan TTT ini kita harus bisa mendefinisikan semua value state (V(s)) dari value function yang mungkin, di mana ini akan menjadi dasar Agent bergerak untuk memilih solusi terbaik.

Secara logika kasar (common sense) kita bisa saja mencari semua kemungkinan nilai V(s) dengan menjabarkan (enumerate) semua kemungkinan yang terjadi. Namun tentu saja ini akan memakan banyak memory, karena ada banyak sekali kemungkinannya. Jika kita lakukan enumerasi maka akan tampak seperti sebuah decision tree. Ilustrasi enumerasi semua kemungkinan bisa dilihat sebagai berikut:

Enumerasi value TTT
Enumerasi value TTT

Decision tree di atas jika dijabarkan maka:

  • Langkah pertama dimulai dari 9 pilihan
  • Langkah kedua ada 8 pilihan
  • Langkah ketiga ada 7 pilihan
  • Jika diteruskan sampai ujung, maka hanya tersisa 3 pilihan langkah saja.

Jika kita jabarkan maka akan ada 9! (9 faktorial) atau sama saja dengan 362880 pilihan dan ini jauh lebih besar dari saat kita mendefinisikan jumlah state di pembahasan sebelumnya (3 pangkat 9).

Dengan demikian, yang akan kita lakukan untuk me-generate state value nya adalah dengan meng-enumerasi semua permutasinya. Perlu diingat bahwa nilai v kita berkisar antara 0, 1 atau 2. Maka fungsinya akan tampak sebagai berikut:

def akses_state_end_winner(env, i=0, j=0):
    results = []
    for v in (0, env.x, env.o):
        env.board[i,j] = v
        if j == 2:
            if i == 2:
                state = env.akses_state()
                ended = env.game_over(proses_rekalkulasi=True)
                winner = env.winner
                results.append((state, winner, ended))
            else:
                results += akses_state_end_winner(env, i + 1, 0)
        else:
            results += akses_state_end_winner(env, i, j + 1)
    return results

Fungsi ini bertujuan untuk mengembalikan ke sistem 3 variabel, yaitu:

  1. State
  2. Winner (siapa pemenangnya di state tersebut jika memang ada)
  3. Ended (apakah game sudah berakhir atau belum di state tersebut)

Penjelasan:

  • Line 1 mendefinisikan nama fungsinya yaitu akses_state_end_winner. Sesuai namanya, yang ingin kita dapatkan adalah 3 variabel. Input dari fungsi ini adalah env, i, dan j.
  • Line 2 mendefiniskan variabel dengan nama results sebagai variabel kosong yang nantinya diisi oleh line di bawahnya.
  • Line 3-14 adalah for loop untuk nantinya mengakses 3 variabel.
  • Line 3 for loop dengan inputnya adalah 3 variabel yaitu 0, env.x dan env.o. Artinya ia akan melakukan iterasi sebanyak 3 kali. Env.x dan env.o merepresentasikan posisi simbol X dan simbol O yang didefinisikan di luar dari fungsi ini.
  • Line 4 bertujuan untuk mengisi koordinat papan TTT (i,j) dengan nilai v, di mana v ini tergantung dari apakah ia diisi oleh simbol X, O atau kosong (dijelaskan di line 3). Ketika papannya kosong, maka sudah pasti nilai v adalah nol.
  • Line 5 dan 6 memberikan gambaran jika semua koordinat sudah terisi penuh (i,j) = (2,2) maka proses looping sudah selesai. Kita tinggal mengambil hasilnya (results). Perlu diingat bahwa i adalah kolom dan j adalah baris.
  • Line 7 mengisi variabel state dengan fungsi akses_state().
  • Line 8 mengisi variabel ended dengan fungsi game_over(). Attribute proses_rekalkulasi kita setting dengan nilai True. Attribute ini didefinisikan di luar fungsi ini (di fungsi game_over di class Environment).
  • Line 9 mengisi variabel winner dengan attribute winner. Attribute ini didefinisikan di luar fungsi ini.
  • Line 10 menambahkan ketiga variabel (state, ended, winner) ke variabel results. Dengan fungsi append maka isi dari list results akan ditambahkan tanpa menghilangkan data-data sebelumnya.
  • Line 11-12 menyatakan jika i belum mencapai nilai 2, maka kita lakukan terus (mengulang lagi dengan mereset j=0 dan menambahkan i dengan 1 sampai i = 2). Hasilnya akan dimasukkan ke variabel results.
  • Line 13-14 menyatakan bahwa kita terus melakukan iterasi. Kali ini nilai i bernilai sama, namun j terus ditambahkan sampai j = 2. Jika nilai j = 2, maka line 5 akan tereksekusi.
  • Line 15 mengembaikan hasil variabel results ke sistem.

Mengisi Value Function untuk X dan O

Sekarang kita ingin mengisi value function untuk pemain 1 dan pemain 2. Masing-masing pemain merepresentasikan masing-masing simbol (X atau O).

Sudah kita bahas di halaman sebelumnya, bahwa ada 3 kemungkinan value function dari terminal state (state akhir) TTT kita, yaitu:

  • V(s) = 1, jika agent menang (winning terminal state)
  • V(s) = 0, jika agent kalah atau menang (lose or draw terminal state)
  • V(s) = 0.5, selain keduanya di atas

Karena X dan O selalu berlawanan, maka jika X memiliki nilai V(s) = 1 maka V(s) untuk 0 adalah = 0. Begitu pula sebaliknya, jika V_X(s) = 0, maka V_O(s) = 1, dan bernilai 0.5 jika seri (draw). Dengan demikian, masing-masing simbol akan memiliki value function yang berbeda.

def awal_V_x(env, state_winner_triples):
    V = np.zeros(env.num_states)
    for state, winner, ended in state_winner_triples:
        if ended:
            if winner == env.x:
                v = 1
            else:
                v = 0
        else:
            v = 0.5
        V[state] = v
    return V

def awal_V_o(env, state_winner_triples):
    V = np.zeros(env.num_states)
    for state, winner, ended in state_winner_triples:
        if ended:
            if winner == env.o:
                v = 1
            else:
                v = 0
        else:
            v = 0.5
        V[state] = v
    return V

Fungsi awal_V_x dan awal_V_o sama saja, hanya peruntukannya yang berbeda, yang pertama untuk simbol X dan kedua untuk simbol O.

Penjelasan:

  • Line 1 mendefinisikan nama fungsinya yaitu awal_V_x dengan input yang diperlukan adalah env (Environment) dan state_winner_triples (state_winner_triples) didefinisikan di script utama, di mana ia sebenarnya merupakan hasil dari fungsi akses_state_end_winner.
  • Line 2 mendefinisikan variabel V di mana ia akan kita isi dengan angka nol sebanyak jumlah states nya. Untuk itu kita gunakan fungsi numpy.zero.
  • Line 3-11 melakukan for loop di mana kita ingin mengisi variabel V dengan aturan V(s) = 1 jika menang, V(s) = 0 jika kalah dan 0.5 selain keduanya.
  • Line 12 mengembalikan nilai V ke sistem.

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.!!