IMPLEMENTASI ALGORITMA ITERATIVE DEEPENING SEARCH (IDS) PADA GAME EDUCATION PUZZLE KATA MENGGUNAKAN MOBILE TECHNOLOGY
TUGAS AKHIR Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Oleh :
CHANDRA BAYU KRISTANTO 06560235
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2012
LEMBAR PENGESAHAN IMPLEMENTASI ALGORITMA ITERATIVE DEEPENING SEARCH (IDS) PADA GAME EDUCATION PUZZLE KATA MENGGUNAKAN MOBILE TECHNOLOGY
TUGAS AKHIR Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang Disusun Oleh : CHANDRA BAYU KRISTANTO NIM. 06560235
Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal 25 Juli 2012 Menyetujui, Penguji I
Penguji II
Wahyu Andhyka Kusuma, S.Kom
Lailatul Husniah, S.ST
NIDN: 0720068701
NIDN : 0730108401
Mengetahui, Ketua Jurusan Teknik Informatika
Eko Budi Cahyono, S.Kom, M.T NIP : 10895040330
KATA PENGANTAR Dengan memanjatkan puji syukur kehadirat Allah SWT. Atas limpahan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan tugas akhir berjudul. “IMPLEMENTASI ALGORITMA ITERATIVE DEEPENING SEARCH (IDS) PADA GAME EDUCATION PUZZLE KATA MENGGUNAKAN MOBILE TECHNOLOGY” Di dalam tulisan ini disajikan pokok-pokok bahasan yang meliputi perancangan aplikasi game edukasi dengan menggunakan mobile technology. Dalam tulisan ini Anda akan diajak untuk mengenal, memahami, dan mengimplementasikan Algoritma Iterative Deepening Search (IDS) Pada Game Education Puzzle Kata Menggunakan Mobile Technology. Penulis menyadari sepenuhnya bahwa dalam penulisan tugas akhir ini masih
banyak kekurangan dan keterbatasan. Oleh karena
itu penulis
mengharapkan saran yang membangun agar tulisan ini bermanfaat bagi perkembangan ilmu pengetahuan kedepan.
Malang, 19 Januari 2013
Penulis
DAFTAR ISI ABSTRAK ..................................................................................................... i ABSTRACT ................................................................................................... ii LEMBAR PERSEMBAHAN .......................................................................... iii KATA PENGANTAR .................................................................................... iv DAFTAR ISI .................................................................................................. v DAFTAR GAMBAR ...................................................................................... vii DAFTAR TABEL .......................................................................................... ix BAB I PENDAHULUAN ............................................................................... 1 1.1. Latar Belakang .................................................................................. 1 1.2. Rumusan Masalah ............................................................................. 2 1.3. Batasan Masalah ............................................................................... 4 1.4. Tujuan Penelitian .............................................................................. 4 1.5. Metodologi........................................................................................ 4 1.6. Sistematika Penulisan ........................................................................ 6 BAB II LANDASAN TEORI ......................................................................... 8 2.1. Artificial Intelligence (AI) ................................................................. 8 2.2. Algoritma Pencarian .......................................................................... 10 2.2.1. Contoh Pencarian ..................................................................... 11 2.2.2. Algoritma Breadth First Search (BFS) ..................................... 12 2.2.3. Algoritma Depth First Search (DFS) ........................................ 15 2.2.4. Algoritma Iterative Deepening Search (IDS) ............................ 16 2.3. Mobile Technology ............................................................................ 18 2.4. Pengertian Game ............................................................................... 20 2.4.1. Game Sliding Puzzle Kata ........................................................ 21 2.4.2. Android SDK (Software Development Kit) ............................... 23 2.4.3. Kelebihan Android Dibandingkan Platform Lain...................... 24 2.5. Finite State Machine ......................................................................... 25 BAB III PERANCANGAN SISTEM .............................................................. 26 3.1. Perancangan Sistem........................................................................... 26
3.1.1. Bahasa Pemrograman Yang Digunakan .................................... 26 3.1.2. Mobile Technology Yang Digunakan........................................ 26 3.1.3. Use Case Diagram ................................................................... 27 3.1.4. Activity Diagrams ..................................................................... 29 3.1.5. Sequence Diagrams .................................................................. 33 3.1.6. Class Diagram.......................................................................... 35 3.1.7. Finite State Machine Game Puzzle Kata ................................... 36 3.1.8. Desain Interface ....................................................................... 37 BAB IV IMPLEMENTASI DAN PENGUJIAN ............................................. 40 4.1. Implementasi Sistem ......................................................................... 40 4.1.1. Tampilan Awal (Splash Screen) Game Puzzle Kata .................. 41 4.1.2. Tampilan Menu Utama ............................................................. 42 4.1.3. Tampilan Play Game ................................................................ 43 4.1.4. Tampilan Menu Setting ............................................................ 46 4.1.5. Tampilan Permainan Selesai..................................................... 47 4.1.6. Tampilan Score ........................................................................ 48 4.2. Pengujian pada Handphone ............................................................... 48 4.3. Pengujian Algoritma Iterative Deepening Search (IDS)..................... 52 4.3.1. Pengujian Tingkat Kesulitan Easy ............................................ 52 4.3.2. Pengujian Tingkat Kesulitan Normal ........................................ 53 4.3.3. Pengujian Tingkat Kesulitan Hard ........................................... 54 BAB V PENUTUP ......................................................................................... 57 5.1. Kesimpulan ....................................................................................... 57 5.2. Saran ................................................................................................. 57 DAFTAR PUSTAKA ..................................................................................... 58
DAFTAR GAMBAR Gambar 1.1 : Puzzle 2 x 2 ................................................................................ 3 Gambar 1.2 : Puzzle 3 x 3 ................................................................................ 3 Gambar 1.3 : Puzzle 4 x 4 ................................................................................ 3 Gambar 2.1 : Bidang-bidang tugas dari AI ....................................................... 10 Gambar 2.2 : Contoh permainan yang menerapkan pencarian ........................... 11 Gambar 2.3 : Ruang keadaan ............................................................................ 12 Gambar 2.4 : Algoritma pencarian Breadth First Search ................................... 13 Gambar 2.5 : Algoritma Pencarian Depth First Search ..................................... 15 Gambar 2.6 : Algoritma Pencarian IDS ............................................................. 17 Gambar 2.7 : Contoh Sliding Puzzle n-puzzle ................................................... 22 Gambar 2.8 : Contoh Sliding Puzzle Kata ......................................................... 22 Gambar 3.1 : Use Case Diagram ....................................................................... 27 Gambar 3.2 : Activity Diagrams Memilih Menu ................................................ 30 Gambar 3.3 : Activity Diagrams Memulai Game ............................................... 30 Gambar 3.4 : Activity Diagrams Setting ............................................................ 31 Gambar 3.5 : Activity Diagrams Menentukan Tingkat kesulitan ........................ 32 Gambar 3.6 : Activity Diagrams Mengatur Suara .............................................. 32 Gambar 3.7 : Activity Diagrams Melihat Score ................................................. 32 Gambar 3.8 : Sequence Diagrams Play Game ................................................... 33 Gambar 3.9 : Sequence Diagrams Setting .......................................................... 33 Gambar 3.10 : Sequence Diagrams Tingkat kesulitan.......................................... 34 Gambar 3.11 : Sequence Diagrams Pengaturan Suara ......................................... 34 Gambar 3.12 : Sequence Diagrams Score ............................................................ 34 Gambar 3.13 : Class Diagram Game Puzzle Kata ............................................... 35 Gambar 3.14 : Finite State Machine Game Puzzle Kata ...................................... 36 Gambar 3.15 : Tampilan Awal/Splashscreen ...................................................... 37 Gambar 3.16 : Tampilan Menu ........................................................................... 37 Gambar 3.17 : Tampilan Permainan.................................................................... 38 Gambar 3.18 : Tampilan Score ........................................................................... 38
Gambar 3.19 : Tampilan Akhir Permainan .......................................................... 39 Gambar 3.20 : Tampilan Setting ......................................................................... 39 Gambar 4.1 : Splash Screen pada emulator ....................................................... 41 Gambar 4.2 : Potongan Program Splash Screen ................................................ 42 Gambar 4.3 : Menu Utama................................................................................ 42 Gambar 4.4 : Potongan Program Menu Utama .................................................. 43 Gambar 4.5 : Play Game Tingkat Kesulitan Easy ............................................. 43 Gambar 4.6 : Play Game Tingkat Kesulitan Normal ......................................... 43 Gambar 4.7 : Play Game Tingkat Kesulitan Hard ............................................. 44 Gambar 4.8 : Potongan Program Play Game ..................................................... 45 Gambar 4.9 : Potongan Program Algoritma ...................................................... 46 Gambar 4.10 : Menu Setting ............................................................................... 46 Gambar 4.11 : Potongan Program Menu Setting ................................................. 46 Gambar 4.12 : Tampilan Permainan Selesai ........................................................ 47 Gambar 4.13 : Potongan Program Permainan Selesai .......................................... 47 Gambar 4.14 : Tampilan Score ........................................................................... 48 Gambar 4.15 : Potongan Program Tampilan Score .............................................. 48 Gambar 4.16 : Splash Screen pada Handphone ................................................... 49 Gambar 4.17 : Menu Utama pada Handphone .................................................... 49 Gambar 4.18 : Tampilan Play Game pada Handphone ........................................ 50 Gambar 4.19 : Tampilan Permainan Selesai pada Handphone ............................. 50 Gambar 4.20: Tampilan Menu Score pada Handphone....................................... 51 Gambar 4.21 : Tampilan Menu Setting pada Handphone .................................... 51 Gambar 4.22 : Contoh Soal Puzzle Easy ............................................................. 52 Gambar 4.23 : Contoh Soal Puzzle Normal ......................................................... 53 Gambar 4.24 : Contoh Soal Puzzle Hard ............................................................ 54
DAFTAR TABEL
Tabel 3.1 : Spesifikasi Use Case Memainkan Game .......................................... 27 Tabel 3.2 : Spesifikasi Use Case Menentukan Tipe Puzzle ................................ 28 Tabel 3.3 : Spesifikasi Use Case Menentukan Soal ............................................ 28 Tabel 3.4 : Spesifikasi Use Case Mencari Solusi ............................................... 29 Tabel 3.5 : Spesifikasi Use Case Menyimpan Score........................................... 29 Tabel 4.1 : Pengujian Fungsionalitas Aplikasi Game Puzzle Kata ..................... 51 Tabel 4.2 : Pengujian algoritma Iterative Deepening Search pada tingkat kesulitan Easy .................................................................................................. 53 Tabel 4.3 : Pengujian algoritma Iterative Deepening Search pada tingkat kesulitan Normal.............................................................................................. 53 Tabel 4.4 : Pengujian algoritma Iterative Deepening Search pada tingkat kesulitan Hard ................................................................................................. 55
DAFTAR PUSTAKA [1]
Achmad, Rezan. 2009. Penerapan Pohon dan Algoritma Heuristic dalam Menyelesaikan
Sliding
Puzzle.
http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/20092010/Makalah0910/MakalahStrukdis0910-055.pdf, diakses: Maret 2012. [2]
Hendratno, Angga Tri . 2011. Pembuatan Aplikasi Student Access Sistem Absensi Mahasiswa Dan Informasi Daftar Nilai Mahasiswa Pada Sistem Operasi
Android.
http://papers.gunadarma.ac.id/index.php/industry/article/viewFile/697/663, diakses: Juli 2011. [3]
Korf, Richard E. 1996, Artificial Intelligence Search Algorithms. http://lvk.cs.msu.su/~bruzz/articles/IR/korf96artificial.pdf, diakses: Juni, 2012.
[4]
Qian, Ting. 2007. Using Genetic Algorithm to Solve Sliding Tile Puzzles. http://www.cs.oswego.edu/~qian/csc466/Ting%20-%20GA.pdf,
diakses:
Maret 2012. [5]
Rokhman, Moh. Miftakhur. 2011. Finite State Machines (FSM) Sebagai Agen Cerdas Animasi Wajah Dalam Game Assyuhada. http://lib.uinmalang.ac.id/thesis/chapter_ii/07650025-moh-miftakhur-rokhman.ps, diakses: Maret 2012.
[6]
Rohman, Arif. 2011. Rancang Bangun Game Petualangan Berbasis Game Artificial Intelligence Untuk Pembelajaran Bahasa Arab. http://lib.uinmalang.ac.id/thesis/introduction/05550126-rohman-arif.pdf, diakses: Juni 2012.
[7]
Roslianti, Rini. 2011. Education Game Puzzle Kata Multiplayer Pada Handphone
Menggunakan
Mobile
Technology.
Universitas
Muhammadiyah Malang: Malang. [8]
Sabdifha, Noswa. 2010. Perancangan Dan Pembuatan Aplikasi Word Game
Scramble
Pada
Board
Dua
Dimensi.
http://digilib.its.ac.id/public/ITS-Undergraduate-13390-Paper.pdf, diakses: Maret 2012. [9]
Safaat H., Nazruddin. 2011. ANDROID: Pemrograman Aplikasi Mobile Smartphone dan Tablet PC Berbasis Android. Informatika: Bandung.
[10]
Sunaryo, Anthony Rahmat. 2007. Algoritma Pencarian Simpul Solusi Dalam Graf. http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/20072008/Makalah/MakalahIF2153-0708-042.pdf, diakses: Oktober 2011.
[11]
Sutrisno, Rano Tri. 2011. Puzzle Slider Game Development Using Python Version
2.4.1.
http://papers.gunadarma.ac.id/index.php/industry/article/viewFile/11430/1 0933, diakses: Maret 2012. [12]
Yoga S., Budi. 2007. Perancangan Aplikasi Permainan Teka-Teki Silang. http://elib.unikom.ac.id/files/disk1/116/jbptunikompp-gdl-s1-2007budiyogasu-5782-9_bab-ii-i.pdf, diakses: Maret 2012.
