Berbagi Ilmu: Algoritma Yang Digunakan Untuk Membuat Game
Algoritma yang Digunakan dalam Membuat Game
Algoritma Greedy
Algoritma greedy merupakan jenis algoritma yang menggunakan
pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada
setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah local
maximum. Pada kebanyakan kasus, algoritma greedy tidak akan menghasilkan
solusi paling optimal, begitupun algoritma greedy biasanya memberikan solusi
yang mendekati nilai optimum dalam waktu yang cukup cepat.
Algoritma greedy merupakan 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.
Dari
impementasi yang kita lakukan, dapat dilihat bagaimana algoritma greedy
memiliki beberapa fungsionalitas dasar, yaitu:
- Fungsi
untuk melakukan penelusuran masalah.
- Fungsi
untuk memilih local maximum dari pilihan-pilihan yang ada
tiap langkahnya.
- Fungsi
untuk mengisikan nilai local maximum ke solusi
keseluruhan.
- Fungsi
yang menentukan apakah solusi telah didapatkan.
Algoritma
Minimax
Algoritma minimax merupakan basis dari semua permainan
berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah
sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia
sekalipun. Pada algoritma minimax, pengecekan akan seluruh kemungkinan yang ada
sampai akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon
permainan yang berisi semua kemungkinan tersebut. Tentunya dibutuhkan resource
yang berskala besar untuk menangani komputasi pencarian pohon solusi tersebut
berhubung kombinasi kemungkinan untuk sebuah permainan catur pada setiap geraknya
sangat banyak sekali.
Keuntungan
yang didapat dengan menggunakan algoritma minimax yaitu algoritma minimax mampu
menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan
yang terbaik karena algoritma minimax ini bekerja secara rekursif dengan
mencari langkah yang akan membuat lawan mengalami kerugian minimum. Semua
strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini
berarti, pada langkah pertama komputer akan menganalisis seluruh pohon
permainan. Dan untuk setiap langkahnya, komputer akan memilih langkah yang
paling membuat lawan mendapatkan keuntungan minimum, dan yang paling membuat
komputer itu sendiri mendapatkan keuntungan maksimum. Dalam penentuan keputusan
tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan
yang akan diperoleh jika langkah tersebut dipilih.
Untuk itulah
disini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagai
nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah
tersebut dipilih. Biasanya pada permainan tic tac toe ini digunakan nilai
1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang, seri, dan kalah.
Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana dari
pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut
adalah simpul dengan nilai heuristic yang akan menuntun permainan ke hasil
akhir yang menguntungkan bagi komputer.
Referensi:
EmoticonEmoticon