ANALISIS SISTEM CERDAS PADA GAME MISSIONARIES AND CANNIBALS

Artikel terkait : ANALISIS SISTEM CERDAS PADA GAME MISSIONARIES AND CANNIBALS

“Missionaries and Cannibals”

Game “Missionaries and Cannibals” merupakan salah satu game bergenre puzzle yang terkenal di dunia. Game ini bercerita tentang tiga orang misionaris dan tiga kanibal yang ingin menyebarang sungai. Untuk menyebrangi sungai tersebut disediakan perahu yang dapat digunakan oleh kanibal maupun misionaris.

Pemain dikatakan berhasil memainkan permainan ini jika sampai akhir permainan jumlah misionaris dan kanibal masing masing tiga. Dan aturan pokok yang menjadi cirri dari permainan ini, yaitu jumlah kanibal tidak boleh lebih dari jumlah misionari di berbagai sisi. Jika jumlah kanibal lebih banyak dari misionari, maka kanibal akan memakan misionari dan permainan berkhir.

Aturan Permainan :

Perahu bisa berisi max. 2 penumpang (Missionaris maupun Kanibal)
Jika jumlah Kanibal melebihi Misionaris pada suatu sisi, maka Missionaris tersebut akan dimakan oleh Kanibal dan Puzzle berakhir (Kalah)
Ada tiga misionaris dan tiga kanibal yang harus menyebrang sungai.
Hanya disediakan satu perahu.
Perahu bisa berjalan jika ada minimal satu orang atau satu kanibal (satu penumpang).
Perahu maksimaum berisi dua (1kanibal/1 misionaris /2 kanibal /2 misionaris)
Jumlah kanibal tidak boleh lebih banyak dari jumlah misionaris di salah satu sisi daratan.
Jika jumlah kanibal lebih banyak dari jumlah misionaris pada suatu sisi daratan maka kanibal akan memakan misionaris.
Pemain berhasil menyelesaikan permainan jika semua misionaris dan semua kanibal ada di sisi seberang yang menjadi tujuan.

Metode Pencarian Melebar pertama BFS (Breadth First Search) adalah algoritma pencarian solusi yang melakukan pencarian pada graf atau pohon berakar secara melebar dengan cara mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Simpul yang belum dikunjungi dan bertetangga dengan simpul - simpul yang tadi dikunjungi , demikian seterusnya.

Jika diilustrasikan dalam pohon berakar, maka semua simpul pada x dikunjungi lebih dahulu sebelum simpul-simpul pada x + 1. Algoritma ini memerlukan sebuah antrian (queue) Q untuk dapat menyimpan simpul yang telah dikunjungi. Setiap simpul yang telah dikunjungi

Algoritma :

Buat suatu variabel Node_List dan tetapkan sebagai keadaan awal·
Kerjakan langkah-langkah berikut ini sampai tujuan tercapai atau node_list dalam keadaan kosong:

a. Hapus elemen pertama dari

Node_List sebut dengan nama E,

Jika Node_List kosong, keluar

b. Pada setiap langkah yang aturannya cocok dengan E, kerjakan:

i. Aplikasikan aturan tersebut untuk membentuk suatu keadaan baru

ii. Jika keadaan awal adalah tujuan yang diharapkan, sukses dan keluar

iii. Jika Tidak, tambahkan keadaan awal yang baru tersebut pada akhir Node_List.

Prinsip Pencarian Solusi pada BFS

Secara umum, prinsip pencarian solusi dengan algoritma Breadth First Search (BFS) dimulai dengan simpul akar (simpul akar terlebih dahulu dimasukkan dalam antrian, lalu di pop()), lalu mengekspansi simpul-simpul anak dari dari simpul akar, dan memasukkan simpul anak dalam sebuah antrian. Antrian tadi digunakan untuk memberikan tanda pada simpul – simpul tetangga yang nantinya akan dikunjungi berdasarkan urutan yang ada pada antrian. Penjabaran dari langkah – langkah pada prinsip pencarian solusi dengan algoritma BFS ini adalah sebagai berikut :

- Akar dimasukkan dalam antrian (Simpul paling awal yang akan dikunjungi).
- Simpul yang ada pada awal antrian diambil dan dilakukan pengecekan untuk mengetahui status simpul tersebut sebagai solusi permasalahan atau tidak, dan mengekspansi anak-anaknya jika ada.
- Jika simpul yang sudah dicek tadi merupakan solusi permasalahan, pencarian selesai dan hasil dikembalikan.
- Jika simpul yang sudah dicek sebelumnya bukan merupakan solusi permasalahan, semua simpul yang bertetanggan dengan simpul tadi (simpul anak) dimasukkan kedalam antrian.
- Jika antrian ternyata telah kosong dan semua simpul sudah dicek maka status pencarian selesai dan berarti solusi tidak ditemukan.
- Hal ini dilakukan secara berulang (simpul berisi solusi ditemukan/sampai antrian kosong)

Analisis

Penggunaan algoritma BFS pada pencarian solusi puzzle Missionaries and Cannibals menghasilkan langkah-langkah menuju solusi yang optimal (terpendek), ini dikarenakan pencarian dilakukann secara melebar dari simpul akar hingga simpul akhir. Tidak seperti penggunaan algoritma DFS (Dept-First Search), yang lebih mengutamakan kedalaman untuk mencapai ke simpul solusi. Kekurangan penggunaan BFS disini, langkah proses pencarian lebih banyak dibandingkan dengan DFS, penggunaan ruang (memori) juga lebih banyak, karena tiap simpul anak-anak hasil ekspansi suatu simpul dimasukkan ke dalam antrian.

Langkah-langkah Penyelesaian Game “Missionaries and Cannibals” :

1. Canibal dengan canibal menyebrang, satu canibal turun

2. Canibal kembali

3. Canibal dengan canibal menyebrang, satu canibal turun

4. Canibal kembali dan turun

5. Dua Missionaries menyebrang, satu turun

6. Satu Missionaries kembali menjemput

7. Dua Missionaries menyebrang, keduanya turun

8. Canibal naik dan menjemput canibal

9. Satu kanibal turun

10. Canibal satunya menjemput

11. Dua canibal menyebrang dan turun