Analisis Game "Missionaries and Cannibals" atau "Suami Pencemburu"

Game Missionaries and Cannibals adalah salah satu permainan bergenre puzzle yang terkenal di dunia khususnya dalam pengembangan kecerdasan buatan, dimana masalah tersebut dipakai oleh Saul Amarel sebagai contoh representasi masalah. 

Daftar Isi

Sejarah Singkat

---

Pada abad pertengahan sebelum adanya permaianan Game Missionaries and Cannibals, permaianan serupa yang lebih dulu dikenal yaitu permainanan suami-suami pencemburu. Dalam perumusan Alcuin, pasangan-pasangan tersebut adalah para saudara dan saudari, tetapi yang menjadi hambatan yaitu tak ada wanita yang dapat bersama dengan pria lain tanpa kehadiran saudaranya. Dari pasangan - pasangan tersebut saat ini disebut para suami dan istri.

Masalah tersebut kemudian ditempatkan dalam bentuk para tuan dan pelayan, perumusan dengan para missionaries and cannibals belum muncul hingga akhir abad ke-19. Jumlah pasangan dan ukuran perahu yang diragamkan muncul pada permulaan abad ke -16. Cadet de Fontenay menempatkan sebuah pulau di tengah sungai pada 1879 sebuah ragam dari masalah tersebut, dengan perahu dua orang, sepenuhnya dipecahkan oleh Ian Pressman dan David Singmaster pada 1989.

Aturan Permainan

---

Game Missionaries and Cannibals

• Ada tiga misionaris dan tiga kanibal yang harus menyeberangi sungai untuk ke tempat tujuan yang sama.
• Hanya disediakan satu perahu.
• Perahu dapat berjalan dengan minimal satu penumpang dan maksimal berisi dua penumpang (1 Kanibal / 1 Misionaris / 2 Kanibal / 2 Misionaris / 1 Misionaris dan 1 Kanibal).
• Jumlah  Kanibal tidak boleh lebih banyak dari jumlah misionaris di salah satu sisi daratan.  Jika jumlah Kanibal melebihi Misionaris pada suatu sisi, maka Misionaris tersebut akan dimakan oleh Kanibal dan Puzzle berakhir (Kalah).
• Permainan dianggap berhasil jika semua misionaris dan semua Kanibal berada di sisi seberang yang menjadi tujuan.

Game Suami - Suami Pencemburu

• Ada tiga pasangan suami istri yang harus menyeberangi sungai untuk ke tempat tujuan yang sama.
• Hanya disediakan satu perahu.
• Perahu dapat berjalan dengan minimal satu penumpang dan maksimal berisi dua penumpang (1 Pria / 1 Wanita / 2 Pria / 2 Wanita / Pasangan suami istri).
• Jumlah  Pria tidak boleh lebih banyak dari jumlah wanita di salah satu sisi daratan.  Jika jumlah Pria melebihi Wanita pada suatu sisi, maka Wanita tersebut berada dalam keadan tanpa suami mereka dan Puzzle berakhir (Kalah).
• Permainan dianggap berhasil jika semua pasangan suami istri berada di sisi seberang yang menjadi tujuan.

Solusi Penyelesaian Permainan

---

Game Missionaries and Cannibals

Penyelesaian :

Angka pergerakan	Tepi awal	Pergerakan	Tepi akhir
(awal)	kkk mmm
1	k mmm	kk →
2	k mmm	←k	k
3	mmm	kk →	k
4	mmm	← k	kk
5	k m	mm →	kk
6	k m	← k m	k m
7	kk	mm →	km
8	kk	← k	mmm
9	k	kk →	mmm
10	k	← k	mmm k
11		kk →	mmm k
(akhir)			mmm kkk

Penjelasan :

1. Kanibal dengan Kanibal menyeberang, satu Kanibal turun.
2. Kanibal kembali.
3. Kanibal dengan Kanibal menyeberang, satu Kanibal turun.
4. Kanibal kembali.
5. Dua Misionaris menyeberang, satu turun.
6. Satu Misionaris kembali bersama kanibal, Kanibal turun.
7. Dua Misionaris menyeberang, keduanya turun.
8. Kanibal kembali.
9. Dua kanibal menyeberang, satu Kanibal turun.
10. Kanibal kembali.
11. Dua Kanibal menyeberang dan turun.

Game Suami - Suami Pencemburu

Pasangan suami istri diwakili sebagai :

• Pasangan 1 terdiri dari a dan b | a adalah pria dan b adalah wanita.
• Pasangan 2 terdiri dari c dan d | c adalah pria dan d adalah wanita.
• Pasangan 3 terdiri dari e dan f | e adalah pria dan f adalah wanita.

Penyelesaian :

Angka pergerakan	Tepi awal	Pergerakan	Tepi akhir
(awal)	ab cd ef
1	cd ef	ab →
2	cd ef	←a	b
3	a c e	d f →	b
4	a c e	← b	d f
5	ab	c e →	d f
6	ab	← cd	ef
7	b d	a c →	ef
8	b d	← f	a c e
9	d	b f →	a c e
10	d	← c	ab ef
11		cd →	ab ef
(akhir)			ab cd ef

Penjelasan :

1. (ab) menyeberangi sungai.
2. (b) turun di tepi akhir dan (a) kembali ke tepi awal. 
3. (a) turun di tepi awal dan (df) menyeberangi sungai.
4. (df) turun di tepi akhir dan (b) kembali ke tepi awal.
5. (b) turun di tepi awal dan (ce) menyeberangi sungai.
6. (e) turun di tepi akhir dan (cd) kembali ke tepi awal.
7. (d) turun di tepi awal dan (ac) menyeberangi sungai.
8. (ac) turun di tepi akhir dan (f) kembali ke tepi awal.
9. (bf) menyeberangi sungai.
10. (bf) turun di tepi akhir dan (c) kembali ke tepi awal.
11. (cd) menyebrangi sungai dan (cd) turun di tepi akhir.

Ilustrasi Gambar Penyelesaian Permainan

---

Game Missionaries and Cannibals

Game Suami - Suami Pencemburu

Analisis Problem Solving Game

---

Analisis sistem kecerdasan problem solving ini hanya mengambil salah satu contoh game saja yaitu Missionaries and Cannibals, analisis ini menggunakan metode algoritma BFS (Breadth First Search). Berikut penjelasannya :

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

A. Algoritma BFS

B. Prinsip Pencarian Solusi Algoritma 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 :

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

C. Penerapan Algoritma BFS di Game Missionaries and Cannibals 

Dalam mengembangkan Artificial Intellegence hal yang sangat diperhatikan adalah sebuah sistem harus mampu mencari solusi dan menyelesaikan suatu masalah. Pada Artificial Intellegence permasalahan di definisikan dalam 4 item yaitu :

1. Initial state (keadaan awal) : 3 misionaris dan 3 kanibal yang ingin menyeberang bersama.
2. Successor Function (kombinasi tindakan) : memindahkan 3 misionari dan 3 kanibal menyeberangi sungai menggunakan perahu yang bisa menampung 2 penumpang saja, dengan syarat jumlah misionaris harus lebih banyak dari jumlah kanibal.
3. Goal Test (tujuan yang dicapai) : berhasil menyeberangi 3 misionaris dan 3 kanibal ke seberang sungai dengan selamat.
4. Path Cost (banyaknya jalur yang ada) :  11 jalur penyelesaian untuk menuju seberang sungai.

Setiap state dijadikan sebuah simpul pada pohon. State awal adalah sisi kiri masih kosong, dan sisi kanan terdapat 3 misionaris & 3 kanibal. Untuk mempermudah penggambaran, maka dibuat notasi untuk setiap simpul. Untuk state awal, notasinya adalah “(0,0)|(3,3)K” yg berarti di sisi kiri terdapat 0 misionaris & 0 kanibal, dan di sisi kanan terdapat 3 misionaris & 3 kanibal. Sedangkan notasi akhirnya adalah “K(3,3)|(0,0)”. Berikut state space pohon pencariannya :

Keterangan gambar :

• Warna merah mendakan state tersebut salah
• Warna merah + garis bawah menandakan state tersebut telah dikunjungi.
• Warna hijau + garis bawah menandakan state berhasil.

D. Kesimpulan Penerapan Algoritma BFS di Game Missionaries and Cannibals 

Algoritma Breadth-First Search (BFS) dapat diterapkan untuk berbagai macam masalah, salah satunya adalah untuk pencarian solusi dari game Missionaries and Cannibals. Karena pencarian dilakukan secara melebar dari node akar sampai node akhir. Kelemahan dari algoritma ini adalah memerlukan banyak memori dikarenakan pencarian yang banyak. Dan keuntungannya adalah langkah yang dihasilkan lebih optimal.