AGEN CERDAS GAME REMI BERBASIS MINIMAX DWI KURNIAWAN SAPUTRO Program Pasca Sarjana Game Technology Institut Teknologi Sepuluh Nopember Surabaya
Abstrak: Salah satu penggunaan agen game sebagai coumputer controlled character dalam game adalah sebagai lawan main dari pengguna game. Agen diharapkan dapat memberikan perlawanan agar pengguna merasa tertantang untuk memainkan game tersebut. Keberadaan agen game yang terlalu kuat akan membuat pengguna cepat merasa frustasi dan jika terlalu lemah membuat pengguna tidak tertarik lagi untuk memainkan game. Pendekatan untuk mengatasi masalah tersebut biasanya dilakukan dengan memberikan fasilitas kepada pengguna untuk dapat mengatur atau memilih tingkat kesulitan atau kemampuan agen sebelum game dimulai. Namun cara tersebut dinilai terlalu statis karena selama game berlangsung kemampuan agen game tidak dapat berubah seiring dengan perkembangan kemampauan pengguna. Penelitian ini mencoba untuk merancang kerangka kerja suatu agen game remi yang dapat berperilaku dinamis menggunakan minimax. Bentuk perilaku didasarkan pada peroleh nilai pemain yang kemudian digunakan minimax untuk melakukan pencarian maksimum atau minimum. Hasil yang diperoleh menunjukan bahwa agen dapat memberikan tanggapan yang berbeda tergantung dari perolehan nilai pemain.. Kata Kunci : game remi, agen game, perilaku dinamis, minimax PENDAHULUAN Game kartu merupakan salah satu game yang sering dimainkan oleh banyak orang. Selain alat yang digunakan mudah diperoleh, banyaknya jumlah pemain yang ikut serta dalam game tersebut, bisanya 4 orang, menyebabkannya digemari oleh banyak orang. Teknologi komputer memampukan permainan kartu ini untuk dimainkan dengan atau tanpa orang lain sebagai lawan dalam bentuk game komputer. Peran pemain lawan dapat digantikan oleh keberadaan agen game. Penelitian tentang agen game telah menjadi perhatian para peneliti di bidang Artificial Intelligence (AI). Dan sejauh ini penelitian di bidang AI untuk game playing telah sukses menghasilkan program yang kompetitif untuk two-player game, seperti checker [Schaeffer et al.(1992)], backgammon [Tesauro(1994)] dan catur dengan Deep Blue-nya [Campbell et al.(2002)]. Game dengan agen sebagai lawan yang terlalu kuat akan membuat player cepat merasa frustasi dan pada akhirnya akan mengakhiri niatnya untuk bermain game [Livingstone et al.(2004)]. Tetapi jika agen terlalu lemah akan menyebabkan player menjadi tidak tertarik lagi untuk memainkan game [Scott(2002)]. Hal ini biasanya diatasi dengan menyediakan pengaturan level kesulitan game (easy, medium, hard) pada awal permainan. Jadi player dapat menentukan level lawan yang akan dihadapi sebelum game dimulai. Cara seperti ini dinilai terlalu statis, karena selama permainan level lawan tidak dapat serta merta berubah seiring dengan perkembangan kemampuan bermain player [Andrade(2005)]. Penyelesaian masalah untuk game yang kompetitif merupakan domain dari adversarial search. Karena
adversarial search menggunakan metode pencarian yang melibatkan dua pihak yang saling berlawanan. Satu pihak akan mendapatkan keuntungan sebesar kerugian yang diterima oleh pihak lainnya. Salah satu algoritma adversarial search adalah minimax. Dalam penelitian ini akan dicobakan membuat agen game remi yang dapat berperilaku dinamis. Menggunakan minimax untuk menyelesaikan permasalahan game remi. DEFINISI GAME REMI Peraturan yang berlaku dalam permainan remi ada bermacam-macam. Tiap-tiap kelompok mempunyai aturan sendiri-sendiri. Dalam penelitian ini permainan remi adalah permainan kartu yang dimainkan oleh dua orang dan memiliki aturan permainan sebagai berikut : Alat : Standar 52 kartu Ranking : As = nilai tertinggi Nilai : King, Queen, dan Jack = 10; As = 15; lainnya = 5; Pegangan : 7 buah kartu diberikan pada tiap player diawal pertandingan; kartu berikutnya membentuk tumpukan buangan; kartu yang tersisa membentuk tumpukan ambilan; tumpukan buangan selalu menghadap ke atas; tumpukan ambilan menghadap ke bawah Tujuan : membentuk urutan yang terdiri dari 3 atau lebih kartu yang se-jenis atau kumpulan 3 atau 4 buah As dan satu kartu sisa digunakan untuk menutup permainan Urutan main : setiap urutan bermain tiap player dapat mengambil satu kartu teratas yang terdapat pada tumpukan buangan atau tumpukan ambilan; setelah itu harus menaruh satu kartu pada
tumpukan buangan; kartu urut yang didapat karena mengambil satu kartu dari tumpukan buangan harus dipisahkan dari pegangan dan ditaruh pada tumpukan jadi dengan menghadap keatas; Penutup : tiap player dapat melakukan penutupan jika semua kartu dapat dijadikan urutan dan tersisa satu kartu yang digunakan untuk menutup. Penilaian : kartu penutup mempunyai nilai sebagai berikut; King, Queen, Jack = 50; As = 150; lainnya = 50; Player lawan akan mendapatkan pengurangan nilai sebesar nilai kartu penutup lawannya. Kartu jadi bernilai sama seperti nilai aslinya.
Permasalahan dalam game remi adalah bagaimana menentukan strategi untuk menyusun kartu yang ada ditangan menjadi urutan seri atau pararel. Pada tiap gilirannya masing-masing permain harus dapat menentukan kartu mana yang harus diambil, menyusun kartu menjadi urutan dan menentukan kartu yang harus dibuang. AGEN GAME Penelitian tentang agen game telah menjadi perhatian para peneliti di bidang AI. Dan sejauh ini penelitian di bidang AI untuk game playing telah sukses menghasilkan program yang kompetitif untuk two-player game. Deep Blue berhasil mengalahkan juara dunia catur Garry Kasparov. Chinook menjadi juara kedua US Open tahun 1990 untuk game checker. TD-Gammon menjadi tiga pemain terhebat di dunia untuk game backgammon . Agen game adalah suatu agen perangkat lunak. Agen perangkat lunak adalah suatu suatu sistem yang berada atau merupakan bagian dari suatu lingkungan dimana ia dapat merespon (sense) lingkungan tempat dia berada dan bertindak terhadapnya setiap waktu, untuk melakukan tugasnya dan yang akan dapat memberikan dampak akan apa yang akan dilakukan berikutnya [Franklin et al.(1996)]. Secara umum sebuah agen generik terlihat seperti gambar berikut ini.
Gambar 1.
Agen Berinteraksi dengan Lingkungan melalui Sensor dan Efektor [Russel et al. (2003)]
Ada kriteria yang harus dipenuhi agar suatu program dapat disebut sebagai agen. Kriteria atau ciri-ciri dasar suatu agen adalah :
Reactivity : kemampuan untuk dapat cepat beradaptasi dengan adanya perubahan informasi yang ada dalam suatu lingkungan. Autonomy : kemampuan untuk dapat melakukan tugasnya sendiri dan tidak dipengaruhi secara langsung oleh manusia atau agen lain maupun oleh lingkungannya. Dapat dikatakan juga sebagai kemampuan mengatur setiap aksi yang dibuatnya. Proactivity dan Goal-Oriented : kemampuan untuk bertindak tidak hanya sebagai respon dari lingkungannya, tetapi juga berinisiatif untuk menyelesaikan permasalahan. Oleh karena itu agen mempunyai tujuan (goal) yang jelas dan selalu berorientasi pada tujuan tersebut. Continuity : kemampuan untuk dapat merespon lingkungannya secara terus menerus selama periode tertentu Kriteria lainnya dapat ditambahkan seperti kemampuan untuk beradaptasi termasuk didalamnya kemampuan untuk belajar (learning) dan reasoning. Kemampuan untuk berpindah (mobile), dinamis dan mempunyai karakter atau mempunyai ‘emosi’. PERILAKU DINAMIS Game dengan agen sebagai lawan yang terlalu kuat akan membuat pengguna akan cepat merasa, jika agen terlalu lemah akan menyebabkan player menjadi bosan dan pada akhirnya tidak tertarik lagi untuk memainkan game. Pengaturan tingkat kesulitan game pada awal permainan disediakan untuk mengatur kemampuan agen game. Cara seperti ini dinilai terlalu statis, karena selama permainan level lawan tidak dapat serta merta berubah seiring dengan perkembangan kemampuan bermain pengguna. Perilaku dinamis oleh agen game juga merupakan kajian dalam AI. Andrade menggunakan reinforcement learning yang diaplikasikan pada game Knock’Em [Andrade et al.(2004)] untuk membuat agen game yang dapat belajar untuk memperoleh strategi yang optimal dan agen yang dapat berperilaku adaptif untuk menentukan seleksi terhadap mekanisme untuk menentukan aksi berdasarkan kemampuan lawannya. MINIMAX Dalam multiagent environment, masing-masing agen akan mempertimbangkan perilaku dari agen lainnya dan bagaimana akibatnya terhadapnya dalam mencapai tujuannya sendiri. Hubungan antar agen yang dapat saling membantu biasa disebut cooperative multiagent environment (agen kawan) dan hubungan yang saling mengalahkan disebut competitive multiagent environment (agen lawan). Lingkungan yang kompetitif akan mengakibatkan konflik antar agen untuk mencapai tujuannya, dan hal ini disebut adversarial search problem atau biasa disebut game. Minimax sebagai salah satu algoritma untuk menyelesaikan permasalahan adversarial melakukan proses pencarian solusi dengan membangun suatu pohon
pencarian (search tree) dan mekanisme pencarian menggunakan prinsip kerja depth first search. Misalkan game dengan dua pemain, yaitu Max dan Min. Max mendapat giliran bermain pertama kemudian dilanjutkan oleh Min begitu seterusnya sampai game berakhir. Pada akhir game pemain yang menang akan mendapatkan nilai sebagai reward dan pemain yang kalah mendapatkan pinalty. Optimal strategi dari suatu pohon pencarian dapat ditentukan dengan menghitung nilai minimax pada tiap node, biasa ditulis MValue(n). MValue ini adalah nilai utility (dari sudut pandang Max) pada suatu state tertentu dengan asumsi bahwa kedua player bermain secara optimal sampai akhir. Misal diberikan pilihan, Max akan lebih memilih untuk menuju state yang mempunyai nilai maksimum sedangkan Min lebih menuju ke state yang bernilai minimum. Sedemikan hingga diperoleh persamaan sebagai berikut : jika n terminal node Utility(n) MVALUE max sSuccessor( n ) MVALUE ( s) jika n MAX node min MVALUE ( s) jika n MIN node sSuccessor( n )
Agen dirancang untuk dapat menerima input dengan lingkungannya, mengolah data yang diterimanya dan memberikan aksi berdasarkan hasil pengolahan data yang dilakukan. Mekanisme kerja agen dapat dilihat seperti pada Gambar 3.
Gambar 3. Alur Kerja Agen Game Remi Untuk dapat menjalankan fungsi-fungsi tersebut maka agen disusun dari beberapa operator seperti yang ditunjukan oleh Gambar 4.
(1)
Gambar 4. Arsitektur Agen Game Remi
Gambar 2. Contoh Pohon Pencarian Pada Gambar 2, node A adalah ‘Max’ node yang menunjukkan giliran Max dan node adalah ‘Min’ node. Terminal node menunjukkan nilai utility untuk Max. sedangkan node lainnya menunjukkan MValue-nya. Langkah terbaik dari Max adalah a1 karena menuju pada successor yang mempunyai nilai tertinggi, dan langkah terbaik berikutnya oleh Min adalah b1 karena menuju pada successor dengan nilai terendah. Menurut definisi MValue seperti pada Persamaan 1 maka Min node yaitu node dengan label B mempunyai 3 successor yang bernilai 3,12 dan 8. Sehingga MValue nya bernilai 3. Untuk nilai pada node C dan D bernilai masing-masing 2. Node root A adalah Max node mempunyai 3 successor yang bernilai 3,2 dan 2, sehingga didapatkan MValue-nya sama dengan 3. Aksi a1 adalah pilihan optimal untuk Max karena action ini menuju pada successor yang mempunyai Minimax-Value tertinggi. AGEN GAME REMI Penelitian ini mengajukan suatu agen game remi yang dapat berperilaku dinamis selama game berlangsung.
Interactor sebagai operator yang bertanggung jawab untuk menyaring input dari lingkungannya dan menyampaikan output sebagai bentuk tanggapan agen. Pada intinya interactor berfungsi sebagai operator komunikasi agen. Memory adalah komponen penyimpanan data sebagai basis pengetahuan agen. Selector bertugas untuk menentukan bentuk perilaku agen menggunakan basis pengetahuan yang dimiliki agen. Program operator yang berfungsi untuk memproses data untuk menghasilkan aksi (output) agen.
Gambar 5. Flowchart Pemilihan Bentuk Perilaku Agen Dari data input yang diterima agen dapat mengetahui perolehan nilai dari kedua pemain. Dari informasi ini agen membuat aturan (rule) seperti
ditunjukan oleh Gambar 5 untuk menentukan bentuk perilaku agen berikutnya. Dalam penelitian ini ada dua bentuk perilaku yang digunakan yaitu berperilaku 'pintar' (max) dan 'bodoh' (min). Perilaku pintar berarti melakukan pencarian untuk mendapatkan nilai maksimum dan perilaku bodoh untuk mendapatkan nilai minimum. Algoritma minimax digunakan oleh agen untuk dapat menentukan kartu mana yang harus diambil, kartu yang bisa disusun seri atau pararel dan kartu yang harus dibuang pada setiap giliran main sampai game berakhir. Pengoptimalan aksi agen didapatkan dengan menggunakan rumusan seperti pada Persamaan 1. Sebagian hasil pembentukan pohon pencarian dapat dilihat seperti pada Gambar 6.
Masing-masing agen akan saling dilawankan sebanyak 10 kali dan ukuran kinerja agen didasarkan pada selisih perolehan nilai tiap sesinya. 1600 1400 1200 1000 800
MaxM
600
MinM DM
400 200 0 1
-200
2
3
4
5
6
7
8
9
10
-400
Gambar 7. Kinerja Agen MaxM Melawan Agen Lainnya Gambar 7 menunjukan kinerja agen MaxM terhadap ketiga tipe agen. Nilai negatif titik-titik berwarna biru menunjukan bahwa MaxM kalah terhadap dirinya sendiri dan nilai positif menunjukan kemenangan atas dirinya sendiri. Nilai positif pada titik-titik berwarna merah menunjukan bahwa agen MaxM mengalahkan MinM pada tiap sesi dengan perbedaan nilai yang cukup bersar. Titik-titik berwarna hijau menunjukan MaxM juga selalu mengalahkan DM akan tetapi selisih nilainya tidak begitu besar. 200 0 1
2
3
4
5
6
7
8
9
10
-200 MaxM
-400
MinM -600
DM
-800 -1000 -1200
Gambar 6. Pohon Pencarian Agen Game Remi HASIL UJI COBA AGEN GAME REMI Sebagai uji coba, game remi dimainkan dengan menggunakan 16 kartu dimana masing-masing suit (spade,heart,diamond,club) diwakili oleh 5 macam kartu (As,2,3 dan 4), satu sesi game terdiri dari 10 ronde dan dimainkan oleh dua pemain yang berada di utara (north) dan di selatan (south). Model tipe agen yang digunakan adalah : MaxM, agen game yang selalu memilih perilaku maksimal (pintar) sebagai representasi pemain yang selalu berusaha menang. MinM, agen game yang selalu memilih perilaku minimal (bodoh) sebagai representasi pemain yang selalu berusaha kalah. DM, agen game yang dapat memilih perilaku berdasarkan total nilai, sebagai representasi pemain yang dinamis.
Gambar 8. Kinerja Agen MinM Melawan Agen Lainnya Gambar 8 menunjukan kinerja agen MinM. Dengan menggunakan analisa seperti sebelumnya, agen MinM selalu kalah terhadap MaxM dengan selisih nilai yang besar. Selalu kalah juga dari DM tetapi selisih nilai yang kecil. 150 100 50
0 -50
1
2
3
4
5
6
7
8
9
10
MaxM MinM
-100
DM
-150
-200 -250 -300
Gambar 9. Kinerja Agen DM Melawan Agen Lainnya
KESIMPULAN Agen game remi dapat berperilaku dinamis dengan menggunakan minimax dimana perilaku dinamis dilakukan dengan memperhatikan perolehan total nilai agen selama game berlangsung. Minimax digunakan untuk penyelesaian game yang dimainkan untuk dua orang. Sedangkan game remi sendiri dapat dimainkan sampai empat orang. Sebagai bahan penelitian berikutnya disarankan untuk menggunakan metode penyelesaian permasalah game remi untuk empat. Metode pemilihan perilaku agen game dapat dikembangkan dengan memperhatikan pola permainan lawan. DAFTAR REFERENSI Andrade,G.,Ramalho,G., Gomes,A., dan Corruble,V., (2005), Challenge-sensitive Game Balancing: an Evaluation of User Satisfaction, In Proceedings of the 4rd Brazilian Workshop on Computer Games and Digital Entertainment (WJogos05), hal 66-76. Andrade, G., Santana, H., Furtado, A., Leitão, A., dan Ramalho, (2004), G. Online Adaptation of Computer Games Agents: A Reinforcement Learning Approach, In Proceedings of the 3rd Brazilian Workshop on Computer Games and Digital Entertainment, Curitiba. Campbell,M., Hoane,A.J.,Jr. dan Hsu, F.,H.,(2002), Deep Blue, Artificial Intelligence,vol.134,hal.57-83. Franklin, S. dan Graesser, A., (1996) Is it an Agent, or just a Program?: A Taxonomy for Autonomous Agents, Proceedings of the Third International Workshop on Agent Theories, Architectures and Languages, Springer-Verlag. Herik,J., Donkers,J.,dan Spronck,P.,(2005), Opponent modelling and commercial games, Proceedings of the IEEE 2005 Symposium on Computational Intelligence and Games (eds. Graham Kendall and Simon Lucas), hal.15-25. Livingstone, D. dan Charles, D.,(2004), Intelligent interfaces for digital games, Proceedings of the AAAI04 Workshop on Challenges in Game Artificial Intelligence (eds. D. Fu, S. Henke, and J.Orkin), AAAI Press, Menlo Park, CA, hal.6-10. Russell, S. dan Norvig, P.,(2003), Artificial Intelligence : A Modern Approach, Prentice Hall, Pearson Education, Upper Saddle River, NJ, second edition. Schaeffer, J., Culberson, J., Treloar, N., Knight, B., Lu, P. dan Szafron, D., (1992), A world championship Caliber Checkers Program, Artificial Intelligence, vol.53, hal.2-3. Tesauro, G.,(1994),TD-Gammon, a Selfteaching Backgammon Program Achieves Master-Level Play, Neural Computation, The MIT Press, Massachusetts, vol.6(2),hal.215-219.
