BAB II TINJAU UAN PUS STAKA 2.1
Teori Game G Game ad dalah suatu kegiatan k pem mecahan maasalah yangg dilakukan
denggan pendekattan yang beersifat menyyenangkan(Schell, 2008)). Terdapat empaat buah elem men dasar yanng membenttuk sebuah ggame, yaitu Mechanics, M Storyy, Aesthetics, dan Tecchnology. Keempat K eleemen tersebbut disebut Elem mental Tetradd.
Gambar 22.1Elementaal Tetrad
1. Mechanics M merupakan m p prosedur dan n peraturan yang y berlaku dalam game g 2. Story S merupakan urutan kejadian yaang terjadi daalam game.
7
8 3. Aestheetics merupaakan bagaimaana penampiilan sebuah game dapat mempengaruhi pen ngalaman peemain. 4. Techno ology meruppakan mediaa yang menghhubungkan m mechanics, story, dan aesthetiics.
2.2
Arrtificial Intelligence Penngertian Artif ificial Intelliggence dapat dirangkumkkan sebagai
berikut(Ruussell & Norvvig, 1995):
Gambaar 2.2Pengerrtian AI dikaategorikan menjadi m 4 kategori. •
Acting hu umanly: Thee Turing Test approacch. Dikatakaan menurut Alan Turing (19 950), Kompuuter perlu meemiliki kemaampuan sebaagai berikut: o Natural
languuage proceessing, meemungkinkann untuk dapat d
berrkomunikasi.
9 o Knowledge representation, untuk menyimpan apa yang diketahui atau didengar. o Automated reasoning, untuk menggunakan informasi yang tersimpan untuk menjawab pertanyaan dan menggambarkan kesimpulan baru. o Machine learning, untuk beradaptasi terhadap keadaan baru dan untuk mendeteksi dan meramalkan kemungkinan dari pola yang ada. •
Thinking humanly: The cognitive modeling approach dikatakan untuk mendapatkan program yang dapat berpikir seperti seorang manusia, kita harus mempunyai beberapa cara untuk menentukan bagaimana manusia berpikir dengan cara masuk ke dalam pekerjaan nyata dari pikiran manusia. Ada 3 cara untuk melakukan hal ini: melalui introspeksi-mencoba untuk mendapatkan pemikiran sendiri berdasarkan jalannya pemikiran; melalui eksperimen psikologis-mengamati seseorang dalam aksi; dan melalui brain imaging-mengamati aksi otak. Dari hal tersebut, akan memungkinkan dihasilkan teori seperti program komputer.
•
Thinking rationally: The “laws of though” approach Ada dua poin penting yang berhubungan dengan bagian ini. o bukan hal yang mudah untuk mengambil pengetahuan informal dan menyatakannya dalam istilah formal yang diperlukan oleh notasi logis. o Ada perbedaan besar mengenai penyelesaian masalah secara prinsip dan penyelesain secara praktek.
10 •
Acting rationally: The rational agent approach Pada bagian ini menjelaskan dua keuntungan: o hal ini lebih umum dibandingkan pendekatan peraturan dalam berpikir karena kesimpulan hanya satu dari beberapa mekanisme yang memungkinkan untuk mencapai akal yang logis. o lebih disetujui ke pengembangan
secara ilmiah daripada
pendekatan berdasarkan tingkah laku manusia atau pikiran manusia.
2.3
Game AI Penggunaan kata Game AI (Artificial Intelligence) merupakan
batasan terhadap game dengan kumpulan koleksi programming dan desain perancangan termasuk pathfinding, neural-networks, models of emotion dan social situations, finite-state machines, rule systems, decision-tree learning, dan teknik-teknik lainnya. Game AI memberikan perhatian kepada sifat kepintaran, yang dimana kepintaran yang dapat diperlihatkan ke pemain sebagai aksi dan respon AI itu sendiri. Game AI menghasilkan bagian dari karakterisitik permainan dimana pemain dapat memahami dengan membaca sifat sebagai hasil dari pengejaran atas tujuan dan atas diberikannya beberapa pengetahuan yang saling berhubungan. Akan tetapi Game AI bukan hanya bicara mengenai penyelesaian atas masalah, tetapi juga mengenai unsur kehidupan, unsur dimana ada sesuatu yang hidup dalam komputer yang mempunyai kehidupan sendiri secara bebas terhadap
11 pemain dan peduli terhadap bagaimana aksi dari pemain atas dampak yang diberikan terhadapnya (Mateas (. M., 2003).
2.4
Game AI Research Game AI merupakan sebuah contoh dari ekspresi AI, Penelitian AI
yang mengambil seni dan hiburan berbasiskan AI sebagai first class problem(Mateas (. M., 2001). Berikut rangkuman atas dua tujuan dari penelitian dalam konteks games. •
Game AI focuses on audience experience AI dikatakan selalu memberikan performa, menghibur, menakutkan, dan memukai pemain. Hal pokok yang terdapat pada tujuan AI adalah untuk menciptakan pengalaman bagi pemain. Pengukuran efektifitas yang digunakan pada penelitian AI secara tradisional, seperti waktu untuk menyelesaikan suatu pekerjaan, jumlah eror, dan seterusnya, merupakan langkah panduan pekerjaan AI dalam game. Game AI tidak hanya menyelesaikan pekerjaan dalam dunia game, tapi harus menyelesaikannya dengan style.
•
Game AI supports human authorship Arsitektur AI harus mendukung game artists dalam memberikan ekspresi kesanggupan karakteristik yang diperlukan untuk desain yang spesifik. Game AI dikatakan lebih dari sebuah hasil implementasi dari ketertarikan kepada game designers, game AI merupakan sebuah bahas dari karakteristik yang disengaja. Untuk game designers, game AI
12 mempunyai pengaruh yang kuat terhadap sisi perancangan. Dan untuk para peneliti AI, game AI menawarkan sejumlah tujuan berkelas tinggi, yang membuka tantangan teknis baru.
2.5
Machine Learning Machine Learning mempunyai makna besar dari kata “learning”
itu sendiri. Ada banyak peneliti yang berusaha melakukan pemeriksaan, mengenai apa yang ada di belakang kemampuan seseorang. Tetapi sampai sekarang tidak ada definisi unik yang dapat memberikan arti learning. Berdasarkan penjelasan secara mudah, maka definisi learning itu sendiri
diartikan
mengandung
keteringatan,
kemampuan
untuk
mengkombinasikan fakta yang diketahui dengan baik dan mengenali polapola (Mitchell, 1997). Proses pembelajaran manusia terlalu kompleks untuk digambarkan, tetapi hal ini sangat baik sebagai titik awal untuk memikirkan mengenai hal ini.
Dalam konteks program komputer, machine learning dapat
didefinisikan sebagai berikut(Mitchell, 1997): “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E ” Bidang Machine Learning merupakan evolusi dari bidang besar Artificial Intelligence, yang mengarahkan ke kemampuan memainkan peran kepintaran manusia oleh mesin(Gunnar, R). Dalam bidang Machine
13 Learning, pertanyaan paling penting adalah bagaimana cara membuat mesin dapat mempunyai kemampuan untuk belajar.
2.6
Supervised Classification Supervised Classification merupakan metode klasifikasi yang
digunakan untuk melakukan ekstraksi informasi kuantitatif dari remotely sensed image data (Richards & Jia, 2005). Dengan metode ini, memungkinkan melakukan penghasilan perwakilan dari parameter untuk tiap class yang berkepentingan. Tahap ini dikatakan training. Sekali diberikan training, Classifier lalu digunakan untuk melampirkan label kepada semua pixel pada gambar berdasarkan parameter yang diberikan training sebelumnya.
2.7
Unsupervised Classification Unsupervised Classification merupakan metode klasifikasi yang
digunakan tanpa memerlukan manusia untuk mempunyai pengetahuan terlebih dahulu dari class yang ada, dan sebagian besar menggunakan beberapa algoritma clustering untuk melakukan klasifikasi dari image data(Richards & Jia, 2005).
2.8
NPC (Non Playable Character) NPC merupakan sebuah karakter yang bukan dikontrol oleh
seorang pemain sekaligus merupakan satu dari tantangan utama dalam
14 menghadapi industri video game untuk memberi kehidupan Non-Player Characters(Ochs, Sabouret, & Corruble, 2009).
2.9
CBR (Cased-Based Reasoning) Cased-Based Reasoning (CBR) merupakan teknik berbasiskan
pengetahuan yang dapat mengatasi permasalahan baru berdasarkan pengetahuan dan pengalaman dari masalah lama yang telah sebelumnya dikumpulkan dalam sebuah bentuk kasus dan disimpan dalam sumber atau basis kasus (Leake, 1996).
2.10
Genetic Algorithm Genetic
Algorithm
merupakan
sebuah
famili
dari
model
komputasional yang terinspirasi dari evolusi. Algoritma ini menyandikan sebuah solusi potensial kepada permasalahan yang spesifik pada struktur data yang menyerupai chromosom simpel dan memberikan operator rekombinasi pada struktur-struktur tersebut untuk memelihara informasi kritis (Mathew, 2005).
2.11
Neural Network Neural
Network
merupakan
sebuah
metode
dengan
menganalogikan sebagai model dari otak manusia. Neural Network biasa digunakan
untuk
bidang
Classification
yang
mencakup:
pattern
recognition, feature extraction, image matching. Lalu bidang Noise reduction dimana NN dapat mengenal pola-pola dalam input dan
15 memproduksi output yang noiseless. NN juga digunakan dalam bidang prediksi, sperti melakukan Extripolation berbasikan data histori (Cheung & Cannons, 2002).
2.11.1
Neural NetworksStructure Dalam tulisan yang dijabarkan oleh(Bourg & Seemann, 2004)
mengenai three-layer feed-forward networks. Struktur Neural Network dapat digambarkan sebagai berikut:
Gambar 2.3 Three-layer feed-forward neural network(Bourg & Seemann, 2004). Sebuah three-layer network terdiri dari satu input layer, satu hidden layer, dan satu output layer. Tidak ada batasan pada jumlah neuron yang ada pada tiap layer. Setiap neuron yang berasal dari input layer dihubungkan ke setiap neuron yang ada pada hidden layer. Selanjutnya, setiap neuron pada hidden layer dihubungkan ke setiap neuron pada output layer. Dan juga, setiap neuron, dengan tanpa pengecualian dari input layer, mempunyai sebuah tambahan input yang disebut bias.Angka yang tertera
16 pada Gambar 2.3 diberikan untuk mengidentifikasikan tiap node pada tiga layer tersebut. Angka-angka ini nantinya dipergunakan saat menulis formula untuk melakukan perhitungan nilai di tiap neuronnya. Memberikan perhitungan pada nilai output untuk sebuah jaringan bermula dengan adanya ketersediaan beberapa input pada tiap neuron input. Lalu input ini nantinya akan diberikan bobot dan dilanjutkan ke neuron hidden-layer. Proses ini akan berulang, berjalan dari hidden layer ke output layer, dimana output dari neuron hidden-layer tersedia sebagai input ke output layer. Proses ini berjalan dari input ke hidden lalu ke outputlayer. Hal ini disebut feed-forward process.
2.11.2
Input Input terhadap Neural Network merupakan hal yang sangat
penting. Tanpa adanya input, tidak akan ada yang diproses oleh neural network. Oleh karena itu, jumlah dan bentuk seperti apa yang perlu diperhatikan sebagai kandidat input layer(Bourg & Seemann, 2004). Kebutuhan karakteristik mengenai input layer tergantung oleh permasalahan yang dihadapi. Permasalahan yang ada harus disusun dan diperhatikan untuk dapat menyelesaikan tiap parameter yang ada dalam game, data, dan karakterisitik lingkungan yang merupakan hal penting pada game itu sendiri. Beberapa input dapat diperkirakan sebagai indikasi dari kepemilikan pemain, senjata, dan beberapa aksi lainnya.
17 Tugas dari neural network ini sendiri akan menjadi lebih mudah jika jumlah input neuron yang diberikan dijaga sesedikit mungkin.
2.11.3
Weights Weights dalam istilah neuralnetwork memberikan besarnya
pengaruh dari input yang diberikan dan mendefinisikan sifat dari suatu jaringan syaraf (Bourg & Seemann, 2004). Setiap koneksi dari satu neuron ke neuron lainnya mempunyai weight. Hasil perhitungannya diperoleh melalui rumus berikut:
Dengan n disini merupakan representasi nilai dari suatu neuron. Sedangkan w merupakan variabel weight dan b merupakan variabel bias. Untuk i dan j merupakan tanda pada layer mana suatu neuron berada.
2.11.4
Activation Functions Activation functions berperan untuk mengambil nilai dari net input
menuju suatu neuron dan mengoperasikannya untuk menghasilkan sebuah output untuk neuron(Bourg & Seemann, 2004). Activation functions seharusnya bersifat nonlinear. Jika tidak, jaringan syaraf akan dikurangi menjadi sebuah kombinasi linear dari suatu fungsi linear. Activation function yang umum digunakan ialah logistic function atau sigmoid function (Bourg & Seemann, 2004).
18
Gambar 2.4 Logistic Activation Function
Formula dari logistic function dapat ditulis sebagai berikut:
1 1
Atau fungsi dapat dituliskan sebagai berikut:
1
1
/
Istilah c digunakan untuk merubah bentuk dari fungsi dimana berkemungkinan untuk meregangkan atau memampatkan fungsi sepanjang sumbu horizontal. Input berada sepanjang sumbu horizontal dan output dari fungsi berjarak 0 sampai 1 untuk tiap nilai pada x. Dalam rentang pengujianya seperti dari 0.1 sampai 0.9, dimana nilai berkisar 0.1 menyatakan neuron tidak aktif dan nilai berkisar di 0.9 menyatakan neuron aktif. Hal ini sangat penting bahwa tidak masalah seberapa besar nilai x, logistic
19 function tidak akan pernah mencapai nilai 1.0 atau 0.0; mereka hanya mendekati nilai tersebut. Activation function lainnya adalah step function dan hyperbolic tangen function.
Gambar 2.5 Step Activation Function(Bourg & Seemann, 2004)
Gambar 2.6 Hyperbolic Activation Tangent Function(Bourg & Seemann, 2004)
20
Formula untuk step function adalah sebagai berikut:
0; 1;
0 0
Step function digunakan pada awal pengembangan neural network, akan tetapi mempunyai kekurangan kejadian training yang cukup berat. Sebagai contoh logistic function mempunyai kejadian yang mudah untuk dievaluasi, yang nantinya akan diperlukan untuk pembelajaran jaringan. Formula untuk hyperbolic tangent function adalah sebagai berikut: Hyperbolic
tangentfunction
terkadang
digunakan
untuk
mempercepat waktu pembelajaran(Bourg & Seemann, 2004). Activation function lainnya digunakan dalam jaringan syaraf untuk beragam aplikasi. Secara umum, logistic function terlihat sebagai bentuk fungsi yang paling banyak dipergunakan dan dapat dipakai oleh sebagian besar jenis aplikasi. Activation function lainnya yang terkadang digunakan ialah linear activation function.
21
Gambar 2.7 Linear Activation Function
2.11.5
Bias Istilah bias telah disebutkan sebelumnya bahwa tiap neuron
mempunyai sebuah bias yang terhubung olehnya. Hal ini diartikan sebagai nilai bias dan bias weight untuk tiap neuron dan tampil pada formula net input yang telah ditampilkan sebelumnya(Bourg & Seemann, 2004).
bjmerupakan nilai bias dan wjmerupakan bias weight. Secara dasar, istilah bias menggeser net input sepanjang sumbu horizontal dari activation function, yang secara efektif merubah threshold pada saat neuron aktif. Nilai bias selalu diberikan 1 atau -1 dan weight nya diatur melalui training, sama seperti weight lainnya. Hal ini sangat penting
22 bahwa jaringan syaraf belajar threshold yang tepat untuk tiap aktivasi neuron.
2.11.6
Output Sama halnya dengan input, pilihan berupa neuron output untuk
jaringan yang diberikan tergantung dari permasalahan yang ada. Secara mendasar, hal ini akan sangat baik jika menjaga jumlah neuron output sesedikit
mungkin
untuk
mengurangi
perhitungan
dan
waktu
pembelajaran(Bourg & Seemann, 2004). Hal yang menjadi pertimbangan pada jaringan, dengan input yang diberikan, peneliti menentukan output yang dapat mengklasifikasikan input. Ada saat dimana diperlukan penentuan saat sekumpulan input digolongkan pada class tertentu. Pada kasus ini, diperlukanlah adanya peran output neuron. Jika diaktifkan, maka hasilnya bernilai true, dimana jika tidak diaktifkan, hasilnya akan bernilai false atau input tidak digolongkan pada class atas pertimbangan tertentu. Jika logistic function digunakan sebagai output activation, sebuah output berkisar di 0.9 akan mengindikasikan aktif, atau true, dimana sebuah output berkisar di 0.1 akan mengindikasikan tidak aktif, atau false. Dalam prakteknya, peneliti berkemungkinan besar tidak mendapatkan nilai berkisar 0.9 yang dapat diindikasikan sebagai aktif, atau true, yang dimana output berkisar di 0.1 akan mengindikasikan tidak aktif, atau false. Sebagai contoh, peneliti harus menentukan batasan yang dapat memungkinkan akses informasi dari input yang diberikan untuk mengindikasikan bahwa output tersebut aktif.
23 Secara umum, peneliti dengan sederhana memilih batasan tengah dari output antara dua kubu yang berbeda. Untuk logistic function, angka 0.5 dapat dipergunakan untuk menentukan batasan tersebut. Jika output lebih besar dari 0.5, maka hasil akan diaktifkan atau bernilai true, lain dari itu akan bernilai false.
2.11.7
Hidden Layer Umunya dalam three-layer feed-forward network, tersedia satu
hidden layer dari tumpukan neuron yang berada di antara input dan output layer (Bourg & Seemann, 2004). Sebagaimana diilustrasikan pada strukur jaringan syaraf, setiap input dikoneksikan pada tiap hidden neuron. Selanjutnya, setiap hidden neuron akan mengirimkannya pengeluarannya ke tiap output neuron. Hidden Layer bersifat sangat penting sekali dalam memberikan fasilitas jaringan terhadap fitur proses dalam input data. Semakin banyak neuron pada hidden layer, semakin banyak fitur pada jaringan yang dapat dikendalikan. Sebaliknya, semakin sedikit neuron pada hidden layer, akan semakin sedikit juga fitur pada jaringan yang dapat dikendalikan.
2.11.8
Training Tujuan dari pembelajaran atau training ini adalah untuk mencari
nilai untuk weights yang menghubungkan kesemua neuron seperti input data menghasilkan nilai output yang diinginkan. Seperti yang mungkin diperkirakan, ada maksud lebih dari training, bukan hanya untuk
24 mendapatkan beberapa nilai weight. Secara garis besar, pembelajaran neural network merupakan proses optimisasi dimana peneliti berusaha mencari nilai optimal dari weight yang akan memungkinkan jaringan untuk menghasilkan output yang benar. Pembelajaran dapat diberikan dalam dua kategori: supervised training dan unsupervised training.
2.12
Fuzzy Logic Fuzzy logic merupakan sistem logis yang dapat bekerja dengan
data yang tidak mempunyai nilai yang didefinisi secara tepat. Sistem fuzzy secara khas memperkerjakan peraturan untuk mengartikan istilah yang samar, seperti kemampuan atau kenyamanan, ke dalam output dari suatu sistem (Yen & Langari, 1998).
2.13
Reinforcement Learning Reinforcement learning merupakan pembelajaran atas apa yang
dilakukan, bagaimana menempatkan situasi menjadi aksi,
untuk
mendapatkan memaksimalkan sinyal upah dalam bentuk angka(Sutton & Barto, 1998). Pembelajar tidak diberitahu apa tindakan yang akan dilakukan seperti hal umumnya yang ada pada machine learning, tetapi dengan cara menemukan tindakan dan upah dengan cara mencobanya. Dalam beberapa kasus yang menarik dan menantang, tindakan akan memberikan pengaruh tidak hanya pada upah saat itu, tetapi juga untuk situasi selanjutnya. Dua karakteristik penting yaitu “trial-and-error search”
25 dan “delayed reward” merupakan dua fitur hal paling penting dalam reinforcement learning. Menurut(Sutton & Barto, 1998), Reinforcement learning tidak didefinisikan oleh algoritma penggolongan pembelajaran, tetapi dengan menggolongkan masalah pembelajaran yang ada. Segala algoritma yang cocok penempatannya untuk memberikan solusi pada suatu masalah, dapat dipertimbangkan menjadi algoritma reinforcement learning. Adapun inti dalam reinforcement learning ini secara singkat adalah dengan mudah menangkap aspek paling penting dari permasalahan nyata dengan menghadirkan learning agent berinteraksi dengan lingkungannya dan mencapai sebuah tujuan. Secara jlas, agent tersebut harus mampu untuk mengartikan kondisi dari lingkungan menjadi luas dan harus dapat mengambil tindakan yang memberikan pengaruh pada kondisi tersebut. Agent juga harus memiliki sebuah atau beberapa tujuan yang berhubungan dengan kondisi dari lingkungannya. Reinforcement learning berbeda dari supervised learning, salah satu jenis studi pembelajaran dalam riset machine learning yang ada saat ini, dimana mempunyai pengenalan pola fisik, dan artificial neural network. Supervised learning merupakan pembelajaran dari contoh yang disediakan oleh pembimbing luar yang memiliki pengetahuan terhadap suatu masalah. Jenis pembelajaran ini merupakan suatu hal yang penting, tetapi jika sendiri, tanpa adanya pembimbing, akan mejadi pembelajaran yang tidak memadai(Sutton & Barto, 1998).
26 Satu dari tantangan yang menonjol dalam reinforcement learning dan tidak terdapat dalam pembelajaran jenis lainnya yaitu adanya pertukaran antara eksplorasi dan eksploitasi. Untuk mendapatkan banyak upah, sebuah agent dalam reinforcement learning harus memilih tindakan yang telah dilakukan sebelumnya di masa lampau dan menemukan cara yang lebih efektif dalam menghasilkan upah. Akan tetapi untuk menemukan suatu tindakan, agent harus melakukan tindakan yang belum pernah dipilih sebelumnya. Agent harus mengeksploitasi hal yang telah diketahui sebelumnya bertujuan untuk mendapatkan upah, akan tetapi agent juga harus mengeksplorasi bertujuan untuk membuat pilihan tindakan yang lebih bak selanjutnya. Agent harus dapat mencoba variasi dari tindakan dan mengerti mana yang menunjukkan upah terbaik. Pada hal yang sama, tiap tindakan diharuskan untuk dicoba beberapa kali untuk dapat mendapatkan estimasi upah yang dapat dipercaya(Sutton & Barto, 1998). Hal lain yang menjadi sisi menarik reinforcement learning yaitu ada dalam mempertimbangkan masalah yang dihadapi agent untuk melakukan tujuan namun berinteraksi dengan lingkungan yang tidak pasti. Hal ini jelas berbeda dengan banyak pendekatan lainnya yang mengalokasikan permasalahan tanpa mengalokasikan bagaimana mereka bisa masuk ke dalam gambaran yang lebih besar. Reinforcement learnig mengambil arah jalan yang berlainan, dengan memulai dengan sebuah agent pencari tujuan yang lengkap, interaktif. Semua agent reinforcement learning mempunyai tujuan jelas, dapat merasakan aspek dari lingkungan
27 mereka, dan dapat memilih tindakan mana untuk memberikan pengaruh pada lingkungannya. Dan juga, dapat diasumsikan bahwa saat awal, agent harus bertindak meskipun adanya ketidaktentuan mengenai lingkungan yang mereka tempati. Ketika reinforcement learning mengikutsertakan perencanaan, hal ini menunjukan bahwa diperlukan pengalokasian bagaimana bentuk lingkungan diperoleh dan ditingkatkan. Ketika reinforcement learning melibatkan supervised learning, hal ini juga menunjukkan bahwa reinforcement learning melakukan hal yang sama dengan alasan yang spesifik dengan cara menentukan kemampuan yang kritis dan bukan(Sutton & Barto, 1998). Hal yang membuat reinforcement learning menjadi penelitian tren ialah ia merupakan bagian dari hal yang lebih besar antara artificial intelligence dan disiplin ilmu teknik lainnya(Sutton & Barto, 1998). Artificial intelligence dulunya dilihat dan hampir sepenuhnya dipisahkan dari teori kontrol dan statistic. Semua harus dihubungkan dengan logika dan symbol, bukan angka. Artificial intelligence dulunya merupakan program LISP besar, bukan aljabar linier, persamaan diferensial, atau statistic. Namun dalam beberapa waktu ke depannya, pandangan ini dihilangkan. Peneliti modern artificial intelligence menyetujui statistic dan algoritma teori kontrol, sebagai contoh, metode relevan yang bersaing atau secara mudah dapat dikatakan sebagai alat perdagangan mereka. Bidang yang dulunya sempat diabaikan diantara artificial intelligence dan teknik sekarang
menjadi diantara topic yang aktif dari semuanya, termasuk
bidang-bidang baru seperti neural networks, intelligent control, dan
28 reinforcement learning. Keberadaan reinforcement learning menjadi ide yang meluas dari teori kontrol optimal dan penaksiran yang berhubungan untuk mengalokasikan lebih luas dan lebih berambisi mendukung tujuan artificial intelligence. Menurut(Sutton
&
Barto,
1998),Reinforcement
learning
merupakan sebuah metode pembelajaran mesin unsupervised dalam bidang Artificial Intelligence dan menawarkan performa tinggi dalam mensimulasikan kemampuan berpikir seperti manusia(Yung-Ping Fang, IHsien Ting, 2010).Reinforcement learning merupakan cabang yang berdiri sendiri dari artificial intelligence yang membedakannya dari variasi artificial intelligence lainnya dalam fokusnya pada pembelajaran dalam percobaan dan kesalahan, dan merupakan area aktif riset yang mengagumkan (Carr, 2005).
2.13.1
The Agent-Environtment Interface Reinforcement learning memerlukan adanya peran sebagai
pembelajar dan pelaku untuk mencapai tujuan(Sutton & Barto, 1998). Pembelajar dan penentu tindakan tersebut disebut agent. Hal yang menjadi sarana tempat interaksi agent disebut environtment. Hal ini saling berinteraksi secara terus menerus, agent memilih tindakan dan environtment memberikan dampak terhadap tindakan dan memberikan situasi baru ke agent.
29
Gambar 2.8 Framework Reinforcement Learning
(Kok, 2008)menggunakan konsep ini untuk diaplikasikan dalam penelitiannya. Agent bertindak dalam sebuah environtment. Tindakan di eksekusi dalam environtment, dimana nantinya akan ditempatkan sesuai dengan
peraturan
agent-environtment.
Implementasi
reinforcement
learning dalam penelitiannya dilakukan dalam 2apl agent programming language, atau disebut 2aplLearn. Dengan cara ini setiap agent yang direncanakan
menggunakan
2apl
mendapatkan
keuntungan
dari
framework ini. Programmer agent tidak perlu untuk mengimplementasikan algoritma tiap waktu tetapi dapat menggunakan framework umum, dengan semua keuntungan yang ada dalam menggunakan agent programming language.
2.13.2
Goal dan Reward Dalam reinforcement learning, maksud atau tujuan dari agent
disusun dalam istilah special signal, disebut reward atau upah, yang diberikan dari environtment ke agent(Sutton & Barto, 1998). Reward yang dimaksud hanya angka yang nilainya bervariasi dari langkah ke langkah.
30 Dengan kata lain, tujuan agent adalah untuk memaksimalkan jumlah total dari reward yang didapatkan. Hal ini berarti memaksimalkan tidak hanya reward dalam jangka dekat, tetapi reward kumulatif dalam jangka panjang.
2.11.3Returns Tujuan dari agent adalah untuk memaksimalkan reward yang diterima dalam jangka panjang(Sutton & Barto, 1998). Bagaimana caranya untuk didefinisikan? Jika urutan rewards yang didapatkan setelah waktu t ditunjukkan dengan
,
,
, …. Secara umum, diperlukan adanya
maksimalisasi dari expected return, dimana return,
, didefinisikan
sebagai fungsi khusus dari urutan reward. Dalam kasus paling sederhana, return hanya merupakan jumlah dari reward: =
+
+
+…+
,
Dimana T merupakan langkah waktu paling akhir. Pendekatan ini membuat pengertian dalam aplikasi dimana ada dugaan dasar dari langkah waktu akhir, yang ketika interaksi agent-environtment terbagi secara dasar menjadi subsequence, yang biasa disebut episode, seperti permainan dalam game, perjalanan dalam maze, atau hal-hal yang berhubungan dengan interaksi yang diulang-ulang. Tiap episode berakhir pada special state yang disebut terminal state, diikuti oleh reset ke kondisi permulaan dasar atau ke penyederhanaan dari distribusi standar dari kondisi awal. Task dengan episode sejenis ini disebut episodic tasks. Dalam episodic tasks terkadang diperlukan untuk membedakan set dari semua kondisi
31 nonterminal, ditandai sebagai S, dari set semua kondisi plus terminal state, ditandai sebagai
(Sutton & Barto, 1998).
Dalam banyak kasus, interaksi agent-environtment tidak terpisah secara dasar menjadi episode yang teridentifikasi, tetapi akan tetap melanjutkan secara terus menerus tanpa batas. Sebagai contoh, hal ini akan menjadi cara mendasar untuk merumuskan sebuah tugas proses-kontrol yang berkelanjutan, atau sebuah aplikasi untuk robot dengan rentang umur yang panjang, yang disebut continuing task. Perumusan return meragukan untuk continuing task karena tahap waktu akhir akan menjadi T = ∞, dan return, sesuatu yang diinginkan untuk dimaksimalkan, memungkinkan sendirinya dengan mudah menjadi tak terbatas. (Sebagai contoh, andaikan agent memperoleh reward +1 di tiap langkah.) Konsep tambahan yang diperlukan yaitu discounting(Sutton & Barto, 1998). Menurut pendekatan ini, agent berusaha untuk memilih tindakan sehingga jumlah dari discounted rewards yang diterima di waktu yang
akan
datang
maksimal.
Faktanya,
untuk
dipilihlah
memaksimalkan perkiraan dari discounted return.
=
+
+
+…=∑
+
1,
Dimana γ merupakan parameter, 0 ≤ γ ≤ 1, yang disebut discount rate. Discount rate menentukan nilai sekarang dari reward masa depan: sebuah reward memperoleh k satuan waktu di masa depan bernilai hanya kali yang akan bernilai jika diterima segera. Jika γ < 1, penjumlahan
32 tak terhingga mempunyai batas nilai selama urutan reward { } dibatasi. Jika γ = 0, agent menjadi “myopic” terkait hanya dalam memaksimalkan immediaterewards: tujuan dalam hal ini adalah untuk mempelajari bagaimana untuk memilih
sehingga untuk memaksimalkan hanya
.
Jika tiap tindakan agent memberikan pengaruh hanya pada immediate reward, bukannya pada future reward, maka myopic agent dapat memaksimalkan dengan cara terpisah memaksimalisasi tiap immediate reward. Tapi pada umumnya, tindakan untuk memaksimalisasi immediate reward dapat mengurangi akses untuk future rewards sehingga return pun akan berkurang juga. Dengan memberi pendekatan nilai 1 pada γ, tujuan mengambil future rewards ke dalam tanggungan menjadi lebih kuat: agent mempunyai pandangan jauh ke depan(Sutton & Barto, 1998).
2.13.3
Unified Notation: Episodic dan Continual Tasks Menurut (Sutton & Barto, 1998), Kasus episodic task secara
matematik lebih mudah dibandingkan continual task karena tiap tindakan hanya memberikan pengaruh pada angka reward yang terbatas satu per satu diperoleh dalam episode. Oleh karena itu perlu adanya pertimbangan atas kemungkinan terjadi satu jenis permasalahan berkaitan dengan episodic task dan kadang-kadang continual task, atau bahkan keduanya. Hal ini mendukung dibuatkannya satu notasi yang memperbolehkan pengguna untuk berbicara secara tepat tentang kasus keduanya secara serempak.
33 Untuk lebih tepat mengenai episodic task diperlukan beberapa notasi tambahan. Daripada satu urutan panjang langkah waktu, diperlukan pertimbangan rangkaian dari episode, yang mana tiap rangkaian tersebut terdiri dari urutan langkah waktu yang terbatas. Langkah waktu diurutkan tiap episode bermulai dari nol. Oleh karena itu, proses ini tidak hanya mengacu pada
, state representasi pada waktu t, tetapi ke
,
,
representasi state pada waktu t dari episode I (dan dengan cara yang sama untuk
,
,
,
,
,
,
, dan lainnya)(Sutton & Barto, 1998). Namun,
kenyataan yang ada bahwa dalam pembahasanepisodic task, hampir tidak pernah harus membedakan antara episode yang berbeda. Hal ini selalu membuat pertimbangan pada fakta di single episode, atau menyatakan sesuatu yang benar pada tiap episode. Oleh karena itu, dalam penggunaanya hampir selalu disalah gunakan notasi sedikitnya dengan cara meletakkan referensi eksplisit pada nomor episode. Yaitu dengan sederhana dapat ditulis sebagai berikut:
untuk mengacu pada
,
, dan
lainnya. Pada bagian ini memerlukan satu konvensi lainnya untuk mendapatkan single notation yang mencakup kedua task yang ada, episodic dan continuing. Pemberian definisi untuk return sebagai jumlah dari sekumpulan batasan angka dalam satu kasus dan sebagai jumlah dari sekumpulan tak terhingga dari angka. Hal ini dapat dipersatukan dengan mempertimbangkan perhentian episode untuk masuk ke dalam special absorbing state yang hanya mengalihkannya sendiri dan hanya
34 menghasilkan reward nol. Berikut penggambaran contoh dari diagram transisi:
Gambar 2.9Diagram transisi(Sutton & Barto, 1998)
Tanda
berbentuk
persegi
menggambarkan
sebagai
special
absorbing state yang sesuai dengan akhirnya dari episode. State dimulai dari
, urutan reward yang didapat +1, +1, +1, 0, 0, 0, … Dengan
menjumlahkannya, return yang sama akan didapatkan walaupun penjumlahan dilakukan pada reward T pertama (disini T = 3) atau melingkupi urutan penuh yang tak terhingga. Hal ini menyatakan kebenaran walaupun dimasukkannya discounting. Dengan demikian, return dapat didefinisikan, secara umum, menurut perumusan yang ada pada returns sebelumnya, menggunakan persetujuan untuk menghilangkan sejumlah episode ketika mereka tidak diperlukan, dan mencakup kemungkinan bahwa γ = 1 jika penjumlahan tetap didefinisikan(karena semua episode berakhir). Secara alternative, perumusan return dapat dituliskan sebagai berikut:
=∑
1,
35 Mencakup kemungkinan bahwa T = ∞ atau γ = 1(tapi tidak keduanya). Penggunaan persetujuan ini digunakan dalam penelitian pada umumnya untuk menyederhanakan notasi dan untuk mengekspresikan paralel yang erat antara tugas episodic dan continuing(Sutton & Barto, 1998).
2.13.4
Markov Property Dalam framework reinforcement learning, agent membuat
keputusan sebagai fungsi sinyal dari environtment yang disebut environtment’s state(Sutton & Barto, 1998). Istilah mengenai apa yang dibutuhkan state signal, dan jenis informasi yang seharusnya dan tidak seharusnya diharapkan untuk diberikan, dengan sederhana, property dari environtments dan state signal mereka yang menjadi minat khusus, disebut Markov property. State yang dimaksudkan disini merupakan segala informasi yang tersedia untuk agent. Hal ini diasumsikan bahwa state yang diberikan oleh beberapa sistem preprocessing yang secara nominal bagian dari environtment. Pendekatan ini diambil bukan karena pertimbangan bahwa representasi state tidak menjadi hal yang penting, tetapi bertujuan untuk fokus secara penuh pada persoalan pembuatan keputusan. Dengan kata lain, fokus utama dalam hal ini bukan dalam perancangan state signal, tetapi memutuskan tindakan apa yang akan diambil sebagai fungsi atas state signal apapun yang tersedia. State signal harus memasukkan immediate sensations seperti sensory measurements(Sutton & Barto, 1998). Representasi dari statedapat
36 menjadi versi yang secara penuh diproses dari original sensations, atau dapat menjadi struktur kompleks yang dibangun dari waktu ke waktu dari urutan sensations. Sebagai contoh, kita dapat mengerakan mata kita melihat suatu pemandangan, dengan hanya satu titik kecil yang sesuai dengan fovea terlihat secara rinci pada satu waktu, namun membangun representasi kaya dan rinci dari sebuah pemandangan. Secara lebih mendalam, kita dapat melihat sebuah objek, lalu melihat kea rah lain, dan mengetahui bahwa objek tersebut masih tetap berada disana. Kita dapat mendengar kata “yes” dan menganggap diri kita menjadi secara keseluruhan berbeda tergantung dari pertanyaan yang datang sebelumnya dan yang tidak lagi terdengar. Sistem kontrol dapat mengukur posisi pada dua waktu yang berbeda dan menghasilkan representasi state termasuk informasi mengenai kecepatan. Dalam semua kasus ini, state dibangun dan dipelihara pada dasar immediate sensations secara bersama dengan state sebelumnya atau beberapa memori lainnya dari past sensations. Dengan kata lain, state signal seharusnya tidak diperkirakan untuk menginformasikan agent segala sesuatu tentang environtment, atau bahkan segala
hal
yang
akan
berguna
untuknya
dalam
mengambil
keputusan(Sutton & Barto, 1998). Jika agent bermain blackjack, kita seharusnya tidak mengharapkan agent untuk mengetahui segera urutan kartu selanjutnya yang ada di tumpukan. Jika agent sedang menjawab telepon, kita seharusnya tidak mengharapkan untuk mengetahui dengan ahli siapa peneleponnya. Jika agent merupakan paramedic yang dipanggil menuju kecelakaan di jalan, kita seharusnya tidak mengharapkan agent
37 untuk mengetahui segera luka adlam yang terdapat pada korban yang pingsan. Dalam semua kasus ini, ada informasi state yang tersembunyi dari environtment, dan informasi tersebut akan berguna jika agent mengetahuinya, tetapi agent tidak dapat mengetahuinya karena ia tidak pernah memperoleh sensation yang berhubungan. Kita tidak menyalahkan agent karena ketidaktahuannya akan sesuatu yang terjadi, tetapi hanya untuk mengetahui sesuatu kemudian melupakannya. Hal yang sebenarnya diinginkan, secara ideal, merupakan state signal yang dapat merangkumkan past sensations dengan lengkap, namun sedemikian rupa sehingga semua informasi yang relevan dipertahankan. Hal ini secara normal membutuhkan lebih dari immediate sensations, tetapi tidak pernah lebih dari sejarah lengkap dari semua sensations di masa lalu. State signal yang berhasil dalam menahan semua informasi yang berhubungan dikatakan sebagai Markov, atau memiliki Markov property(Sutton & Barto, 1998). Markov propery didefinisikan dalam bentuk matematika yang sederhana, yaitu dengan mengasumsikan adanya batasan jumlah dari states dan nilai reward(Sutton & Barto, 1998). hal ini memperbolehkan pekerjaan dalam bentuk penjumlahan dan kemungkinan dibandingkan adanya integral dan kepadatan probabilitas, tetapi pendapat dapat dengan mudah diperluas untuk memasukkan continuous states dan reward. Mempertimbangkan bagaimana environtment umum memberikan respon pada waktu t + 1 terhadap tindakan yang diambil pada waktu t. Umumnya, kasus seperti ini mungkin tergantung pada segala sesuatu yang telah terjadi
38 sebelumnya. Dalam hal ini dinamika dapat didefinisikan hanya dengan menentukan distribusi probabilitas lengkap:
Pr {st+1 = s’, rt+1 = r | st, at, rt, st-1, at-1, …, r1, s0, a0},
Untuk semua s’, r, dan semua nilai kemungkinan di kejadian lampau: st, at, rt,…, r1, s0, a0. Jika state signal mempunyai Markov property, dengan kata lain, maka respon environtment pada t + 1 bergantung hanya pada state dan tindakan repsentasi pada t, yang dimana dalam hal dinamika lingkungan yang dapat didefinisikan dengan hanya penetapan
Pr {st+1 = s’, rt+1 = r | st, at }, Untuk semua = s’, r, st, dan at. Dengan kata lain, sebuah state signal mempunyai Markov property, dan merupakan sebuah Markov state, jika dan hanya jika perumusan tersebut sama dengan perumusan sebelumnya untuk semua s’, r, dan sejarah, st, at, rt, …, r1, s0, a0. Dalam kasus ini, environtment dan task secara keseluruhan juga dikatakan mempunyai Markov property. Jika sebuah environtment mempunyai Markov property, maka hal tersebut menjadi satu langkah dinamis perumusan tersebut memungkinkan untuk melakukan prediksi state selanjutnya dan memperkirakan reward selanjutnya yang diberikan pada state dan tindakan saat ini. Dengan
39 melakukan iterasi pada persamaan ini, seseorang dapat memprediksi semua future state dan expected reward dari pengetahuan hanya dari current state dan juga memberikan kemungkinan sejarah lengkap pada waktu saat ini. Hal ini juga memberitahukan bahwa Markov states menyediakan dasar kemungkinan yang terbaik untuk memilih tindakan. Yang dimana, aturan terbaik untuk memilih tindakan sebagai fungsi dari Markov state merupakan sama baiknya dengan aturan terbaik untuk memilih tindakan sebagai fungsi dari sejarah yang lengkap. Walaupun ketika state signal bukan merupakan non-Markov. Masih tetap merupakan suatu hal yang tepat untuk berpikir pada state dalam reinforcement learning sebagai sebuah taksiran pada Markov state(Sutton & Barto, 1998). Kenyataan yang ada mengatakan bahwa semua orang menginginkan state untuk menjadi dasar baik untuk memprediksi future reward dan untuk memilih tindakan. Markovstates menyediakan dasar yang tak dapat dibandingi untuk mengerjakan hal seperti ini. Untuk lebih luasnya, state mendekati kemampuan Markov states dalam hal ini, satu akan memperoleh kinerja lebih baik dari sistem reinforcement learning. Untuk alasan dari semua ini, hal ini akan menjadi sangat berguna untuk berpikir state pada setiap langkah waktu sebagai penaksiran pada Markov state, walaupun ada hal yang seharusnya diingat bahwa hal tersebut mungkin tidak memuaskan Markov property. Markov property penting dalam reinforcement learning karena keputusan dan nilai diasumsikan menjadi hanya sebuah fungsi dari state saat ini(Sutton & Barto, 1998). Dalam tujuan menjadikannya efektif dan
40 informative, representasi stae harus bersifat informative. Tidak semua teori secara ketat mengaplikasikan kasus dimana Markov property tidak secara ketat diaplikasikan. Akan tetapi, teori yang dikembangkan untuk kasus Markov tetap membantu untuk memahami tingkah laku dari algoritma, dan algoritma dapat berhasil diaplikasikan pada banyak tugas dengan states yang tidak ketat pada Markov. Pemahaman penuh mengenai teori kasus Markov merupakan pondasi dasar untuk memperpanjangnya ke kasus non-Markov yang lebih kompleks dan realistis. Pada akhir kata, representasi dari Markov state tidak bersifat unik pada reinforcement learning tetapi juga berada pada istilah umum jika semua pendekatan lain tidak bersifat artificial intelligence.
2.13.5
Markov Decision Processes Tugas reinforcement learning yang memuaskan Markov property
disebut Markov decision process, atau MDP. Jika state dan ruang action terbatas, maka ini disebut finite Markov decision process (finite MDP)(Sutton & Barto, 1998). Finite MDP merupakan hal penting dalam teori reinforcement learning. Keterangan mengenai finite MDP didefinisikan oleh kumpulan state dan action dan dengan satu langkah dinamik dari environtment. Dengan diberikan state dan action, s dan a, kemungkinan pada tiap state tepat selanjutnya, s’, adalah
P
= Pr {st+1 = s’ | st= s, at= a}.
41 Kuantitas ini disebut transition probability. Dengan cara yang sama, diberikan state dan action saat ini, s dan a, bersamaan dengan state selnjutnya, s’, nilai yang diperkirakan dari reward selanjutnya adalah
R
= E {rt+1 | st = s, at = a, st+1= s’}.
Kuantitas ini,
P
dan
R
, dengan lengkap menetapkan aspek
paling penting dari dinamik finite MDP (hanya informasi tentang distribusi reward sekitar nilai yang diperkiraan hilang).
2.13.6
Value Functions Menurut (Sutton & Barto, 1998), Hampir semua algoritma
reinforcement learning berdasarkan penaksiran value functions dari states (atau dari state-action pairs) yang memperkirakan seberapa baik algoritma tersebut untuk agent pada state yang diberikan (atau seberapa baik untuk menjalankan action yang diberikan dalam state yang diberikan). Notasi seberap baik disini didefinisikan dalam istilah future reward yang dapat diperkirakan, atau, untuk lebih tepatnya, dalam hasil return diinginkan. Tentu saja rewardsagent dapat diperkirakan untuk mendapatkan di masa depan tergantung dari apa action yang akan diambil. Jadi, value functions didefinisikan dengan mematuhi peraturan-peraturan utama yang ada. Ingatlah bahwa kebijakan, π, merupakan pemetaan dari tiap state, s S, danaction, a A(s), ke kemungkinanπ(s, a) dari pengambilan actiona ketika state s. Secara informal, nilai dari sebuah states dibawah kebijakan
42 π, dinotasikan Vπ(s), merupakan ekspektasi return ketika memulai dalam s dan diikuti πsetelahnya. Untuk MDP, kita dapat mendefinisikannya Vπ(s) secara formal sebagai
Dimana Eπ{} merupakan notasi dari perkiraan value saat agent mengikuti policy π, dan t merupakan langkah waktu. Perlu diketahui bahwa value dalam terminal state, jika ada, selalu bernilai nol. Fungsi ini disebut Vπstate-value function untuk policyπ. Dengan cara yang sama, definisi value dari pengambilan action a dalam states dibawah policy π, dinotasikan Qπ(s,a), sebagai return yang diperkirakan bermulai dari s, mengambil action a, dan sesudah itu mengikuti policyπ:
Perumusan di atas disebut Qπ action-value function untuk policy π(Sutton & Barto, 1998). Value functionVπ dan Qπ dapat diestimasikan dari pengalaman. Sebagai contoh, jika agent mengikuti policy π dan mempertahankan ratarata, untuk setiap keadaan yang dihadapi, dari return sesungguhnya yang telah mengikuti state tersebut, maka rata-rata akan bertemu pada state’s value, Vπ(s), sebagai jumlah waktu dari state yang dihadapi mendekati tak
43 terhingga. Jika rata-rata disimpan terpisah untuk setiap tindakan yang diambil di sebuah state, maka rata-rata akan sama bertemu dengan action values, Qπ(s, a). Hal mengenai metode estimasi seperti ini disebut Monte Carlo method karena hal ini melibatkan merata-ratakan dari banyak contoh acak return yang sebenarnya. Jika tersedia banyak states, maka menjadi tidak praktis untuk menjaga rata-rata terpisah untuk tiap state secara individual. Agent harus menjaga Vπ dan Qπsebagai parameter fungsi dan mengatur parameter untuk lebih cocok dengan return yang diamati. Hal ini juga dapat
menghasilkan
prediksi
akurat, walaupun kebanyakan
bergantung pada dasar parameterized function approximator. Sebuah property dari value function digunakan seluruhnya dalam reinforcement learning dan dynamic programming adalah mereka yang memenuhi hubungan rekursif tertentu. Untuk policy apa saja π dan state saja s, kondisi konsisten di bawah ini memegang peranan antara value dari s dan value dari possible successor state:
44 dimana ini menjadi bersifat mutlak bahwa action, a, diambil dari set A(s), dan state selanjutnya, s’, diambil dari set S, atau dari S+ dalam kasus permasalahan episodic. Persamaan di atas merupakan Bellman equation untuk Vπ(Sutton & Barto, 1998). Perumusan tersebut berfungsi untuk mengekspresikan hubungan antara value dari suatu state dan value dari successor states. Pikirkan melihat ke depan dari satu state ke possible successor state, seperti yang disarankan oleh Gambar berikut
Gambar 2.10Backup diagram untuk (a)Vπ dan (b)Qπ(Sutton & Barto, 1998)
Tiap lingkaran yang terbuka merepresentasikan sebuah state dan lingkarang yang hitam merepresentasikan state-action-pair. Dimulai dari state s,root node pada atas, agent dapat mengambil beberaoa dari action yang ada(Gambar a). Dari tiap-tiap ini, environtment dapat memberikan respon terhadap satu dari beberapa state selanjutnya, s’, diikuti reward r. Dari persamaan Bellman di atasmerata-ratakan semua kemungkinan yang ada, memberikan bobot dengan kemungkinan kejadian yang ada. Hal ini menyatakan bahwa value dari start state harus sama dengan (diskon)
45 valuedari perkiraan state selanjutnya, plus diikuti dengan reward yang diekspektasikan.
2.13.7
Optimal Value Functions Menurut
(Sutton
&
Barto,
1998),
Menyelesaikan
tugas
reinforcement learning berarti mencari sebuah policy yang dapat memperoleh banyak reward dalam jangka waktu yang panjang. Untuk finite MDP, dapat didefinisikan secara tepat sebuah optimal policy dalam cara berikut. Value function mendefinisikan sebagian pemesanan dalam policy. Sebuah policyπ dedefinisikan untuk menjadi lebih baik atau sama dengan policy π’ jika return yang diperkirakan lebih besar atau sama dengan dari π’ untuk semua state. Dengan kata lain, π ≥ π’ jika dan hanya jika Vπ(s) ≥ Vπ’(s) untuk semua s S. Selalu ada setidaknya satu policy yang lebih baik atau sama dengan semua policy yang lainnya. Hal ini merupakan optimal policy. Walaupun mungkin ada lebih dari satu, notasi untuk semua optimal policies adalah π*. Mereka membagi state-value function yang sama, yang disebut optimal state-value function, dinotasikan V* dan di definisikan sebagai
Untuk semua s S.
Optimal policy juga membagi optimal action-value function yang sama, dinotasikan Q*, dan didefinisikan sebagai
46
Untuk semua s S dan a A(s). Untuk state-action pair (s,a), fungsi ini memberikan ekspektasi return untuk mengambil action a dalam state s dan selanjutnya mengikuti optimal policy. Dengan demikian, penulisan Q* dalam penulisan V* sebagai berikut:
2.13.8
Optimality danApproximation Menurut (Sutton & Barto, 1998), Agent yang mempelajari optimal
policy telah memberikan hasil sangat baik, tetapi dalam prakteknya hal ini jarang terjadi. Untuk jenis tugas yang menarik, optimal policy dapat dihasilkan hanya dengan permintaan perhitungan yang ekstrim. Jika seseorang mempunyai model yang lengkap dan akurat dari dinamik environtment, hal ini biasanya tidak mungkin untuk menyederhanakan untuk menghitung optimal policy dengan memecahkan Bellmanoptimality equation. Ketersediaan memori juga merupakan persyaratan utama. Jumlah memori yang besar sering dibutuhkan untuk membangun penaksiran dari value function, policies, dan model. Dalam tugas kecil, kumpulan finite state, merupakan hal yang mungkin untuk menggabungkan penaksiran ini menggunakan array atau tabel dengan satu masukkan untuk tiap state (state-action-pair). Hal ini disebut sebagai tabular case, dan metode yang berhubungan disebut tabular methods. Dalam banyak kasus prakteknya,
47 akan tetapi, ada state yang sangat banyak daripada yang diperkirakan untuk dimasukkan ke dalam tabel. Dalam kasus ini, fungsi harus diperkirakan, menggunakan urutan representasi parameter fungsi. Pandangan orang terhadap masalah reinforcement learning memaksa untuk menyelesaikan penaksiran. Akan tetapi, hal ini juga memberikan kesempatan unik untuk mendapatkan penaksiran yang berguna. Sebagai contoh, dalam penaksiran optimal behavior, ada banyak state yang agent hadapi dengan kemungkinan rendah yang memilih suboptimal actions untuk mereka dengan pengaruh kecil pada jumlah award yang didapatkan oleh agent. Tesauro’s backgammon player,sebagai contoh, bermaian dengan kemampuan pengecualian walaupun hal tersebut mungkin menjadi keputusan paling buruk dalam pengaturan yang tidak pernah terjadi dalam permainan melawan ahli. Kenyataannya, hal ini mungkin bahwa TD-Gammon membuat keputusan buruk untuk sebuah pecahan dari sekumpulan state dalam game. Dasar on-line dari reinforcement learning membuatnya menjadi mungkin untuk menaksirkan optimal policies dengan memberikan usaha lebih dalam pembelajaran untuk membuat keputusan baik dalam state yang sering dihadapi, pada pengorbanan sedikit usaha untuk states yang jarang dikunjungi. Hal ini merupakan kunci property yang membedakan reinforcement learning berbedari dari pendekatan lainnya untuk menaksirkan pemecahan MDP.
48
2.14
Temporal Difference Learning Metode
Temporal
Difference
Learning
digunakan
untuk
melakukan estimasi terhadap value functions(Sutton & Barto, 1998). Jika value functions dikalkulasikan tanpa adanya estimasi, agent akan memerlukan waktu untuk menunggu sampai reward akhir diterima sebelum state-action pair values dapat diperbaharui. Ketika reward akhir diterima, jalur yang diambil untuk mencapai final state perlu untuk ditelusuri kembali dan tiap value diperbaharui. Hal ini dapat digambarkan sebagai berikut(Sutton & Barto, 1998): Å
+α[
– V( )]
Dimana St merupakan state yang datang pada waktu t, Rt merupakan reward setelah waktu t dan α merupakan parameter konstan. Disamping itu, dengan Metode Temporal Difference, sebuah estimasi dari final reward dikalkulasikan di tiap state dan state-action value diperbaharui di tiap langkah.
Hal ini dapat digambarkan sebagai
berikut(Sutton & Barto, 1998): Å
+α[
+ γV(
) – V( )]
Dimana rt+1 merupakan reward yang telah di observasi pada waktu t+1. Metode Temporal Difference disebut metode “bootstrapping”, karena value diperbaharui sebagian menggunakan sebuah estimasi yang ada dan bukan merupakan sebuah final reward.
49
2.15
On-Policy dan Off-Policy Learning Metode On-Policy Temporal Difference mempelajari value dari
suatu policy yang digunakan untuk memperoleh keputusan(Sutton & Barto, 1998). Value functions diperbaharui menggunakan hasil dari suatu jalannya aksi yang ditentukan oleh suatu policy. Policy ini biasanya bersifat “soft” dan non-deterministic. Pengertian dari “soft” dalam hal ini merupakan penjaminan akan selalu adanya sebuah elemen dari eksplorasi kepada policy. Policy tidak bersifat selalu disiplin dimana ia selalu memilih aksi yang memberikan reward pada umumnya. Tiga policy umum yang digunakan, ε-soft, ε-greedy, dan softmax. Penjelasan mengenai masing-masing policy akan dijelaskan kemudian. Metode Off-Policy dapat mempelajari policy yang berbeda-beda untuk perilaku dan perkiraan. Sama dengan sebelumnya, perilaku dari policy ini biasanya “soft” sehingga adanya eksplorasi yang cukup terjadi. Algoritma Off-Policy dapat memperbaharui value functions yang telah diperkirakan sebelumnya dengan menggunakan aksi hipotesis(Sutton & Barto, 1998). Hal ini yang membedakan terhadap Metode On-Policy yang memperbaharui value functions berdasarkan pengalaman terus menerus. Maksudnya dalam hal ini adalah algoritma Off-Policy dapat memisahkan eksplorasidari kontrol, dan Algoritma On-Policy tidak. Dengan kata lain, sebuah agent yang ditraining menggunakan metode off-policy mungkin berakhir mempelajari taktik yang keberadaannya tidak diperlukan selama fase pembelajaran.
50
2.16
Action Selection Policies Ada tiga policy umum yang digunakan sebagai pemilihan aksi.
Tujuan dari kesemua policy ini adalah untuk menyeimbangkan pertukaran antara eksploitasi dan eksplorasi, dengan tidak selalu melakukan eksploitasi yang telah dipelajari secara jauh(Eden, Knittel, & Uffelen). •
ε-greedy – Biasanya aksi dengan estimasi reward tinggi dipilih, disebut aksi tamak (greediest action). Setiap saat, dimisalkan dengan probabilitas yang kecil, sebuah aksi dipilih secara random. Aksi yang dpilih bersifat merata, bebas dari estimasi action-values. Metode ini memastikan bahwa jika percobaan yang cukup telah diselesaikan, tiap aksi akan dilakukan percobaan sebanyak tak terhingga, demikian memastikan aksi optimal telah diketemukan.
•
ε-soft – sangat mirip dengan ε-greedy. Aksi terbaik dipilih menggunakan probabilitas 1 – ε dan sisanya aksi random akan dipilih secara merata.
•
Softmax – Satu kekurangan yang ada pada ε-greedy dan ε-soft adalah mereka memilih aksi random secara merata. Kemungkinan dari aksi terburuk sama seperti dipilihnya sebagai kedua yang terbaik. Softmax menutupi kekurangan ini dengan menugaskan sebuah rank atau weight untuk tiap aksi, menurut estimasi action-value mereka. Sebuah tindakan acak dipilih berkaitan dengan weight yang berhubungan dengan setiap tindakan, yang berarti tindakan terburuk tampaknya tidak akan dipilih. Hal ini merupakan pendekatan yang baik untuk
51 mengambil
dimana
tindakan
terburuk
adalah
sangat
tidak
menguntungkan. Tidak jelas mana dari kebijakan-kebijakan tersebut yang menghasilkan hasil terbaik secara keseluruhan. Sifat dari tugas akan memiliki beberapa bantalan pada seberapa baik setiap kebijakan berpengaruh dalam proses belajar. Jika masalah yang kita coba untuk pecahkan adalah sebuah permainan bermain alam, melawan lawan manusia, faktor manusia juga mungkin berpengaruh.
2.17
Q-Learning Q-Learning merupakan algoritma Off-Policy untuk Temporal
Difference learning. Dapat dibuktikan bahwa dengan diberikannya pelatihan yang memadai dibawah kebijakan ε-soft, Algoritma tersebut dengan probabilitas 1 menuju ke pendekatan dari action-value function untuk target kebijakan yang sewenang-wenang. Q-learning mempelajari kebijakan optimal walaupun ketika tindakan dipilih menurut kebijakan yang lebih tereksplorasi atau bahkan acak(Sutton & Barto, 1998). Bentuk prosedur algoritmanya adalah sebagai berikut:
Initialize Q(s, a) arbitrarily Repeat (for each episode) : Initialize s Repeat (for each step of episode): Choose a from s using policy derived from Q (e.g., ε-greedy) Take action a, observe r, s’ Q(s, a) Å Q(s, a) + α [r + γ maxα, Q(s’, a’) – Q(s, a)] s Å s’;
52 until s is terminal Parameter yang digunakan dalam proses pembaharuan Q-value adalah: -
α – learning rate, bernilai antara 0 dan 1. Dengan memberi nilai 0 berarti Q-values tidak akan pernah diperbaharui, maka tidak ada yang dipelajari. Dengan memberi nilai tinggi seperti 0.9 berarti pembelajaran dapat terjadi dengan cepat.
-
γ – discount factor, juga bernilai antara 0 dan 1. Ini merupakan model fakta bahwa future reward nantinya akan bernilai kurang dari reward langsung. Secara matematis, discount factor harus ditetapkan kurang dari 0 pada algoritma untuk disatukan.
-
maxα – maximum reward yang dapat dicapai dalam suatu state. Contohnya reward untuk mengambil tindakan yang optimal setelahnya.
Pendekatan prosedural tersebut dapat diartikan sebagai berikut: 1. Inisialisasi Q-values table, Q(s,a). 2. Lakukan observasi pada state saat ini, s. 3. Pilih tindakan(action), a, untuk state tersebut berdasarkan satu dari kebijakan seleksi tindakan (action selection policies) yaitu -soft, εgreedy, softmax. 4. Ambil tindakan(action), dan observasi reward, r, serta state baru, s’.
53 5. Lakukan perubahan Q-value untuk state yang menggunakan reward yang telah diobservasi dan kemungkinan reward terbesar untuk state selanjutnya. Perubahan diselesaikan menurut formula dan parameter yang dijelaskan diatas. 6. Atur state menjadi state baru, dan ulangi proses sampai akhiran state (terminal state) tercapai.
2.18
Sarsa Algoritma Sarsa merupakan algoritma On-policy dari Temporal
Difference Learning. Dasar yang menjadi perbedaan antara Sarsa dan QLearning, adalah maximum reward untuk state lanjut tidak perlu digunakan untuk memperbaharui Q-values. Sebaliknya, sebuah action baru, karena reward, dipilih dengan menggunakan kebijakan yang ditentukan oleh tindakan asli. Nama Sarsa sendiri berasal dari fakta bahw perubahan tersebut telah dilakukan dengan menggunakan quintuple Q(s, a, r, s’, a’). Dimana s, a merupakan state dan action asli, r merupakan reward yang telah diobservasi dalam state yang diikuti dan s’, a’ merupakan stateaction pair yang baru(Sutton & Barto, 1998). Bentuk prosedural dari algoritma Sarsa dibandingkan dengan Q-Learning: Initialize Q(s, a) arbitrarily Repeat (for each episode) : Initialize s Choose a from s using policy derived from Q (e.g., ε-greedy) Repeat (for each step of episode): Take action a, observe r, s’ Choose a’ from s using policy derived from Q
54 (e.g., ε-greedy) Take action a, observe r, s’ Q(s, a) Å Q(s, a) + α[r + γQ(s’, a’) – Q(s, a)] s Å s’; a Å a’; until s is terminal Ada dua langkah pilihan action yang diperlukan, untuk menentukan state-action pair berikutnya bersamaan dengan yang pertama. Parameter α dan γ memiliki arti yang sama seperti yang mereka lakukan di Q-Learning.
2.19
Kajian Penelitian Reinforcement Learning Penelitian mengenai Reinforcement Learning sudah dilakukan
sebelumnya dan berbagai metodologi telah diteliti dalam bidang ini. Kategori reinforcement learning pun digunakan di banyak sub-bidang, salah satu diantaranya adalah game. Masing-masing penelitian yang berkaitan dengan reinforcement learning pada game ini sendiri tentunya akan memberikan informasi yang berharga dalam mendukung perkembangan di bidang ini. Berikut pembahasan singkat mengenai penelitian-penelitian terkait dengan reinforcement learning yang terletak pada bidang game. 1.
(Fang & Ting, 2010)menuliskan sebuah penelitian berjudul “Applying Reinforcement Learning for the AIin a Tank-Battle Game”. Mereka menyebutkan bahwa reinforcement learning merupakan sebuah metode unsupervised machine learning dalam bidang artificial intelligence dan memberikan kinerja baik dalam mensimulasikan kemampuan berpikir dari seorang manusia. Akan tetapi, reinforcement learning memerlukan
55 proses trial-and-erroruntuk mencapai tujuannya. Dalam bidang penelitian artificial intelligence dalam game, akan menjadi suatu pendekatan yang menarik jika dapat memberikan non-playercharacters(NPC) atau agent dalam permainan yang mempunyai kualitas
mirip
permasalahan
seorang terbesar
manusia. dalam
Mereka
reinforcement
mengetahui
bahwa
learning
adalah
memerlukan banyak waktu bagi agent untuk mempelajari solusi terbaik. Untuk mengatasi masalah tersebut, mereka menggunakan konsep fuzzy logic untuk meningkatkan kemampuan dalam reinforcement learning. Mereka menulis plot(Gambar 2.6) dan metodologi(Gambar 2.7) yang mereka pergunakan untuk meneliti reinforcement learning dengan cara sebagai berikut:
56
Gambar 2.11Plot study(Fang & Ting, 2010)
1.
Tank game: sebagai inisialisasi awal untuk uji coba penelitian ini. Mereka menggunakan game engine untuk membuat sebuah tank game.
2.
Reinforcement
learning:
Mengaplikasikan
algoritma
reinforcement learning mereka pada NPC tank. 3.
Fuzzy Logic: konsep dari fuzzy logic dan fuzzy sets akan digunakan untuk meningkatkan kinerja dari reinforcement learning.
57 4.
Eksperimen dan Analisa: Berdasarkan hasil yang didapat, pengaturan nilai dari parameter akan dilakukan untuk mencari fungsi fuzzy terbaik.
Gambar 2.12Research methodology(Fang & Ting, 2010) Hasil pengujian yang mereka lakukan menunjukkan bahwa metode reinforcement
learning
tidak
menunjukkan
kinerja
lebih
baik
dibandingkan metode machine learning lainnya. Akan tetapi, hal ini juga mengindikasikan sebuah kemampuan baik dalam berperilaku seperti manusia nyata. Dengan kata lain, reinforcement learning tidak dimaksudkan untuk menghasilkan AI sempurna yang tidak membuat kesalahan sekalipun, tetapi mencoba untuk menjadi AI yang masuk akal yang dapat berperilaku seperti manusia.
2.
(Micić, Arnarsson, & Jónsson, 2011) menuliskan sebuah penelitian berjudul “Developing Game AI For the Real-Time Strategy Game Starcraft”. Mereka mengatakan bahwa penelitian terhadap intelligent agent yang dirancang untuk Real-Time Strategy (RTS) games terbatas
58 dibandingkan jumlah penelitian yang bertujuan untuk merancang agent untuk permainan board games seperti Catur. Hal ini disebabkan karena adanya fakta mengembangkan agent pada RTS lebih kompleks. Mereka memanfaatkan pengembangan yang ada dalam beberapa tahun yang lalu dengan dikenalkannya Brood War API, yang memungkinkan para peneliti untuk mengkaitkan AI mereka pada game RTS yang populer saat ini. StarCraft menyediakan platform yang menarik untuk penelitian AI RTS karena variasi unit yang banyak dan seimbang. Mereka melakukan rancangan terhadap AI agent untuk membuat keputusan yang diinformasikan
dalam
StarCraft.
Agent
tersebut
menggunakan
reinforcement learning untuk meningkatkan kinerjanya sewaktu-waktu. Dengan tujuan untuk menguji konsep implementasi reinforcement learning pada RTS game, mereka sepakat untuk membuat skenario sederhana dan mengujinya terlebih dahulu. Skenario #1: Dragoon vs. Zealot Dalam scenario ini, dragoon unit dikontrol oleh agent, sedangkan zealot unit dikontrol oleh AI yang ada dalam game tersebut. Dragoon dan zealot merupakan dua unit utama dalam ras Protoss pada game starcraft. Dragoon merupakan unit dasar jarak jauh, dan zealot merupakan unit dasar jarak dekat. Tiap health pada unit tersebut diukur dalam poin, yang dinamakan health points, dan hal yang akan dilakukan oleh kedua unit adalah untuk mengalahkan lawannya hingga health pointsnya menjadi nol dengan cara menyerangnya.
59 Oleh karena dragoon merupakan unit dengan daya serang jarak jauh dan zealot merupakan unit dengan daya serang dekat, tingkat efektifitas dari dragoon akan lebih baik dibandingkan zealot. Hal ini sangat menguntungkan jika dragoon menggunakan kemampuan jarak jauhnya untuk menyerang dan tetap bergerak selagi menyerang zealot. Jika dragoon tetap diam saat pertarungan berlangsung, maka zealot akan menang. Tapi jika dragoon tetap bergerak dan menjaga jarak dari zealot, ia mempunyai kesempatan untuk menang. Menyerang, akan tetapi, tidak instan dan sebuah unit harus tetap diam untuk beberapa saat saat proses menyerang dilakukan. Dalam kasus ini, serangan dragoon, tembakan dari cannon dibelakangnya, membutuhkan waktu yang lebih lama untuk bekerja daripada serangan zealot, mengayunkan pedang plasmannya. Dragoon memerlukan tindakan bahwa ia perlu untuk berhenti saat mendapatkan jarak yang cukup untuk melakukan tembakan dan tetap lari, sebelum zealot menangkap dan memukulnya. Setiap serangan juga mempunyai istilah yang disebut cooldown time, sedikit waktu yang diperlukan antara serangan menuju serangan berikutnya. Sebuah serangan dikatakan cooldown jika ia telah tersedia untuk digunakan. Hal ini menunjukkan scenario sangat sederhana awalnya yang hanya mengatakan agent apakah senjatanya sedang dalam cooldown atau tidak, dimana unit lawan ada dalam jarak serang dan dimana dia berada dalam jarak serang musuh. Setelah melihatnya bekerja dan hal tersebut adalah pembelajaran fakta, dapat dijabarkan seperti berikut:
60
Distance d diantara unit yang diukur dalam satuan pixel dipresentasikan dengan 5 nilai diskrit: o
d > 140
o
100 ≤ d ≤ 140
o
80 ≤ d 100
o
35 ≤ d ≤ 80
o
35 > d Health points h untuk tiap unit juga merupakan bagian dari representasi
state, dan hal tersebut dipresentasikan dengan enam nilai diskrit: o
h > 60
o
40 < h ≤ 60
o
30 < h < 40
o
20 < h < 30
o
10 < h < 20
o
h ≤ 10
Cooldown dari senjata dragoon dideskripsikan dengan dua nilai diskrit: o
On: dragoon tidak dapat menyerang.
o
Off: dragoon dapat menyerang.
Indikator dimana Zealot berada dalam jarak serang dragoon: o
On: zealot jauh dari jangkauan.
o
Off: zealot berada dalam jangkauan.
Indikator dimana dragoon berada dalam jarak serang zealot: o
On: dragoon jauh dari jangkauan.
61 o
Off: dragoon berada dalam jangkauan.
Dragoon juga mempunyai dua tindakan yang tersedia: o
Attack
o
Retreat
Agent diberikan reward berdasarkan perbedaan health point antara dia dan lawan pada setiap langkahnya. Jadi jika health dari agent telah berkurang sejak frame terakhir ia mendapatkan negative reward yang setara dengan banyaknya health yang hilang, demikian juga jika unit lawan mempunyai sedikit health, agent akan mendapatkan positive reward setara dengan jumlah health yang telah hilang, jika keduanya mendukung jumlah yang kerusakan yang setara, ia mendapatkan reward 0. Perlu diperhatikan bahwa tindakan ini merupakan peralihan pada agents FSM dan saat agent berada state tersebut ia mengikuti mekanisme yang telah direncanakan sebelumnya. Mekanisma penyerangan bersifat sederhana, hanya menembak pada zealot kapanpun memungkinkan. Tindakan mundur menggunakan posisi dragoon dan zealot untuk membentuk sebuah vector. Vector tersebut digunakan posisi dragoon untuk lari menghindari zealot. Kombinasi dari state dan tindakan menghasilkan total 12 state-action-pairs.
62 Dengan menambahkan jarak yang diperbolehkan bagi agent untuk mencari tahu bahwa ada saat ketika dia mungkin mendapatkan banyak tembakan sebelum ia memulai tindakan mundur lagi. Tindakan yang ada sama, attack atau retreat. Hal ini menambahkan total 2,880 state-actionpairs. Dalam MDP, metode rewards tetap sama seperti yang ada dalam scenario pertama. Hal ini merumuskan keseimbangan yang sulit antara mencoba untuk meminimalisasi jumlah state-action pair untuk belajar, dan menahan informasi yang berhubungan untuk tindakan yang diinformasikan sebelumnya.
3.
(Takadama & Fujita, 2004)dalam penelitian yang berjudul “Q-learning and Sarsa Agents in Bargaining Game” menceritakan mengenai fokus dalam sensitivity of learning mechanism yang diaplikasikan pada agents dalam simulasi berdasarkan agent dan melakukan eksplorasi kriteria untuk pemberian mekanisme pembelajaran dengan membandingkan hasil simulasi yang didapat dari agents yang mempunyai mekanisme pembelajaran berbeda. Mereka memberikan dua jenis perbedaan reinforcement learning dalam pembelajaran ini, Q-learning dan Sarsa.
Melalui analisa dari hasil simulasi dalam bargaining game sebagai satu dari contoh dalam teori game, maksud yang diinginkan telah berhasil
63 dinyatakan: (1)hasil antara agentsQ-learning dan Sarsa hampir sama dari satu sudut pandang, tetapi berbeda dari sudut pandang lain; (2) agent Sarsa memimpin agentQ-learning dalam perundingan, saat agent Sarsa tidak dapat memperoleh perilaku masuk akal, yang dapat diperoleh dari agent Q-learning ; dan (3) implikasi (1) dan (2) mendapat kriteria berikut yang menyediakan garis pedoman kasar untuk mekanisme pemanfaatan pembelajaran dalam simulasi berdasarkan agent. Ada dua simulasi yang diselenggarakan sebanyak 1,000,000 permainan, dimana angka maksimal dari proses negosiasi adalah 6, dan keduanya kedua proses dan negosasi tiap simulai diteliti. Variabel dalam pengaturan parameter diberikan sebagai berikut: -
α(learning rate): 0.1
-
γ (discount rate): 1.0
-
ε (digunakan untuk ε-greedy method): 0.1
•
Simulasi 1 (mekanisme pembelajaran sama): Investigasi dari hasil simulasi agent yang mengikuti mekanisme pembelajaran sama. (1) kedua agent sama-sama menjalankan Q-learning dan (2) Sarsa.
•
Simulasi 2 (mekanisme pembelajaran berbeda): Investigasi dari hasil simulasi agent yang mempunyai mekanisme pembelajaran berbeda: (1) tawaran pertama agent bekerja menggunakan Q-learning dan yang kedua menjalankan Sarsa dan (2) kasus berlawanan dari (1). Hasil dari simulasi memberikan dua implikasi penting: (1)hasil
antara agentQ-learning dan Sarsa hampir sama; Saat ukuran proses
64 negosiasi diantara mereka berbeda; (2) agent Sarsa lebih memimpin dari agentQ-Learning dalam negosiasi, selama agent Sarsa tidak dapat memperoleh perilaku masuk akl, yang dapat diperleh oleh agent QLearning. Dari hasil ini, berikut kriteria yang menyediakan garis pedoman kasar dalam memperkerjakan mekanisme pembelajaran dalam simulasi berdasarkan agent. •
Kriteria 1:Discount factor:Tidak seperti hasil akhir, proses negosasi antara agentQ-learning dan Sarsa, walaupun perbedaan diantara mereka sangat kecil (sebagai contoh perbedaan max yang digunakan dalam melakukan update Q-values, seperti yang ditunjukan pada persamaan (1) dan (2)). Hasil perbedaan datang dari rewards yang diperoleh dalam strategi yang digunakan terakhir (contoh Q‐ values) disebarkan pada strategi yang digunakan di awal tanpa atenuasi atau tidak, yang dapat dimengerti dengan mengubah bentuk persamaan (1) dan (2). Saat atenuasi ini bekerja seperti faktor diskon yang dilihat di banyak mekanisme pembelajaran, mekanisme pembelajaran seharusnya dipilih dari sudut pandang ini.
•
Kriteria 2: Penggabungan agent dengan pembelajaran berbeda: Implikasi bahwa agents Q-Learning dapat memperoleh perilaku rasional saat agentSarsa tidak dapat ditemukan dengan cara menginvestigasi keduanya proses hasil akhir dan negosiasi pada agentQ-learning dan Sarsa. Akan tetapi, implikasi ini tidak memberikan tanda bahwa agentQ-learning lebih memimpin daripada
65 agentSarsa dalam negosiasi. Hal sebaliknya benar, yang mengindikasikan bahwa kemampuan untuk memperoleh perilaku rasional berbeda dari perolehan strategi kuat dalam negosiasi. Hal ini memberitahu bahwa mekanisme pembelajaran seharusnya dipilih setelah melakukan investigasi hasil simulasi agent yang berbeda pembelajaran. Dari hasil tinjauan penelitian yang dijabarkan, peneliti meletakkan penelitian ini dalam kategori permainan strategy game sederhana. Konsep ini merupakan pondasi permainan strategi seperti game dengan genre Real-time Strategy, seperti Warcraft dan Starcraft. Seperti penelitian yang dilakukan oleh(Fang & Ting, 2010), mereka menggunakan media games untuk melakukan pembelajaran pada agent. Mereka menggunakan game engine untuk membuat environment dalam permainan tersebut, sedangkan peneliti menggunakan program java untuk membuat environment sederhana. Pembelajaran Q-Learning dan Sarsa digunakan dalam penelitian yang digunakan oleh (Takadama & Fujita, 2004)dalam bargaining game yang dimana dalam penelitian ini juga digunakan metode pembelajaran yang sama hanya saja media permainannya yang berbeda.
