Cover
- 1. ANALISIS DAN IMPLEMENTASI ALGORITMA BACKTRACKING PADA PERMAINAN CONGKLAK SKRIPSI ADHHAL HUDA BAKRI 061401067 PROGRAM STUDI SARJANA ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010 Universitas Sumatera Utara
- 2. ANALISIS DAN IMPLEMENTASI ALGORITMA BACKTRACKING PADA PERMAINAN CONGKLAK SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer ADHHAL HUDA BAKRI 061401067 PROGRAM STUDI SARJANA ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010 Universitas Sumatera Utara
- 3. PERSETUJUAN Judul : ANALISIS DAN IMPLEMENTASI ALGORITMA BACKTRACKING PADA PERMAINAN CONGKLAK Kategori : SKRIPSI Nama : ADHHAL HUDA BAKRI Nomor Induk Mahasiswa : 061401067 Program Studi : SARJANA (S1) ILMU KOMPUTER Departemen : ILMU KOMPUTER Fakultas : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 18 Desember 2010 Komisi Pembimbing : Pembimbing 2 Pembimbing 1 Dian Rachmawati, S.Si, M.Kom Drs. James P. Marbun, M.Kom NIP 198307232009122004 NIP 195806111986031002 Diketahui/Disetujui oleh Departemen Ilmu Komputer FMIPA USU Ketua, Prof. Dr. Muhammad Zarlis NIP 195707011986011003 Universitas Sumatera Utara
- 4. PERNYATAAN ANALISIS DAN IMPLEMENTASI ALGORITMA BACKTRACKING PADA PERMAINAN CONGKLAK SKRIPSI Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya. Medan, 18 Desember 2010 ADHHAL HUDA BAKRI 061401067 Universitas Sumatera Utara
- 5. PENGHARGAAN Alhamdulillah penulis ucapkan kepada Sang Khaliq Allah SWT yang melimpahkan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi S1 Ilmu Komputer Departemen Ilmu Komputer Universitas Sumatera Utara. Ucapan terima kasih penulis sampaikan kepada Drs. James P. Marbun, M.Kom selaku pembimbing pertama dan Dian Rachmawati, S.Si, M.Kom selaku pembimbing kedua yang telah banyak meluangkan waktunya dalam memberikan masukan- masukan kepada penulis. Ucapan terima kasih juga ditujukan kepada Drs. Marihat Situmorang, M.Kom dan M. Andri Budiman, ST, M.Comp.Sc, MEM yang telah bersedia menjadi dosen penguji. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Ilmu Komputer, Prof. Dr. Muhammad Zarlis dan Syahriol Sitorus, S.Si, MIT, Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen serta pegawai di Program Studi S1 Ilmu Komputer Departemen Ilmu Komputer FMIPA USU. Tidak lupa juga penulis ucapkan terima kasih kepada Ayahanda Drs. Zulbakri dan Ibunda Netty Juwita yang memberikan dukungan, doa, dan semangat tanpa henti. Untuk adik penulis, M Aziz Bakri yang selalu memberikan dorongan kepada penulis serta Mirnawati yang selalu memberi perhatian dan dorongan kepada penulis selama menyelesaikan skripsi ini. Terima kasih penulis ucapkan kepada teman-teman yang selalu memberikan dukungan, Sonavia Tanius, Nurjannah, Hadianto, M Anggi Rivai Nst, Mhd Makmur Rasyid Lbs, Denis Afriawanto dan Edwin Prawiro Hakim serta teman-teman satu angkatan yang sama-sama berjuang dalam penyusunan skripsi. Sekali lagi penulis mengucapkan terima kasih kepada semua pihak yang membantu dalam penyelesaian tugas akhir ini yang tidak dapat disebutkan satu persatu, terima kasih atas ide, saran dan motivasi yang diberikan. Semoga Tuhan Yang Maha Esa memberikan limpahan karunia kepada semua pihak yang telah memberikan bantuan, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini. Universitas Sumatera Utara
- 6. ABSTRAK Permainan congklak merupakan salah satu permainan tradisional yang berasal dari Indonesia. Permainan ini dimainkan oleh dua pemain dengan menggunakan sebuah papan congklak dan biji congklak yang berjumlah 14 x 7 buah. Pada permainan ini, diterapkan sebuah agen cerdas sebagai salah satu pemain. Agen cerdas adalah sesuatu yang dapat mengamati dan merasakan lingkungannya melalui sensor dan memberikan tindakan terhadap lingkungan tersebut melalui actuator. Agen cerdas akan menjadi salah satu pemain dengan menggunakan algoritma Backtraking. Algoritma backtracking merupakan perbaikan dari algoritma brute force yang tidak menelusuri seluruh kemungkinan solusi tetapi hanya pencarian yang mengarah ke solusi saja yang dipertimbangkan. Melalui pembahasan dalam tulisan ini, algoritma backtracking digunakan untuk memilih langkah optimal yang akan diambil agen dari lubang-lubang pada arena milik agen untuk mengumpulkan biji sebanyak-banyaknya ke dalam lumbung. Pada tulisan ini, permainan ini dibangun dengan menggunakan Delphi 7.0. Melalui pengujian secara kuisoner, kehandalan agen cerdas ini tergolong handal dengan persentase kemenangan dengan pemain bermain terlebih dahulu sebesar 75% dan agen bermain terlebih dahulu sebesar 100%. Universitas Sumatera Utara
- 7. ANALYSIS AND IMPLEMENTATION BACKTRACKING ALGORITHM ON CONGKLAK GAME ABSTRACT Congklak game is one of the traditional game which is originated from Indonesia. The game is played by two players using a congklak¡¯s board and congklak¡¯s seeds, amounting to 14 x 7 pieces. In this game, an intelligent agent is applied as one of the players. Intelligent agent is something that can observe and experience their environment via sensors and provides action to the environment via actuators. Intelligent agent will be one of the players with Backtraking Algorithm. Backtracking algorithm is a refinement of brute-force algorithm that do not search all possible solutions but the only search that leads to the solution are considered. Through the discussion in this paper, backtracking algorithm is used to select the optimal step to be taken by agent from the holes in the arena of agents to collect as many seeds into the barn. In this paper, the game is developed by using Delphi 7.0. Through testing the questionnaire, the reliability of intelligent agents is quite reliable with victory percentage with the first is player¡¯s turn by 75% and the first is agent¡¯s turn by 100%. Universitas Sumatera Utara
- 8. DAFTAR ISI Halaman Persetujuan ii Pernyataan iii Penghargaan iv Abstrak v Abstract vi Daftar Isi vii Daftar Tabel ix Daftar Gambar x Bab 1 Pendahuluan 1 1.1 Latar Belakang 1 1.2 Rumusan Masalah 2 1.3 Batasan Masalah 2 1.4 Tujuan Penelitian 3 1.5 Manfaat Penelitian 3 1.6 Metode Penelitian 3 1.7 Sistematika Penulisan 4 Bab 2 Tinjauan Teoretis 6 2.1 Kecerdasan Buatan 6 2.1.1 Intelligent Agent (Agen Cerdas) 7 2.1.2 Penggunaan Kecerdasan Buatan di berbagai Bidang 8 2.2 Game 9 2.2.1 Sejarah Game 10 2.2.2 Klasifikasi Game 11 2.3 Permainan Congklak 12 2.3.1 Sejarah Permainan Congklak 12 2.3.2 Peraturan Permainan Congklak 13 2.4 Searching (Pencarian) 17 2.5 Depth-First Search (DFS) 17 2.6 Algoritma Runut-Balik (Backtracking Algorithm) 18 2.6.1 Properti Umum Metode Runut-Balik 19 2.6.2 Prinsip Pencarian Solusi dengan Metode Runut-Balik 19 Bab 3 Analisis dan Perancangan Sistem 23 3.1 Analisis Kebutuhan Sistem 23 3.1.1 Analisis Arena Permainan 23 3.1.2 Analisis Algoritma 24 3.2 Perancangan Sistem 29 3.2.1 Perancangan Alur Permainan 29 3.2.1.1 Flowchart Abacktracking() 32 3.2.1.2 Flowchart Bermain() 33 Universitas Sumatera Utara
- 9. 3.2.1.3 Flowchart Tembak() 34 3.2.1.4 Flowchart CekbijiArena() 35 3.2.1.5 Flowchart Hitungskor() 36 3.2.2 Perancangan Aplikasi Permainan 37 3.2.3 Perancangan Antarmuka 38 Bab 4 Implementasi dan Pengujian 44 4.1 Implementasi Sistem 44 4.2 Spesifikasi Perangkat Lunak 44 4.3 Spesifikasi Perangkat Keras 44 4.4 Tampilan Aplikasi 45 4.4.1 Tampilan Utama 45 4.4.2 Tampilan Arena Permainan 46 4.4.3 Tampilan Undi Giliran 46 4.4.4 Tampilan Permainan 47 4.4.5 Tampilan History Permainan 48 4.4.6 Tampilan Panduan Permainan 49 4.4.7 Tampilan Tentang Permainan 50 4.5 Pengujian Aplikasi 51 4.5.1 Pengujian Integrasi Aplikasi 51 4.5.1.1 Proses pada Tampilan Utama 52 4.5.1.2 Proses pada Tampilan Panduan Permainan 52 4.5.1.2 Proses pada Tampilan Tentang Permainan 53 4.5.1.2 Proses pada Tampilan Undi Giliran 53 4.5.1.2 Proses pada Tampilan History Permainan 54 4.5.1.2 Proses pada Tampilan Arena Permainan 55 4.5.2 Pengujian Aspek Antarmuka Aplikasi 56 4.5.3 Pengujian Aspek Penggunaan Aplikasi 58 4.5.4 Pengujian Penilaian Aplikasi 60 4.5.5 Pengujian Aspek Kehandalan Aplikasi 61 Bab 5 Kesimpulan dan Saran 63 5.1 Kesimpulan 63 5.2 Saran 64 Daftar Pustaka 65 Lampiran 66 Universitas Sumatera Utara
- 10. DAFTAR TABEL Halaman Tabel 4.1 Hasil Evaluasi Proses pada Tampilan Utama pada Windows 52 Tabel 4.2 Hasil Evaluasi Proses pada Tampilan Panduan Permainan pada Windows 53 Tabel 4.3 Hasil Evaluasi Proses pada Tampilan Tentang Permainan pada Windows 53 Tabel 4.4 Hasil Evaluasi proses pada Tampilan Undi Giliran pada Windows 54 Tabel 4.5 Hasil Evaluasi proses pada Tampilan History Permainan pada Windows 54 Tabel 4.6 Hasil Evaluasi proses pada Tampilan Arena Permainan pada Windows 55 Tabel 4.7 Hasil Kuisioner Aspek Antarmuka 57 Tabel 4.8 Hasil Kuisioner Aspek Penggunaan 59 Tabel 4.9 Hasil Kuisioner Penilaian Aplikasi 60 Tabel 4.10 Hasil Kuisioner Kehandalan Aplikasi 62 Universitas Sumatera Utara
- 11. DAFTAR GAMBAR Halaman Gambar 2.1 Ilustrasi dari Agent 8 Gambar 2.2 Peralatan Permainan Congklak 13 Gambar 2.3 Proses terjadinya kondisi 4a 14 Gambar 2.4 Proses terjadinya kondisi 4b 15 Gambar 2.5 Proses giliran permainan berakhir 16 Gambar 2.6 DFS untuk mencari simpul j 17 Gambar 2.7 Pohon ruang kemungkinan solusi persoalan 4-Ratu 21 Gambar 2.8 Penelusuran Solusi Backtraking 4-Ratu pada papan catur 22 Gambar 2.9 Pohon pencarian solusi dengan Backtraking pada persoalan 4-Ratu 22 Gambar 3.1 Papan permainan congklak 23 Gambar 3.2 Keadaan papan permainan congklak untuk strategi a 27 Gambar 3.3 Pohon penelusuran backtracking untuk hasil C7 28 Gambar 3.4 Keadaan papan permainan congklak untuk strategi b 28 Gambar 3.5 Pohon penelusuran backtracking untuk hasil C2 29 Gambar 3.6 Flowchart Alur Permainan 30 Gambar 3.7 Flowchart Abacktracking() 32 Gambar 3.8 Flowchart Bermain() 33 Gambar 3.9 Flowchart tembak() 34 Gambar 3.10 Flowchart CekbijiArena() 35 Gambar 3.11 Flowchart HitungSkor() 36 Gambar 3.12 Flowchart Aplikasi 37 Gambar 3.13 Form Utama 38 Gambar 3.14 Form Undi Giliran 39 Gambar 3.15 Form Panduan Permainan 40 Gambar 3.16 Form Tentang Permainan 41 Gambar 3.17 Form History Permainan 42 Gambar 3.18 Form Arena Permainan 43 Gambar 4.1 Tampilan Utama 45 Gambar 4.2 Arena Permainan 46 Gambar 4.3 Tampilan Undi Giliran 47 Gambar 4.4 Kondisi saat permainan berlangsung 47 Gambar 4.5 Message Dialog 48 Gambar 4.6 Tampilan History Permainan 49 Gambar 4.7 Tampilan Panduan Permainan 50 Gambar 4.8 Tampilan Tentang Permainan 50 Universitas Sumatera Utara