Penulisan Kedua

Penulisan Kedua

Implementasi Adaptive Artificial Intelligence pada game Capture The Flag dengan metode Dynamic Scripting

(1Chandra Mahendra, 2Vera Suryani, ST. MT., 3Gandeva Bayu, ST.MT)

Primawan Satrio1, Agung Toto Wibowo, S.T.,  M.T. 2, Bayu Munajat, S.T., M.T.3

1primawan.satrio@gmail.com, 2agungtoto@telkomuniversity.ac.id, 3bayumunajat@telkomuniversity.ac.id

Dynamic Scripting

Dynamic   scripting (DS)   memenuhi   lima   dari   delapan kebutuhan komputasional dan fungsional, yaitu :

-       Speed  (computational):  DS cepat secara komputasional, karena DS hanya membutuhkan ekstraksi dari rulebase dan mengganti bobot setiap perulangan.

-     Effectiveness  (computational):  Efektivitas  dari  DS

teruji ketika semua aturan di rulebase masuk akal, berdasarkan domain knowledge yang sesuai. Setiap aksi dimana agent mengeksekusi melalui skrip yang mengandung  aturan-aturan  ini,  adalah  aksi  yang paling tidak efektif (walaupun itu mungkin tidak sesuai untuk beberapa situasi). Dengan catatan jika seorang pengembang game membuat kesalahan dan memasukkan sebuah aturan yang kurang cerdas di rulebase, teknik DS akan segera  meng-alokasi-kan aturan ini ke bobot nilai terendah. Oleh karena itu, kebutuhan dari efektivitas haruslah terpenuhi bahkan jika rulebase terdapat beberapa aturan yang kurang cerdas. Singkatnya, jika kebanyakan aturan di rulebase adalah kurang cerdas, algoritma DS tidak akan mampu untuk membangkitkan game AI yang cukup.

Robustness (computational):

algoritma      DS merupakan algoritma yang handal, karena bobot dari sebuah aturan di rulebase merepresentasikan sebuah kegunaan secara statis, diturunkan dari beberapa sampel Fitness yang diharapkan dari skrip yang terdapat   dari   aturan   tersebut. 

Sebuah hukuman(penalty) yang kurang tepat  tidak akan menghilangkan sebuah aturan dari rulebase, dan akan diberi keringanan ketika aturan tersebut dipilih kembali, atau bahkan ketika aturan lain terkena hukuman.   Sama   halnya   ketika   sebuah   hadiah (reward) mengakibatkan sebuah aturan kurang cerdas dipilih lebih sering, dimana hanya mengakibatkan itu akan mengumpulkan hukuman yang kurang cepat lebih cepat.

Clarity  (functional):  algoritma  DS  membangkitkan skrip, dimana skripnya bisa dengan mudah dipahami oleh pengembang game.

Variety  (functional): algoritma DS  membangkitkan skrip baru untuk setiap agent, dan skrip baru ini menyediakan variasi di behavior nya.

Dynamic scripting adalah teknik online competitive machine- learning untuk game AI, sehingga bisa di-klasifikasi-kan sebagai optimasi stokastik. Dynamic scripting menjaga beberapa rulebase, satu dari setiap kelas agent di dalam game. Setiap kali sebuah instance sebuah agent dibangkitkan, rulebase digunakan untuk membuat skrip baru yang mengendalikan behavior setiap agent. Probabilitas setiap aturan yang ditentukan untuk sebuah skrip dipengaruhi oleh nilai  bobot  yang  dipasang  di  setiap  aturan.  Tujuan  dari dynamic  scripting  adalah  untuk  mengadaptasikan bobot  di setiap  rulebase sehingga nilai  fitness yang diharapkan dari setiap behavior didefinisikan dari skrip yang dibangkitkan meningkat   secara   drastis,   bahkan   di   lingkungan   yang cenderung berubah-berubah.

Rumus yang digunakan untuk team-fitness yaitu :

Dalam rumus team-fitness, g merujuk ke tim, c merujuk ke agent, Ng    N adalah total jumlah agents di tim g, dan ht(c) N  adalah nyawa agent c  di  waktu t.  Hasil dari rumus  ini adalah, apabila sebuah tim memiliki fitness 0, maka dianggap kalah. Dan apabila tum yang memiliki fitness > 0 maka dianggap menang.

Rumus yang digunakan untuk agent-fitness yaitu :

Dimana g adalah tim dimana agent a berada. Rumus ini mengandung empat komponen : (1) F(g), adalah fitness untuk tim g, diturunkan dari rumus team-fitness. (2) A(a)     [0,1], dimana adalah rata-rata dari kemampuan bertahan dari agent a, (3) B(g)    [0,1] dimana adalah parameter nyawa dari semua agents di tim g, dan (4) C(g)    [0,1] dimana adalah parameter besarnya kerusakan yang telah diberikan semua agent di tim lawan g.

Algorithm 1 Script Generation

Algoritma 1 merepresentasikan prosedur pembangkitan skrip. Di  algoritma ini,  fungsi  ‘InsertInScript’ menambah sebuah baris skrip ke skrip. jika baris skrip tersebut sudah terdapat di skrip, fungsi tersebut tidak mempunyai efek, dan mengembalikan nilai ‘false’. Di sisi lain, baris skrip tersebut dimasukkan dan fungsi nya mengembalikan nilai ‘true’. Algoritma ini bertujuan untuk meletakkan baris 'scriptsize' di dalam skrip, tapi mungkin berakhir dengan baris skrip yang lebih sedikit jika membutuhkan lebih dari percobaan 'maxtries' untuk menemukan sebuah baris baru. Fungsi ‘FinishScript’ menambahkan satu atau lebih bari skrip yang secara umum bisa diaplikasikan ke skrip, untuk meyakinkan bahwa skrip tersebut akan selalu menemukan cara untuk mengeksekusi.

Algorithm 2 Weight Adjustment

Fungsi   ‘CalculateAdjustment’   meng-kalkulasi-kan   hadiah, atau hukuman untuk setiap diterimanya aturan yang telah diaktifkan. Parameter 'Fitness' adalah tolak ukur dari peformansi    skrip    tersebut    ketika    dijalankan.    Fungsi

‘DistributeRemainder’   mendistribusikan   perbedaan   antara total bobot yang sekarang, dan total semua bobot asli.

Secara umum,'Fitness' ini akan diimplementasikan sebagai perulangan di atas semua bobot, menyerahkan sebagian kecil pecahan dari sisa untuk setiap bobot jika itu tidak menyebabkan  bobot  tersebut  melebihi  batas  bobot,  hingga 'remainder' nya nol. Ketika banyak dari bobot di rulebases mencapai batas bobot, ini bisa menjadi proses yang menghabiskan sangat banyak waktu yang benar-benar mengganggu    game play.    Sebagai    solusi,    bagian    dari 'remainder' bisa di bawa ke panggilan penyesuaian bobot berikutnya.

C.  Capture The Flag

Game dengan genre CTF diadaptasi dari genre Real Time Strategy (RTS), atau Turn Based Strategy (TBS). Game CTF merupakan game yang bertujuan dimana setiap tim harus menguasai satu tempat yang dikategorikan sebagai tempat bendera musuh untuk  memenangkan permainan. Pemenang bisa didapat dari tim mana yang paling banyak menguasai tempat bendera musuh, atau hingga waktu yang ditentukan habis. Game CTF memerlukan strategi tim untuk bertahan, dan menyerang tim musuh. Game ini juga membutuhkan kemampuan individual seperti kecepatan berlari, menganalisa medan permainan, dll.

SKENARIO SIMULASI

A.  Analisis Kebutuhan Sistem

Untuk  tahap  perancangan sistem,  simulasi  membutuhkan sebuah tools yang mampi mengimplementasikan 'script generation' & 'weight adjustment' secara online learning, dan parameter performansi yang jelas. Dalam hal ini, parameter performansi yang dimaksud adalah 'skor'.

Proses tahapan dalam membangun simulasi dapat di lihat pada gambar berikut :

B.  Perancangan Simulasi

1.    Blue bot vs red bot

Player akan mengendalikan pihak blue bot untuk melawan red bot.Pemain akan berperan sebagai AI Commander, yang artinya hanya akan memerintahkan secara global, bukan secara mikro seperti game RTS pada umumnya.

2.    Aturan dasar dari AI Sandbox yang digunakan Beberapa  perubahan  seperti  jarak  pandang  bot,  kecepatanberjalan,  waktu  tunda  saat  botberputar  untuk  mengambil posisi menembak akan diseimbangkan lagi apabila diperlukan. Ada tujuh aturan dasar dari game ini, yaitu :

Satu  bot  yang  mengambil  posisi  bertahan  di  arah yang tepat, akan selalu menang melawan bot yang menyerang.Satu bot yang menyerang dengan arah yang tepat, akan selalu menang melawan bot yang sedang menyerbu.Dua  bot  yang  menyerang  satu  bot  akan  menang, setelah terdapat satu korban dari pihak yang menyerang Dua  bot  yang  menyerbu  satu  bot  akan  menang, setelah terdapat satu korban dari pihak yang menyerbu.Satu bot yang menyerbu akan menang melawan bot yang bertahan menghadap arah yang kurang tepat.Untuk konsep bendera, ada dua aturan dasar, yaitu :

Saat   ada   bendera  yang  jatuh  setelah  bot   yang membawa ditembak oleh pihak lawan, bendera hanya bisa diambil oleh pihak bot yang membawa sebelumnya.

Setelah sekian detik bendera tersebut tidak ada yang mengambil, bendera tersebut akan kembali lagi ke tempat semula.

Untuk konsep bertarung, bot akan otomatis meng-handle ini. Ada tiga aturan dasar yaitu :

Jeda  menembak  dari  berjalan  atau  berlari  (jeda menembak dari berlari akan lebih lama)

Jeda menembak untuk berputar, dan mengambil garis lurus pada target.

Waktu jeda menembak yang konstan (0,5 detik)

3.    AI Commander

AI Commander berperan sebagai otak dari kubu merah atau biru. Disini, AI Commander berperan sebagai strategic level untuk AI pada game ini. Beberapa  aturan  yang  diimplementasikan  untuk  AI Commander ini adalah :

4. Empat perintah global untuk bot

Sebagai AI Commander,  perintah yang bisa diberikan untuk bot adalah :

Defend - Bot akan mengambil posisi jongkok, dan fokus membidik musuh di sekitarnya. Membidik berakibat tembakan sangat akurat, dan  mematikan. Akan tetapi jarak pandang terbatas, dan butuh waktu untuk di-set ke posisi seperti ini.

Attack   –   Bot   akan   menyerang  ke   posisi   yang ditentukan.  Jika  ada  bot  musuh  yang  terlihat,  bot akan langsung menembak

Charge – Bot akan menyarang ke posisi yang telah ditentukan dengan kondisi berlari. Gerakan ini lebih cepat dari Attack tetapi mendapat pinalti waktu tunda untuk menembak.

 Move   -   Berjalan   meng-eksplorasi   peta.   Dalam kondisi ini, bot tidak akan menyerang musuh yang masuk dalam jangkauan tembak.

1.1.1Ruang Lingkup Simulasi

Simulasi dijalankan dengan spesifikasi sebagai berikut :

Perangkat lunak

1. AI Sandbox 0.20.9 dengan 4 AI yang diujikan.
2.  Eclipse  dengan  plugin  PyDev  untuk  memprogram AAI dengan bahasa Python.
3. Microsoft   Office   untuk    pengolahan   data    dan penulisan laporan.

Perangkat keras

1.  Single CPU
2. 50 GB HDD
3.  2048 Mb RAM

C.  Skenario Simulasi

Pada simulasi yang dijalankan terdapat berbagai macam faktor yang akan mempengaruhi output yang dihasilkan, baik secara langsung  maupun  tidak  langsung. Untuk itu, perlu didefinisikan terlebih dahulu pemodelan simulasi secara umum untuk mengetahui faktor apa saja yang berpengaruh saat proses simulasi berlangsung.

Capture The Flag SDK adalah simulasi yang digunakan untuk menguji   commander   yang   beradaptasi   lewat   AI   buatan pemain, dan dijalankan dengan AI Sandbox™. AI yang dibuat akan memerintah bot dari tim sendiri, dan beradaptasi untuk mengalahkan tim lawan di beberapa variasi level. Game ini dimainkan oleh dua tim oleh bot, dimana poin nya diperoleh kapanpun sebuah tim mengambil bendera tim lain dan mengembalikan nya ke lokasi dimana bendera mencetak skor. Pemenangnya adalah tim yang mencetak paling banyak poin. Bendera dan bot akan kembali hidup secara sinkron pada interval yang teratur sampai game berakhir. Bot di game ini tidak bisa dikontrol secara interaktif, tetapi mereka dikendalikan oleh AI commander strategis yang dibuat di Python.

Blok  diagram  ini  menjelaskan  tentang  bagaimana  seluruh

proses pada Tugas Akhir ini.

Gambar III.1 Blok diagram simulasi CTF

Penggambaran proses  implementasi untuk  AAI  pada  game CTF ini dijabarkan menjadi lima tahap, yaitu insialisasi gameinfo.py, jalankan class LevelInfo(object), commander memberi perintah(informasi) ke bot, update weight adaptation & learning rate, dan looping hingga skor atau batas waktu yang ditentukan.

DAFTAR PUSTAKA

[1] Alexander Nareyek , Game AI Is Dead. Long Live GameAI!: National Univesity of Singapore, 2007.

[2] J Hagelback and S.J. Johansson , Measuring player experience on runtime dynamic difficulty scaling in an RTS game., 2009.

[3] Schaeffer J, "‘A Gamut of Games’," Artificial IntelligenceMagazine 22(3), pp. 29–46, 2001.

[4] Haomiao Huang and Jerry Ding, A Differential Game Approach to Planning in Adversarial Scenarios: A. Berkeley: NASA (NNA06CN22A) AFOSR, 2011.

[5] J van Waveren and J Rothkrantz, "Artificial player forQuake III arena," International Journal of Intelligent Games& Simulation 1, 2003.

[6] Marc S Atkin , David L Westbrook , and Paul R Cohen , Capture the Flag: Military Simulation Meets Computer Games.: IN PROCEEDINGS OF AAAI SPRING SYMPOSIUM SERIES ON AI AND COMPUTER GAMES,1999.

[7] Bijan Fazlollahi and Mihir A Parikh , Adaptive DecisionSupport Systems.: Georgia State University, 1997.

[8] A Ram , S Ontanon , and M Mehta , Artificial Intelligence for Adaptive Computer Games., 2007.Evolutionary Learning., 2005.

[9] P Spronck and D.W Aha , Automatically Acquiring

Domain Knowledge For Adaptive Game AI Using

·         Pengenalan Komputer” karangan Jogiyanto Hartono, MBA, Ph.D

·         Artificial Intelligence, Sri Kusumadewi, Graha Ilmu Yogyakarta, 2003

·         Artificial Intelligence, Sandi Setiawan, Andi Offset Yogyakarta, 1993

·         Mengenal Artificial Intelligence, Suparman, Andi Offset Yogyakarta, 1991.

·         http://siferrsaankes.blogspot.com/2012/05/kecerdasaan-buatan.html

·         http://setiyanugroho.wordpress.com/2011/04/12/kecerdasan-buatan-dalam-game/

·         http://blog-habibie.blogspot.co.id/2012/05/artificial-intelligence-pada-game.html