IMPLEMENTASI METODE GENERATE AND TEST DALAM PENYELESAIAN PUZZLE 2048 BERBASIS MOBILE
SKRIPSI DEVINA PRATIWI HALIM 101401094
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA 2016
Universitas Sumatera Utara
IMPLEMENTASI METODE GENERATE AND TEST DALAM PENYELESAIAN PUZZLE 2048 BERBASIS MOBILE SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer
DEVINA PRATIWI HALIM 101401094
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016
Universitas Sumatera Utara
PERSETUJUAN
Judul
:
Kategori Nama Nomor Induk Mahasiswa Program Studi Fakultas
: : : : :
IMPLEMENTASI METODE GENERATE AND TEST DALAM PENYELESAIAN PUZZLE 2048 BERBASIS MOBILE SKRIPSI DEVINA PRATIWI HALIM 101401094 SARJANA (S1) ILMU KOMPUTER ILMU KOMPUTER DAN TEKNOLOGI INFORMASI
Diluluskan di Medan, 2 Nopember 2016 Komisi Pembimbing Pembimbing 2
Pembimbing 1
Rahmat Aulia, S.Kom, M.Sc.IT
Ade Candra, ST, M. Kom
NIP
NIP 197909042009121002
-
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP 196203171991031001
Universitas Sumatera Utara
iii
PERNYATAAN
IMPLEMENTASI METODE GENERATE AND TEST PADA PERMAINAN PUZZLE 2048 BERBASIS MOBILE
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, 2 Nopember 2016
Devina Pratiwi Halim 101401094
Universitas Sumatera Utara
iv
PENGHARGAAN
Segala puji dan syukur penulis ucapkan kehadirat Tuhan Yang Maha Esa yang telah memberikan rahmat dan karunia-Nya kepada penulis sehingga dapat menyelesaikan skripsi ini tepat waktu sesuai dengan instruksi dan peraturan yang berlaku di Fakultas Ilmu Komputer dan Teknologi Informasi. Dalam penyusunan dan penulisan skripsi ini, penulis banyak mendapat bantuan, dukungan, dan bimbingan dari berbagai pihak.Pada kesempatan ini penulis ingin mengucapkan rasa terima kasih dan penghargaan kepada :
1. Bapak Prof. Dr. Runtung Sitepu, SH, M.Hum selaku Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. Opim Salim Sitompul, M.Sc sebagai Dekan Fakultas Ilmu Komputer dan Teknologi Informasi. 3. Bapak Dr. Poltak Sihombing, M.Kom sebagai Ketua Program Studi S-1 Ilmu Komputer dan selaku penguji I yang telah memberikan kritik, saran dan dukungan kepada penulis dalam menyelesaikan skripsi ini. 4. Ibu Dian Rachmawati, S.Si,M.Kom selaku Kepala Studio Lab TA S-1 Ilmu Komputer. 5. Ibu Dr. Elviawaty M Z, ST, MT, MM, selaku dosen penguji II yang memberikan kritik, saran dan dukungan kepada penulis dalam menyelesaikan skripsi ini 6. Bapak Ade Candra, ST, M. Kom, selaku dosen pembimbing I yang telah memberikan saran dan dukungan kepada penulis dalam menyelesaikan skripsi ini 7. Bapak Rahmat Aulia, S.Kom, M.Sc.IT, selaku dosen pembimbing II yang memberikan saran dan dukungan kepada penulis dalam menyelesaikan skripsi ini 8. Seluruh dosen S-1 Ilmu Komputer atas semua ilmu yang telah diberikan kepada penulis selama masa pendidikan di S-1 Ilmu Komputer USU. 9. Seluruh staf pegawai Fakultas Ilmu Komputer dan Teknologi Informasi, terkhusus buat abangda Faisal Hamid dan kakanda Dwi.
Universitas Sumatera Utara
v
10. Teristimewa orang tua yang penulis sayangi, ibunda Hermina dan ayahanda Halim yang tidak henti-hentinya memberikan doa, motivasi, dan dukungan yang selalu menjadi sumber semangat penulis. 11. Adik tersayang Dea Nora, Natasha Valmay, dan Nathan Alexander yang telah memberikan dukungan terhadap penulis agar dapat menyelesaikan skripsi ini. 12. Sahabat Ricky Steven yang memberi semangat danmotivasi kepada penulis 13. Sahabat- sahabat dekat Cabin 9 yang tetap menyemangati dan memberi nasehat kepada penulis. 14. Teman – teman dari stambuk 2010 yang tetap menyemangati penulis untuk tidak berhenti menyelesaikan skripsi ini. 15. Semua pihak yang terlibat langsung ataupun tidak langsung yang tidak dapat penulis ucapkan satu per satu yang telah membantu menyelesaikan skripsi ini. Penulis menyadari bahwa skripsi ini masih memiliki banyak kekurangan, baik dari segi teknik, tata penyajian ataupun dari segi tata bahasa. Oleh karena itu, penulis bersedia menerima kritik dan saran dari pembaca dalam upaya perbaikan skripsi ini. Semoga skripsi ini dapat bermanfaat bagi penulis dan pembaca, khususnya rekan – rekan mahasiswa lainnya yang mengikuti perkuliahan di Universitas Sumatera Utara.
Medan, 2 Nopember 2016 Penulis
Devina Pratiwi Halim NIM. 101401094
Universitas Sumatera Utara
vi
ABSTRAK
Kecerdasan buatan sering digunakan untuk menyelesaikan masalah dengan suatu metode yang konkrit, salah satunya adalah untuk membuat solusi untuk permainan 2048. Dalam mencapai poin 2048 pada permainannya, dapat digunakan beberapa algoritma dimana salah satunya adalah metode generate and test. Metode generate and test adalah algoritma yang membangkitkan semua n langkah yang memungkinkan dan mengambil langkah yang mendapatkan poin yang tertinggi. Kecerdasan buatan kemudian akan menjalankan langkah – langkah yang dapat menghasilkan poin yang ingin dicapai. Dalam membangkitkan n yang berbeda, maka hasil dan waktu yang didapatkan juga akan berbeda. Pembangkitan n yang lebih tinggi akan menghasilkan solusi yang lebih diinginkan namun akan memakan waktu rata- rata yang lebih lama daripada pembangkitan n yang lebih kecil.
Kata kunci: Kecerdasan buatan, Generate and Test , puzzle game 2048.
Universitas Sumatera Utara
vi
IMPLEMENTATION OF GENERATE AND TEST METHODS ON MOBILE BASED PUZZLE GAME 2048
ABSTRACT
Artificial intelligence is often used to solve problems with a concrete method, one of them is to create a solution for game 2048. In reaching point 2048 in the game, there are algorithms that can be used and one of them is generate and test method. Generate and test method is an algorithm that generate every possible n - steps possibility and determined the best steps with the highest point. Then, the artificial intelligence will perform the steps that will produce the specified point. For n different generation will produce different results and different time. For higher n will produce a more desirable solution, however it will take longer time. Kata kunci: Artificial Inteligence, Generate and Test, puzzle game 2048.
Universitas Sumatera Utara
viii
DAFTAR ISI
Halaman Persetujuan ................................................................................................................ ii Pernyataan .................................................................................................................. iii Penghargaan ............................................................................................................... iv Abstrak ....................................................................................................................... vi Abstract ...................................................................................................................... vii Daftar isi ..................................................................................................................... viii Daftar Gambar............................................................................................................ x Daftar Tabel .............................................................................................................. xi Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
1 2 2 3 3 3 4
Bab 2 Tinjauan Pustaka 2.1 Kecerdasan Buatan 2.1.1 Turing Test 2.2 Bidang – Bidang Terapan pada Kecerdasan Buatan 2.3 Metode Pencarian Heuristik 2.3.1 Generate and Test 2.3.1.1 Algoritma Generate and Test 2.4 Unity 2.4.1 Fitur – Fitur Pada Unity 2.4.1.1 Rendering 2.4.1.2 Scripting 2.4.1.3 Asset Tracking 2.4.1.4 Multi-Platform 2.4.1.5 Asset Store 2.4.1.6 Physics Engine 2.5 Android
5 7 8 9 9 11 12 13 13 13 14 14 14 15 15
Bab 3 Analisis dan Perancangan sistem 3.1 Analisis 3.1.1 Analisis Masalah (Problem Analysis) 3.1.2 Analisis Persyaratan (Requirement Analysis) 3.1.2.1 Persyaratan Fungsional
16 16 17 17
Universitas Sumatera Utara
ix
3.1.2.2 Analisis Persyaratan Non – Fungsional 3.2 Pemodelan Perangkat Lunak 3.2.1 Use-Case Diagram 3.2.1.1 Use Case Generate and Test 3.2.2 Activity Diagram 3.2.3 Sequence Diagram 3.3 Flowchart System 3.3.1 Flowchart menentukan langkah terbaik 3.4 Pseudocode Sistem 3.5 Perancangan Antarmuka Pengguna (User Interface)
17 18 18 19 20 22 22 24 24 27
Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi Sistem 4.1.1 Tampilan Permainan 4.2 Perhitungan Manual 4.3 Pengujian Sistem
28 28 30 31
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
35 35
Daftar Pustaka
36
Lampiran Lampiran Lampiran Lampiran Lampiran Lampiran
A B C D E F
A-1 B-1 C-1 D-1 E-1 F-1
Universitas Sumatera Utara
x
DAFTAR GAMBAR Halaman Gambar 2.1
Ilustrasi Lintasan Metode Generate and Test
10
Gambar 2.2
Ilustrasi Alur pencarian Generate and Test untuk pencarian 4 langkah
10
Gambar 3.1
Diagram Ishikawa untuk Analisis Permasalah Sistem
16
Gambar 3.2
Use Case Generate and Test
18
Gambar 3.3
Activity Diagram Generate and Test
21
Gambar 3.4
Sequence Diagram Generate and Test
22
Gambar 3.5
Flowchart Sistem
23
Gambar 3.6
Flowchart Langkah Terbaik
24
Gambar 3.7
Rancangan Tampilan Pertama
27
Gambar 4.1
Tampilan Permainan (Gameplay Scene)
28
Gambar 4.2
Tampilan Berhasil
29
Gambar 4.3
Tampilan Gagal
30
Gambar 4.4
Ilustrasi Pembangkitan Untuk 2 Langkah
30
Gambar 4.5
Grafik perbandingan waktu mencapai 1024
33
Gambar 4.6
Grafik perbandingan waktu mencapai 2048
34
Universitas Sumatera Utara
xi
DAFTAR TABEL
Halaman 11
Tabel 2.1
Hasil lintasan terpendek menggunakan Generate and Test
Tabel 3.1
Spesifikasi Use Case Generate and Test
19
Tabel 4.1
Hasil Perhitungan Jumlah Iterasi untuk n buah langkah
31
Tabel 4.2 Tabel 4.3
Hasil Pengujian program terhadao waktu dan keberhasilan program dengan 5 langkah Hasil Pengujian program terhadap waktu dan keberhasilan program dengan 6 langkah
32 32
Universitas Sumatera Utara
