PENERAPAN ALGORITMA GREEDY PADA PERMAINAN MILL BERBASIS ANDROID
SKRIPSI
SUANDO H SIMANJUNTAK 091402035
PROGRAM STUDI TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
PENERAPAN ALGORITMA GREEDY PADA PERMAINAN MILL BERBASIS ANDROID
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Teknologi Informasi
PROGRAM STUDI TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
ii
PERSETUJUAN Judul Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PENERAPAN ALGORITMA GREEDY PADA PERMAINAN MILL BERBASIS ANDROID : SKRIPSI : SUANDO H SIMANJUNTAK : 091402035 : SARJANA (S1) TEKNOLOGI INFORMASI : TEKNOLOGI INFORMASI : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI Diluluskan di Medan, Februari 2015
Komisi Pembimbing
:
Pembimbing 2
Maya Silvi Lydia, B.Sc., M.Sc NIP. 197401272002122001
Diketahui/Disetujui oleh Program Studi Teknologi Informasi Ketua,
M. Anggia Muchtar, ST.,MM.IT NIP. 19800110 200801 1 010
Pembimbing 1
Dr. Erna Budhiarti Nababan, M.IT NIP. -
iii
PERNYATAAN
PENERAPAN ALGORITMA GREEDY PADA PERMAINAN MILL BERBASIS ANDROID SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Februari 2015
SUANDO H SIMANJUNTAK 091402035
iv
UCAPAN TERIMA KASIH
Segala puji dan syukur penulis panjatkan kepada Tuhan Yesus Kristus atas segala berkat dan pengasihanNya yang sungguh berlimpah, sehingga penulis dapat menyelesaikan skripsi ini sebagai syarat untuk memperoleh gelar Sarjana Teknologi Informasi Program Studi S1 Teknologi Informasi Universitas Sumatera Utara. Penyelesaian skripsi ini tidak terlepas dari bantuan dari berbagai pihak, untuk itu, penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada: 1. Kedua orangtua penulis yang telah memberikan dukungan moril dan spiritual, terlebih ayah penulis, Theo Simanjuntak, SE., MM. (+) yang terlebih dahulu meninggalkan dunia saat masa akhir perkuliahan penulis. Penulis juga mengucapkan terima kasih untuk ibu penulis, Rony Herawati Siahaan yang selalu sabar dalam membesarkan dan mendidik penulis hingga saat ini. 2. Ibu Dr. Erna Budhiarti Nababan, M.IT dan Ibu Maya Silvi Lydia, B.Sc., M.Sc selaku pembimbing yang telah banyak meluangkan waktu dan pikirannya, memotivasi dan memberikan kritik dan saran kepada penulis. 3. Bapak Dedy Arisandi, ST., M.Kom dan Bapak Baihaqi Siregar, S.Si., M.T yang telah bersedia menjadi dosen pembanding yang telah memberikan kritik dan saran kepada penulis. 4. Ketua dan Sekretaris Program Studi Teknologi Informasi, Bapak M. Anggia Muchtar, ST.,MM.IT dan Bapak M. Fadly Syahputra, B.Sc.,M.Sc.IT. 5. Terima kasih juga penulis ucapkan kepada teman-teman, Dessy, Jhoannes, Toni, Boho, Leo, Boho, Robert, Ganesha, Anggreiny, Sion, Stella, Cynthia, Riska, Rogate dan seluruh teman-teman seperjuangan yang tidak dapat disebutkan. Akhir kata, penulis ucapkan terimakasih kepada semua pihak yang telah membantu menyelesaian skripsi ini yang tidak bisa penulis sebutkan satu persatu. Semoga
Tuhan
Yang
Maha
Esa
membalas
kebaikan
kalian
semua.
v
ABSTRAK
Permainan Mill adalah pengembangan dari penggabungan konsep permainan Tic Tac Toe dan permainan Twelve Men's Morris. Permainan mill menggunakan aturan dan konsep permainan Tic Tac Toe yang bertujuan menempatkan 3 bidak masing-masing pemain dalam
suatu garis lurus yang dapat berupa garis
horisontal, vertikal, ataupun diagonal. Algoritma greedy adalah algoritma yang membentuk solusi langkah demi langkah. Pada setiap langkahnya terdapat banyak pilihan yang perlu dieksplorasi dan pada setiap langkahnya harus dibuat keputusan yang terbaik dalam menentukan pilihan. Maksud dari prinsip tersebut adalah pada setiap langkah dalam Algoritma Greedy diambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Fungsi prioritas adalah fungsi yang dipadukan dengan algoritma Greedy yang menjadi strategi peletakan bidak oleh komputer di path yang tersedia pada papan permainan. Tujuan penelitian ini yaitu membangun AI yang dapat melakukan langkah terbaik peletakan bidak pada papan permainan. Hasil yang diperoleh dari aplikasi yang dibangun yaitu penerapan algoritma Greedy yang dipadukan fungsi prioritas dapat membangun AI yang kompetitif untuk melawan pemain.
Kata kunci : Permainan Mill, Greedy, AI.
vi
THE IMPLEMENTATION OF GREEDY ALGORITHM IN MILL GAME ON ANDROID
ABSTRACT
Mill game is the developement of merging concepts Tic Tac Toe game and Twelve Men's Morris game. Mill game using rules and concepts of Tic Tac Toe and Twelve Men's Morris game. Mill game using rules and concepts of Tic Tac Toe game that the aims to put three pawns of each player in a straight line which can be horizontal, vertical, or diagonal lines. Greedy algorithm is an algorithm that form the solution step by step. At each step there are many options that need to be explored and every step should be made the best decision in determining the choice. The intent of this principle is at each step in the Greedy algorithm is taken decision that the optimal for such a step without regard to the consequences in the next step. Priority Function is a function which combined with Greedy algorithm that become pawns by computer laying on the path provided on the game board. The purpose of this research is to build AI that can do the best move laying pawns on the game board. The result obtained from the application built is application the greedy algorithm that combined with priority function which can build a competitive AI to fight against player.
Keywords : Mill Game, Greedy, AI.
vii
DAFTAR ISI
Hal PERSETUJUAN PERNYATAAN UCAPAN TERIMA KASIH ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR BAB I
BAB II
ii iii iv V Vi Vii X Xii
PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Rumusan Masalah
2
1.3 Batasan Masalah
3
1.4 Tujuan Penelitian
3
1.5 Manfaat Penelitian
3
1.6 Metodologi Penelitian
3
1.7 Sistematika Penulisan
4
LANDASAN TEORI
6
2.1 Kecerdasan Buatan (Artificial Intelligence)
6
2.2 Game Playing
6
2.3 Mobile Games
7
2.4 Permainan Mill
7
2.5 Algoritma Greedy
8
2.6 Android
9
2.7 UML (Unified Modeling Language)
12
2.8 Penelitian Terdahulu
13
viii BAB III
ANALISIS DAN PERANCANGAN
14
3.1 Analisis Permainan
14
3.2 Fungsi Prioritas dan Analisis Algoritma Greedy
15
3.2.1 Fungsi Prioritas
15
3.2.2 Analisis Algoritma Greedy
16
3.3 Perancangan Sistem 3.3.1 Flowchart algoritma Greedy
23
3.3.2 Flowchart Aplikasi
24
3.3.3 Pemodelan Visual menggunakan UML
25
3.4 Transisi Layar dan Antarmuka
BAB IV
22
35
3.4.1 Transisi Layar
35
3.4.2 Antarmuka
35
IMPLEMENTASI DAN PENGUJIAN
40
4.1 Implementasi
40
4.1.1 Spesifikasi Perangkat Lunak
40
4.1.2 Spesifikasi Perangkat Keras
40
4.2 Tanpilan Aplikasi
41
4.2.1 Tmpilan Halaman Utama
41
4.2.2 Tampilan Halaman Menu Lawan Komputer
41
4.2.2.1 Pilihan Lomba 1 Mill Lawan Komputer
42
4.2.2.2 Pilihan Lomba Banyak Mill Lawan Komputer
43
4.2.3 Tampilan Halaman Lawan Teman
44
4.2.3.1 Pilihan Lomba 1 Mill Lawan Teman
44
4.2.3.2 Pilihan Lomba 1 Banyak Mill Lawan Teman
45
4.2.4 Halaman Papan Permainan
46
4.2.5 Halaman Statistik
48
4.2.6 Halaman Panduan
49
4.2.7 Halaman Tentang
49
4.3 Pengujian 4.3.1 Pengujian Integrasi
50 50
ix
BAB V
4.3.2 Pengujian Antarmuka Aplikasi
50
4.3.3 Pengujian Penggunaan Aplikasi
53
KESIMPULAN DAN SARAN
56
5.1 Kesimpulan
56
5.2 Saran
56
DAFTAR PUSTAKA
57
x
DAFTAR TABEL Hal Tabel 3.1
Fungsi Prioritas
15
Tabel 3.2
Giliran ke-1 (Pemain)
17
Tabel 3.3
Giliran ke-2 (Komputer)
18
Tabel 3.4
Giliran ke-3 (Pemain)
19
Tabel 3.5
Giliran ke-4 (Komputer)
19
Tabel 3.6
Giliran ke-5 (Pemain)
20
Tabel 3.7
Giliran ke-6 (Komputer)
21
Tabel 3.8
Giliran ke-7 (Pemain)
21
Tabel 3.9
Giliran ke-8 (Komputer)
22
Tabel 3.10
Use Case Mulai Lawan Kmputer
26
Tabel 3.11
Use Case Mulai Lawan Teman
28
Tabel 3.12
Use Case memilih Duluan Main,Level dan Jlh Putaran
29
Tabel 3.13
Use Case Bermain
30
Tabel 3.14
Use Case Evaluasi Langkah
31
Tabel 3.15
Use Case Statistik
32
Tabel 3.16
Use Case Panduan
33
Tabel 3.17
Use Case Tentang
34
Tabel 4.1
Kategori Pemberian Nilai
51
Tabel 4.2
Sasaran Penilaian Antarmuka Aplikasi
51
Tabel 4.3
Sasaran Penilaian Penggunaan Aplikasi
54
xi
DAFTAR GAMBAR Hal Gambar 2.1
Papan Permainan Mill
8
Gambar 2.2
Aristektur platform android
10
Gambar 3.1
Giliran ke-1 (Pemain)
17
Gambar 3.2
Giliran ke-2 (Komputer)
18
Gambar 3.3
Giliran ke-3 (Pemain)
18
Gambar 3.4
Giliran ke-4 (Komputer)
19
Gambar 3.5
Giliran ke-5 (Pemain)
20
Gambar 3.6
Giliran ke-6 (Komputer)
20
Gambar 3.7
Giliran ke-7 (Pemain)
21
Gambar 3.8
Giliran ke-8 (Komputer)
22
Gambar 3.9
Flowchart Algoritma Greedy
23
Gambar 3.10
Flowchart Aplikasi
24
Gambar 3.11
Use Case Aplikasi
26
Gambar 3.12
Activity Diagram Lawan Komputer
27
Gambar 3.13
Activity Diagram Lawan Teman
28
Gambar 3.14
Memilih Duluan Main, Level dan Jumlah Putaran
29
Gambar 3.15
Activity Diagram Bermain
30
Gambar 3.16
Activity Diagram Evaluasi Langkah
31
Gambar 3.17
Activity Diagram Statistik
32
Gambar 3.18
Activity Diagram Panduan
33
Gambar 3.19
Activity Diagram Tentang
34
Gambar 3.20
Transisi Layar
36
Gambar 3.21
Antarmuka Halaman Menu Utama
36
Gambar 3.22
Antarmuka Lawan Komputer dan Lawan Teman
37
Gambar 3.23
Antarmuka Statistik
37
Gambar 3.24
Antarmuka Halaman Panduan
38
Gambar 3.25
Antarmuka Halaman Tentang
38
Gambar 3.26
Antarmuka Papan Permainan
39
Gambar 4.1
Tampilan Halaman Menu Utama
41
Gambar 4.2
Halaman Lawan Komputer
42
Gambar 4.3
Pilihan Lomba 1 Mill Lawan Komputer
43
xii
Gambar 4.4
Pilihan Lomba Banyak Mill Lawan Komputer
43
Gambar 4.5
Halaman Lawan Teman
44
Gambar 4.6
Pilihan Lomba 1 Mill Lawan Teman
45
Gambar 4.7
Pilihan Lomba Banyak Mill Lawan Teman
45
Gambar 4.8
Papan Permainan
46
Gambar 4.9
Notifikasi -1
47
Gambar 4.10
Notifikasi -2
47
Gambar 4.11
Notifikasi -3
48
Gambar 4.12
Notifikasi -4
48
Gambar 4.13
Halaman Statistik
48
Gambar 4.14
Halaman Panduan
49
Gambar 4.15
Halaman Tentang
49
