ANALISA GAME
Aplikasi Permainan Agar.io Menggunakan Algoritma Greedy
Agar.io merupakan
game online multiplayer berbasis web base dengan gameplay dimana player
bertahan pada area permainan dan menjadikan dirinya menjadi lebih besar dengan
memakan makanan atau lawan yang lebih kecil pada area permainan, yang dapat
dimainkan hanya dengan bermodalkan koneksi internet dan aplikasi browser yang
telah terinstall addons flash player. Tidak hanya media komputer, setalah
semakin populer Agar.io kini dapat dimainkan pada smartphone juga.
Sampai
saat ini Agar.io sendiri memiliki 3 mode permainan yang dapat dimainkan :
- FFA (Free-For-All) Mode : Disini Kita Bisa Bermain Menggunakan Skin. Misismu Adalah Menjadi No 1 di leaderboards
- Teams Mode : Di Mode ini Ada Tiga Warna Sel : Biru, Merah Dan Hijau Ketiga Tim Tersebut Harus Bersaing Untuk Mendominasi Map Tersebut, Bekerjasamalah Untuk Mendapat Hasli Yang Terbaik
- Experimental Mode : Di Sini Kita Tetap bisa menggunakan Skin. Di Tengah Map Ada Cell Berwarna Coklat Besar yang Disebut Mother Cell (Sel Induk)
Algoritma greedy merupakan jenis algoritma yang menggunakan
pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada
setiap langkahnya. Algoritma greedy adalah algoritma yang besifat heuristik,
mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang
cukup baik. Meskipun tidak selalu mendapatkan solusi terbaik (optimum),
algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga
algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat
meskipun tidak optimal seperti sistem real-time atau game.
Bisa dikatakan bahwa algoritma ini merupakan algoritma yang
digunakan pada game Agar.io, karea jika dilihat dari gameplaynya bahwa player
harus bertahan hidup dengan tidak dimakan oleh lawan yang lebih besar dan
menjadikan dirinya makin besar pada arena permainan dengan cara mamakan makanan
yang ada dan memakan lawan lain yang lebih kecil pada arena permainan. Dengan
kata lain game ini sangat memenuhi Prinsip utama dari algoritma greedy yang
berbunyi “ take what you can get now! ”
Aplikasi Permainan Battleship Menggunakan Algoritma
Backtracking Dengan Breadth First Search
Battleship merupakan permainan berjenis board
game. Cara memainkannya dengan menembakan
kotak-kotak yang kosong
pada papan permainan sampai
salah satu menang
antara pemain atau
komputer (AI). Permainan battleship
ini berbasis komputer
memiliki kecerdasan buatan
atau Artificial Intelligence (AI) sehingga permainan ini tidak
membutuhkan dua orang untuk bermain.
Selain juga tidak memerlukan dua orang untuk bermain, pemain juga dapat
menimati permainan battleship ini dengan kecerdasan buatan (AI) yang
dilengkapi dengan algoritma
atau metode.
Metode yang
diambil sebagai pembuatan permainan
battleship ini adalah
algoritma backtracking dengan menggunakan metode BFS. Tujuan dari
pembuatan aplikasi ini
adalah agar pemain
yang ingin memainkan permainan
battleship ini dapat
menjalankan aplikasi ini
dengan algoritma yang sudah dilengkapi dengan pencarian solusi yang
dibuat. Gambaran permainan
battleship ini seperti permainan yang
saling menghancurkan, tetapi yang
tema yang diambil dalam pembuatan
aplikasi ini adalah apakah pencarian solusi
dengan menggunakan algoritma
backtracking metode BFS
merupakan metode atau algoritma
yang sangat efisien dalam aplikasi permainan battleship ini.
Aplikasi permainan
battleship ini dibuat
dengan menggunakan metode waterfall dengan
pemodelan Unified Modeling
Language (UML). Serta menerapkan algoritma
backtracking metode BFS. Aplikasi
menggunakan penerapan
pencarian solusi yang digunakan
dengan menggunakan algoritma backtracking. Aplikasi ini dapat
digunakan sebagai media hiburan. Selain sebagai media hiburan,
aplikasi ini pun
dapat dikembangkan dengan
fitur yang lebih menarik lagi.
Aplikasi Algoritma Greedy pada Permainan Tower Defense
Permainan Tower Defense (TD)
merupakan permainan strategi pengaturan tower (bangunan, senjata, naga,
tanaman, dan lain-lain) yang bertujuan menghentikan musuh yang akan melintas.
Tower ini akan menembaki musuh dalam radiusnya. Tower memiliki beberapa tipe
dan level dengan kemampuan, biaya pembelian, biaya penggunaan, dan biaya
upgrade yang berbeda. Untuk setiap musuh yang berhasil dikalahkan, pemain akan
mendapatkan uang untuk meng-upgrade towers. Strategi dalam permainan ini
mencakup pemilihan tower yang akan di-upgrade.
Permainan ini biasanya memiliki misi
untuk meminimalkan jumlah musuh yang lolos atau menjaga sejumlah barang. Pemain
dianggap menang jika jumlah musuh yang lolos kurang dari batas yang ditentukan
atau barang yang dijaga masih ada.
Komputer bermain menggunakan
algoritma greedy, sedangkan manusia bermain menggunakan akal dan intuisinya.
Program yang dibuat harus memungkinkan melakukan permainan TD dengan pemainnya
adalah: 1. User (manusia) lawan komputer 2. Komputer dengan dirinya
sendiri.
Jika pemainnya adalah user (manusia)
versus komputer, maka manusia akan mengatur kemampuan sejumlah tower yang ada,
dan komputer akan mengaplikasikan algoritma greedy untuk melakukan penyusunan
rombongan musuh (wave) agar semakin banyak musuh yang dapat lolos. Penyusunan
rombongan musuh dibatasi oleh jumlah uang yang tersedia. Penyusunan wave ini
akan dilakukan setelah tower selesai diatur.
Jika pemain adalah komputer versus
dirinya sendiri, maka pihak komputer pertama mengaplikasikan algoritma
greedy untuk penyusunan wave, dan pihak
komputer kedua mengaplikasikan algoritma greedy untuk pengaturan kemampuan
tower. Pengaturan tower akan dilakukan setelah hasil penyusunan wave
diberikan.
Anda harus merancang minimal
masing-masing dua buah strategi greedy yang berbeda (greedy by X dan greedy by
Y) untuk penyusunan rombongan musuh (wave) dan strategi pengaturan kemampuan
tower. Deskripsi algoritma greedy tersebut harus dapat memperlihatkan properti
algoritmanya, yaitu himpunan kandidiat, himpunan solusi, fungsi seleksi, fungsi
kelayakan, dan fungis obyektif.
ALGORITMA KNUTH MORRIS PRATT PADA GAME HANACARAKA
Hanacaraka adalah game ber-genre word
puzzle game yang dapat digunakan sebagai media pengenalan aksara jawa bagi
orang umum dengan implementasi algoritma Knuth Morris Pratt pada pencocokan
string-nya yang dapat dimainkan pada platform mobile berbasis OS Android.
Dalam game ini, terdapat soal yang ditulis
dengan aksara jawa dan juga gambar sebagai pendukung, kemudian pemain diminta
untuk menerjemahkan aksara jawa tersebut ke dalam aksara latin kemudian digabungkan
dengan gambar yang ada untuk mengetahui jawaban dari soal tersebut. Setelah itu
menuliskan jawabannya ke dalam field yang sudah disediakan.
Algoritma yang digunakan untuk pencocokan
string pada game Hanacaraka adalah
menggunakan algoritma Knuth Morris Pratt atau sering disingkat menjadi
algoritma KMP. Algoritma Kunth Morris Pratt sendiri adalah algoritma yang
dikembangkan secara terpisah oleh D. E. Knuth pada tahun 1967, dan J.H Morris
bersama V. R. Pratt pada tahun 1966, namun keduanya mempublikasikannya secara
bersamaan pada tahun 1977 (Munir, 2007).
Tidak seperti algoritma Brute Force yang
mencocokkan string dengan melakukan pengecekan dan melakukan pergeseran setiap
satu karakter, pada algoritma Knuth Morris Pratt informasi ketidak cocokan
pattern dengan teks disimpan untuk menentukan jumlah pergeseran. Sehingga
algoritma Knuth Morris Pratt melakukan pergeseran lebih jauh sesuai dengan
informasi yang disimpan, yang menyebabkan waktu pencarian dapat dikurangi
secara signifikan.
Selain itu, dari penyimpanan informasi
pada pencocokan string yang dilakukan algoritma Knuth Morris Pratt dapat diambil
keuntungan lain. Yaitu dari informasi yang disimpan dapat digunakan untuk
menentukan berapa persen kedekatan string yang akan dicocokkan dengan pattern
yang ada. Dan hal ini juga yang diimplementasikan pada game Hanacaraka.
Sehingga apabila pemain salah dalam memasukkan jawaban, maka akan dilihat berapa
persen kesalahannya. Apabila kesalahan nya kurang dari 30 persen maka status
jawabanyya bukan “salah”, melainkan “hampir benar” dan nyawa yang diberikan
kepada pemain tidak berkurang.
PENGGUNAAN ALGORITMA GREEDY PADA ARTIFICIAL INTELIGENCE DALAM PERMAINAN
DEFENCE OF THE ANCIENTS
Defence of the Ancients (atau
disingkat DotA) adalah sebuah peta buatan untuk permainan komputer buatan
Blizzard berjudul Warcraft III : Frozen Throne, yang dibuat berdasarkan map
“Aeon of Strife”dari permainan Blizzard lainnya, Starcraft. Tujuan utama
permainan ini adalah untuk menghancurkan “Ancient” musuh, sebuah struktur yang
dijaga ketat di pojok kiri bawah atau
(yang satu untuk sisi sendiri dan yang satu lagi untuk sisi musuh).
Kedua sisi yang bertarung adalah The Sentinel dan The Scourge. Permainan dapat
menggunakan tokoh kuat yang disebut pahlawan dan dibantu oleh pasukan sekutu
dan anak buah petarung yang dikontrol oleh Artificial Inteligence. Seperti
dalam permainan peran lainnya, pemain dapat meningkatkan level tokoh pahlawan
mereka dan menggunakan emas untuk membeli perlengkapan selama permainan, DotA
dapat dimainkan dengan sistem pemain lawan pemain dan pemain lawan Artificial
Inteligence.
Pahlawan dapat membeli senjata untuk
digunakan dalam pertempuran. AI dalam melakukan pembelian barang menggunakan
algoritma Greedy. Dengan uang yang dimiliki oleh AI, AI akan membeli senjata
termurah yang dapat dibeli dengan uang yang dimilikinya, akan tetapi pembelian
barang dan senjata tidak sembarangan karena setiap AI sudah memiliki daftar
senjata yang harus dibeli untuk pahlawan yang digunakannya.
Dalam menghancurkan anak buah
petarung, AI menggunakan algoritma Greedy. AI akan menghancurkan anak buah
petarung yang memiliki darah tersedikit dan berada di sekitarnya. Dalam
melakukan penghancuran anak buah petarung ini, AI memiliki tiga perhitungan
prioritas yaitu:
·
Anak
buah petarung teman.
·
Anak
buah petarung musuh.
·
Anak
buah petarung terdekat.
Dalam penggunaan algoritma Greedy
dalam hal ini akan tepat sekali jika digunakan bersama algoritma Divide and
Conquer. Dengan menggunakan algoritma Divide and Conquer akan sangat memudahkan
AI untuk mendeteksi anak buah petarung yang sekarat. Sehingga kebutuhan akan
komputasi sistem permainan yang cepat pun akan tercapai.
Dalam memperhitungkan kapan menyerang
pahlawan musuh, AI juga akan menggunakan algoritma Greedy. Selama AI berada
dalam posisi menguntungkan, yaitu:
1. Pahlawan AI memiliki jarak serang
yang lebih jauh dibandingkan dengan jarak serang pahlawan
musuh.
2. Pahlawan AI memiliki darah yang
lebih banyak dibandingkan pahlawan musuh.
3. Pahlawan AI memiliki tingkatan
yang lebih tinggi dibanding pahlawan musuh.
4. Pahlawan musuh berada di wilayah
kekuasaan AI.
5. Pahlawan musuh menyerang pahlawan
AI.
6. Pahlawan AI memiliki persedian
obat-obatan.
7. Dan kondisi lainnya yang
menguntungkan bagi AI.
Kelebihan dari algoritma Greedy dalam
hal ini, dengan kondisi awal yang jelas, AI menjadi lebih hati-hati dalam
menyerang dan bertahan. Dan kekurangannya adalah AI tidak terlalu memikirkan
keadaan setelah aksi yang dilakukannya, misal AI menyerang pahlawan musuh, AI
akan terus menyerang walaupun pahlawan musuh dibantu oleh anak buah
petarungnya. Sehingga menyebabkan AI akan cepat memasuki kondisi yang tidak
menguntungkan baginya.
Kekurangan lainnya adalah serangan
yang dilakukan tidak menghancurkan pahlawan musuh. Karena pahlawan AI menyerang
ketika berada pada kondisi yang menguntungkannya bukan ketika pahlawan musuh
tidak menguntungkan. Tujuan penyerangan yang dilakukan oleh AI untuk
menghancurkan tetapi terkadang tidak tercapai karena serangan yang lemah, tidak
adanya skill yang dapat membantu dalam penyerangan, atau pahlawan musuh berada
dalam kondisi yang baik atau tidak sekarat.
Kekurangan algoritma Greedy yang
digunakan dalam usaha kabur adalah AI tidak memikirkan apa saja yang akan
terjadi di masa mendatang, jadi ketika sedang berada di posisi yang tidak menguntungkan
bagi pahlawannya maka AI akan kabur walaupun terkadang pahlawannya dapat
menghancurkan bangunan atau pahlawan musuh dengan kondisi pahlawannya yang
tidak menguntungkan tersebut. Tetapi di kasus lain, algoritma Greedy ini
memberikan solusi terbaik yaitu menghindarkan pahlawan AI untuk dihancurkan.
Dalam penggunaan skill pahlawan, AI
juga menggunakan algoritma Greedy. Jika terdapat banyak anak buah petarung dan
pahlawan musuh dalam satu daerah AI akan otomatis mengeluarkan skill area yang
dapat memberikan kerusakan ke banyak unit. Keuntungannya, AI mendapatkan banyak
uang dari banyaknya anak buah petarung yang hancur dan sekaligus memberikan
kerusakan kepada pahlawan musuh. Kekurangannya karena hanya menginginkan uang,
biasanya serangan ini tidak dilanjutkan dengan serangan lainnya yang bersifat
serius untuk menghancurkan pahlawan musuh (jika berada pada posisi yang tidak
menguntungkan bagi AI).
Dalam melindungi bangunannya AI
memiliki dua cara yaitu menggunakan Glyph yang menyebabkan bangunan menjadi
kebal dan mendatangi bangunan dan melindunginya secara langsung. Beberapa
keuntungan dalam penggunaan algoritma Greedy di dalam perlindungan bangunan ini
adalah AI sangat protektif dengan bangunannya. Tetapi tentu saja terdapat
kekurangan yang sangat mendasar dari algoritma ini ketika digunakan dalam
perlindungan bangunan.
Aliyanto, Arif.,
Ishak, Novendo, Felix. 2013. Aplikasi Permainan Battleship Menggunakan Algoritma Runut-Balik Dengan Breadth First Search.Semantik,Semarang.
Zaky,
Mahan, Abi.2015.Implementasi Algoritma Knuth Morris Pratt pada Perancangan Game
Hanacaraka.
Nevada,
Gurun.2011.Penerapan Algoritma Greedy pada
Artificial Inteligence dalam
Permainan Defence of the Ancient.
http://luckybinuntung.b