Pembahasan Game 8 Puzzle ~ Dey's

8 puzzle merupakan salah satu game yang diimplementasi dari Artificial Intelegence /Kecerdasan Buatan. Dalam proses penyelesaian game ini banyak terdapat algoritma- algoritma pencarian yang dapat diterapkan. Permasalahan pada game 8 puzzle adalah bagaimana cara agar dapat menyusun petak- petak puzzle sesuai dengan urutann yang sudah di acak letaknya.

Untuk menyelesaikan permasalahan 8 puzzle kita menggunakan metode Heuristic Search.

Ada 2 cara untuk menentukan permasalahan pada game 8 puzzle yaitu:

1.) Jumlah dari petak- petak yang salah tempat.

2.) Total jarak Manhattan (jumlah petak- petak dari lokasi yang seharusnya untuk setiap tile).

Mari kita coba cara yang pertama dulu.

1.) Jumlah dari petak- petak yang salah tempat.

Pada gamabar tersebut, banyak petak yang salah tempat ada 6 buah.

Kita mulai menyelesaikan puzzle ini dengan patokan pada petak- petak kosong, jika kita lihat ada 3 pilihan yang dapat kita lakukan.

a.) Jika UP petak 7 jika kita hitung jumlah petak yang salah tempat = 7 buah.

b.) Jika DOWN petak 1 jumlah petak yang salah tempat = 7 buah.

c.) Jika LEFT petak 4 jumlah petak yang salah tempat = 5 buah.

Pilihanan yang kita ambil yaitu langkah yang kesalahannya kecil yang di ambil.

Langkah selanjutnya ada 3 kemungkinan yang dapat kita ambil.

a.) Jika DOWN petak 8 ,maka jumlah petak yang salah tempat = 5 buah.

b.) Jika UP petak 6 ,maka jumlah petak yang salah tempat = 5 buah.

c.) Jika LEFT petak 3 ,maka jumlah petak yang salah tempat = 5 buah.

Karena semuanya memiliki jumlah salah yang sama ,maka kita bebas memilih mana saja ,disini kita pilih petak yang a kita pindahkan. Sehingga posisi menjadi.

Kemudian ada 2 kemungkinan yang dapat kita lakukan.

a.) Jika RIGHT petak 1 ,maka jumlah petak yang salah tempat = 6 buah.

b.) Jika LEFT petak 2 ,maka jumlah petak yang salah tempat = 4 buah.

Kita pilih yang paling kecil yaitu pilihan b. Sehingga puzzle menjadi.

Kemudian Kita pindahkan petak 3 keatas maka = 3 kesalahannya.

Kembali muncul pilihan.

a.) Jika RIGHT petak 8 ,maka jumlah petak yang salah tempat = 3 buah.

b.) Jika UP petak 5 ,maka jumlah petak yang salah tempat = 3 buah.

Karena semuanya memiliki jumlah salah yang sama ,maka kita bebas memilih mana saja ,disini kita pilih petak yang a kita pindahkan. Sehingga menjadi.

Kemudian ada 2 kemungkinan yang dapat kita lakukan.

a.) Jika LEFT petak 4 ,maka jumlah petak yang salah tempat = 4 buah.

b.) Jika UP petak 6 ,maka jumlah petak yang salah tempat = 3 buah.

Kita ambil pilihan yang b ,Sehingga menjadi.

Kemudian ada 2 kemungkinan yang dapat kita lakukan.

a.) Jika LEFT petak 5 ,maka jumlah petak yang salah tempat = 3 buah.

b.) Jika RIGHT petak 7 ,maka jumlah petak yang salah tempat = 4 buah.

Maka kita ambil yang a ,Sehingga menjadi.

Tidak ada pilihan lagi jadi kita DOWN petak 8 , maka menjadi.

Lalu terdapat 2 pilihan yaitu :

a.) Jika DOWN petak 3 ,maka jumlah petak yang salah tempat = 2 buah.

b.) Jika RIGHT petak 6 ,maka jumlah petak yang salah tempat = 4 buah.

Kita pilih yang a ,Sehingga menjadi.

Kemudian Kita pindahkan petak 5 keatas maka = 1 kesalahannya.

Dan yang terakhir LEFT petak 8 ,sehingga semua petak- petak tidak memiliki kesalahan.

Mari kIta coba cara yang ke 2 yaitu dengan menentukan total jarak Manhattan (jumlah petak- petak dari lokasi yang seharusnya untuk setiap tile). Hampir sama dengan cara yang ke 2 tetapi ini dengan menentukan petak ke lokasi yang benar. Lihat gambar dibwah ini.