1. Game Agar.io
Agar.io sendiri 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.
Penerapan Algoritma
Bisa dikatakan bahwa
algoritma Greedy 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!
”
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.
2.
Game Tetris
Tetris adalah permainan teka-teki yang
disusun dan diprogram oleh sepasang programmer berkebangsaan Rusia.Dalam
permainan tetris, balok-balok tetris berjatuhan ke area permainan dalam waktu
konstan.Balok tetris selalu terdiri dari 4 balok kecil yang membentuk 7 macam
rupa.
Penerapan Algoritma
Pemain dapat mengontrol balok tetris yang
jatuh melalui 4 tombol arah panah untuk menggeser ke kanan atau ke kiri dan
tombol arah panah ke bawah untuk mempercepat jatuhnya balok tetris. Satu
kendali yang lain adalah untuk memutar bentuk balok tetris 90º’. Algoritma yang
gunakan untuk mencari solusi dari permainan tetris adalah algoritma yang
menggunakan konsep-konsep yang ada dalam algoritma Greedy dan Algoritma
BruteForce.Algoritma Greedy merupakan metode yang paling umum digunakan untuk
memecahkan masalah optimasi. Algoritma ini sederhana dan sesuai dengan tujuan
yang ada.
Algoritma
Greedy memecahkan masalah langkah per langkah, pada setiap langkah:
- Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”.
- Berharap bahwa dengan memilih optimum local pada setiap langkah akan berakhir dengan optimum global Brute force adalah sebuah pendekatan yang sesuai (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan.
Algoritma brute force memecahkan
masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious
way). Algoritma yang digunakan untuk mendapatkan susunan tumpukan balok
yang paling baik dengan menempatkan balok ke tempat yang tepat.Algoritma ini
menggunakan prinsip Greedy dalam mencari langkah sollusi yang paling
menguntungkan. Prioritas keuntungan yang tersusun terdiri dari:
- Membentuk satu atau lebih baris paling penuh
- Membentuk satu atau lebih baris paling mendekati penuh
- Tidak membentuk ruang kosong pada susunan tumpukan balok
- Balok dapat masuk ke dalam susunan tumpukan balok paling dalam Algoritma yang kami kemukakan akan mencari penempatan balok yang jatuh ke ruang yang paling tepat sesuai prioritas keuntungan di atas diantara susunan tumpukan balok. Pencarian ini akan dilakukan secara Brute Force. Balok yang jatuh akan dicoba untuk ditempatkan ke ruang di antara susunan tumpukan balok dibawah.
Algoritma ini akan mencari penempatan yang
sesuai dengan prioritas di atas. Pencarian solusi diantara susunan tumpukan
balok akan dilakukan secara Brute Force. Algoritma ini akan
mencari solusi paling menguntungkan untuk setiap sisi balok yang sedang jatuh.
Pencarian solusi untuk setiap sisi dilakukan secar Brute Force.
Apabila pada skala prioritas tertinggi
memiliki lebih dari satu solusi terbaik yang sama, maka diantara solusi
tersebut akan dibandingkan satu sama lain untuk mencari yang paling
menguntungkan dengan standard prioritas selanjutnya, dan begitu selanjutnya.Apabila
pada skala prioritas tertinggi tidak memiliki solusi, maka akan mencari solusi
paling menguntungkan dengan skala prioritas selnjutnya, dan begitu selanjutnya.
Apabila pada skala prioritas tertinggi hanya memiliki satu solusi paling menguntungkan,
maka akan dibandingkan dengan solusi dari hasil pencarian solusi untuk sisi
balok yang lain. Diantara setiap solusi sisi balok, dicari solusi yang paling
menguntungkan sesuai skala prioritas di atas. Dan balok akan ditempatkan pada
ruang tersebut.
3.
Game
Checkers
Permainan checkers
(dalam bahasa Inggris Amerika) atau disebut draughts (dalam bahasa Inggris
British) merupakan permainan yang menggunakan strategi abstrak dimainkan oleh
dua pemain dengan menggunakan langkah diagonal token dan menangkap dengan melompati
token musuh.
Permainan ini
telah dimainkan di Eropa sejak abad ke-16, dikembangkan dari permainan
alquerque. Bentuk yang paling populer dari pemainan p ini adalah
international draughts, yang dimainkan pada papan 10x10. Bentuk yang juga
populer adalah English draughts, yang disebut American checkers, dimainkan
pada papan 8x8.
Penerapan Algoritma
Algoritma Minimax merupakan
algoritma yang digunakan untuk menentukan pilihan agar memperkecil kemungkinan
kehilangan nilai maksimal. Algoitma ini diterpkan dalam permainan yang
melibatkan dua pemain seperti tic tac toe, checkers, go dan permainan yang
menggunakan strategi atau logika lainnya. Hal ini berarti permainan-permainan
tersbut dapa dijelaskan sebagai suatu rangkaian aturan dan
premis.
Algoritma ini mulai
dikembangkan dari teori game zero-sum. Teori ini mendeskripsikan
situasi dimana jika terdapat pemain yang mengalami pendapatan, pemain lain akan
mengalami kehilangan dengan nilai yang sama dari pendapatan tersebut, dan
sebaliknya. Jumlah pendapatan dari pemain yang dikurangi
dengan jumlah kehilangan akan berjumlah nol.
Teori minimax
menyatakan, Untuk setiap dua orang pemain dalam zero-sum game, terdapat nilai V
dari strategi yang dimiliki pemain seperti :
- Stratregi yang ditentukan pemain kedua akan menghasilkan konsekuensi kemungkinan untuk pemain pertama, V
- Strategi yang dutentukan pemain pertama akan menghasilkan konsekuensi kemungkinan untuk pemain pertama, -V
Secara setara, strategi
pemain pertama akan memastikan suatu nilai V tanpa memperdulikan strategi
pemain kedua, dan bersamaan dengan itu pemain kedua akan memastikan dirinya
kehilangan nilai sebesar –V.
Algoritma Minimax merupakan algoritma
dasar pencarian DFS (Depth-First Search) untuk melakukan traversal dalam
pohon. DFS akan mengekspansi simpul paling dalam terlebih dahulu. Setelah
simpul akar dibangkitkan, algoritma ini akan membangkitkan simpul
pada tingkat kedua, yang akan dilanjutkan pada tingkat ketiga, dst. Dalam melakukan
treversal, misalkan dimulai dari suatu simpul i, maka simpul selanjutnya yang
akan dikunjungi adalah simpul tetangga j, yang bertetangga dengan simpul k,
selanjutnya pencarian dimulai lagi secara rekursif dari simpul j.
Ketika telah mencapai simpul m, dimana semua simpul yang bertetangga
dengannya telah dikunjungi, pencarian akan dirunut balik ke simpul
terakhir yang dikunjungi sebelumnya dan mempunyai simpul j yang belum
dikunjungi.
Selanjutnya
pencarian dimulai kembali dari j. Ketika tidak ada lagi simpul yang belum dikunjungi
yang dapat dicapai dari simpul yang telah dikunjungi maka pencarian selesai. Dalam
repersentasi pohon dalam algoritma Minimax, terdapat dua jenis node, yaitu node
min dan node max. Max node akan memilih langkah dengan nilai tertinggi dan min node
akan memilih langkah dengan nilai terendah. Berikut merupakan gambar pohon untuk
algoritma Minimax. Dalam algoritma ini, langkah yang dapat dilakukan pemain ditentukan
oleh langkah pemain lawan sebelumnya. Sebagai contoh pada tabel berikut di
berikan tabel nilai yang memberitahukan hasil dari pilihan.
sumber:
http://chachados.blogspot.com/2012/04/algoritma-pada-game-tetris.html
http://luckybinuntung.blogspot.co.id/2016/05/analisis-algoritma-pada-game-agario.html
sumber:
http://chachados.blogspot.com/2012/04/algoritma-pada-game-tetris.html
http://luckybinuntung.blogspot.co.id/2016/05/analisis-algoritma-pada-game-agario.html
Tidak ada komentar:
Posting Komentar