Ilustrasi Dan Deskripsi Non Heuristics Dengan Algoritma Breadth First Search Dalam Game Sliding Puzzle

Disusun sebagai salah satu tugas untuk memenuhi mata kuliah Kecerdasan Buatan

Disusun oleh:

Amelia Hermayanti (10112659)

Sarah Septia G. P. (10112642)

Kelas : AI-12

Kelompok : 1

PROGRAM STUDI TEKNIK INFORMATIKAFAKULTAS TEKNIK DAN ILMU KOMPUTER

UNIVERSITAS KOMPUTER INDONESIA2015

1. Ilustrasi Algoritma Breadth First Search

Dalam implementasinya pada program, maka setiap node yang telah dikunjungi harus dimasukkan dalam sebuah queue (antrian) sebagai tempat menampung urutan node tahap demi tahap. untuk memperjelas bagaimana alur algoritmanya, berikut penjelasaannya : 

1. Masukkan node akar (root) ke dalam queue2. Ambil node dari awal antrian, lalu cek apakah node tersebut merupakan solusi3. Jika node merupakan solusi, pencarian selesai dan hasil dikembalikan.4. Jika node bukan solusi, masukkan node yang bertetangga dengan node tersebut (node

anak) ke dalam queue 5. Jika queue kosong dan setiap simpul sudah dicek, pencarian selesai dan

mengembalikan hasil solusi tidak ditemukan6. Ulangi pencarian dari langkah kedua. 

1

2. Deskripsi Kasus

Permainan (game) merupakan salah satu implementasi dari ilmu dibidang komputer. Inti dari sebuah aplikasi permainan (game) adalah mengembangkan kemampuan otak untuk mengatur strategi, kecepatan, dan ketepatan dalam mencapai tujuan akhir. Salah satu contoh permainan (game) adalah puzzle. Puzzle terdiri dari beberapa jenis, ada yang menggunakan angka, huruf, dan gambar. Dalam permainan (game) puzzle, pemain diharapkan dapat mencapai tujuan akhir untuk membentuk sebuah puzzle menjadi sebuah susunan atau pola yang benar dengan waktu yang cepat. Dalam proyek akhir ini penulis memilih untuk membuat aplikasi pemecahan puzzle gambar. Perkembangan permainan pada masa kini sudah sangat pesat dan telah menjadi mode tersendiri di dunia karena mayoritas pengguna komputer menghabiskan sebagian besar waktu mereka di depan komputer dalam program permainan tidak hanya dalam permainan komputer ini pun sudah masuk dalam gadget yang sudah perkembang. Permainan ini mempunyai nama yaitu puzzle slider. Puzzle slider merupakan permainan menyusun potongan gambar dengan aturan sebuah potongan hanya dapat dipindahkan dengan menggesernya ke ruang kosong. Puzzle ini membentuk ruang solusi yang diorganisasikan ke dalam struktur pohon dinamis. Struktur pohon dinamis sendiri dibangun dengan 2 metode traversal yaitu Breadth First Search (BFS) dan Depth First Search (DFS). Game puzzle juga dapat melatih logika dan daya imaginasi seseorang. Sliding Puzzle merupakan salah satu permainan yang cukup terkenal. Permainan ini ditemukan oleh Sam Loyd pada sekitar tahun 1870. Dalam tugas ini, kita mencoba untuk menggunakan salah satu algoritma yang cukup terkenal, yaitu algoritma Breadth First Search, dengan menggunakan fungsi non heuristik sekaligus dalam perancangan sliding puzzle ini. Fungsi non heuristik ini tentunya memiliki prioritas yang berbeda. Prioritas pertama yang penulis ambil yaitu banyaknya grid puzzle yang berada ditempat yang salah, sedangkan prioritas yang kedua yaitu total keseluruhan jarak dari grid-grid yang tidak berada pada tempatnya yang sesuai. Prosedur Breadth First Search merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara sistematis pada setiap level hingga keadaan tujuan (goal state) ditemukan. Atau dengan kata lain, penelusuran yang dilakukan adalah dengan mengunjungi tiap-tiap node pada level yang sama hingga ditemukan goal state-nya. Untuk lebih jelasnya, perhatikan ilustrasi dari Breadth First Search pada gambar.

Masalah RisetKarena penulisan ini hanya menjelaskan untuk menganalisis game silder

puzzle yang ada pada gadget ataupun komputer, maka kami disini hanya menjelaskan bagaimana biasanya game silder puzzle ini dibuat dan cara menyelesaikan game slider puzzle ini.

2

Contoh pencarianUntuk menyelesaikan game tersebut kita dapat memisalkan ada tiga kotak A,

B, C pada sebuah papan. Sebuah kotak dapat dipindahkan jika tidak ada kotak lain di atasnya dan hanya ada satu kotak yang boleh dipindahkan. Ada dua kemungkinan pemindahannya, yaitu:

1) Pindahkan sebuah kotak ke atas papan.2) Pindahkan sebuah kotak ke bawah/samping kotak lainnya.

Masalah muncul jika diketahui keadaan awalnya (initial state atau current state) dan tujuan akhirnya (goal state atau final state), Seperti pada Gambar :

Pada gambar selanjutnya dapat dilihat bahwa ruang keadaan tersebut memiliki 4 elemen atau node, dengan perpindahan sebagai berikut :

1) Perpindahan kotak 3 ke bawah papan untuk lintasan a.2) Perpindahan kotak 1 ke bawah papan untuk lintasan b.3) Perpindahan kotak 2 ke atas kotak 3 untuk lintasan c.4) Perpindahan kotak 1 ke atas kotak 2 untuk lintasan d.

EvaluasiAdapun evaluasi dari analisis game ini adalah permainan game slider puzzle

ini merupakan game sederhana tetapi game ini juga dapat melatih logika dan mengasah daya ingat seseorang.  Namun kekurangan game ini ialah game ini masih bersifat statis.

Ide Pengembangan Riset Tidak hanya mengurutkan angka namun bisa dirubah ke dalam gambar Tingkat permainan dapat di persulit dengan menambahkan puzzle Dapat menggunakan gambar yang diinginkan.

3

goal stateInitial state

db ca

3 333

3

22

222 1

1

1

11

A

A

B

B

C

C

Initial stategoal state