TUGAS 2 (PROBLEM SOLVING, SEARCH)

 Missionaries and Cannibals Problem

  

  Sekarang ini, sudah banyak game / permainanpermainan

menarik yang beredar di masyarakat. Ada

yang dalam bentuk console seperti PlayStation

maupun permainan pada komputer. Permainan ini

awalnya adalah suatu hiburan untuk menyegarkan

pikiran. Namun banyak juga orang yang sampai

kecanduan terhadap suatu permainan karena

permainan itu sangat menarik dan terus berlanjut.

Hal seperti ini kurang bagus. Permainan yang baik

adalah permainan yang bukan hanya menghibur,

tetapi juga mengasah otak ibarat sambil menyelam

minum air. Namun biasanya permainan seperti itu

kurang populer sehingga banyak yang tidak

mengetahuinya.

    Oleh karena itu, pada makalah ini, akan dibahas suatu

permainan logika yaitu 3 missionaries and 3

cannibals dimana tujuan akhir dari permainan ini

adalah menyebrangkan tiga missionaries dan tiga

cannibals ke sisi lainnya dengan perahu yang hanya

mampu mengangkut dua orang dan dikendalikan oleh

salah satu orang pada perahu tersebut. Pada

permainan ini, ada banyak kemungkinan yang dapat

dilakukan dan juga terdapat beberapa kemungkinan

yang menuju ke penyelesaian. Salah satu algoritma

yang cukup mangkus untuk menyelesaikan

permasalahan ini adalah dengan menggunakan

algoritma runut-balik (backtracking). Algoritma ini

mampu memangkas kemungkinan-kemungkinan yang

tidak menuju solusi sehingga waktu yang diperlukan

untuk mencari penyelesaian dari permainan ini

menjadi lebih singkat.

Problem didefinisikan dalam 4 item:

1.   Initial State, yaitu memutuskan apa yang harus dilakukan dengan mencari urutan tindakan yang mengarah pada keadaan (state) yang diinginkan

2.    Successor function / Action, yaitu kombinasi dari berbagai "tindakan nyata"

3.    Goal test, yaitu merumuskan tujuan yang ingin dicapai

4.    Path cost, yaitu menetapkan besarnya biaya untuk setiap jalur yang ada.

Penjelasan Game

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 ciri 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 berakhir.

Game ini terasa lebih sulit dimainkan oleh pemain jika diberi aturan-aturan yang harus dipatuhi. ini dia aturan-aturan tersebut:

• 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 (1 kanibal/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. 

Salah satu metode yang dipakai dalam pemecahan masalah pada game missionaries and cannibals ini adalah dengan Breadth First Search (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 langkah-langkahnya sebagai berikut:

1.    Akar dimasukkan dalam antrian (Simpul paling awal yang akan dikunjungi). 

2.    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. 

3.    Jika simpul yang sudah dicek tadi merupakan solusi permasalahan, pencarian selesai dan hasil dikembalikan. 

4.    Jika simpul yang sudah dicek sebelumnya bukan merupakan solusi permasalahan, semua simpul yang bertetanggan dengan simpul tadi (simpul anak) dimasukkan kedalam antrian.

5.    Jika antrian ternyata telah kosong dan semua simpul sudah dicek maka status pencarian selesai dan berarti solusi tidak ditemukan. 

6.    Hal ini dilakukan secara berulang (simpul berisi solusi ditemukan/sampai antrian kosong).

Agar mempermudah penggambaran, maka dibuat notasi untuk tiap-tiap simpul/state. Untuk state awal, notasinya adalah `(0,0)|(3,3)K` yang artinya, di sisi kiri ada 0 Misionaris 0 Kanibal, dan disisi kana nada 3 Misionaris, 3 Kanibal dan perahu. State akhir notasinya adalah `K(3,3)|(0,0)`.

Gambar Puzzle:

Runtutan langkah-langkah dari state awal hingga solusi dapat diperolah dengan melakukan backtrack tiap parent dari simpul solusi ke simpul state awal.

Berikut pohon state yang dibuat, dari simpul state awal hingga simpul solusi: 

Kesimpulan

Algoritma Breadth-First Search (BFS) dapat diterapkan dalam berbagai macam masalah untuk melakukan pencarian solusi, salah satunya pada puzzle Missionaries and Cannibals. Algoritma BFS melakukan pencarian pada graf atau pohon dengan cara melebar, yang tentu memerlukan memori dan langkah pencarian yang lebih banyak dibandingkan dengan Depth-First Search (DFS). Keuntungan menggunakan BFS adalah langkah dari state awal ke state akhir optimal (terpendek). 

Tulisan ini dibuat untuk memenuhi tugas  mata kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT . Prodi Teknik Informatika Fakultas Teknik UHAMKA.


Refrensi

https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

https://id.wikipedia.org/wiki/Masalah*http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-007.pdf