DESAIN PERILAKU AGEN PADA PERMAINAN BULUTANGKIS DENGAN MENGGUNAKAN MULTI-OBJECTIVE GENETIC ALGORITHM Adianto*,Supeno Mardi, ST, MT** Moch Hariadi, ST, Ms.c,Ph.D**
[email protected],
[email protected],
[email protected] *Jurusan Teknik Elektro – FTI, ITS, Surabaya *Jurusan Teknik Elektro – FTI, ITS, Surabaya *Jurusan Teknik Elektro – FTI, ITS, Surabaya
Sulit untuk mendesain suatu agen NPC’s (non-player characters) yang memiliki kemampuan mengembangkan permainannya pada saat melawan player. Pengembangan permainan itu meliputi kemampuan untuk menyerang dan bertahan. Pada kebanyakan game saat ini dibuat menggunakan single object dengan melibatkan fungsi satu objektif dan biasanya hasil dalam satu solusi. Untuk mengatasi masalah tersebut dengan membuat solusi optimal yang dapat digunakan untuk berbagai fungsi object, yaitu dengan menggunakan Multi-objective Algoritma Genetika. Optimasi. Multiobjective mempertimbangkan beberapa konflik untuk mendapatkan tujuan secara bersamaan. Dalam kasus ini, biasanya tidak ada satu solusi optimal, tetapi satu set alternatif dengan trade-off berbeda. Multi-objective yang dipakai pada penelitian ini dengan memakai NSGA II (Non-Dominated Sorting in Genetic Algorithms). NSGA II akan memberikan nilai pareto front untuk fungsi minimal dan fungsi maksimal. Diharapkan dari penelitian ini akan didapatkan solusi optimal yang dapat mengakomodir object dalam game permainan bulutangkis dan agen NPC’s akan dapat memiliki kemampuan adabtif dalam mengembangkan permainannya. Keyword: Multi-objective Algoritma Genetika, Non-Dominated Sorting in Genetic Algorithms, pareto front I. PENDAHULUAN Game yang memiliki perilaku agent dimana kemampuan agentnya bisa berkembang dengan mempelajari kemampuan player sulit untuk diimplementasikan. Perilaku agent yang memiliki kemampuan kompleks akan bermanfaat untuk pengembangan pola permainan game yang lebih menarik. Para perancang game bisa menggunakan metoda ini untuk memberikan karakter kepada agent non-player characters (NPC’s), atau mereka bisa melatih agent untuk melawan player yang memiliki perilaku yang didesign menggunakan script dan juga bisa dimanfaatkan untuk menemukan kelemahan-kelemahan pada pola script yang dibuat. Metoda ini digunakan agent untuk melatih perilakunya pada saat melawan pemain. Untuk membuat game semakin menarik maka game harus melibatkan multiobjective yang disertakan [Jacob Schrum and Risto Miikkulainen,2008]. Pada saat ini kebanyakan game dibuat menggunakan single object dimana metoda pembelajaran berdasarkan nilai scalar reward-nya dan metoda evolusinya memakai nilai fitness function-nya. Optimasi persoalan single-objective melibatkan satu objektif dan biasanya hasil dalam satu solusi, dinamakan sebuah solusi optimal. Untuk mengatasi masalah ini maka kita menggunakan metoda multi-objective optimization. Metode multi-objective optimization berhubungan dengan Metode
Pareto[Coelo 1999]. Multi-objective optimization digunakan juga oleh beberapa peneliti sebelumnya namun tidak digunakan untuk menemukan perilaku agent NPC’s pada permainan game. Metode itu dipakai antara lain untuk penelitian mengenai system scheduling [Tamaki, Kita, and Kobayashi 1996],Tic-tac-toe[ Yau, Teo, and Anthony 2007 ], n-parity problem [Jong,Watson, and Pollack 2001] dan masalah-masalah lainya yang berhubungan dengan optimization. Pada penelitian ini akan dicoba menggunakan multi-objective opotimization untuk diaplikasikan ke game permainan bulutangkis. Pada penelitian ini kami akan mencari langkah-langkah untuk diimplementasikan pada agent NPC’s supaya memiliki perilaku yang dapat secara adaptif melawan perilaku player yang didesign menggunakan script. Selain itu NPC’s akan dapat mengembangkan kemampuannya dari pembelajaran yang diterima dari player. Diharapkan penelitian ini dapat membuat game permainan badminton jadi lebih menarik II. METODE Penelitian ini dilakukan dengan menggunakan multi-objective genetic algorithm (MOGA), dalam hal ini memakai Elist Non-dominated Sorting Genetic Algorithm (NSGA II). Adapun urutan kerja dari NSGA II ini dapat kita lihat berdasarkan flow chart dibawah ini Start
Initialise Populasi gen
Pop Classified
No
Fitness
Gen= gen+1 Crossover
Mengidentifikasi Individu yang dominan
Mutation Yes
Apakah Pop Terklasifikasi NO STOP
Gambar 2.1 Flowchar NSGA II
2.1 Inisialisasi Populasi Inisialisasi populasi dilakukan dengan membentuk sejumlah populasi. Pada penelitian ini ditentukan jumlah populasi 75 kromosom. Kromosom terdiri atas 3 gen dimana merupakan variable factor dari penyelesaian yaitu kecepatan bola lawan (X1), kecepatan angina (X2), dan jarak agent dengan lawan (X3). Inisialisasi populasi yang dibuat untuk penelitian ini dengan memakai gen float atau bilangan decimal. Pemakaian gen float ini digunakan untuk menyederhanakan system, sehingga tidak perlu adanya converting binary ke decimal atau sebalaiknya. Kromosom dibangkitkan dari random yang bersifat uniform bilangan 0 < X < 1. Nilai ini merupakan representasi dari bentuk
level nilai variable factor yang akan menentukan besarnya nilai objective (fitness function) yang kita buat nanti. 2.2 Objective ( Fitness Funtion) Dalam penelitian ini kita menggunakan 2 objective atau fitness function untuk menentukan fungsi minimal dan fungsi masimal. Untuk Fitness Function (1) kita membuat sebagai fungsi maksimal yaitu merupakan fungsi level pukulan agent dimana hubungannya sebagai berikut: Fungsi pertama ini berhubungan dengan momentum tumbukan 2 benda.
Gambar 2.2 Kekekalan Momentum '
m1v1 + m2v2 = m1v1 + m2 v2
'
Karena shuttlecock dan raket mengalami lenting sebagaian maka nilai koefisien restitusi a ( e ) = 0 ≤ e ≤ 1 dimana koefisien restitusi
v1'− v2' e=− v1 − v2 Sehingga kita mengambil nilai '
'
m1v1 + m2 v2 = 1 Maka dapat kita ambil :
m1v1 = 1 − m2 v2
f1 ( x) = 1 − x dimana:
f1 ( x) x
: Fungsi maksimal ( Fungsi pukulan agent ) : Kecepatan bola lawan ( 0<x<1 )
Untuk Fitness Function (2) kita buat sebagai fungsi minimal yaitu merupakan fungsi stamina, dimana faktor stamina ini, akan dibuat persamaan berdasarkan beberapa asumsi di bawah ini :
1) Stamina adalah simpanan energi energi residu. Hubungan antara stamina dan energi merupakan hubungan berbanding terbalik, artinya semakin besar energi yang dikeluarkan maka semakin kecil/ sedikit simpanan energinya (stamina berkurang). Sebaliknya, semakin kecil energi yang dikeluarkan maka semakin besar simpanan energinya (stamina besar). Stamina ≈
1 Energi
2) Energi disini adalah besar Energi kinetik yang dikeluarkan oleh pemain. Enegi kinetik oleh pemain sebanding dengan Energi kinetik oleh bola dari lawan Ek pemain = Ek bola
Ek =
1 m.v 2 2
Dimana: Ek = Energi Kinetik m = Massa Bola, tetap, misal 1
3) Kecepatan bola lawan (v) akan dipengaruhi (dihambat) oleh faktor kecepatan angin yang searah dengan pemain (r) dan jarak antara pemain dengan lawan (p), sehingga hubungan anatara kecepatan bola (v) dengan kecepatan angin (r) dan jarak (p) merupakan hubungan berbanding terbalik dan (v) berbanding lurus dengan (x) Jika tidak ada pengaruh kecepatan angin ( r ) dan jarak ( p ) maka :
v=x
Karena kecepatan bola lawan (v) dipengaruhi (dihambat) oleh faktor kecepatan angin yang searah dengan pemain (r) dan jarak antara pemain dengan lawan (p) maka :
v=
x (r + p)
4) Total Energi yang dimiliki pemain adalah 120 Kkalori. Asumsi ini didasarkan pada teori yang disampaikan oleh Jhon R.Cameron,James G.Skofronick,Roderick M.Grant dalam bukunya yang berjudul “Physics of the Body” Dari keempat asumsi diatas, dapat ditarik suatu hubungan sebagai berikut : Stamina yang terisisa adalah Energi maksimal (120 kalori) dikurangi enegi yang dikeluarkan Stamina ≈ 120 −
1 Energi
Stamina ≈ 120 −
1 Ek
Stamina ≈ 120 − 1
2
dimana m =1 sehingga :
1 mv 2
1 x 1( )2 2 (r + p)
Stamina ≈ 120 − 1
Stamina ≈ 120 −
2( r + p ) 2 x2
2( r + p ) 2 f 2( x, r , p ) = 120 − x2 dimana :
f 2 ( x, r , p) = Fungsi minimal ( Fungsi stamina agent ) x = Kecepatan bola lawan ( 0<x<1 ) r = Kecepatan angina ( 0<x<1 ) p = Jarak agent dengan lawan ( 0<x<1 ) 2.3 Seleksi Pada multi-objective genetic algorithm (MOGA) dalam hal ini NSGA II sebagai proses seleksinya dengan memakai Non-Dominated Sort dan kemudian diseleksi lagi dengan menggunakan Crowding distance. Adapun langkah-langkah yang dilakukan digambarkan sebagai berikut • Semua individu yang ada didalam populasi dilakukan insialisasi.langkah yang pertama adalah membuat kumpulan dominasi S p = φ , S p ini nantinya berisi kumpulan individu yang dominan. • Membentuk variabel n p yang digunakan untuk menghitung jumlah individu didalam kumpulan dominasi S p . •
Setelah kumpulan dominasi S p
terpenuhi dan nilai n p merupakan
representasi dari jumlah dominasi yang ada didalam kumpulan S p •
Setelah itu terbentuk kumpulan front yang didapat dari jumlah n p
•
Langkah selanjutnya adalah proses crowding distance
• • •
Crowding distance adalah proses sorting dari kumpulan S p dan menghasilkan nilai non-dominated. Pada proses crowding ini adalah untuk menemukan jarak euclidian diantara masing-masing individu didalam sebuah front berdasarkan fungsi objectivnya. Kemudian individu tersebut terpilih menjadi parent yang akan dicrossover
2.4 Genetic Operators Genetic operator terdiri atas dua bagian yaitu Crossover dan Mutasi. 2.4.1 Cross-Over Pada proses Crossover ini dilakukan atas 2 kromosom untuk menghasilkan kromosom baru (offspring). Kromosom anak yang terbentuk akan mewarisi sebagaian sifat kromosom induknya. Pada penelitian ini crossover dilakukan dengan menggunakan arithmetic crossover. Proses crossover arithmetic dapat digambarkan seperti dibawah ini :
O1 = R(OP1 ) + (1 − R)OP2 O2 = R(OP2 ) + (1 − R)OP1
dimana : O1 O2 OP1 OP2 R
= Offspring (1) = Offspring (2) = Old Parent(1) = Old Parent(2) = Nilai Random ( 0 < R < 1 )
Dalam proses croosover ini ada parameter penting yang harus diperhatikan karena berkaitan dengan rasio anak yang akan dihasilkan dalam satu generasi. Parameter itu adalah probabilitas crossover. Probabilitas crossover menunjukan presentase jumlah Old Parent yang akan di crossover dan menghasilkan offspring (keturunan baru). Penentuan besar kecilnya crossover tergantung dengan permasalahan yang dicari optimalnya. 2.4.2 Mutasi Proses mutasi ini adalah suatu proses eksploitasi terhadap kemungkinankemungkinan modifikasi pada hasil yang telah ada. Pada proses mutasi dilakukan dengan menentukan keturunan baru yang dipilih secara random dari sejumlah populasi. Kemudian kromosom yang terpilih akan dipilih secara acak posisi gen yang akan dimutasi. Setelah terpilih gen pada salah satu kromosom kemudian dimutasi dengan merandom lagi nilai gen yang telah diperoleh. Pada proses mutasi ini sama dengan pada proses crossover, dimana mutasi yang terjadi tergantung pada nilai probabilitas mutasinya. Probabilitas mutasi menunjukan
presentase jumlah offspring yang terkena mutasi. Penentuan nilai probabilitasnya tergantung pada permasalahan yang dicari optimalnya. III. HASIL DAN DISKUSI Pada bagian ini akan dibahas mengenai hasil pengujian dan pembahasan hasil pengujian. Hasil pengujian ini berupa data pareto front dari MOGA NSGA II.
MOP1 using NSGA-II
120 110 100
f(x2)
90 80 70 60 50 40
0
0.1
0.2
0.3
0.4
0.5 f(x 1)
0.6
0.7
0.8
0.9
1
Hasil Plot diatas diambil dari running program NSGA II dengan nilai parameter sebagai berikut: Jumlah Generasi: 5 Population size (Even no.): 75 Crossover probability: 0,9 Mutation probability: 0,9 Plot diatas adalah data Pareto Front dari fungsi pukulan dan fungsi stamina agent. Fungsi stamina menunjukan nilai yang tinggi pada semua level nilai pada fungsi pukulan. Dari data hasil diatas dapat diketahui bahwa nilai-nilai pareto front yang didapatkan dari MOGA NSGA II nilainya sesuai dengan yang kita inginkan dan menghasilkan nilai yang dapat memenuhi untuk kedua fungsi objective tersebut. Nilainilai pada kedua fungsi itu memenuhi untuk diimplementasikan menjadi perilaku agent pada game bulutangkis. Agent pada game bulutangkis akan dapat diatur level staminanya untuk berbagai level pukulan sehingga agent akan dapat berkembang kemampuannya dalam menghadapi player. Proses pengujian dari hasil pareto front ini dilakukan pada game bulutangkis sederhana dimana parameter permainan yaitu kecepatan bola lawan, kecepatan angin searah dengan pemain dan jarak pemain dengan lawan. Dan faktor tindakan dari pemain berdasarkan fungsi stamina dan fungsi pukulan. Tindakan / respon pemain ditentukan oleh fungsi stamina dan fungsi pukulan. Sedangkan lawan tindakannya didesain dengan script.
Dari hasil pengujian didapatkan respon dari pemain (agent) dimana pukulannya dari setiap level pukulan dapat merespon pukulan lawan yang didesain dengan script, dan respon tersebut dapat menyesuaikan dengan kondisi stamina. Karena setiap level pukulan dapat didukung oleh stamina yang adaptif. Sehingga pemain akan dapat memilih level pukulan sesuai dengan stamina yang dimilikinya. Dari hasil pengujian ini dapat dilihat bahwa level stamina memberikan respon pukulan yang sesuai dengan hasil pareto front dari NSGA II. IV. KESIMPULAN DAN SARAN • • •
Dari penelitian yang telah dilakukan,dapat diambil suatu kesimpulan: MOGA NSGA II menghasilkan solusi alternative yang optiamal untuk lebih dari satu fungsi. MOGA NSGA II dapat diimplementasikan pada agent permainan game bulutangkis untuk memberikan pengembangan permainan yang lebih menarik MOGA NSGA II dapat digunakan untuk pengembangan game bulutangkis dengan menambah variable factor dan fungsi hasil yang lebih dari satu fungsi
Dari penelitian ini MOGA NSGA II dapat digunakan untuk dikembangkan jumlah fungsi yang akan dicari solusi optimal bersamanya untuk menambah perilaku dari agent. Selain itu juga dapat ditambah variable factor yang mempengaruhi fungsi objective sehingga dapat dihasilkan game permainan bulutangkis yang lebih menarik V. DAFTAR PUSTAKA [1] [2] [3] [4] [5] [6] [7] [8]
Jacob Schrum and Risto Miikkulainen . Constructing Complex NPC Behavior via Multi-Objective Neuroevolution.Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference 2008 Coello, C. A. C. A comprehensive survey of evolutionarybased multiobjective optimization techniques. KAIS 129–156. 1999 Tamaki, H.; Kita, H.; and Kobayashi, S. Multi-objective optimization by genetic algorithms: a review. Evol. Comput.1996 Yau, Y. J.; Teo, J.; and Anthony, P. Pareto Evolution and Co-evolution in Cognitive Game AI Synthesis. EMO 227–241.2007 Jong, E. D.; Watson, R.; and Pollack, J. Reducing bloat and promoting diversity using multi-objective methods. GECCO. 2001 Http://id.wikipedia.org/wiki/Bulutangkis Srinivas Mukkamala, Andrew Sung, Feature Ranking and Selection for Intrusion Detection, Proceedings of the International Conference on Information and Knowledge Engineering – IKE 2002, June 2002 Klein, J. 2003. BREVE: a 3D environment for the simulation of decentralized systems and artificial life. ALIFE 329–334.
