i

PERBANDINGAN ALGORITMA SMA* DAN ALGORITMA A*

PADA PERMAINAN ONET

Tugas Akhir

oleh

SETYAWATI

22104821

PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS TEKNOLOGI

INFORMASI

UNIVERSITAS KRISTEN DUTA WACANA

2015

@UKDW

ii

PERBANDINGAN ALGORITMA SMA* DAN ALGORITMA A*

PADA PERMAINAN ONET

Tugas Akhir

Diajukan kepada Program Studi Teknik Informatika Fakultas Teknologi Informasi

Universitas Kristen Duta Wacana

Sebagai Salah Satu Syarat dalam Memperoleh Gelar

Sarjana Komputer

Disusun oleh

SETYAWATI

22104821

PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS TEKNOLOGI

INFORMASI

UNIVERSITAS KRISTEN DUTA WACANA

2015

@UKDW

iii

@UKDW

iv

@UKDW

v

@UKDW

vi

KATA PENGANTAR

Puji syukur penulis panjatkan kepada Tuhan Yesus Kristus yang telah

melimpahkan segala rahmat–Nya sehingga penulis dapat menyelesaikan

penyusunan tugas akhir yang berjudul “Perbandingan Algoritma SMA* Dan

Algoritma A* pada Permainan Onet” dengan baik dan tepat waktu.

Tugas Akhir ini disusun sebagai salah satu syarat untuk memperoleh gelar

sarjana pada program studi Teknik Informatika , Fakultas Teknologi Informasi ,

Universitas Kristen Duta Wacana. Dalam usaha menyusun tugas akhir ini, penulis

telah mendapat banyak bantuan dan bimbingan yang tak ternilai dari berbagai

pihak. Oleh karena itu, penulis ingin menyampaikan terima kasih yang sebesar-

besarnya kepada :

Tuhan Yesus Kristus yang selalu membimbing dan menyertai penulis.

Keluarga penulis, Papa, Mama, dan Kakak penulis yang selalu

memberikan dukungan.

Ibu Gloria Virginia, S.Kom., MAI, Ph.D. selaku dosen pembimbing I yang

telah memberikan masukan dan bimbingan hingga terselesaikannya tugas

akhir ini.

Bapak Nugroho Agus Haryono, M.Si selaku dosen pembimbing II yang

telah memberikan masukan dan bimbingan hingga terselesaikannya tugas

akhir ini.

Teman-teman penulis yang senantiasa menyemangati dan memberikan

bantuan kepada penulis.

Penulis menyadari bahwa dalam penyusunan tugas akhir ini masih jauh

dari penulis harapkan saran dan kritik dari pembaca semuanya. Akhir kata,

penulis berharap semoga tugas akhir ini dapat memberikan manfaat bagi seluruh

pihak yang membutuhkan.

@UKDW

vii

INTISARI

PERBANDINGAN ALGORITMA SMA* DAN ALGORITMA A* PADA

PERMAINAN ONET

Permainan Onet adalah salah satu jenis permainan puzzle yang cara

penyelesaiannya adalah dengan mencocokkan dua buah gambar dengan syarat

kedua gambar tersebut dapat dihubungkan oleh tiga buah garis yang berhubungan.

Permainan ini membutuhkan kejelian mata untuk dapat menemukan gambar mana

yang sesuai. Setiap gambar yang berhasil dicocokkan akan menghilang dari papan

permainan. Permainan berakhir ketika pemain dapat menghilangkan semua

gambar yang terdapat pada papan permainan dalam batasan waktu yang

ditentukan.

Algoritma A* adalah algoritma pencarian jalur yang dalam pencariannya

dibimbing menggunakan metode heuristik. Nilai heuristik adalah nilai yang

digunakan untuk membantu penentuan jalur terpendek yang akan diambil.

Algoritma SMA* adalah salah satu variasi dari algoritma A* yang memiliki

keunggulan penggunaan memori yang lebih sedikit. Dalam penelitian ini, penulis

mencoba untuk membandingkan penerapan algoritma A* dan algoritma SMA*

pada permainan Onet. Nilai heuristik yang digunakan dalam penelitian ini

dihitung menggunakan metode Manhattan Distance.

Hasil analisis penelitian ini menunjukkan bahwa algoritma SMA*

menggunakan jumlah node yang rata-rata lebih sedikit dibandingkan dengan

algoritma A*. Tetapi jalur yang dihasilkan dari implementasi algoritma SMA*

lebih panjang daripada algoritma A*.

@UKDW

viii

DAFTAR ISI

HALAMAN SAMPUL DEPAN...............................................................................i

HALAMAN SAMPUL DALAM............................................................................ii

PERNYATAAN KEASLIAN SKRIPSI................................................................iii

HALAMAN PERSETUJUAN................................................................................iv

HALAMAN PENGESAHAN..................................................................................v

KATA PENGANTAR............................................................................................vi

INTISARI..............................................................................................................vii

DAFTAR ISI.........................................................................................................viii

DAFTAR GAMBAR...............................................................................................x

DAFTAR TABEL...................................................................................................xi

BAB I.......................................................................................................................1

PENDAHULUAN....................................................................................................1

1.1. Latar Belakang Masalah................................................................................1

1.2. Perumusan Masalah.......................................................................................2

1.3. Batasan Masalah............................................................................................2

1.4. Tujuan Penelitian...........................................................................................3

1.5. Metode Penelitian..........................................................................................3

1.6. Sistematika Penulisan....................................................................................3

BAB II......................................................................................................................6

TINJAUAN PUSTAKA...........................................................................................6

2.1. Tinjauan Pustaka...........................................................................................6

2.2. Landasan Teori..............................................................................................7

2.2.1. Permainan Onet.......................................................................................8

2.2.2. Manhattan Distance..............................................................................11

2.2.3. Algoritma A*........................................................................................11

@UKDW

ix

2.2.4. Algoritma SMA*..................................................................................13

BAB III..................................................................................................................17

PERANCANGAN SISTEM..................................................................................17

3.1. Spesifikasi Sistem........................................................................................17

3.2. Flowchart....................................................................................................17

3.3. Perancangan Program..................................................................................19

3.4. Rancangan Tampilan (Mockups).................................................................23

BAB IV..................................................................................................................27

IMPLEMENTASI DAN ANALISIS SISTEM......................................................27

4.1. Implementasi Awal......................................................................................27

4.2. Implementasi Rancangan Tampilan............................................................27

4.2.1. Halaman Index......................................................................................27

4.2.2. Halaman Acak Gambar.........................................................................28

4.2.3. Halaman Algoritma A*.........................................................................29

4.2.4. Halaman Algoritma SMA*...................................................................30

4.3. Validasi Internal..........................................................................................30

4.4. Analisis.......................................................................................................32

4.4.1. Analisis Implementasi Algoritma A* dan SMA*.................................32

4.4.2. Analisis Kompleksitas Algoritma.........................................................35

BAB V....................................................................................................................38

KESIMPULAN......................................................................................................38

5.1. Kesimpulan..................................................................................................38

5.2. Saran............................................................................................................38

DAFTAR PUSTAKA............................................................................................40

@UKDW

x

DAFTAR GAMBAR

Gambar 2.1. Empat kategori definisi AI..................................................................7

Gambar 2.2. Permainan Onet ..................................................................................8

Gambar 2.3. Path Permainan Onet..........................................................................9

Gambar 2.4. Langkah-langkah permainan Onet....................................................10

Gambar 2.5. Flow chart A*...................................................................................12

Gambar 2.6. Flow chart SMA*..............................................................................15

Gambar 2.7. Pseudocode algoritma SMA*............................................................16

Gambar 3.1. Flowchart sistem...............................................................................18

Gambar 3.2. Graf permainan Onet.........................................................................19

Gambar 3.3. Contoh kasus permainan Onet...........................................................19

Gambar 3.4. Contoh langkah 1 penyelesaian kasus...............................................20

Gambar 3.5. Contoh langkah 2 penyelesaian kasus...............................................21

Gambar 3.6. Contoh langkah 3 penyelesaian kasus...............................................22

Gambar 3.7. Contoh langkah 4 penyelesaian kasus...............................................22

Gambar 3.8. Contoh langkah 5 penyelesaian kasus...............................................23

Gambar 3.9. Tampilan halaman Index...................................................................23

Gambar 3.10. Tampilan halaman Acak Papan Permainan.....................................24

Gambar 3.11. Tampilan halaman Perbandingan....................................................25

Gambar 3.6. Halaman cek hasil.............................................................................26

Gambar 4.1. Tampilan halaman index...................................................................28

Gambar 4.2. Tampilan halaman Acak Gambar......................................................28

Gambar 4.3. Tampilan halaman Algoritma A*......................................................29

Gambar 4.4. Tampilan halaman Algoritma SMA*................................................30

Gambar 4.5. Contoh kasus.....................................................................................31

Gambar 4.6. Contoh penyelesaian kasus................................................................31

Gambar 4.7. Sample papan permainan...................................................................32

Gambar 4.8. Perhitungan Big-O algoritma A*......................................................36

Gambar 4.9. Perhitungan Big-O algoritma SMA*.................................................37

@UKDW

xi

DAFTAR TABEL

Tabel 3.1. Perhitungan f cost langkah 1.................................................................20

Tabel 3.2. Perhitungan f cost langkah 2.................................................................21

Tabel 3.3. Tabel 3.2. Perhitungan f cost langkah 3................................................21

Tabel 3.3. Perhitungan f cost langkah 4.................................................................22

Tabel 3.4. Tabel 3.2. Perhitungan f cost langkah 5................................................22

Tabel 4.1. Jalur yang didapat dari implementasi algoritma A* pada kasus

permainan di Gambar 4.7.......................................................................................33

Tabel 4.2. Rata-rata waktu yang dibutuhkan untuk menyelesaikan kasus

permainan di Gambar 4.7 dengan algoritma A*....................................................33

Tabel 4.3. Hasil implementasi algoritma SMA* pada kasus permainan di Gambar

4.7...........................................................................................................................34

Tabel 4.4. Rata-rata waktu yang dibutuhkan untuk menyelesaikan kasus

permainan di Gambar 4.7 dengan algoritma SMA*..............................................34

Tabel 4.5. Perbandingan jumlah node dan waktu antara algoritma A* dan

SMA*.....................................................................................................................35

@UKDW

1

BAB I

PENDAHULUAN

1.1. Latar Belakang Masalah

Permainan Onet adalah salah satu jenis permainan puzzle yang cara

penyelesaiannya adalah dengan mencocokkan dua buah gambar dengan syarat

kedua gambar tersebut dapat dihubungkan oleh tiga buah garis yang berhubungan.

Setiap gambar yang berhasil dicocokkan akan menghilang dari papan permainan.

Pemain dinyatakan menang ketika semua gambar yang terdapat pada papan

permainan berhasil dicocokkan dalam batasan waktu yang ditentukan. Pada

permainan yang sudah ada, urutan gambar yang dicocokkan ditentukan

berdasarkan keinginan pemain. Dalam penelitian ini, dilakukan modifikasi pada

penentuan pencocokkan gambar. Urutan gambar yang dicocokkan adalah dimulai

dari gambar dengan jalur terpendek terlebih dahulu.

Untuk menyelesaikan permainan ini, dapat diterapkan sebuah algoritma

pathfinding, seperti Brute Force, Breadth-First-Search (BFS), Depth-First-Search

(DFS), atau Branch and Bound, dan A*(A-star). Dalam algoritma Brute Force,

akan dilakukan perbandingan posisi antara titik awal dengan titik akhir dan

menentukan langkah selanjutnya. Algoritma ini tidak dapat menyelesaikan

persoalan yang memiliki penghalang di jalur antara titik awal dan titik akhir tanpa

dilakukan modifikasi (Fauzan, 2012). Fauzan pada tahun 2012 juga menyatakan

bahwa Breadth-First-Search (BFS) mencari solusi dengan cara mengeksekusi

setiap node yang ada secara menyebar. Akibatnya, algoritma ini memakan waktu

lebih lama dan memerlukan memori yang cukup besar. Pada Depth-First-Search

(DFS), pencarian memiliki kemungkinan untuk tidak ditemukannya tujuan yang

diharapkan.

Dari penelitian yang pernah dilakukan oleh Refi Rufaidah pada tahun

2012, algoritma DFS dan BFS dapat menyelesaikan permainan onet, tetapi

menggunakan langkah-langkah yang cukup banyak dan untuk mendapatkan hasil

@UKDW

2

yang maksimum, kedua algoritma tersebut harus digunakan bersama-sama. (Ru-

faidah, 2012)

Dalam penelitian ini, algoritma yang akan dibandingkan adalah algoritma

SMA* (Simplified Memory Bounded A-Star) dan algoritma A* (A-star).

Algoritma A* merupakan algoritma yang paling banyak digunakan untuk

memecahkan pencarian jalur dalam suatu permainan (Hart, Nilsson, & Raphael,

1968). Algoritma SMA* adalah sebuah algoritma pencarian jalur yang merupakan

salah satu variasi dari algoritma A* yang memiliki keunggulan penggunaan

memori yang lebih sedikit.

1.2. Perumusan Masalah

a. Bagaimana penerapan algoritma SMA* dan algoritma A* dalam

permainan Onet?

b. Bagaimana perbandingan penggunaan memori dalam penerapan

algoritma SMA* dan algoritma A* dalam pemecahan masalah

permainan Onet?

c. Bagaimana efisiensi penerapan algoritma SMA* dan algoritma A*

dilihat dari performa permainan Onet?

d. Bagaimana efisiensi penulisan dan pengeksekusian kode dari algoritma

A* dan SMA*?

1.3. Batasan Masalah

a. Dalam penelitian ini, tidak meletakkan fokus pada masalah visual

permainan.

b. Permainan dibuat dengan basis web.

@UKDW

3

1.4. Tujuan Penelitian

Penelitian ini bertujuan untuk menilai efektifitas dari algoritma A* dan

SMA* ketika diimplementasikan pada permainan Onet berdasarkan:

a. Penggunaan memori dari algoritma A* dan SMA*.

b. Efisiensi dari implementasi SMA* dan A* dilihat dari performa

permainan Onet.

c. Efisiensi penulisan dan eksekusi kode dari masing-masing algoritma.

1.5. Metode Penelitian

a. Pengumpulan data dilakukan dengan studi pustaka mengenai

implementasi algoritma SMA*, algoritma A*, algoritma graf, dan

kecerdasan buatan.

b. Metode pengujian dilakukan dengan :

1. Mengimplementasikan algoritma A* dan algoritma SMA*

pada penyelesaian permainan Onet.

2. Menguji perbandingan ketepatan, kecepatan, serta efektifitas

antara algoritma SMA* dan algoritma A* untuk menyelesaikan

permainan Onet.

c. Analisis dilakukan dengan cara membandingkan data yang diperoleh

dari hasil pengujian antara algoritma A* dan algoritma SMA*.

1.6. Sistematika Penulisan

Sistematika penulisan penelitian ini disusun untuk memberikan gambaran

umum tentang penelitian yang dijalankan. Sistematika penulisan tugas akhir ini

adalah sebagai berikut :

@UKDW

4

BAB 1 PENDAHULUAN

Berisi gambaran tentang penelitian ini, dijelaskan pada bagian latar

belakang masalah, rumusan masalah, batasan masalah dan tujuan penelitian. Latar

belakang masalah menjelaskan tentang alasan melakukan penelitan, awal dari

timbulnya masalah, dan pentingnya penelitian ini. Pada bagian rumusan masalah,

dituliskan tentang masalah yang menjadi fokus penelitian ini. Batasan masalah

menjabarkan tentang batasan-batasan dalam melakukan penelitian. Tujuan

penelitian dituliskan selanjutnya.

BAB 2 TINJAUAN PUSTAKA

Membahas berbagai konsep dasar teori yang berkaitan dengan topik

penelitian yang dilakukan dan hal-hal yang berguna dalam proses analisis

permasalahan yaitu tentang pembuatan aplikasi permainan, kecerdasan buatan dan

algoritma, terutama algoritma A* dan algoritma SMA*.

BAB 3 ANALISIS DAN PERANCANGAN

Bab ini membahas analisis terhadap permainan yang dibuat serta

bagaimana merancang dengan menggunakan HTML5, merancang tampilan

permainan, serta analisis bagaimana penerapan algoritma SMA* dan algoritma A*

pada permainan Onet yang akan diterapkan pada sistem untuk mencari pemecahan

masalah.

BAB 4 IMPLEMENTASI DAN PENGUJIAN

Berisi tentang tahapan-tahapan yang dilakukan untuk menerapkan sistem

yang telah dirancang. Melakukan pengujian terhadap aplikasi yang telah dibangun

untuk menguji algoritma A* dengan SMA*.

@UKDW

5

BAB 5 KESIMPULAN DAN SARAN

Berisi kesimpulan hasil dari implementasi, pengujian, dan analisis

algoritma SMA* dan algoritma A* dalam rangka mencapai tujuan yang ingin

dicapai sebelumnya dan memberikan masukan atau saran dari masalah-masalah

yang ditemukan selama proses penelitian terhadap pembandingan algoritma

SMA* dan algoritma A*.

@UKDW

38

BAB V

KESIMPULAN

5.1. Kesimpulan

Berdasarkan implementasi algoritma A* dan algoritma SMA* pada

permainan Onet yang telah dibuat, dapat ditarik beberapa kesimpulan sebagai

berikut:

1. Penggunaan memori algoritma SMA* lebih banyak bila dibandingkan

dengan algoritma A* dilihat dari jumlah node yang disimpan dalam closed

list. Sedangkan apabila dilihat dari rata-rata jumlah node yang disimpan

dalam open list, algoritma A* menggunakan lebih banyak memori.

2. Rata-rata total jalur yang diambil sistem dari penerapan algoritma SMA*

dalam sebuah permainan lebih banyak daripada algoritma A*. Pada Tabel

4.5 ditunjukkan bahwa rata-rata jumlah node yang digunakan algoritma

A* adalah sebanyak 29,1428 buah dan algoritma SMA* sebanyak 29,7142

buah.

3. Waktu yang dibutuhkan untuk eksekusi algoritma A* lebih cepat

dibandingkan algoritma SMA*, ditunjukkan dengan hasil pengujian pada

Tabel 4.5. Rata-rata waktu yang dibutuhkan oleh algoritma SMA* untuk

menyelesaikan sebuah papan permainan adalah 1,8967ms sedangkan

algoritma A* membutuhkan waktu rata-rata 1,608 ms.

4. Analisis kompleksitas algoritma A* dan SMA* menggunakan notasi Big-

O menghasilkan notasi yang sama, yaitu O(n4), meskipun jumlah eksekusi

yang dilakukan fungsi algoritma SMA* lebih banyak.

5. Algoritma A* maupun algoritma SMA* kurang tepat diterapkan dalam

permainan Onet karena fokus permainan Onet adalah untuk menghabiskan

semua gambar pada papan permainan, tanpa mempedulikan panjang jalur

yang ditempuh.

@UKDW

39

5.2. Saran

Dari hasil penelitian dan implementasi yang telah dilakukan, disarankan

pengembangan sistem lebih lanjut, dengan aspek pengembangan seperti berikut:

1. Untuk pengujian algoritma SMA* dapat dikembangkan dengan cara

memberikan jumlah limit yang berbeda.

2. Ukuran papan permainan dibuat berbeda untuk proses evaluasi algoritma.

3. Untuk membuat pengujian atau pembandingan algoritma A* maupun

SMA* sebaiknya menggunakan permainan selain Onet.

@UKDW

40

DAFTAR PUSTAKA

-(2012). http://socs.binus.ac.id/2012/03/02/a-little-brief-about-artificial-

intelligence/ Diakses tanggal 9-3-14 jam 21:07.

Doni, F. (2013). IMPLEMENTASI ALGORITMA SMA* PADA GAME TPS

MONSTER NEST BERBASIS MOBILE. Perpustakaan UNIKOM.

Hart, P.; Nilsson, N. J.; and Raphael, B. (1968). A formal basis for the heuristic

determination of minimum cost paths. IEEE Transactions on Systems Science and

Cybernetics 100.107.

Lengacher, D., Cammarata, C., & Lloyd, S. (2014). Measuring Relative

Efficiency and Effectiveness. Encyclopedia of Business Analytics and

Optimization , 1529-1538.

Rufaidah, R. (2012). Perbandingan Algoritma Breadth First Search dan Depth

First Search pada Aplikasi Game Onet Menggunakan Platform Android.

Russel, S. J., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach

Second Edition. New Jersey: Prentice Hall.

Utama, M. (2010). Simulasi Penyelesaian Masalah Jalur Terpendek dengan

Algoritma Simplified Memory-bounded A* (SMA*) SEARCH. Yogyakarta: Duta

Wacana Christian University.

@UKDW