Algoritma Game Tetris
Algoritma
yang digunakan dalam permainan tetris dan akan kami bahas dalam makalah ini
adalah algoritma yang menggunakan konsep-konsep algoritma greedy dan algoritma
brute force. Algoritma greedy banyak digunakan dalam memecahkan masalah
optimasi, algoritma ini juga cukup sederhana dan sesuai dengan tujuan yang ada.
Algoritma Greedy
memecahkan masalah langkah per langkah, pada setiap langkah:
1.
mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa
memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
2.
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 pada tetris untuk mendapatkan susunan balok dengan posisi akhir
yang paling baik, yaitu membentuk suatu baris penuh sehingga baris dapat
terhapus. Algoritma ini menggunakan prinsip mencari langkah solusi yang paling
manguntungkan yaitu algoritma greedy.
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:
1. Membentuk satu atau
lebih baris paling penuh
2. Membentuk satu atau
lebih baris paling mendekati penuh
3. Tidak membentuk ruang
kosong pada susunan tumpukan balok
4. Balok dapat masuk ke
dalam susunan tumpukan balok paling dalam
Algoritma
yang kami jelaskan akan mencari penempatan balok yang turun pada posisi yang
paling tepat dan sesuai dengan keuntungan diatas diantara susunan tumpukan
balok. Pencarian solusi akan dilakukan dengan pendekatan algoritma 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.
Apabila ada masalah seperti diatas, maka algoritma akan mencari solusi
yang paling tepat, yaitu yang paling menguntungkan untuk penempatan balok yang
turun diantara susunan balok yang sudah turun sebelumnya. Pencarian dicari dari
kiri ke kanan untuk sisi yang pertama kali keluar yaitu secara algoritma brute
force.
Setelah algoritma ini mancari solusi sampai paling kanan, maka
algoritma ini akan menyimpan satu solusi terbaik yang ada. Apabila ada beberapa
solusi yang sama baiknya, maka akan diambil penempatan paling kiri, seperti
dilihat dibawah ini.
Setelah menyimpan solusi terbaik untuk sisi tersebut, lalu algoritma
ini akan mencari solusi optimum untuk sisi berikutnya. Seperti yang tampak pada
gambar di bawah, algoritma ini seakan-akan memutar balok untuk memulai
pencarian sisi berikutnya. Sisi berikut yang kami maksud disini adalah sisi
dimana balok yang sedang jatuh diputar 90o searah jarum jam.
Setelah itu, algoritma ini akan menyimpan solusi dari setiap sisi
berikutnya, seperti terlihat pada tiga gambar berikut ini.
Diantara
setiap solusi sisi balok, dicari solusi yang paling menguntungkan sesuai skala
prioritas di atas. Dan balok akan ditempatkan pada ruang tersebut. Seperti
terlihat pada gambar berikut, algoritma ini telah menemukan solusi terbaik, dan
menempatkan balok pada ruang tersebut.
