Zuma

Aplikasi Algoritma Greedy pada Permainan Zuma

Dalam permainan Zuma, pemain dikatakan menang apabila semua gundu telah dimusnahkan sebelumpangkal rantai gundu mencapai lubang. Jika dilihat sekilas, yang terpenting  dalam  permainan  Zuma  adalah kecepatan dalam memusnahkan gundu.  Anggapan ini  tidak salah. Akan tetapi, hal yang patut jadi perhatiansebenarnya adalah keadaan Zuma meter.

Pada   kenyataannya,   solusi   akhir   yang   dibentuk algoritma greedy tidak selalu merupakan solusioptimal. Hal ini terjadi karena algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusiyang ada, tetapi hanya pada solusi yang terbaik relatif terhadap fungsi seleksi.

Walaupun demikian, algoritma greedy sangat cocok digunakan dalam menghasilkan solusi hampiran(approximation). Strategi  penggunaan algoritma  greedy tidak  hanya  satu,  namun  bisa  sangat  banyak.  Fungsiseleksi   yang   digunakan   pun   berbeda-beda.   Karena terdapat beberapa fungsi seleksi yang berbeda, kita harusjeli dalam memilih fungsi yang tepat jika kita ingin algoritma menghasilkan solusi yang lebih mendekati optimaldibanding fungsi lainnya.

Strategi Greedy by Time adalah bagaimana memusnahkan gundu secepat-cepatnya. Pemusnahan gundu akanmemberikan poin standar. Logikanya walaupun poin yang didapatkan tidak terlalu banyak tetapi jika cepat makaZuma meter akan cepat penuh.

Pada  setiap  langkah,  sistem  akan  mencatat  jumlah setiap rangkaian gundu sewarna dan letaknya berurutanserta  letak  gundu-gundu  istimewa.  Rangkaian  di  sini berarti dua atau lebih gundu. Rangkaian sewarna gundu tembakan   yang   memiliki   gundu   istimewa   memiliki prioritas  yang  lebih  tinggi  dibanding  yang  berjumlahpaling banyak. Sedang gundu tunggal, gundu yang tidak berdekatan dengan gundu yang sewarna dengannya,memiliki prioritas terendah.

Gundu istimewa juga memiliki proritas. Gundu bom memiliki   prioritas   dibanding   ketiga   gundu   istimewa lainnya karena mampu memusnahkan gundu dalam jumlah besar. Gundu pause dan gundu mundur memilikiprioritas yang sama karena sama-sama memberikan waktu ekstra untuk sistem. Gundu arah tidak dipedulikan karenatidak memiliki keuntungan bagi sistem (sistem mampu mencatat posisi gundu dengan tepat).

Strategi Greedy by Stealing Point and Coin adalah bagaimana memusnahkan gundu dengan memperhatikanletak koin emas. Penembakan koin emas  akan  memberikan poin  bonus  yang  cukup besar. Dengan banyakmenembak koin emas, Zuma meter akan penuh  dengan  cepat.  Stealing point  di  sini  maksudnya mencuri  poin dari  menciptakan  pemusnahan  beruntun yang terjadi langsung setelah pemusnahan dari gundu tembakan(consecutive). Contohnya dalam suatu bagian terdapat 2 gundu merah, 2 gundu hijau, 1 gundu merah, berurutan.Jika gundu hijau dimusnahkan, gundu-gundu merah di kedua sisinya akan turut musnah karena terjadi tabrakan 3atau lebih gundu berwarna sama. Pemusnahan karena tabrakan juga menyumbang poin.

Pada  setiap  langkah,  sistem  akan  mencatat  jumlah setiap rangkaian gundu sewarna dan letaknyaberurutan dan mana yang akan menciptakan pemusnahan beruntun dan mana yang mengandung gundu bom. Gunduistimewa selain gundu bom dianggap gundu biasa karena tidak memberikan keuntungan yang besar bagi sistem.Selain itu,  sistem juga  akan  mencatat  letak  koin  emas.  Perlu menjadi catatan bahwa koin ini muncul sesekalisehingga letak koin emas bisa null.

Koin emas memiliki prioritas tertinggi, disusul oleh rangkaian yang mengandung gundu bom. Prioritasselanjutnya dihitung berdasar jumlah gundu dalam rangkaian. Jika suatu rangkaian bisa menciptakan pemusnahanberuntun, jumlah rangkaiannya dihitung dari jumlah rangkaian sebenarnya ditambah jumlah gundu di sisi kanan dankiri yang berwarna sama yang bisa musnah setelahnya. Gundu tunggal memiliki prioritas terendah.

Pada awal permainan :

Dengan memakai greedy by time, sistem akan langsung memuntahkan   tembakan   ke   rangkaian   gundu  yang memiliki jumlah paling banyak karena gundu-gundu istimewa biasanya belum keluar. Zuma meter masih terisisedikit.

Dengan memakai greedy by stealing point and coin, sistem  bereaksi  hampir  sama  seperti  greedy  by  timekarena gundu bom dan koin belum muncul. Perbedaannya hanyalah jika ada  rangkaian yang terjepit diantara duarangkaian panjang gundu yang sewarna di sisi kanan dan kirinya maka rangkaian yang terjepit itu akan ditembak terlebih dahulu.

Pada tengah permainan :

Dengan greedy by time, tujuan tembakan yang utama adalah rangkaian yang memiliki gundu-gundu istimewa, disusul kemudian rangkaian yang panjang. Gundu-gundu tunggal terpinggirkan bahkan yang berada didekat lubang dibiarkan saja. Hal ini memungkinkan sistem kalah karena ada gundu yang tidak langsung ditanganidan berakhir di lubang. Zuma meter terisi sedikit demi sedikit.

Dengan greedy by stealing point and coin, sistem mengutamakan penembakan koin. Jika koin berada dalamjangkauan tembak, koin tersebut langsung ditembak. Dengan begini, isi dari Zuma meter bertambah lumayanbanyak. Jika koin tidak berada dalam jangkauan tembak, sistem akan mencari rangkaian yang mengandung gundubom. Ilustrasi letak koin dapat dilihat pada gambar (4) di atas.   Jika   tidak   ada   juga,   sistem   akan   menembakrangkaian yang mampu menciptakan pemusnahan beruntun. Contoh rangkaian yang mampu menciptakanpemusnahan beruntun jika ditembak terdapat pada gambar (5).  Pemusnahan  beruntun  mengisi  Zuma  meter  lebih cepat dari pemusnahan biasa atau tunggal. Kelemahannya sama dengan greedy by time, yaitu gundu-gundu tunggalyang berada di dekat lubang terpinggirkan dan berpotensi membuat sistem kalah karena jatuh ke dalam lubangtanpa sempat ditangani.

Setelah Zuma meter terisi penuh :

Dengan algoritma greedy by time, tugas sistem tinggal memusnahkan  gundu-gundu  yang   tersisa.   Seharusnya tidak  ada  masalah  yang  berarti  selain  adanya  gundu tunggal yang berada di dekat lubang yangmasih jadi prioritas terakhir dan belum ditangani.

Dengan algoritma greedy by stealing point and coin, sistem  akan  lebih  cepat  menyelesaikan permainandari greedy  by  time  karena  berpikir  selangkah  ke  depan. Gundu   tunggal   juga   menjadi   masalah.   Namun  jika terdapat  dua  atau  lebih  gundu  sewarna  gundu  tunggal yang hanya dipisahkan oleh suatu rangkaian gundu,hal ini tidak lagi menjadi masalah karena sistem akan menembak rangkaian gundu yang menjadi pemisah keduanya.Lalu gundu tunggal akan bertabrakan dengan rangkaian gundu sewarna dan akhirnya ikut musnah.

Kedua contoh strategi pemenuhan Zuma meter dengan pendekatan greedy memberikan hasil yang berbeda.Dari studi kasus diatas terlihat algoritma mana yang memberikan hasil lebih optimal. Algoritma greedy by stealingpoint and coin memberikan hasil yang lebih optimal dibanding algoritma greedy by time.

Walaupun  permainan  Zuma  mengandalkan  strategi yang jitu, penggunaan kedua algoritma greedy di atas terkadang tidak memberikan hasil yang diinginkan. Contohnya saja sistem yang bisa saja kalah karena tidakmempedulikan  gundu  tunggal  yang  berada  di  dekat lubang. Seharusnya gundu yang berada di dekat lubang jugaturut mendapat penanganan khusus.

Agar permainan berjalan lebih mulus, diperlukan penanganan gundu berdasar kedekatan posisinya dengan lubang serta mekanisme setelah Zuma meter terisi penuh. Perlakuan sebelum Zuma meter terisi penuh dan sesudahZuma  meter  terisi  penuh  seharusnya  sedikit  berbeda karena obyektifnya bukanlah pemenuhan Zuma meter lagi,melainkan pemusnahan untuk menghabiskan gundu yang tersisa.

Pemecahan masalah optimisasi dapat diselesaikan dengan  cukup  baik  melalui  pendekatan  greedy.  Hasilsolusi   yang   didapatkan   cenderung   mendekati   hasil optimal. Keampuhan algoritma greedy terletak padapemilihan fungsi seleksi yang tepat, dari sekian banyak fungsi seleksi yang bisa digunakan.

Pengimplementasian  algoritma  greedy  sangat sederhana. Jika sudah memiliki gambaran akan suatupenyelesaian, penentuan elemen pun sangat mudah. Agar mendapat hasil yang lebih baik, sebelumnya pikirkandahulu segala kondisi yang mungkin dihadapi dengan matang.  Hal  ini  bertujuan  untuk  menghindarikecerobohan-kecerobohan   kecil   yang   bisa   membuat sistem kecolongan. Meskipun demikian, kita tidak bisamemutuskan suatu cara benar-benar akan memberikan hasil paling optimal tanpa melalui perhitungan secaramatematis. Untuk kasus sederhana seperti pemenuhan Zuma  meter  pada  permainan Zuma  yang  cukup  diberihasil aproksimasi, penggunaan algoritma greedy sudah cukup memenuhi target.