IMPLEMENTASI ALGORITMA HILL CLIMBING PADA GAME PACMAN

Algoritma Hill Climbing 

Berikut adalah algoritma dari Simple Hill Climbing :

  1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagaikeadaan awal.
  2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atausampai tidak ada operator baru yang akan diaplikasikan pada keadaansekarang :

a)         Cari operator yang belum pernah digunakan; gunakan operator iniuntuk mendapatkan keadaan yang baru.

b)        Evaluasi keadaan baru tersebut.

1)        Jika keadaan baru merupakan tujuan, keluar.

2)        Jika bukan tujuan, namun nilainya lebih baik daripada keadaans ekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.

3)        Jika keadaan baru tidak lebih baik daripada keadaan sekarang,maka lanjutkan iterasi.

Pada simple hill climbing ini, ada 3 masalah yang mungkin terjadi, yaitu :

1)        Algoritma akan berhenti kalau mencapai nilai optimum lokal.

2)        Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi.

3)        Tidak diijinkan untuk melihat satupun langkah sebelumnya.

Penjelasan Game Pacman

 

 

Pacman adalah sebuah permainan video arkade yang cukup terkenal. Cara bermainnya mudah yaitu pemain (pacman) diharuskan memakan makanan (berbentuk titik-titik kecil) dan sebuah bulatan besar (energizer) sampai habis di dalam sebuah labirin yang berliku-liku. Tidak hanya menghabiskan makanan tersebut, pemain juga harus menghindari 4 ‘hantu’ yang berkeliaran secara random untuk menangkap pemain. Jika pemain bertemu dengan hantu-hantu tersebut maka pemain dinyatakan gagal dan harus mengulangi dari awal lagi. Tetapi pemain bisa mengalahkan hantu tersebut dengan memakan energizer yang terdapat di pojokkan labirin. Jika pemain memakan titik besar tersebut, maka para hantu akan ketakutan dan berusaha menjauh dari pemain[1]. Dalam hal ini pemain bisa memakan hantu tersebut dan mendapatkan bonus yang besar, tetapi para hantu yang termakan tidak mati begitu saja, mereka kembali ke posisi semula dan kembali mengejar pemain. Pemain dinyatakan menang jika semua makanan habis tak tersisa dan pemain akan memasuki level berikutnya.

Pergerakan para hantu ini dipengaruhi oleh kecerdasan buatan atau Artificial intelligence (AI), dimana para hantu diberi kecerdasan untuk menentukan langkah dan mengambil keputusan akan bergerak kemana dengan menentukan rute yang paling pendek (minimum), tujuannya adalah menangkap pemain. Setiap hantu harus memiliki pemikiran berbeda dan memiliki kemampuan bekerja sama untuk mengejar pemain, sehingga permainan akan tampak lebih menarik. Persoalan mendekati karakter Pacman ini dapat diselesaikan dengan berbagai macam cara, salah satunya dengan menggunakan algoritma hill climbing.

Untuk melakukan hal ini, kita harus memberikan prioritas yang berbeda-beda pada masing-masing musuh, maka dengan sendirinya dia akan bergerak ke arah yang berbeda.

 

 

 

Cara Kerja Game Pacman 

Kami akan menjelaskan cara kerja dari karakter musuh pacman tersebut dengan memberikan salah satu contoh keadaan dalam permainan pacman. Pada contoh kasus ini diasumsikan bahwa karakter Pacman tidak bergerak (diam saja di tempat), untuk menentukan apakah rute yang dipilih dari hasil algoritma hill climbing merupakan yang paling optimum atau tidak.  

Misal fungsi seleksi gerakkanMusuh diterapkan pada musuh Pacman yang berwarna oranye (gambar yang dilingkari). Posisi karakter musuh oranye berada di sebelah kiri karakter Pacman yang berwarna kuning, maka karakter musuh oranye seharusnya bergerak ke kanan, namun karena adanya dinding yang menghalangi, maka dilakukan pengecekan lagi terhadap perbandingan posisi Y dan didapati posisi karakter musuh oranye berada di sebelah atas karakter Pacman dan tidak ada dinding maupun karakter musuh lain yang menghalangi di atasnya, maka karakter musuh oranye dipindahkan ke atas.

Setelah itu, diterapkan lagi algoritma hill climbing untuk kedua kalinya, posisi karakter oranye sekarang ada di sebelah kiri karakter Pacman dan tidak ada yang menghalangi di sebelah kanannya, jadi karakter musuh bisa bergerak ke kanan.

Setelah bergerak ke kanan, algoritma hill climbing diterapkan lagi dan karakter musuh berada di atas Pacman, maka karakter musuh digerakkan ke bawah sampai bertemu dengan karakter Pacman : jarak yang ditempuh untuk menemukan Pacman adalah jarak yang paling pendek

Untuk kasus ini, algoritma hill climbing menghasilkan solusi yang optimal. Namun sesuai dengan dasar teori, algoritma hill climbing tidak selalu dapat menghasilkan solusi yang optimal karena algoritma hill climbing tidak memeriksa semua kemungkinan.

Contoh kasus berikut adalah kasus lain dari permainan pacman yang ternyata tidak dapat diselesaikan secara optimum oleh algoritma hill climbing seperti contoh kasus pertama di atas, namun solusi yang dihasilkan tidak terlalu buruk..

Pada contoh kasus yang kedua, tetap diasumsikan bahwa karakter Pacman tidak bergerak, selain itu, karakter musuh juga tidak ikut bergerak. Misal fungsi seleksi diterapkan pada karakter musuh warna oranye. Pada gambar 5, karena musuh oranye ada di sebelah kiri posisi Pacman, maka musuh digerakkan ke kanan. 

Setelah digerakkan ke kanan, posisi karakter musuh masih tetap di sebelah kiri Pacman, namun  musuh tidak bisa bergerak ke kanan lagi karena terhalang dinding, setelah dicek, ternyata karakter musuh berada di sebelah atas Pacman, maka sesuai dengan algoritma hill climbing yang telah ditetapkan, karakter musuh digerakkan ke bawah.

Setelah digerakkan ke bawah, posisi karakter musuh oranye ada di sebelah kiri dan di bawah Pacman. Algoritma hill climbing diterapkan sekali lagi dan karakter musuh seharusnya digerakkan ke kanan, namun karena ada karakter musuh lainnya di sana, maka karakter musuh oranye digerakkan ke bawah sekali lagi. 

Pada hasil pergerakan ketiga diatas, karakter oranye bergerak ke bawah sekali lagi, dan dari sini terlihat bahwa rute yang ditempuh oleh karakter musuh oranye sudah tidak mungkin menjadi optimal lagi jika dibandingkan dengan solusi optimal (rute terpendek) seperti contoh kasus pertama.

Solusi yang telah dicapai oleh algoritma hill climbing hingga pada gambar 8 di atas menunjukkan bahwa algoritma hill climbing yang dipilih ternyata tidak selalu menghasilkan solusi yang paling optimal. Namun demikian, karena objektif dari karakter musuh Pacman ini tidak harus selalu bergerak pada rute yang merupakan solusi paling optimum, maka algoritma hill climbing cukup baik untuk mendapatkan hampiran-hampiran yang mendekati solusi paling optimum tersebut.

 

KESIMPULAN

Simpulan dari pembahasan yang telah diuraikan di atas yaitu:

  1. Hill Climbing adalah proses pengujian yang dilakukan dengan menggunakan fungsi heuristik. Hill Climbing terdiri dari dua macam metode yakni Simple Hill Climbing dan Steepest-Ascent Hill Climbing.
  2. Terdapat beberapa langkah dalam algoritma Simple Hill Climbing yaitu:

a)        Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

b)        Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:

  • Cari operator yang belum pernah digunakan; gunakan operator iniuntuk mendapatkan keadaan yang baru.
  • Evaluasi keadaan baru tersebut.

                                                          i.     Jika keadaan baru merupakan tujuan, keluar.

                                                        ii.     Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.

                                                      iii.     Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

  1. 3.         Algoritma Simple Hill Climbing pada umumnya diterapkan dalam masalah Travelling Salesman Problem (TSP) dan bisa diterapkan untuk menyelesaikan game Pacman. 

 

Link Video : https://www.youtube.com/watch?v=MvJXmwDgtG8

 

Kirim Komentar

Nama :
E-mail :
Web : tanpa http://
Komentar :
Verification Code :