Penerapan Deduksi Logika dan Skema Runut Balik dalam Memecahkan Misteri pada Permainan Inspector Parker

Penerapan Deduksi Logika dan Skema Runut Balik dalam Memecahkan Misteri pada Permainan Inspector Parker Tifani Warnita (13513055) Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia [email protected]

Abstrak—Permainan telah menjadi salah satu sarana rekreasi yang paling digemari oleh berbagai lapisan masyarakat. Saat ini, telah tersebar berbagai jenis permainan dengan tipe dan mekanisme bermain yang beragam. Tidak hanya bersifat menghibur, ada banyak pula permainan yang bersifat mendidik seperti Inspector Parker. Inspector Parker sendiri merupakan sebuah permainan berbasis logika di mana pemain diberikan beberapa buah petunjuk agar pemain dapat memecahkan misteri pada setiap level yang disuguhkan. Makalah ini menjelaskan bagaimana penggabungan metode deduksi logika dan skema runut balik yang diterapkan terhadap papan permainan dan petunjuk yang tersedia dapat digunakan untuk memecahkan permasalahan yang dihadapi oleh Inspector Parker. Kata kunci—Deduksi, permainan, runut balik

Inspector

Parker,

logika,

seperti kebanyakan media rekreasi lain, suatu permainan juga menyuguhkan berbagai jenis genre (aliran) yang beragam. Dengan berbagai jenis genre yang tersedia, pemain dapat dengan leluasa menentukan permainan apa yang ingin dia mainkan. Salah satu genre yang menarik untuk ditelusuri adalah permainan berbasis logika yang saat ini sudah tak terhitung banyaknya. Mulai dari Sudoku, Kakurasu, sampai yang baru-baru ini sangat marak di pasaran, 2048. Dengan permainan berbasis logika, pemain dituntut untuk memecahkan setiap persoalan yang ada dengan memikirkan suatu solusi yang mungkin berdasarkan perhitungan yang akurat. Salah satu permainan berbasis logika yang cukup menarik perhatian adalah Inspector Parker. Inspector Parker sendiri menyuguhkan permainan puzzle bertajuk misteri pembunuhan pada setiap level yang ia miliki.

I. PENDAHULUAN Seiring dengan teknologi yang senantiasa berkembang, mendukung pula berbagai game developer untuk semakin mengembangkan sayapnya di ranah hiburan. Setiap harinya, dapat kita temukan permainan baru menduduki pasar aplikasi baik itu untuk PC (personal computer) maupun untuk telepon genggam. Penikmat permainan ini bukan hanya remaja melainkan dapat kita temui dari berbagai kalangan. Bahkan menurut Jason Allaire, Ph.D., seorang profesor psikologi asal North Carolina State University, setiap orang dari berbagai umur memainkan video games saat ini. Prof. Allaire juga menyatakan bahwa pandangan mengenai game player sudah tidak lagi berlaku karena untuk saat ini, orang yang memainkan permainan benar-benar bisa siapa saja saja seperti kakek kita, bos kita, atau bahkan professor kita. Di Amerika sendiri, diketahui bahwa 59% penduduk Amerika memainkan video game. Hal ini didasari oleh survei yang dilakukan pada tahun 2014 lalu oleh Essential Software Association. Selain itu, survei lain mengatakan bahwa 42% orang tua dengan anak yang seorang pemain game kerap kali bermain bersama anaknya setidaknya satu kali seminggu. Berdasarkan fakta-fakta seperti tersebut di atas, agaknya permainan telah menjadi salah satu bentuk sarana rekreasi yang paling banyak dicari. Selain menawarkan akses yang cepat tanpa harus bepergian

Makalah IF2211 Strategi Algoritma – Sem. II Tahun 2014/2015

Gambar 1. Permainan Inspector Parker

Memecahkan suatu misteri pembunuhan pada permainan Inspector Parker membutuhkan penalaran mendalam atas setiap petunjuk yang diberikan. Melalui makalah ini, akan dijelaskan bagaimana metode deduksi serta penerapan skema runut balik dapat menjadi salah satu alternatif pemecahan solusi bagi permainan Inspector Parker.

II. DASAR TEORI Dasar ilmu yang digunakan pada makalah ini adalah mengenai metode deduksi serta algoritma runut balik yang merupakan salah satu strategi algoritma yang dapat

diterapkan untuk permasalahan dengan himpunan solusi lebih dari satu.

2.1 Metode Deduksi Deduksi dapat diartikan sebagai penarikan kesimpulan dari sekumpulan keadaan umum menjadi keadaan khusus. Deduksi juga sering disebut sebagai top-down logic. Dengan demikian, metode deduksi merupakan suatu cara dalam menganalisis sekumpulan fakta umum untuk nantinya digeneralisasi menjadi suatu konklusi yang lebih khusus. Pada metode deduksi, suatu kesimpulan didapatkan dengan cara mengaitkan setiap peraturan umum yang diberikan dari premis-premis yang ada, mengeliminasi jumlah pertimbangan, sampai akhirnya ditarik kesimpulan yang benar dan memenuhi seluruh premis yang sebelumnya didefinisikan. Berikut adalah contoh penggunaan metode deduksi dalam penarikan kesimpulan. 1. Setiap kucing suka makan ikan. Bruno adalah seekor kucing. Kesimpulan: Bruno suka makan ikan. 2. y = 5x + 2 x=3 Kesimpulan: y = 17 3. Jika bertemu dengan kucing maka Tifani senang. Tifani bertemu dengan kucing. Kesimpulan: Tifani senang. Meski terkesan sederhana, namun penalaran deduksi yang salah dapat menimbulkan hasil kesimpulan yang tidak sesuai kenyataan yang berlaku. Berikut ni adalah contoh penggunaan deduksi yang salah dalam penarikan kesimpulan. 1. Jika Quinsy makan ikan maka Quinsy kenyang. Quinsy kenyang. Kesimpulan: Quinsy makan ikan. (salah) Kesimpulan di atas bernilai salah karena suatu akibat berupa Quinsy kenyang belum tentu diakibatkan oleh Quinsy makan ikan. 2. Jika Snowball mengantuk maka Snowball akan tidur. Snowball tidak tidur. Kesimpulan: Snowball mengantuk. Kesimpulan di atas bernilai salah karena jika Snowball tidak tidur, dapat ditarik kesimpulan bahwa Snowball tidak mengantuk karena menurut premis yang ada, Snowball akan tidur jika ia mengantuk.

yang ada sampai akhirnya ditemukan solusi yang sesungguhnya. Algoritma ini dapat dipandang sebagai salah satu dari dua hal, yaitu sebagai sebuah fase yang terdapat pada suatu alogitma traversal DFS (Depth-first Search) atau sebagai suatu metode pemecahan masalah yang terstruktur dan sistematis. Algoritma runut balik ini merupakan salah satu bentuk perbaikan dari algoritma exhaustive search yang merupakan bagian dari algoritma brute-force. Pada algoritma exhaustive search, setiap kemungkinan solusi dieksplorasi satu per satu sehingga kerap kali dianggap sebagai algoritma yang naif. Berbeda dengan brute-force, pada algoritma runut balik, hanya pilihan yang mengarah ke solusi yang dieksplorasi. Setiap kali menemukan percabangan yang tidak mungkin dari sekumpulan himpunan solusi yang terdefinisi, percabangan tersebut tidak akan dikunjungi. Properti umum dari algoritma runut balik adalah sebagai berikut: a. Solusi Persoalan Solusi persoalan dinyatakan sebagai suatu vektor dengan n-tuple. 𝑋 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) 𝑥𝑖  𝑆𝑖 b. Fungsi pembangkit nilai (𝑥𝑘 ) Fungsi pembangkit dinyatakan dalam predikat 𝑇(𝑘) dimana 𝑇(𝑘) membangkitkan nilai untuk 𝑥𝑘 yang merupakan komponen vektor solusi. c. Fungsi pembatas Fungsi pembatas dinyatakan sebagai predikat 𝐵(𝑥1 , 𝑥2 , … , 𝑥𝑘 ) B bernilai benar (true) jika (𝑥1 , 𝑥2 , … , 𝑥𝑘 ) mengarah ke solusi. Jika true, maka pembangkitan nilai untuk xk+1 dilanjutkan, tetapi jika bernilai salah (false) maka (𝑥1 , 𝑥2 , … , 𝑥𝑘 ) dibuang dan tidak akan dievaluasi lagi untuk ke depannya.

Gambar 2. Contoh penggunaan algoritma runut balik pada pewarnaan peta Australia [1]

2.2 Algoritma Runut Balik Runut balik (backtracking) adalah salah satu algoritma yang dapat diterapkan dalam menemukan solusi persoalan berdasarkan himpunan solusi persoalan yang terdefinisi. Istilah ini pertama kali diperkenalkan pada tahun 1950 oleh D.H. Lehmer. Terdapat pula tokoh-tokoh seperti Golomb, Baumert, serta R.J. Walker yang menyajikan uraian umum mengenai algoritma ini. Dalam pengimplementasiannya, semua himpunan solusi yang mungkin diterapkan secara sekuensial pada permasalahan

Prinsip pencarian ruang solusi pada algoritma runut balik menggunakan pohon ruang status adalah sebagai berikut. 1. Untuk pohon ruang status yang terdefinisi, pencarian solusi dilakukan berdasarkan pohon ruang status tersebut dengan skema pencarian dibentuk dari akar ke daun. 2. Dalam pembentukan pohon ruang status, metode yang digunakan adalah metode DFS atau Depth-


first Search. Simpul-simpul yang dilahirkan pada pohon ruang status disebut sebagai simpul hidup (live node) sedangkan simpul yang sedang diperluas disebut sebagai simpul-E (Expand node). 4. Untuk mencegah pengevaluasian kemungkinan yang tidak mengarah ke solusi, diterapkan suatu fungsi pembatas (bounding function) pada setiap simpul yang sudah terdefinisi pada ruang status. Apabila simpul tersebut melewati batas yang telah ditetapkan oleh fungsi pembatas, simpul itu akan dimatikan dan tidak akan diperluas lagi. Simpul yang dimatikan tersebut dinamakan simpul mati (dead node). 5. Jika pembentukan lintasan berakhir dengan simpul mati, proses pencarian dilanjutkan dengan membangkitkan simpul anak yang lain. Bila tidak ada simpul anak yang dapat dibangkitkan karena simpul-simpul anak yang terdefinisi sebelumnya sudah mati, maka pencarian solusi dilanjutkan dengan menggunakan skema runut balik (backtrack) ke simpul terdekat yaitu simpul orang tua dari simpul yang sedang dievaluasi. Simpul ini selanjutnya menjadi simpul-E yang baru. 6. Pencarian solusi dihentikan jika pengevaluasian simpul telah mencapai simpul solusi (goal node). Algoritma runut balik kerap kali diterapkan sebagai salah satu metode pencarian solusi untuk berbagai macam permainan seperti Tic-Tac-Toe, Sudoku, catur, maupun untuk masalah-masalah pada bidang kecerdasan buatan (artificial intelligence). 3.

Gambar 3. Board game permainan Inspektor Parker

Pada setiap level, terdefinisi board game dengan ukuran yang beragam. Misalkan seperti yang tertera pada gambar di atas, tempat kejadian perkara direpresentasikan dalam kotak berukuran 3x2 dengan arti terdapat dua lantai dengan masing-masing lantai memiliki tiga buah kamar yang berbeda-beda mulai dari kamar tidur, tangga, kamar bayi, ruang makan, ruang tengah, sampai ruang keluarga. Pada setiap ruangan ini terdapat pilihan kemungkinan solusi yang didefinisikan oleh permainan. Dari gambar tersebut, dapat kita lihat bahwa setiap ruangan pasti memiliki satu buah senjata dan satu buah orang yang sedang berada di dalamnya. Sebagai pemain, kita dituntut untuk menentukan siapa dan apa yang sedang berada pada suatu ruangan berdasarkan petunjuk yang tersedia. Petunjuk permainan dapat kita lihat pada bagian kanan dari gambar di atas. Pada level ini, terdefinisi tujuh buah petunjuk dengan beberapa deskripsi sebagai berikut.

2.5 Permainan Inspektor Parker Inspector Parker merupakan permainan logika bertajuk misteri pembunuhan keluaran Big Fish Games. Pada permainan ini, pemain dituntut untuk menentukan solusi pemecahan masalah Misanthorpe Manor yang sesuai dengan petunjuk yang diberikan untuk setiap levelnya. Pada permainan ini, terdapat tujuh buah tersangka pembunuhan, senjata, korban, kepingan bukti, dan metode pembuangan jenazah korban yang dapat dijadikan cara untuk memecahkan kasus pembunuhan yang terjadi melalui pengeliminasian kemungkinan pada board game yang ada.


Gambar Petunjuk

Deskripsi Petunjuk Harriet selalu berada di sebelah kiri racun tikus. Tanda tanya (?) mengindikasikan bahwa tidak diketahui seberapa banyak selang ruangan dari ruangan tempat Harriet berada ke ruangan yang terdapat racun tikus di dalamnya. Kapak selalu beada di ruangan sebelah kanan dari kamar tidur namun tidak diketahui seberapa banyak selang ruangan di antaranya. Pada ruangan tempat Ophelia berada ditemukan pula tali tambang yang dapat digunakan untuk gantung diri.

Pisau selalu berada di lantai yang lebih rendah daripada tangga atas namun tidak diketahui seberapa banyak selang lantai di antara keduanya.

Tabel 1. Petunjuk permainan dan deskripsinya

Berdasarkan petunjuk yang diberikan pada setiap level permainan, pemain harus menentukan solusi yang paling benar. Apabila pemain sudah yakin dengan jawabannya, pemain dapat langsung memilih pilihan objek yang terdapat pada masing-masing ruangan sampai hanya terdefinisi satu objek bertipe tertentu untuk satu ruangan. Seiring dengan petunjuk yang berhasil dipecahkan oleh pemain, petunjuk itu akan langsung hilang dari daftar petunjuk. Apabila permainan telah diselesaikan dengan solusi yang tepat, Inspector Parker akan memberikan permasalahan tersebut ke ahli forensik untuk selanjutnya diselidiki sampai akhirnya diketahui deskripsi pembunuhan yang terjadi dengan siapakah pelaku pembunuhannya. Sebagai contoh pemecahan masalah yang tepat berdasarkan petunjuk yang diberikan, berikut adalah solusi dari level permainan pada Gambar 3.

1.

Objek A selalu berada di sebelah kanan objek B Kesimpulan: Pada setiap ruangan yang berada di kolom paling kiri, tidak mungkin terdapat objek B karena jika objek B berada di sana, tidak ada ruang untuk meletakkan objek A yang harus berada lebih kiri dari objek B. Begitu pula sebaliknya, pada setiap ruangan yang terdapat di kolom paling kanan, tidak mungkin terdapat objek A karena jika objek A berada di sana, tidak ada ruang untuk meletakkan objek B yang harus berada lebih kanan dari objek A. 2. Objek A selalu berada di sebelah atas objek B Kesimpulan: Pada setiap ruangan yang berada di baris paling atas, tidak mungkin terdapat objek B karena jika objek B berada di sana, tidak ada ruang untuk meletakkan objek A yang harus berada lebih atas dari objek B. Begitu pula sebaliknya, pada setiap ruangan yang berada di baris paling atas, tidak mungkin terdapat objek A karena jika objek A berada di sana, tidak ada ruang untuk meletakkan objek B yang harus berada lebih bawah dari objek A. 3. Objek A selalu berada bersama dengan objek B Kesimpulan: Pada suatu ruangan, apabila tidak terdapat objek A di dalamnya maka tidak boleh terdapat pula objek B di dalamnya. Berlaku sebaliknya, jika pada suatu ruangan tidak terdapat objek B di dalamnya maka tidak boleh pula objek A berada di dalamnya. Berdasarkan ketiga premis dan hasil deduksi yang berhasil disimpulkan di atas, kita dapat melakukan minimasi jumlah simpul yang dapat dibangkitkan pada pohon ruang status dengan cara menghilangkan daftar objek yang tidak mungkin berada pada suatu ruangan tertentu sehingga jumlah kemungkinan objek yang berada pada suatu ruangan dapat berkurang. Berikut adalah contoh pengeliminasian objek-objek yang tidak mungkin.

Gambar 4. Solusi permainan dari soal pada Gambar 3

III. PENGGUNAAN METODE DEDUKSI UNTUK PENARIKAN KESIMPULAN AWAL Pada awal pemecahan solusi, metode deduksi digunakan untuk melakukan eliminasi atas kemungkinankemungkinan yang tidak mungkin dievaluasi karena sudah terbukti kesalahannya berdasarkan petunjuk yang tersedia. Dalam hal ini, eliminasi kemungkinan dapat diterapkan pada setiap ruangan yang berada di pojok, baik itu di kanan, kiri, atas, maupun bawah serta berdasarkan keberadaan objek pada setiap ruangan. Merujuk pada petunjuk baik itu vertikal maupun horizontal, dapat kita tarik kesimpulan awal sebagai berikut.


Gambar 5. Hasil eliminasi menggunakan metode deduksi

yang terdiri atas empat kolom, apabila petunjuk pertama dievaluasi akan menghasilkan simpul kemungkinan sebanyak dua buah sedangkan petunjuk kedua akan menghasilkan simpul kemungkinan sebanyak enam buah simpul sesuai dengan rumus sebagai berikut.

IV. PENERAPAN SKEMA RUNUT BALIK DALAM PENCARIAN SOLUSI PERMAINAN Berdasarkan eliminasi yang dihasilkan dari tahap analisis menggunakan metode deduksi, penerapan skema runut balik dapat mulai dilakukan. Pada tahap awal, dilakukan pendefinisian properti algoritma runut balik sebagai berikut: a. Solusi persoalan Agar dapat memaksimalkan kinerja skema runut balik yang digunakan, solusi persoalan bukan dibangun secara trivial. Pembangunan solusi secara trivial di sini dapat dimisalkan sebagai simpul solusi merupakan pasangan objek yang mungkin pada sebuah ruangan. Hal ini sebaiknya dihindari karena semakin tinggi level permainan, semakin banyak objek yang terdapat pada satu buah ruangan. Misal ukuran board adalah sebesar 4x4 dengan empat buah objek yang terdefinisi pada setiap ruangan dengan jenis objek yang ada berupa empat buah tersangka, empat buah korban, empat buah senjata, serta empat buah bukti. Dalam setiap empat buah objek yang harus ditempatkan pada satu buah ruangan, terdapat empat buah kemungkinan pada masing-masing objek sehingga jumlah solusi yang mungkin menjadi sejumlah factorial objek yang terdefinisi. Menyikapi hal ini, solusi persoalan didefinisikan pada sebuah vektor dengan n buah tuple. Nilai n di sini merujuk pada jumlah objek yang terdapat pada suatu petunjuk. Misal objek A berada di sebelah kanan objek B berarti terdapat dua buah objek sehingga terdefinisi dua buah tuple. Pada masing-masing tuple ini berisi nomor ruangan objek mungkin berada dengan asumsi nomor ruangan yang tedefinisi adalah sebanyak 1 sampai 𝑛 ruangan. b. Fungsi pembangkit Penentuan fungsi pembangkit didasari dengan prinsip probabilitas penemuan atas solusi permainan yang paling besar. Dalam hal ini, fungsi pembangkit merujuk pada nilai dari masingmasing petunjuk. Setiap petunjuk memiliki nilai prioritasnya masing-masing berdasarkan jarak yang terdefinisi pada petunjuk tersebut. Semisal terdapat dua buah petunjuk, petunjuk pertama mengatakan bahwa objek A berada di sebelah kanan objek B dengan jarak ruangan sebanyak 2 sedangkan petunjuk kedua mengatakan bahwa objek C berada di sebelah atas objek D dengan jarak lantai tidak diketahui. Melalui kedua petunjuk yang ada, petunjuk pertama akan diberi nilai prioritas lebih besar jika dibandingkan dengan petunjuk kedua karena pada petunjuk pertama, nilai jarak antar objek terdefinisi dengan jelas sedangkan pada petunjuk kedua tidak. Hal ini akan mengurangi jumlah evaluasi simpul yang terjadi pada tahap ke-𝑛 dari hasil pembangkitan simpul. Misal kedua petunjuk di atas terdefinisi pada sebuah board berukuran 4x4. Pada satu buah baris

0, 𝐹𝑛 = { (𝑛 − 1) + 𝐹𝑛−1 ,

𝑛=0 𝑛>0

Rumus tersebut di atas merupakan rumus jumlah simpul yang mingkin dibangkitkan untuk pembangkitan suatu petunjuk apabila terdefinisi dua buah objek pada petunjuk tersebut dan tidak diketahui jarak di antara dua buah objek tersebut. Sesuai dengan rumus di atas, tingkat prioritas pembangkitan simpul menggunakan fungsi pembangkit didasari pada jarak yang terdefinisi pada suatu petunjuk dengan petunjuk yang memiliki jarak konkret lebih diprioritaskan dengan yang tidak diketahui serta untuk petunjuk dengan jarak konkret, yang memiliki nilai lebih besar lebih diprioritaskan karena semakin mengurangi jumlah simpul yang mungkin dibangkitkan pada tahap tersebut. c. Fungsi pembatas Untuk pohon ruang status yang telah didapatkan, fungsi pembatas diterapkan apabila suatu simpul telah dievaluasi sebagai simpul n, maka simpul dengan elemen tuple yang sama dengan simpul tidak akan dievaluasi karena merujuk pada peraturan yang terdefinisi dari permainan Inspector Parker, suatu objek tidak akan dapat berada pada dua ruangan yang berbeda dan hanya akan terdapat satu buah objek pada satu buah ruangan dalam suatu level permainan di Inspector Parker. Fungsi pembatas juga diterapkan apabila setelah simpulsimpul yang berhasil dievaluasi, terdapat setidaknya satu buah ruangan yang tidak memiliki satu buah kemungkinan solusi. Hal ini akan menuntut skema runut balik karena sudah pasti hasil analisis pencarian solusi pada tahap tersebut adalah salah. Sesuai dengan ketiga properti runut balik yang terdefinisi di atas, permainan Inspector Parker dapat dilakukan dengan tahap sebagai berikut. 1. Lakukan pembangkitan dengan urutan pembangkitan adalah petunjuk dengan nilai prioritas paling besar pada antrian petunjuk yang terdefinisi. 2. Pilih salah satu simpul yang berhasil dibangkitkan pada pohon ruang status lalu evaluasi simpul tersebut. 3. Setelah pemilihan simpul pada tahap sebelumnya, terapkan metode awal pembatasan berupa penghilangan semua kemungkinan objek pada petunjuk yang sedang dievaluasi pada ruangan-ruangan yang lain.


Apabila ditemukan setidaknya satu buah ruangan yang kosong tanpa kemungkinan solusi, terapkan fungsi pembatas di mana semua anak pada simpul yang sedang dievaluasi dibunuh hingga menjadi simpul mati (dead node). Dalam hal ini, aliran pencarian menuntut terjadinya skema runut balik pada pohon ruang status, yaitu mengevaluasi simpul tetangga dari simpul sebelumnya. 5. Penelusuran simpul terus dilakukan sampai ditemukan simpul dimana semua petunjuk telah berhasil dievaluasi dan tidak menyisakan kekosongan himpunan solusi pada satu pun ruangan yang belum terisi. 6. Penyelesaian permainan diakhiri dengan pengisian ruangan yang belum terisi penuh dengan himpunan solusi yang mungkin yang terdefinisi padanya. Berikut adalah potongan kode program yang digunakan untuk memecahkan persoalan permainan Inspector Parker. Pada blok ini terdapat contoh pendefinisian setiap informasi yang terdapat pada permainan.

Suspect("Borris"));

public void initializingTheBoard() { this.numObjectPerBox = 1; this.row = 2; this.column = 3; this.boardGame = new Box[this.row][this.column]; this.clues = new ArrayList<>(); this.solvedTemporarily = new ArrayList<>();

public void solveInspectorParker() { doDeduction(); // tahap awal deduksi createTrees(); //pembuatan pohon solusi examineResult(); //validasi tahap lanjut solveMystery(0); //solusi rekursif }

4.

/* creating every board */ this.boardGame[0][0] = new Box("Bedroom"); this.boardGame[0][0].addObject(new Weapon("Bottle")); this.boardGame[0][0].addObject(new Weapon("Pistol")); this.boardGame[0][1] = new Box("Upstairs"); this.boardGame[0][1].addObject(new Weapon("Knife")); this.boardGame[0][2] = new Box("Baby Room"); this.boardGame[0][2].addObject(new Weapon("Bottle")); this.boardGame[0][2].addObject(new Weapon("Pistol"));

this.boardGame[1][2] = new Box("Living Room"); this.boardGame[1][2].addObject(new Suspect("Portia")); this.boardGame[1][2].addObject(new Suspect("Maurice")); this.boardGame[1][2].addObject(new Suspect("Borris")); /* creating every clue information */ this.clues.add(new Clue(new Suspect("Borris"), "?", new Suspect("Maurice"), "Horizontal")); this.clues.add(new Clue(new Suspect("Portia"), "?", new Room("Living room"), "Horizontal")); this.clues.add(new Clue(new Weapon("Bottle"), "?", new Suspect("Portia"), "Vertical")); }

Untuk pemecahan persoalan digunakan skema runut balik secara rekursif dalam mengevaluasi setiap petunjuk yang diberikan. Berikut adalah potongan kode program untuk memecahkan misteri Inspector Parker.

public void solveMystery(int i) { while (i
this.boardGame[1][0] = new Box("Dinning Room"); this.boardGame[1][0].addObject(new Suspect("Portia")); this.boardGame[1][0].addObject(new Suspect("Maurice")); this.boardGame[1][0].addObject(new Suspect("Borris")); this.boardGame[1][1] = new Box("Downstairs"); this.boardGame[1][1].addObject(new Suspect("Portia")); this.boardGame[1][1].addObject(new Suspect("Maurice")); this.boardGame[1][1].addObject(new

Pengimplementasian skema runut balik untuk memecahkan misteri pembunuhan pada permainan Inspector Parker menggunakan teorema rekursif dengan tahap secara keseluruhan seperti yang terlihat pada blok kode program di atas. Pada akhir pemecahan misteri, dapat ditemukan hasil jawaban berupa pemecahan permainan seperti pada Gambar 5 sebagai berikut.


kepada kedua orang tua penulis yang telah mendidik dan membesarkan penulis dengan penuh kasih sayang. Selanjutnya, penulis juga mengucapkan terima kasih kepada Bapak Dr. Ir. Rinaldi Munir, MT. serta Ibu Dr. Nur Ulfa Maulidevi, S.T., M.Sc. selaku dosen pengajar mata kuliah Strategi Algoritma atas segala bimbingan serta ilmu yang telah diberikan kepada penulis. Tidak lupa penulis sampaikan pula rasa terima kasih kepada rekan-rekan penulis yang selalu mendukung, mendorong, serta memberi semangat kepada penulis dalam menyelesaikan makalah ini. Terakhir, penulis juga menyampaikan terima kasih kepada seluruh pihak yang ikut membantu pembuatan makalah ini baik yang secara langsung maupun tidak langsung. Gambar 6. Hasil pemecahan misteri pada Gambar 5

REFERENSI VI. KESIMPULAN

[1]

Permainan berbasis puzzle logika kerap kali diselesaikan dengan cara brute force. Namun, penyelesaian hal ini sangat tidak baik untuk permainan seperti Inspector Parker yang memiliki banyak sekali himpunan solusi sebagai hasil dari kombinasi yang mungkin didapat pada setiap level permainan. Penerapan skema runut balik dalam memecahkan misteri permainan Inspector Parker merupakan salah satu metode yang lebih baik jika dibandingkan menggunakan algoritma exhaustive search (brute foce) yang memiliki kompleksitas waktu komputasi ekspononensial. Selain mengeliminasi segala kemungkinan yang pasti tidak menghasilkan solusi, kita dapat melakukan kombinasi antara skema runut balik dengan teori logika untuk permainan berbasis logika seperti ini. Hal yang dapat dilakukan untuk mengurangi jumlah simpul yang harus dibangkitkan untuk pohon ruang status adalah dengan menggunakan metode deduksi. Metode deduksi logika pada permainan ini diterapkan berdasarkan informasi awal yang didapatkan pada saat memulai permainan, yaitu segala petunjuk mengenai tata letak objek pada setiap ruang pada board yang terdefinisi. Penarikan kesimpulan awal menghasilkan eliminasi banyak objek pada beberapa ruang menuntun pada solusi dengan skema runut balik yang lebih optimal. Pada akhirnya, simpul pada pohon ruang status yang dibangkitkan pada saat penerapan algoritma runut balik akan berkurang jauh. Hal ini akan sangat berguna untuk mencari solusi permasalahan pada permainan Inspector Parker yang jumlah calon solusinya meningkat drastis seiring penambahan level sebagai akibat dari ukuran board serta jumlah objek yang bertambah.

[2]

[3] [4] [5] [6]

https://www.cs.montana.edu/~richter/cs436notes/australiabacktrack.gif, diakses pada 5 Mei 2015. MediaCT, Ipsos, The 2014 Essential Facts About the Computer and Video Game Industry, Entertaiment Software Association, April 2014. halaman 2-3. Sternberg, R. J., Cognitive Psychology, Belmont, CA: Wadsworth, 2009. halaman 578. Munir, Rinaldi, Diktat Kuliah IF2211: Strategi Algoritma, Bandung: Institut Teknologi Bandung, 2007. Donald E. Knuth, The Art of Computer Programming, Addison-Wesley, 1968. http://www.bigfishgames.com/games/94/inspectorparker/, diakses pada 4 Mei 2015.

PERNYATAAN Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain, dan bukan plagiasi.

VII. UCAPAN TERIMA KASIH Pada kesempatan ini, penulis mengucapkan terima kasih kepada Tuhan Yang Maha Esa atas segala kenikmatan yang telah diberikan baik berupa nikmat iman, kesehatan, maupun kekuatan dalam menyusun makalah ini. Penulis juga mengucapkan terima kasih Makalah IF2211 Strategi Algoritma – Sem. II Tahun 2014/2015

Bandung, 5 Mei 2015

Tifani Warnita (13513055)

Penerapan Deduksi Logika dan Skema Runut Balik dalam Memecahkan Misteri pada Permainan Inspector Parker

Recommend Documents