![Implementasi Metode Blind Search Pada Permainan Menara Hanoi [PDF]](https://pdfs.asia/img/200x200/implementasi-metode-blind-search-pada-permainan-menara-hanoi.jpg)
9 0 929 KB
IMPLEMENTASI METODE BLIND SEARCH PADA PERMAINAN MENARA HANOI MAKALAH Disusun untuk Memenuhi Tugas Mata Kuliah Kecerdasan Buatan
oleh : Fuji Nugraha
177006052
Anggi Dwi Astuti
177006002
JURUSAN INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS SILIWANGI TASIKMALAYA 2019
KATA PENGANTAR
Segala puji dan syukur penulis panjatkan ke hadirat Alloh Swt. yang telah melimpahkan segala rahmat-Nya sehingga penulis dapat menyelesaikan makalah dengan judul Penerapan Metode Blind Search pada Permainan Menara Hanoi guna memenuhi tugas Mata Kuliah Kecerdasan Buatan Jurusan Informatika Fakultas Teknik Universitas Siliwangi Tasikmalaya.
Penulis menyadari kelemahan serta keterbatasan yang ada sehingga untuk menyelesaikan makalah ini memperoleh bantuan dari berbagai pihak, dalam kesempatan ini penulis mengucapkan terimakasih kepada Dosen Mata Kuliah Kecerdasan Buatan Ibu Neng Ika Kurniati, S.Si., M.Cs. yang telah membimbing penulis.
Berhubungan dengan penggunaan sistem cerdas atau Artificial Intelligence (AI) yang salah satu implementasinya di dalam permainan atau Game yang cukup diminati masyarakat dunia dari berbagai kalangan. Terutama permainan-permainan yang berbasis aplikasi di berbagai platform. Dalam makalah ini akan dibahas tentang kecerdasan buatan secara umum, dan penerapan salah satu metode blind search pada permainan Menara Hanoi.
Penulis menyadari bahwa makalah masih memiliki banyak kekurangan baik isi maupun susunannya. Semoga makalah ini dapat bermanfaat tidak hanya untuk penulis tapi juga bagi para pembaca.
Tasikmalaya, September 2019
Penulis
i
DAFTAR ISI
KATA PENGANTAR .....................................................................................
i
DAFTAR ISI ....................................................................................................
ii
BAB I PENDAHULUAN ................................................................................
1
A. Latar Belakang Masalah ..................................................................
1
B. Rumusan Masalah............................................................................
1
C. Tujuan Makalah ...............................................................................
1
D. Kegunaan Makalah ..........................................................................
2
E. Prosedur Makalah ............................................................................
2
BAB II PEMBAHASAN .................................................................................
3
A. Kajian Teoritis .................................................................................
3
B. Pembahasan .....................................................................................
5
BAB III SIMPULAN DAN SARAN ...............................................................
14
A. Simpulan ..........................................................................................
14
B. Saran ................................................................................................
14
DAFTAR PUSTAKA ......................................................................................
15
ii
BAB I PENDAHULUAN
A. Latar Belakang Masalah Perkembangan teknologi komputer pada saat ini sangat berperan penting dalam berbagai pengembangan kecerdasan buatan atau Artificial Intelegence (AI) khususnya dalam bidang aplikasi permainan (game) saat ini. Banyak sekali permainan-permainan yang dikembangkan dengan kecerdasan buatan, sehingga permainan-permainan tersebut memiliki nilai dan rating yang sangat tinggi karena memiliki sistem cerdas di dalamnya. Permainan-permainan yang dikembangkan dengan sistem cerdas menggunakan metode-metode kecerdasan buatan.
Penerapan metode-metode kecerdasan buatan pada sebuah aplikasi permainan adalah salah satu cara agar aplikasi permainan yang dikembangkan dapat memecahkan permasalahan secara sitematis dan melakukan penalaran-penalaran layaknya manusia secara alami. Metode
kecerdasan
digunakan sebagai metode dalam menyelesaikan
buatan
masalah
sering
penalaran
kali yang
mengandung faktor-faktor ketidakpastian (Astawa, 2012). Salah satu permainan yang bernama Menara Hanoi dapat diselesaikan dengan kecerdasan buatan dengan menerapkan salah satu metode blind search.
B. Rumusan Masalah Berdasarkan latar belakang masalah diatas, penulis merumuskan masalah sebagai berikut : 1. Apa itu Kecerdasan Buatan? 2. Apa saja Metode Blind Search? 3. Bagaimana implementasi Metode Blind Search pada permainan Menara Hanoi?
C. Tujuan Makalah Sejalan dengan rumusan masalah diatas, makalah ini disusun degan tujuan untuk mengetahui dan mendeskripsikan :
1
2
1. pengertian kecerdasan buatan; 2. metode blind search; 3. implementasi metode blind search pada permainan Menara Hanoi.
D. Kegunaan Makalah Makalah ini disusun dengan harapan memberikan manfaat dan kegunaan baik secara praktis maupun teoritis.
Secara teoritis makalah ini bermanfaat untuk menambah pengetahuan tentang kecerdasan buatan dan penerapan metode kecerdasan buatan pada sebuah permaian. Secara praktis makalah ini diharapkan bermanfaat bagi : 1. penulis, sebagai wahana penambah pengetahuan dan konsep keilmuan khusunya tentang implementasi metode blind search pada permainan Menara Hanoi; 2. pembaca, sebagai media informasi tentang implementasi metode blind search pada permainan Menara Hanoi secara teorittis maupun secara praktis.
E. Prosedur Makalah Makalah ini disusun dengan menggunakan pendekatan kualitatif. Metode yang digunakan adalah metode deskriptif. Melalui metode ini penulis akan meguraikan permasalahan yang dibahas secara jelas dan komprehensif. Data teoritis dalam makalah ini dikumpulkan dengan menggunakan teknik studi pustaka, artinya penulis mengambil data dengan kegiatan membaca dari berbagai literatul yang relevan dengan tema makalah. Data tersebut diolah dengan teknik analisis melalui kegiatan melaui kegiatan mengeksposisikan data serta mengaplikasikan data tersebut dalam konteks tema makalah.
BAB II PEMBAHASAN
A. Kajian Teoritis 1. Kecerdasan Buatan Kecerdasan buatan (AI) merupakan sebuah studi tentang bagaimana membuat komputer melakukan hal-hal yang pada saat ini dapat dilakukan lebih baik oleh manusia (Rich & Knight, 1991). Dalam artian lain kecerdasan buatan adalah sebuah sistem yang di program agar bisa berpikir layaknya otak manusia. Sistem cerdas biasanya terdapat pada robot, mesin-mesin pabrik, expert system, games dan lain-lain.
2. Metode Blind Search Pada metode blind search terdapat istilah blind atau buta karena metode ini tidak memiliki informasi awal saat melakukan proses pencarian penyelesaian masalah. Metode blind search memiliki 6 metode diantaranya: a.
Breadth-First Search (BFS)
Metode ini melakukan proses pencarian pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses pencarian pada node di hirarki berikutnya. •
Kekurangan -
tidak akan menemui jalan buntu;
-
menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti solusi yang terbaik;
•
b.
jika ada satu solusi maka bread-first search akan menemukannya.
Kelebihan -
membutuhkan memori yang cukup banyak;
-
membutuhkan waktu yang cukup lama.
Depth-First Search (DFS)
Metode DFS adalah proses pencarian sistematis buta yang melakukan ekspansi sebuah path (jalur) menuju penyelesaian masalah sebelum
3
4
melakukan eksplorasi path lain. Proses pencarian mengikuti sebuah jalur tunggal sampai menemukan goal atau dead end. Apabila proses pencarian menemukan titik temu, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki jalur cabang yang belum di eksplorasi. •
Kekurangan -
penggunaan memori hanya sedikit;
-
jika solusi terdapat pada level yang dalam dan paling kiri, maka akan ditemukan secara cepat.
•
Kelebihan -
tidak ada jaminan untuk menemukan solusi, jika pohon dibangkitkan memilik level yang tak hingga;
-
c.
tidak ada jaminan untuk menemukan solusi yang paling baik.
Depth-Limited Search (DLS)
Metode ini berusaha mengatasi kelemahan DFS yang tidak complete dengan membatasi kelemahan maksimum suatu jalur solusi. Tetapi, sebelum menggunakan DLS, kita harus tahu berapa level maksimum dari suatu solusi.
d.
Uniform Cost Search (UCS)
Konsepnya hamper sama dengan BFS, namun perbedaanya adalah BFS menggunakan urutan level yang paling rendah sampai paling tinggi, sedangkan UCS menggunakan urutan biaya dari paling kecil hingga yang terbesar. UCS berusaha menemukan solusi dengan total biaya terendah yang dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan.
e.
Iterative-Deepening Search (IDS)
Metode ini merupakan metode yang menggabungkan kelebihan BFS (complete dan optimal) dengan kelebihan DFS (space complexity rendah atau hanya membutuhkan sedikit memori). Tetapi konsekuensinya adalah time complexity-nya yan tinggi.
5
f.
Bi-Directional Search (BDS)
Pencarian dilakukan dari dua arah, pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start). Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan , yaitu dengan cara menggabungkan kedua jalur yang bertemu.
B. Pembahasan 1. Tower of Hanoi Permainan Menara Hanoi memiliki peraturan adalah sebuah permainan matematis atau teka-teki. Teka-teki ini ditemukan oleh ahli matematika Perancis di tahun 1883. Permainan ini terdiri dari tiga 3 tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bias dimasukkan ke tiang mana saja. Permainan Menara Hanoi dimulai dengan cakram-cakram yang tertumpuk rapi dari cakram paling besar sampai ke cakram paling terkecil dalam
salah
satu
tiang, sehingga membentuk kerucut. Objektif dari
permainan Menara Hanoi adalah memindahkan tumpukan n buah cakram berlubang dari tiang asal ke tiang tujuan dengan memanfaatkan sebuah tiang perantara. Piringan berukuran tidak sama. Jumlah pemindahan dalam
n
buah cakram adalah sebanyak 2n-1 kali (Supiyandi, 2016).
Permainan Menara Hanoi memiliki beberapa aturan yang harus dipatuhi untuk
menyelesaikan teka-teki dalam
melakukan pemindahan cakram
harus mengikuti aturan berikut: •
hanya
satu
cakram
yang
boleh
dipindahkan dalam setiap kali
perpindahan; •
setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut;
•
tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.
2. Masalah dan Ruang Keadaan
6
a. State Space Permasalah ini dapat direpresentasikan menjadi 6 karakter L, M, S, A, B dan C: -
L = simbol untuk cakram yang terbesar.
-
M = simbol untuk cakram yang berukuran sedang.
-
S = simbol untuk cakram yang terkecil.
-
A = simbol untuk tiang pertama.
-
B = simbol untuk tiang kedua.
-
C = simbol untuk tiang ketiga.
Ruang keadaan: (A{L,M,S} , B{L,M,S}, C{L,M,S}) sehingga {L, M, S} ∈ A, B, C
b. Intial State
Gambar 2.1 Initial State
Keadaan awal: terdapat 3 cakram pada tiang pertama A{L,M,S}
c. Goal State
7
Gambar 2.2 Final State
Tujuan akhir: keadaan dimana ke-3 cakram berada pada tiang ketiga C{L,M,S}
d. Rule State Peraturan dari permainan Menara Hanoi diantaranya: -
hanya
satu cakram yang boleh dipindahkan dalam setiap kali
perpindahan; -
setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut;
-
tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.
8
Aturan Ke-
if
1
A{L,M,S} and B{} and C{}
B{S} or C{S}, pindahkan cakram S ke tiang B atau C
2
A{L,M} and B{S} and C{}
C{M}, pindahkan cakram M ke tiang C
3
A{L} and B{S} and C{M}
C{M,S}, pindahkan cakram S ke tiang C
4
A{L} and B{} and C{M,S}
B{L}, pindahkan cakram L ke tiang B
5
A{} and B{L} and C{M,S}
B{L,S}, pindahkan cakram L ke tiang B
6
A{} and B{L,S} and C{M}
A{M}, pindahkan cakram M ke tiang A
7
A{M} and B{L} and C{}
A{M,S}, pindahkan cakram S ke tiang A
8
A{} and B{L,S} and C{M}
A{M}, pindahkan cakram M ke tiang A
9
A{M} and B{L,S} and C{}
A{M,S}, pindahkan cakram S ke tiang A
10
A{M,S} and B{L} and C{}
C{L}, pindahkan cakram L ke tiang C
11
A{M,S} and B{} and C{L}
B{S}, pindahkan cakram S ke tiang B
12
A{M} and B{S} and C{L}
C{L,M}, pindahkan cakram M ke tiang C
13
A{} and B{S} and C{L,M}
C{L,M,S}, pindahkan cakram S ke tiang C
14
A{L,M,S} and B{} and C{}
C{S}, pindahkan cakram S ke tiang C
15 16 17 18 19 20
then
A{L,M} and B{} and B{M}, pindahkan cakram M ke tiang B C{S} A{L} and B{M} and B{M,S}, pindahkan cakram S ke tiang C{S} B A{L} and B{M,S} C{L}, pindahkan cakram L ke tiang C and C{} A{} and B{M,S} and A{S}, pindahkan cakram S ke tiang A C{L} A{S} and B{M} and C{L,M}, pindahkan cakram M ke tiang C{L} C A{S} and B{} and C{L,M,S}, pindahkan cakram S ke C{L,M} tiang C Tabel 2.1 Rule State
9
e. Representasi dalam pohon pelacakan
Gambar 2.3 Representasi pohon pelacakan
3. Implementasi Metode Blind Search pada Permainan Menara Hanoi a. Breadth-First Search (BFS)
10
Gambar 2.4 BFS
BFS tepat menemukan solusi untuk memecahkan permainan Menara Hanoi pada hirarki level ke-7. Dan menemukan solusi terbaik dari pohon pelacakan tersebut. Namun memakan memori yang cukup banyak juga membutuhkan waktu yang cukup lama untuk menemukan solusi tersebut karena mengecek satu persatu node yang ada.
b. Depth-First Search (DFS)
11
Gambar 2.5 DFS
DFS menemukan solusi dengan cepat karena solusi berada pada level yang paling dalam dan di posisi paling kiri juga memakan memori yang sangat sedikit ketika proses pencarian. Proses DFS diatas berjalan dengan tepat dikarenakan solusi yang ada berada pada posisi paling dalam bagian kiri. Namun, jika solusi tidak berada pada tempat tersebut DFS tidak dapat menjamin menemukan solusi juga tidak menjamin solusi yang terbaik.
c. Depth-Limited Search (DLS)
12
Metode ini dapat mengatasi kelemahan DFS. Namun, pada kasus permainan Menara Hanoi metode DLS tidak diperlukan. Karena DFS masih mampu menemukan solusi dengan cepat dan baik.
d. Uniform Cost Search (UCS) Metode ini tidak relevan dengan studi kasus permainan Menara Hanoi karena pada permainan tidak terdapat biaya dalam menemukan solusi pemecahan masalahnya.
e. Iterative-Deepening Search (IDS)
Gambar 2.6 IDS
13
Metode IDS menggabungkan metode BFS dan DFS untuk mengambil keunggulan dari kedua metode tersebut yaitu dapat menemukan solusi dengan tepat, cepat dan menjamin ditemukannya solusi. Namun memakan waktu yang lama untuk menemukan solusi.
f. Bi-Directional Search (BDS)
Gambar 2.7 BDS
Metode ini meng-generate node yang sama, sehingga dapat menemukan solusi yaitu dengan cara menggabungkan kedua jalur yang bertemu. BDS bisa menjadi alternatif dari metode-metode lain yang telah dibahas sebelumnya.
BAB III SIMPULAN DAN SARAN A. Simpulan Dari semua metode yang digunakan untuk diimplemtasikan pada permainan Menara Hanoi terdapat 3 metode yang cukup efektif untuk digunakan yaitu metode BFS, DFS dan IDS. Karena ketepatan dalam menemukan solusi serta terjaminnya ditemukan solusi jika menggunakan BFS. Juga kecepatan waktu hingga penggunaan memori yang rendah jika menggunaakn DFS. Hingga gabungan keunggulan dari kedua metode BFS dan DFS jika menggunakan IDS, namun waktu yang digunakan cukup lama untuk menemukan solusi.
Kelebihan dan kekurangan dari metode-metode pencarian buta bergantung pada studi kasus yang akan dipecahkan permasalahannya. Maka dapat disimpulkan metode blind search efektif ketika diimplementasikan pada permainan Menara Hanoi. Terutama metode BFS, DFS, dan IDS.
B. Saran Dalam penggunaan metode blind search akan lebih baik jika kita mengidentfikasi ruang keadaan, menentukan initial state dan final state, menentukan rule yang digunakan, hingga merepresentasikan ruang keadaan tersebut dengan pohon pelacakan sehingga akan mudah dalam mengimplementasikan metode-metode blind search diatas.
14
DAFTAR PUSTAKA Astawa, I. G. (2012). Penggunaan Metode Kecerdasan Buatan Runut Maju dalam Memecahkan Permasalahan Game Labirin. Jurnal Ilmu Komputer, 37-46. Rich, E., & Knight, K. (1991). Artificial Intelligence. In M.-G. H. Co., Artificial Intelligence. New York. Supiyandi. (2016). Penyelasaian Problema Tower of Hanoi Menggunakan Algoritma A*. Jurnal TIMES, 1-5.
15
