Reinforcement Learning: Bermain Tic-Tac-Toe

Reinforcement Learning: Bermain Tic-Tac-Toe

Catatan penting : Jika pembaca benar-benar awam tentang apa itu Python, silakan klik artikel saya ini.

Catatan kedua: Untuk bisa mengerti bahasa Python kali ini, pembaca harus sudah memahami konsep OOP (Object Oriented Programming).

Catatan ketiga: Untuk bisa memahami artikel ini dengan baik, pembaca harus sudah memahami konsep dan istilah-istilah dalam Reinforcement Learning.


Permainan Tic-Tac-Toe

Kali ini kita akan belajar bersama bagaimana membuat program reinforcement learning (RL) untuk permainan yang sudah sangat terkenal yaitu tic-tac-toe (TTT). Permainan ini terdiri dari 9 kotak berukuran 3 x 3, di mana kita harus mengisi tiga kotak secara sejajar atau diagonal. Kotak yang diisi bisa berbentuk apapun, namun umunya digunakan 2 simbol untuk mengisinya yaitu X dan O.

Ilustrasi tic-tac-toe tampak sebagai berikut:

Ilustrasi tic-tac-toe
Ilustrasi Tic-Tac-Toe

Secara garis besar, kunci untuk menang permainan ini adalah sebagai berikut:

  1. Jika sekarang giliran kita dan kotak di bagian tengah kosong, maka segera isi kotak bagian tengah.
  2. Jika lawan sudah mengisi dua kotak secara sejajar (termasuk diagonal), maka segera isi kotak ketiganya agar lawan tidak menang.
  3. Jika sekarang giliran kita dan kita sudah mengisi dua kotak secara sejajar (termasuk diagonal), maka segera isi kotak ketiganya agar kita menang.

Pada dasarnya mudah sekali untuk bermain TTT, dan hampir semua orang juga mengetahui kunci memenangkan permainan ini. Namun sekarang permasalahannya adalah bagaimana caranya agar kita bisa mengajarkan kepada mesin kita cara bermain TTT?

Perlu diingat bahwa jika kita ajarkan program cara bermain seperti di atas (3 langkah bermain TTT), maka permainan TTT menjadi sebuah prosedur yang linear dan membosankan. Tidak akan ada variasi, dan program kita akan menjadi program komputer yang standar, di mana ia hanya akan berisi perintah IF … ELSE IF … ELSE IF … dan seterusnya.

Yang kita inginkan adalah mengajarkan kepada agent kita (sebutan untuk pemain utama game) sebuah skill (kemampuan dasar) agar ia bisa bermain game apapun , dan dalam hal ini kita ajarkan dulu bermain TTT, Maka solusi untuk hal tersebut adalah dengan menggunakan teknik RL.

Garis besar yang akan kita lakukan adalah sebagai berikut:

  • Kita memiliki model bagaimana permainan ini dilakukan.
  • Kita memiliki state (kondisi) dengan reward tertinggi, yaitu ketika kita bisa berhasil mengisi 3 kotak secara sejajar (termasuk diagonal).
  • Kita tahu bagaimana agent berubah dari state satu ke state lainnya.
  • Dengan melakukan sebuah action baru, maka agent mendapatkan state baru.

Terminologi Reinforcement Learning

Sekarang mari kita review lagi diagram berikut ini:

Diagram reinforcement learning
Diagram alur reinforcement learning

Melalui diagram di atas, maka bisa kita terjemahkan ke dalam permainan TTT kita, di mana:

  • Agent: Sebuah objek/pelaku yang bermain TTT
  • Environment: Segala sesuatu di mana agent bisa berinteraksi dengannya
  • State: Kondisi di mana agent berada setelah melakukan sebuah action.

Untuk mendapatkan pemahaman yang baik, kita akan sedikit membahas semua istilah di atas melalui beberapa contoh.

State adalah suatu kondisi di mana ia bisa dirasakan (diindera) oleh agent. Sebagai contoh, anggap kita memiliki sebuah handphone yang sedang menyala dan sedang kita pegang, dan posisi kita sedang berada di Indonesia. Maka nyala tidaknya handphone ini tidak akan dipengaruhi oleh segala sesuatu yang terjadi di Belanda. Nyala tidaknya handphone ini hanya dipengaruhi oleh kita yang memegangnya, atau juga oleh segala sesuatu yang berada di dekatnya. Dengan demikian, nyala tidaknya handphone adalah state, dan segala sesuatu yang berada di dekat handphone yang bisa memengaruhinya adalah environment-nya. Bisa dipahami ya sampai sini.

Sekarang kita bahas tentang action. Action adalah segala sesuatu yang bisa dilakukan oleh agent, di mana jika ia lakukan maka state nya agent juga akan berubah. Dalam konteks handphone seperti contoh di atas, action adalah menekan tombol power di handphone untuk menyalakan/ mematikannya. Dalam konteks TTT, maka action yang dimaksud adalah menempatkan symbol (X atau O, pilih salah satu) ke dalam salah satu kotak TTT.

Dengan melakukan sebuah action, maka sang agent akan mendapatkan state baru, dan ada kemungkinan agent akan mendapatkan reward. Keputusan apakah sebuah state tertentu bisa memberikan reward atau tidak, kita tentukan sendiri nantinya.

Reward adalah penghargaan yang diberikan kepada agent karena ia berada di state tertentu. Reward tidak menjelaskan apakah keputusannya (action-nya) baik atau buruk, melainkan ia hanyalah angka kuantitatif yang didapatkan oleh agent. Akumulasi reward yang didapat untuk sekian banyak iterasi belum tentu menggambarkan reward yang akan ia dapatkan di masa mendatang.

Agent tidak mengetahui desain sistem (penilaian) untuk bisa mendapatkan reward. Hanya kita sang pendesain sistem yang memahaminya.

Istilah lain yang harus dipahami adalah episode. Episode merepresentasikan satu siklus permainan. Sebagai contoh, kita memulai permainan TTT dengan 9 kotak kosong (3 x 3). Lalu ketika salah satu pemain berhasil memenangkan permainan dengan mengisi tiga kotak secara sejajar (termasuk diagonal) maka berakhirlah 1 episode. Agent kita akan belajar bermain sekian banyak episodes, bisa jadi 1000, 100.000 bahkan sampai sejuta episodes.

Memainkan game TTT di RL disebut dengan episodic task, karena agent kita bermain berkali-kali (setiap 1 episode selesai, ia akan memulainya lagi) sampai kita tentukan berapa jumlah maksimal episodes-nya.

Kapan sebuah episode berakhir? Itu semua ditentukan oleh state yang kita desain agar 1 episode berakhir. Dalam kasus TTT maka ada 2 kondisi (disebut dengan istilah terminal states) yang bisa membuat sebuah episode berakhir, yaitu ketika:

  • Salah satu pemain berhasil mengisi tiga kotak secara sejajar (termasuk diagonal), atau
  • Semua kotak sudah terisi penuh, sehingga tidak ada kemungkinan pengisian kotak lagi. Jika ini terjadi maka tidak ada yang menang dan tidak ada yang kalan (draw).

Agent kita di tahap-tahap awal (episodes awal) pasti akan banyak melakukan kesalahan / kalah di permainan. Ia akan belajar episode demi episode. Setiap episode baru dimulai, ini seperti permulaan baru baginya, dan ia terus mengakumulasikan (mengumpulkan) pembelajaran dari episodes sebelumnya. Dengan demikian, lama kelamaan ia akan semakin pintar, bahkan bisa jadi ia tidak akan pernah melakukan kesalahan.

Bisa dipahami ya. Jika belum, maka coba dibaca lagi pelan-pelan sampai dipahami dengan benar.


Notasi Reinforcement Learning

Umumnya jika kita menggunakan teknik RL, maka kita sering menggunakan notasi (penggunaan simbol) yang sudah dikenal oleh para pengguna teknik RL. Notasinya sering ditulis sebagai berikut:

S(t), A(t) –> R(t+1), S(t+1)

Jika kita terjemahkan ke dalam bahasa, maka agent yang berada pada state tertentu (S) di waktu tertentu (t) melakukan action (A) pada waktu t tersebut, akan membawa agent tersebut ke state yang baru (S) di waktu baru (t+1), dan reward (R) pada waktu yang baru tersebut (t+1).

Notasi di atas adalah notasi matematis. Untuk keperluan programming notasinya sering ditulis dalam bentuk yang mirip tapi lebih sederhana:

(s, a, r, s’)

s = S(t), yaitu state awal

a = A(t), yaitu action yang dilakukan

r = reward yang didapat karena melakukan a ketika berada di s

s’ = state yang didapat ketika kita melakukan a dari s

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