Membedah AlphaGo


Mungkin Anda sempat mengikuti berita tentang AlphaGo beberapa bulan lalu. AlphaGo merupakan sistem artificial intelligence (AI) yang didesain oleh Google DeepMind yang berhasil mengalahkan pemain Go manusia. Pemainnya bukan sembarang pemain. Melainkan seorang master Go dengan 18 title juara dunia, Lee Sedol. AlphaGo menang dalam pertandingan best-of-five dengan skor 4-1 !

3013s
Sumber: http://www.theguardian.com/technology/2016/mar/12/alphago-beats-lee-sedol-in-third-consecutive-go-game

Pencapaian ini cukup mengejutkan banyak pihak, termasuk perancangnya sendiri, DeepMind. Selama ini Go dianggap sangat kompleks (intractable) untuk dapat dimainkan oleh komputer/AI dibandingkan board games lainnya seperti catur, checkers, dan othello.

Para ahli sebelumnya memprediksi bahwa dibutuhkan paling tidak 1 dekade mendatang agar AI mampu mencapai performa level superhuman di permainan Go. As it happened, fakta yang terjadi dilapangan ternyata jauh lebih cepat dari perkiraan.

Tentunya kita bertanya-tanya, bagaimana bisa AlphaGo mampu mengalahkan juara dunia Go? Apa rahasia dibalik kesuksesan AlphaGo? Dapatkah sekarang kita menyimpulkan bahwa kecerdasan yang dimiliki komputer sama atau bahkan melampaui manusia seperti karakter-karakter film: skynet, ultron?

Tulisan kali ini mencoba membedah cara kerja AphaGo. Sebagian besar tulisan ini berdasarkan paper tentang AlphaGo yang di-publish di Nature.

1. Ramuan AlphaGo

Ramuan utama AlphaGo terdiri dari 3 komponen: Reinforcement Learning (RL), Monte Carlo tree search (MCTS), dan Deep Learning (DL). Bagi yang familiar dengan AI atau machine learning, ketiga komponen tersebut bukan merupakan barang baru dan sudah cukup lama dikaji di bidang pengembangan AI untuk game play.

Penggunaan metode RL dan MCTS untuk AI permainan Go telah dikaji sejak pertengahan tahun 2000-an [Coulom 2006, Muller et al. 2010, Baudis et al. 2012]. Sistem AI nya diklaim sudah mencapai level pemain Go amatir.

Kontribusi utama dari DeepMind adalah mampu meningkatkan level AI nya hingga ke level juara dunia, dengan memanfaatkan Deep Learning. Walaupun DeepMind sekilas tampak hanya menambahkan 1 komponen pada existing system sehingga terbentuklah AlphaGo, ini bukan pekerjaan yang mudah. Dibutuhkan sumber daya komputasi dan human brain yang mumpuni untuk mencapai apa yang telah AlphaGo tunjukkan.

AlphaGo terdiri dari 3 komponen utama: i) Reinforcement Learning (RL), ii) Monte Carlo tree search (MCTS), dan iii) Deep Learning (DL).

Selanjutnya akan dibahas komponen-komponen dari AlphaGo lebih mendetail.

2. Reinforcement Learning

Reinforcement Learning (RL)  merupakan paradigma machine learning yang terinspirasi dari psikologi behaviorisme, yaitu bagaimana manusia atau hewan (selanjutnya, kita sebut sebagai agent) belajar dari pengalamannya berinteraksi dengan environment (lingkungan) [Sutton & Barto 1998]. Sebuah agent dilengkapi kemampuan untuk melakukan berbagai actions.

Perilaku dari aksi yang dilakukan oleh agent tersebut bergantung pada interaksinya dengan lingkungan. Untuk setiap aksi yang dilakukan, agent akan mendapatkan reward atau punishment dari lingkungan. Kemudian, agent “belajar” untuk memperbaiki aksinya dikemudian hari yang dapat memaksimalkan reward atau meminimalkan punishment.

RL berbeda dengan supervised learning (SL) dimana agent tidak pernah diberitahu atau tidak memiliki akses informasi ke tujuan / target utama. Pada SL, data latih selalu dalam bentuk pasangan (x: input, y: label). Pada RL, label y tidak diketahui, namun agent selalu mendapatkan reward / punishment dari setiap aksi. Oleh karena itu, SL diasosiasikan juga dengan istilah “learning with teacher“, sedangkan RL dikenal sebagai “learning with critic“.

Sebagai contoh, perhatikan proses ketika seseorang belajar mengendarai sepeda. Katakanlah actions yang dibutuhkan dalam bersepeda adalah sebagai berikut: mengayuh pedal, memposisikan badan, dan memegang stang. Untuk setiap aksi yang dilakukan, si pembelajar akan merasakan sinyal-sinyal dari environment, misalnya, seberapa cepat sepeda melaju, ke arah mana, dan juga tingkat kemiringan sepeda. Hal-hal yang dirasakan oleh si pembelajar dari environment disebut dengan istilah states.

Aksi berikutnya yang akan dilakukan oleh si pembelajar biasanya bergantung dengan state yang diterima sebelumnya. Kemampuan si pembelajar/agent untuk memutuskan aksi apa yang dilakukan selanjutnya dengan mempertimbangkan state yang diterima disebut sebagai policy.

Di awal percobaan biasanya si pembelajar akan kesulitan menjaga keseimbangan selagi mengayuh sepeda. Sesekali mungkin terjatuh. Perasaan khawatir ketika kehilangan keseimbangan atau rasa sakit ketika terjatuh dapat dianggap sebagai contoh punishment atau negative reward. Secara natural, si pembelajar akan berpikir untuk melakukan sesuatu agar meminimalisir hal-hal tersebut.

Setelah sekian kali percobaan, lama-kelamaan awareness untuk menjaga keseimbangan semakin bertambah. Cara mengayuh, cara memegang stang, dan posisi tubuh menjadi semakin tepat. Tanpa disadari tiba-tiba kita memiliki sense seberapa besar kecepatan minimum yang kita butuhkan agar sepeda tetap seimbang. Lalu perasaan senang, sense of accomplishment pun muncul. Bagi yang sebelumnya biasa berjalan kaki, waktu tempuh untuk mencapai suatu tempat menjadi lebih singkat dengan bersepeda. Hal-hal semacam ini merupakan contoh dari positive reward.

Seiring berjalannya waktu sampailah si pembelajar ke level mature  dalam mengendarai sepeda. Pada level ini, ia bahkah sudah mampu melakukan perencanaan atau memprediski state dan reward seperti apa yang akan diterima ketika melakukan aksi tertentu. “Kalau saya mengayuh dengan kecepatan sekian dan posisi badan seperti ini untuk kondisi jalanan demikian, maka sepedanya seharusnya seimbang dan saya tidak mungkin terjatuh”, kira-kira seperti itu sederhananya. Akumulasi dari future state dan reward yang direncanakan oleh si pembelajar diistilahkan dengan value.

Dari ilustrasi belajar mengendarai sepeda di atas, kita dapat merangkum beberapa elemen utama dari RL (perhatikan kata-kata yang dicetak tebal sebelumnya), yaitu state, action, policy dari agent, reward, value, dan environment. Untuk memudahkan penjelasan yang lebih formal di bagian selanjutnya, kita definiskan elemen-elemen tersebut dalam ekspresi matematis:

  • Himpunan state: \mathcal{S} ;
  • Himpunan action: \mathcal{A};
  • Policy dari agent: \pi: \mathcal{S} \rightarrow \mathcal{A} — fungsi yang menerima input berupa state dan mengembalikan output berupa action;
  • Reward: r: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R} — fungi yang menerima 2 buah input, state dan action, lalu mengembalikan sebuah bilangan real (dapat diasosiakan dengan “skor” untuk pasangan state dan action);
  • Value: v^{\pi}: \mathcal{S} \rightarrow \mathbb{R} — fungsi yang mengakumulasi reward yang akan datang dilihat dari state s_t = s;
  • Environment: \mathcal{T}: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{S} — fungsi yang menerima input berupa state dan action (yang berasal dari policy), lalu mengembalikan state baru. Fungsi ini dapat diinterpretasikan sebagai fungsi transisi dari state yang satu ke state yang lain.

Secara singkat, ekspresi-ekspresi di atas hanya menjelaskan bahwa state dan action dinyatakan dalam “himpunan”, dan policy, reward, value, dan environment dinyatakan dalam bentuk “fungsi”.

Reward vs. value. Fungsi reward dan value saling berkaitan dan sama-sama mengembalikan bilangan real. Agar tidak membingungkan, perlu diingat bahwa kedua fungsi tersebut berbeda secara makna: reward mengkuantifikasi feedback dari lingkungan di masa sekarang, sedangkan value mengkuantifikasi feedback di masa depan.

Bagaimana bentuk spesifik dari himpunan dan fungsi tersebut agar dapat melakukan komputasi secara konkrit? Itu akan sangat bergantung pada konteks permasalahannya. Markov Decision Process (MDP) merupakan salah satu cara mengkonkritkan komputasi pada Reinforcement Learning.

Reinforcement Learning (RL) memungkinkan program komputer (agent) untuk belajar dari lingkungan yang menyediakan reward / punishment untuk setiap aksi yang dilakukan agent dalam mencapai tujuan tertentu. Elemen-elemen penting dari RL adalah sebagai berikut: states, actions, policy, reward, value, dan environment.

3. Markov Decision Process (MDP)

Environment pada Reinforcement Learning dapat diformulasikan dengan Markov Decision Process (MDP) [Howard 1960], yang merupakan sebuah model matematis untuk pengambilan keputusan. MDP sesuai untuk mensimulasi situasi dimana suatu keputusan ditentukan sebagian oleh decision maker, dan sebagian yang lain oleh kejadian acak — seringkali disebut dengan istilah non-deterministic.

Secara formal, MDP merupakan sebuah tuple yang terdiri dari 5 elemen (\mathcal{S}, \mathcal{A}, \mathcal{T}(\cdot, \cdot), r(\cdot), \gamma). Elemen-elemen tersebut, terkecuali \gamma, sudah kita definisikan sebelumnya. \gamma\in [0, 1] merupakan sebuah konstanta yang disebut sebagai discount factor: memberikan bobot seberapa penting reward saat ini dan reward di masa depan (akan saya jelaskan kemudian).

Agar definisi di atas lebih menarik, pertama-tama mari kita asosiasikan himpunan state \mathcal{S} dan action \mathcal{A} pada permainan Go.

  • Himpunan state \mathcal{S} merepresentasikan semua konfigurasi yang mungkin / posisi yang legal dari batu-batu di atas papan Go\mathcal{S}=\emptyset berarti papan tanpa batu. Pada Go, jumlah anggota himpunan \mathcal{S} sangat banyak. Sebagai ilustrasi, pada papan berukuran 19×19 terdapat \sim2.082 \times 10^{170} konfigurasi [Tromp and Farneback, 2015].
Sebuah konfigurasi dari batu-batu Go pada papan berukuran 19×19 grid, yang merupakan sebuah elemen pada himpunan state S (sumber: http://www.tompears.com/goboard.gif)
  • Sebuah elemen dari himpunan action \mathcal{A} merepresentasikan aksi meletakkan batu pada papan Go, bergantung dari konfigurasi papan. Notasi yang lebih tepat untuk himpunan aksi ini yaitu \mathcal{A}(s), dimana s \in \mathcal{S}.

Selanjutnya kita akan memberikan makna terhadap fungsi transisi \mathcal{T} dan fungsi value v^\pi. Pada MDP, karakteristik fungsi-fungsi tersebut adalah sebagai berikut.

i) Fungsi transisi \mathcal{T}: \mathcal{S} \times \mathcal{A} non-deterministik, i.e., untuk setiap s \in \mathcal{S} dan a \in \mathcal{A},

\mathcal{T}(s, a) \sim \mathrm{Pr}(s_{t+1} = s' | s_t = s, a_t = a)

dan memiliki sifat Markov, i.e.,

\mathrm{Pr}(s_{t+1}  | s_t, a_t) = \mathrm{Pr}(s_{t+1}  | s_t , a_t , s_{t-1}, a_{t-1}, \ldots, s_1, a_1).

Singkatnya, \mathcal{T} memiliki karakteristik bahwa state yang berikutnya hanya bergantung pada state dan action saat ini. Istilah lain untuk mendeskripsikan sifat Markov adalah memoryless.

———————

Mengapa Markov? Alasan pertama, komputer sangat menyukainya, dari sisi efisiensi memori dan komputasi: tidak perlu menghabiskan memori untuk menyimpan semua hal di masa lampau untuk mengambil sebuah keputusan di masa sekarang.

Kedua, memberikan sifat Markov pada agent AI, termasuk AlphaGo, cukup logis. Keputusan melakukan aksi berikutnya dalam meletakkan sebuah batu pada papan Go cukup ditentukan oleh konfigurasi batu dan aksi pemain lawan saat ini. Sebagai catatan, pernyataan ini mungkin tidak sepenuhnya benar jika dikaitkan dengan pengambilan keputusan oleh manusia. Bisa jadi pemain Go manusia juga mempertimbangkan 2 atau 3 langkah sebelumnya untuk menghasilkan prediksi yang lebih baik.

———————

ii) Fungsi value v^\pi: \mathcal{S} \rightarrow \mathbb{R} dinyatakan dalam bentuk discounted sum:

\displaystyle v^\pi(s) = \mathbb{E}_{a_j \sim \pi(s_j)} \left[ \sum_{k=0}^{\infty} \gamma^k r(s_{t+k+1}, a_{t+k+1})  \vert s_t = s \right] \quad \quad \quad (1) .

———————

Dalam konteks AlphaGo, fungsi \pi: \mathcal{S} \rightarrow \mathcal{A} merupakan policy yang dimilki AlphaGo untuk meletakkan batu di posisi tertentu. Fungsi value v dapat diartikan sebagai “guru” atau “kritikus” yang memberikan evaluasi terhadap aksi yang dipilih oleh AlphaGo: semakin positif nilai v, maka semakin tepat aksi yang dipilih. Pada game AI, fungsi value v dan reward r umumnya didesain sedemikian rupa sehingga berasosiasi dengan kemenangan atau kekalahan.

———————

Ketika AlphaGo pertama kali diciptakan, policy \pi belum memiliki kemampuan yang mumpuni. RL bertujuan bagaimana membuat AlphaGo menjadi semakin “pintar”. Dalam bahasa MDP, RL mencari policy \pi yang memaksimalkan value v^\pi(s)

\displaystyle \max_{\pi^*} v^\pi(s)

Dengan menggunakan MDP, kita sebenarnya sudah memiliki bahan baku yang cukup untuk menjalankan komputasi AlphaGo. Namun demikian, ada satu permasalahan yang krusial: model MDP yang dipaparkan di atas hanya bekerja untuk satu agent. Untuk memungkinkan terjadinya Reinforcement Learning pada AlphaGo, dibutuhkan interaksi dengan agent yang lain, baik itu pemain manusia ataupun AI Go yang lain, termasuk dirinya sendiri.

4. Model Permainan AlphaGo: Markov Games

Tidak ada agent yang hidup di ruang hampa; ia harus berinteraksi dengan agent yang lainnya untuk mencapai tujuannya.  Begitupun dengan AlphaGo. Framework MDP belum cukup untuk memodelkan interaksi multi-agent.

Adakah framework matematis lainnya yang dapat melakukan hal tersebut? Jawabannya adalah game theory. Oleh karena itu, cukup natural untuk memasukkan unsur game theory pada MDP. Perpaduan antara 2 framework tersebut melahirkan disiplin baru yang disebut Markov games [Littman 1994].

Secara umum, Markov games merupakan konsep dan komputasi yang cukup rumit apabila melibatkan banyak agent. Untungnya, untuk kasus 2 agent, ditambah dengan asumsi zero-sum game, komputasinya dapat dibuat menjadi jauh lebih sederhana. Kasus khusus ini dikenal dengan two-player zero-sum game. Permainan Go termasuk di kategori ini.

Okay. Sekarang mari kita coba konkritkan wacana-wacana di atas. Untuk mengubah MDP menjadi two-player zero-sum game, singkatnya kita hanyalah perlu mendesain fungsi reward dan value secara spesifik.

Reward

Anggap terdapat 1, \ldots, T langkah dalam sebuah sesi permainan Go. T biasa disebut sebagai langkah terminal, bisa berbeda-beda untuk tiap sesi. Kita dapat memformulasikan fungsi reward yang cukup sederhana untuk permainan Go, yaitu

\displaystyle r(s, a)=\begin{cases}R & \text{jika } s=s_T , a=a_T \\ 0 & \text{jika s dan t bukan state dan aksi terminal}\end{cases}\quad\quad\quad(2)

Reward di atas bernilai positif apabila state akhir s_T menunjukkan “kemenangan” dan negatif untuk “kekalahan”; dan tidak ada penalti untuk selain state akhir.

Untuk memasukkan unsur two-player zero-sum game, definisikan fungsi reward untuk 2 pemain/agent, yaitu r_1, r_2. Yang diperlukan hanyalah aturan sebagai berikut:  \displaystyle r_1(s, a) = -r_2(s, a) = r(s, a), yang berarti ketika pemain yang satu menang, pemain yang lain mesti kalah.

Value

Ingat kembali bahwa fungsi reward hanya untuk mengukur feedback pada saat ini. Fungsi value dibutuhkan untuk mengkuantifikasi feedback pada masa mendatang.

Zero-sum games memiliki fungi value optimal yang unik v^* : \mathcal{S} \rightarrow \mathbb{R}, yaitu fungsi rekursif sebagai berikut

\displaystyle v^*(s)=\begin{cases}z_T & \text{jika } s=s_T \\ \max_a \min v^*(\mathcal{T}(s, a))& \text{jika } s \in \{s_1, \ldots, s_{T-1} \}\end{cases}\quad\quad\quad(3),

dimana \mathcal{T}(\cdot, \cdot) merupakan fungsi transisi dan outcome z_t = \pm r(s_T) memberikan nilai hasil akhir dari suatu sesi permainan dari sudut pandang  “agent yang sedang giliran jalan” pada langkah ke-t.

Dengan demikian, MDP yang dibahas pada bagian 3 sebelumnya dapat kita ubah menjadi Markov Games, atau lebih spesifiknya menjadi two-player zero-sum game dengan menggunakan fungsi reward (2) dan fungsi value (3).

Formulasi Markov Games memungkinkan Reinforcement Learning untuk bekerja pada kasus lebih dari satu agent, dimana agent saling berinteraksi satu sama lain.

Makna Fungsi Value Optimal

Sekarang saya ingin mengajak pembaca untuk berhenti sejenak dan bersama-sama mencerna lebih dalam apa makna dan konsekuensi dari fungsi value optimal (3), karena ini sangat krusial. AlphaGo dapat bermain Go dikarenakan komputasi / aproksimasi dari fungsi tersebut.

Pada bagian 3, saya telah membahas bahwa fungsi value berperan sebagai “kritikus”. Dengan demikian, fungsi value optimal v^*(\cdot) dapat diibaratkan sebagai “kritikus sempurna”, yang tidak pernah keliru. Ini berarti AlphaGo tidak akan pernah kalah dalam melawan siapapun, paling tidak, bermain seri jika sepenuhnya mengikuti v^*(\cdot) dan aturannya fair.

Tree.png
Gambar 1. Simulasi perhitungan fungsi value optimal v^*

Secara singkat, fungsi value optimal v^*(\cdot) memberikan agent kemampuan look ahead: memastikan agent untuk menentukan langkah permainan berikutnya yang meminimalisir kekalahan. Detilnya akan lebih mudah dipahami dengan struktur pohon (tree). Node pada tree merepresentasikan sebuah stateedge  (koneksi antar 2 buah node) merepresentasikan action, dan leaf merepresentasikan reward pada state akhir/terminal.

Gambar 1 mengilustrasikan simulasi sederhana dari penghitungan v^*(\cdot), pada dua langkah terakhir permainan. Di sini terdapat dua agent, yaitu Agent 1 yang selalu memilih cabang dengan node maksimum dan Agent 2 yang selalu memilih cabang dengan node minimum. Nilai reward positif pada leaf berarti kemenangan untuk Agent 1, dan nilai reward negatif berarti kemenangan untuk Agent 2.

Pada gambar tersebut Agent 1 sedang mendapatkan giliran bermain. dan dihadapkan dengan pilihan cabang ke kiri atau ke kanan. Karena Agent 1 memiliki policy untuk memainkan “permainan maksimum”, idealnya ia memilih cabang ke kanan, yaitu s^2_{T-1}. Dengan memilih s^2_{T-1} Agent 1 akan berpotensi mendapatkan skor maksimum di akhir permainan, yaitu 8.

Namun demikian, memilih s^2_{T-1} juga memiliki resiko yang tinggi untuk kalah, dikarenakan Agent 2 dilangkah berikutnya akan memilih nilai minimum, yaitu -3. Perhitungan dari fungsi v^* akan memberikan keputusan sebagai berikut:

v^*(s_{T-2}) = \max \{  \min{v^*(s^1_{T-1})}, \min{v^*(s^2_{T-1})}\}

= \max \{ \min\{ 5, 1\}, \min \{-3, 8 \} \} = 1,

yang memastikan Agent 1 untuk memilih cabang ke kiri s^1_{T-1} (warna hijau). Dengan melangkah ke kiri, Agent 1 tidak akan kalah, walaupun tidak berhasil mendapatkan skor maksimum.

Strategi zero-sum semacam ini dikenal dengan istilah minimax search (atau maximin search dari sudut pandang Agent 2).

Kesimpulannya, penghitungan fungsi value optimal sama dengan melakukan tree search. Sudah cukupkah strategi ini untuk membuat agent AI yang tak terkalahkan? Jawabannya sudah, namun dengan satu persyaratan: si agent harus mampu look ahead secara sempurna untuk setiap kemungkinan state.

Pertanyaannya adalah mampukah si agent melakukan look ahead sempurna?

5. Tree Search: Pendekatan Brute Force

Untuk menjawab pertanyaan terakhir, pertama kita mesti pahami terlebih dahulu kompleksitas dari sebuah tree. Kompleksitas tree ditentukan oleh 2 faktor: branching factor (b) dan solution depth (d). Jika dikaitkan dengan board game, branching factor merepresentasikan jumlah aksi legal untuk state tertentu dan solution depth merupakan jumlah langkah total dari suatu state hingga akhir permainan. Sebagai contoh, tree pada Gambar 1 memiliki b=2 dan d=2.

“Look ahead sempurna” secara teknis maksudnya adalah melakukan exhaustive search/brute force pada tree. Ini berarti penghitungan fungsi value optimal  v^* harus melalui semua kemungkinan langkah permainan yang berjumlah b^d + b^{(d-1)} + \ldots + b^2 + b. Dengan kata lain, kompleksitas dari brute force pada tree sebesar b^d.

Strategi brute force tentunya tidak masalah apabila diaplikasikan pada tree di Gambar 1, dengan kompleksitas hanya sebesar 2^2 = 4. Pada board game sesungguhnya ini hampir tidak mungkin dilakukan. Sebagai ilustrasi, permainan catur memiliki b \approx 35, d \approx 80 dan Go memiliki b \approx 250, d \approx 150.

Jika Anda belum memiliki bayangan mengapa brute force pada tree tidak mungkin dilakukan bahkan pada permainan catur, ikuti simulasi kasar berikut ini.

Apabila kita asumsikan kompleksitas brute force pada tree dengan nano seconds, permainan catur memiliki 35^{80} \approx 10^{123} nanoseconds. Di era cloud computing saat ini, mungkin Anda terpikir bahwa komputasi ini barangkali bisa dilakukan di cloud. Sekarang anggaplah kita menggunakan semua atom di alam semesta secara paralel sebagai cluster komputasi pada cloud, yang konon katanya berjumlah 10^{80}, dengan waktu komputasi 1 ns untuk tiap cluster. Dengan menggunakan angka-angka di bawah ini,

  • jumlah detik per tahun: \approx 10^7 detik
  • jumlah nano second per detik: = 10^9 nanoseconds
  • perkiraan umur alam semesta sejak big bang : = 10^{10} tahun,

kita akan ‘hanya’ mendapatkan total waktu 10^{80} \times 10^7 \times 10^9 \times 10^{10} = 10^{106} nanoseconds, dimana brute force pada tree untuk permainan catur memerlukan 10^{123} nanoseconds. 

Dengan kata lain, jika komputasi dengan menggunakan cloud ini dimulai sejak big bang, brute force pada permainan catur ini masih belum selesai, bahkan masih harus menunggu waktu 10 tahun lagi! Bagaimana dengan permainan Go yang memiliki kompleksitas b \approx 250, d \approx 150?? Mudah-mudahan pembaca sekarang sudah memiliki sense betapa kompleksnya look ahead sempurna yang harus dilakukan oleh agent AI.🙂

6. Monte-Carlo Tree Search (MCTS)

Untuk keluar dari permasalahan komputasi yang diuraikan sebelumnya,  kita harus memangkas (pruning) ruang pencarian pada tree. Dengan pemangkasan ini komputasi akan jauh lebih efisien, namun dengan resiko look ahead tidak lagi sempurna. i.e., solusi yang diberikan oleh fungsi value bukan solusi yang optimal. Secara matematis, kita menggunakan fungsi value alternatif yang lebih efisien v^{\pi} yang mendekati fungsi value optimal: v^{\pi}(s) \approx v^*(s)

Salah satu metode yang cukup populer untuk memangkas ruang pencarian adalah alpha-beta pruning dengan skema depth first search [Knuth & Moore 1975]. Alpha-beta pruning membatasi tree untuk menghasilkan percabangan baru dengan memanfaatkan 2 parameter: \alpha dan \beta. Kedua parameter ini berfungsi sebagai lower bound dan upper bound, i.e., tree hanya membuat percabangan baru ketika value dari suatu node berada diantara \alpha dan \beta.

Penjelasan menarik mengenai alpha-beta pruning dapat dilihat di http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html. Metode tree search dengan alpha-beta pruning ini telah berhasil mencapai level superhuman pada permainan catur, checkers, dan othelo, tetapi tidak efisien untuk Go dikarenakan kompleksitasnya yang begitu besar.

Kisah sukses AI pada Go dimulai dengan penggunaan Monte-Carlo Tree Search (MCTS)  yang berbasis simulasi statistik. MCTS memanfaatkan random sampling ketika membuat percabangan baru dari sebuah node. Random sampling dilakukan secara berantai dari suatu non-terminal node hingga ke leaf pada tree / state akhir permainan, yang disebut dengan istilah playout. Ide dasarnya adalah melakukan playout sebanyak mungkin dan menyimpan data statistik menang / kalah dari simulasi tersebut. Data statistik ini, yang di-update secara berkala setiap dilakukan playout, akan digunakan untuk memilih node yang “lebih baik” di playout berikutnya.

Secara umum, MCTS terdiri dari 4 tahap:

  1. Selection: memilih child node “terbaik” berdasarkan data statistik yang sudah ada;
  2. Expansion: jika tidak berakhir di node terminal, buat percabangan baru secara random;
  3. Simulation: melakukan random playout hingga mencapai node terminal;
  4. Backpropagation: meng-update informasi statistik pada tiap-tiap node yang membentuk jalur playout yang dijalankan.

Gambar 2 mengilustrasikan keempat tahapan di atas. Fraksi \frac{A}{B} pada tiap-tiap node mengindikasikan jumlah kemenangan (A) dan total playout yang telah dijalankan.

2000px-mcts_english-svg
Gambar 2. Ilustrasi metode Monte-Carlo Tree Search (diambil dari https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)

Strategi MCTS yang cukup sederhana ini ternyata jauh lebih powerful dibandingkan alpha-beta pruning. Mengapa demikian? Walaupun tujuannya sama, yaitu mengaproksimasi fungsi value optimal v^*(s), MCTS bersifat adaptif, sedangkan alpha-beta pruning cenderung statis. Dengan kata lain, MCTS terus menerus memperbarui kemampuan bermainannya berdasarkan data statistik yang ia terima, sedangkan alpha-beta pruning hanya mengandalkan heuristik yang tidak diperbarui.

AlphaGo menggunakan metode MCTS yang telah termodifikasi dengan menyimpan informasi statistik yang lebih kompleks, namun dengan prinsip kerja yang sama [Silver et al. Nature 2016]. Terobosan utama dari AlphaGo adalah memanfaatkan Deep Learning dan Reinforcement Learning sedemikian sehingga terbentuk sebuah fungsi policy \pi: \mathcal{S} \rightarrow \mathcal{A} yang selevel dengan juara dunia, yang bekerja di dalam mekanisme MCTS.

Monte-Carlo tree search (MCTS) memanfaatkan simulasi statistik untuk mengaproksimasi exhaustive tree search sedemikian sehingga tidak perlu mempertimbangkan semua kemungkinan ketika melakukan pencarian. MCTS lebih powerful dibandingkan alpha-beta prunning dikarenakan karakteristiknya yang dapat memperbarui kemampuannya berdasarkan data. Hal ini menyebabkan MCTS secara natural dapat diintegrasikan dengan algoritma machine learning.

7. Penggunaan Deep Learning

Ingat kembali bahwa tujuan dari Reinforcement Learning adalah mencari policy yang memaksimalkan value, dan policy secara matematis hanya merupakan fungsi yang memetakan state ke action. Pada konteks AlphaGo, tugas dari policy adalah memindahkan batu ke posisi yang mengarahkan pada kemenangan (action) berdasarkan konfigurasi batu pada papan (state).

Problem mencari policy dapat disederhanakan dengan mencari parameter yang tepat, \omega, pada suatu model/fungsi p_{\omega}: \mathcal{S} \rightarrow \mathcal{A}. Problem tersebut analog dengan problem machine learning secara umum. Misalkan sebuah state dinyatakan dalam vektor s \in \mathbb{R}^m, contoh sederhana dari fungsi p adalah model linear p_{\omega}(s) = \omega^{\top} s.

Untuk membentuk agent AI yang kompetitif, kita membutuhkan fungsi yang lebih powerful dari model linear. Salah satu alternatifnya adalah neural networks, yang sekarang ini lebih dikenal dengan deep learning. Dengan ketersediaan data yang banyak dan penggunaan komputasi paralel, neural networks mampu “belajar” dari data secara efisien.

AlphaGo memanfaatkan neural networks baik untuk fungsi policy mauapun untuk fungsi value, yang beroperasi menurut skema MCTS. Terdapat 2 fase learning pada AlphaGo untuk membentuk fungsi policy yang powerful: i) supervised learning (SL) dan ii) reinforcement learning.

Fase SL

Pertama-tama, kita namakan fungsi policy AlphaGo dengan SL policy p_{\sigma} : \mathcal{S} \rightarrow \mathcal{A}. Model yang digunakan untuk fungsi tersebut adalah 13-layer deep convolutional neural networks (ConvNetdengan ReLU sebagai fungsi aktivasi untuk hidden layer dan softmax sebagai fungsi aktivasi untuk output layer.

Pada konteks ini, parameter \sigma merupakan bobot koneksi antar layer pada ConvNet. SL policy di-training untuk memaksimalkan likelihood terhadap action  a yang dipilih pada state s (human expert position) dengan menggunakan stochastic gradient ascent back-propagation:

\displaystyle \Delta \sigma \propto \frac{\partial \log{p_{\sigma}(a | s)}}{\partial \sigma} \.

Pemilihan ConvNet sebagai SL policy model tentunya memiliki alasan tersendiri. Ini dikarenakan ruang state atau input dari SL policy secara fisik merupakan papan Go 2D berukuran 19×19, dimana informasi spasial cukup penting.

Database yang digunakan untuk training SL policy diambil dari KGS Go Server yang memiliki sekitar 30 juta pasangan data state-action: \{ (s_i, a_i) \}. Google DeepMind menggunakan 50 buah Graphical Processing Units (GPU) untuk melatih SL policy AlphaGo selama sekitar 3 minggu. Sebagai perbandingan, pemain Go profesional bermain secara serius sebanyak ~10,000 kali sepanjang hidupnya.

Fase RL

Setelah fase SL selesai, AlphaGo menjalankan fase Reinforcement Learning (RL) untuk meningkatkan kemampuan dari fungsi RL policy p_{\rho}:\mathcal{S} \rightarrow \mathcal{A} dalam memainkan Go. Fungsi RL policy p_{\rho} memiliki struktur yang sama persis dengan fungsi SL policy p_{\sigma}. Dikarenakan karakteristik two-player zero-sum game (lihat bagian 4), AlphaGo memerlukan lawan bermain (agent 2) ketika algoritma RL berjalan. Siapakah lawan bermain dari AlphaGo?

Self-play. Di fase awal RL, AlphaGo bermain melawan dirinya sendiri di versi sebelumnya.  Secara lebih detil mekanismenya sebagai berikut. Pertama-tama parameter \rho diinisialisasi dengan parameter SL Policy yang sudah di training dengan KGS server: \rho_0 := \hat{\sigma}. Kemudian, proses self-play dijalankan: RL policy versi ke-t p_{\rho_t} bermain dengan salah satu dari sekian jumlah RL policy versi sebelumnya, yang dipilih secara random. Alasan mengapa memilih RL policy versi sebelumnya secara random ini untuk mengurangi overfitting.

Jika kita kumpulkan data historis dari self-play, kita akan bisa mengoleksi data set yang digunakan untuk melatih RL policy. Parameter RL policy \rho di-update untuk tiap time-step t dengan stochastic gradient ascent yang memaksimalkan expected outcome dengan gradient dalam bentuk:

\displaystyle \Delta \rho \propto \frac{\partial }{\partial \log{p_\rho(a_t | s_t)}\rho}z_t\quad\quad\quad(4),

dimana a_t, s_t, z_t diperoleh dari self-play, yang berjumlah sebanyak lebih dari 30 juta posisi. Lihat kembali definisi outcome z_t pada bagian 4.

Perlu diketahui bahwa trik self-play ini bukanlah ide yang baru. Teknik ini sudah digunakan sejak TD-Gammon, program AI backgammon yang didesain oleh IBM [Teasuro 1992].

Replay. Tak pelak lagi, lawan main yang lebih natural untuk AlphaGo dibandingkan dirinya sendiri adalah pemain Go manusia atau AI Go yang lainnya. Dengan cara yang sama dengan self-play, seiring dengan bertambahnya lawan main kita pun dapat mengoleksi data historisnya sehingga terbentuk dataset yang baru untuk RL training. Di waktu kemudian, kita dapat melakukan replay pada dataset tersebut untuk meng-update parameter RL policy \rho dengan menggunakan persamaan (4).

3. Value training

Seperti yang telah dibahas pada bagian 4, AlphaGo memerlukan fungsi value untuk melakukan look-ahead dan agar keseluruhan proses RL berjalan. Pilihan ideal adalah fungsi value optimal v^*. Namun kita telah mengetahui bahwa v^* tidak praktis secara komputasi dan memerlukan alternatif lain untuk mengaproksimasi v^*.

AlphaGo menggunakan fungsi value aproksimasi v_{\theta}(s) \approx v^{p_\rho}(s) \approx v^*(s), dimana v_{\theta}(s) : \mathcal{S} \rightarrow \mathbb{R} merupakan ConvNet dengan parameter \theta. v_{\theta}(s) memiliki arsitektur yang sama dengan p_{\rho}, terkecuali output layer-nya, yang mengembalikan nilai skalar. Fungsi v^{p_\rho}(s) dihitung dengan menggunakan Monte-Carlo Tree Search seperti yang dijelaskan pada bagian 6.

Parameter fungsi value \theta dilatih dengan menyelesaikan problem regression, i.e., mean square error (MSE) antara v_\theta(s) dan outcome z, via stochastic gradient descent dengan gradient:

\displaystyle \Delta \theta \propto \frac{\partial v_\theta(s)}{\partial \theta}(z - v_\theta(s))

Teknik memparameterisasi dan mengoptimalkan fungsi policy dan value secara bersamaan ini dikenal dengan nama policy gradient reinforcement learning [Sutton et al. NIPS 2000].

Gambar 3 dibawah ini mengilustrasikan keseluruhan proses dari penggunaan deep learning pada fase SL dan RL.

dl_alphago.png
Gambar 3. Penggunaan Deep Learning di Fase SL dan RL pada AlphaGo. Gambar diambil dari [Silver et al. Nature 2016]

Setelah semua tahap learning selesai, fungsi RL policy p_\rho(a | s) inilah yang digunakan sebagai agent ketika AlphaGo bermain. [Silver et al. Nature 2016] melaporkan RL policy p_\rho ini berhasil meraih kurang lebih 80% kemenangan melawan SL policy p_\sigma dan 99.8% kemenangan melawan AI Go yang lainnya. Versi terdistribusi dari AlphaGo, yang dilatih dengan menggunakan 1,202 CPU dan 176 GPU,  memenangi permainan melawan Fan Hui (juara Go level eropa) dengan skor 5-0.

Seiring berjalannya waktu fase RL terus dilakukan pada AlphaGo, termasuk dari data historis hasil permainan melawan Fan Hui dan lain-lain. Hingga akhirnya terjadilah fenomena dengan berhasilnya AlphaGo mengalahkan juara dunia Lee Sedol !

AlphaGo menggunakan deep convolutional networks untuk memodelkan fungsi policy dan value. Fungsi policy dilatih dengan supervised learning dari KGS server (~30 juta langkah batu Go) dan reinforcement learning via self-play dan replay. Fungsi value dilatih dengan cara menyelesaikan problem regresi antara outcome yang diprediksi oleh fungsi value tersebut dengan outcome hasil simulasi dari Monte-Carlo Tree Search.

8. Caveat

Pesan utama yang kita pelajari dari studi AlphaGo ini adalah bahwa saat ini artificial intelligence sudah sangat kompetitif pada ranah game AI, dengan mengalahkan juara dunia pada permainan Go, yang dianggap sebagai board-game yang paling kompleks. AlphaGo menggabungkan teknik tree search dan machine learning (supervised learning dan reinforcement learning) dalam satu sistem untuk membentuk agent yang mampu memainkan Go.

Ketersediaan jumlah data (~30 juta data posisi batu Go, masing-masing dari KGS server dan self-play) dan juga sumber daya komputasi yang besar (1,202 CPU dan 176 GPU) memainkan peranan yang sangat penting. Ini menjadi faktor utama yang membedakan antara AlphaGo dengan sistem game AI sebelumnya, karena secara algoritmis AlphaGo serupa dengan sistem-sistem AI yang telah ada.

Dengan kemenangan AlphaGo ini, apakah AI telah mengalahkan kecerdasan manusia sepenuhnya (strong AI) seperti pada film-film science fiction? Tentunya kita belum bisa buru-buru menjawab iya. Kecerdasan manusia meliputi banyak aspek antara lain i) reasoning, ii) representing knowledge, iii) planning, iv) learning, v) communication with natural language, vi) sensing, vii) ability to act, dan sebagainya [Russel & Norvig 2003]. Kemenangan AlphaGo ini sekadar mendemonstrasikan AI dapat digunakan untuk menghasilkan pemain boardgame yang kompetitif dan menunjukkan progres kecil (namun signifikan) di beberapa aspek kecerdasaran manusia yang disebutkan di atas, seperti yang dikatakan oleh salah satu perancang utamanya sendiri, Demis Hassabis.

One thought on “Membedah AlphaGo

  1. Saya sering mengikuti blog anda mas Ghifar … seru… terima kasih mas.. ilmu nya sangat bermanfaat bagi saya yang masih baru belajar ini. saya sangat tertarik dengan Machine Learning. dan ingin menanyakan proses perkuliahan disana.. sekalian proses mendapatkan Victoria Doctoral Scholarship dari awal hingga mulai perkuliahan. .. terima kasih sebelumnya, mas ghifar.. maaf saya banyak permintaan..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s