BAB I

PENDAHULUAN

A.    LATAR BELAKANG  

Program permainan ( game ) merupakan salah satu implementasi dari   bidang  ilmu  komputer.  Perkembangan  permainan  pada  masa  kini  sudah sangat pesat dan telah menjadi mode tersendiri di dunia karena mayoritas pengguna komputer menghabiskan sebagian besar waktu mereka di depan   komputer dalam program permainan. Salah satu algoritma yang  digunakan  untuk  mengembangkan  program  permainan  adalah  algoritma berbasis  pohon  ruang  pencarian  (searching  algorithm).  Salah  satu  game yang  menggunakan  algoritma  berbasis  pohon  ruang  pencarian  dalam   menyelesaikan permainannya yaitu  menara hanoi. 

Menara Hanoi merupakan salah satu diantara berbagai teka-teki dalam matematika. Teka-teki ini ditemukan Edouard Lucas, ahli matematika Perancis di tahun 1883.Teka-teki ini berdasarkan pada sebuah cerita legenda tentang candi Indian atau menara Benares di India yang memiliki tiga tiang dan salah satu tiangnya terdapat 64 tumpukan cakram emas. Para pendeta mendapat tugas untuk memindahkan cakram emas itu ke tiang yang lain sesuai dengan suatu aturan. Tidak jelas apakah ini benar-benar legenda, atau inspirasi dari Lucas sendiri. Konon, Dewa Brahma menciptakan tiga tiang pada candi tersebut. Pada salah satu tiang terdapat tumpukan cakram emas sebanyak 64 keping, dengan urutan keping yang terbesar terletak di bawah, makin ke atas makin kecil. Selanjutnya Dewa Brahma memerintahkan para pendeta untuk memindahkan keping-keping emas itu dengan aturan : setiap perpindahan hanya boleh memindah 1 cakram dan cakram yang besar tidak boleh diletakkan di atas cakram yang lebih kecil. Dalam legenda itu dikatakan bahwa dunia akan berakhir jika para pendeta tersebut selesai memindahkan ke 64 cakram.

Dilihat  dari  karakteristik  persoalan  slide  puzzle ,  puzzle   ini  membentuk ruang  solusi  yang  diorganisasikan  ke  dalam  struktur  pohon  dinamis.   Struktur pohon dinamis sendiri dibangun dengan 2 metode traversal yaitu   Breadth  First  Search   (BFS)  dan  Depth  First  Search   (DFS)  [MUN04].   Untuk itu penulis menerapkan algoritma Depth   First Search dalam menyelesaikan permainan  menara hanoi . 

B.     RUMUSAN MASALAH 

Berdasarkan  latar  belakang  permasalahan  di  atas,  maka  penulis  menerapkan pencarian solusi  slide puzzle  dengan menggunakan algoritma  Depth First Search . 

C.       TUJUAN DAN MANFAAT 

Tujuan dari tugas akhir ini adalah mengimplementasikan penerapan algoritma  Depth  First  Search  sehingga  dapat digunakan untuk mengoptimalkan waktu dalam menyelesaikan permainan  Menara hanoi   yang  umumnya  tidak  dapat  digunakan  jika  penyelesaian  permainan dilakukan secara manual (menggunakan orang sebagai pemain) 

Manfaat  dari  tugas  akhir  ini  adalah  menambah  ragam  permainan 

Menara hanoi yang telah ada sehingga dapat digunakan sebagai salah satu media  alternatif untuk mengisi waktu senggang. Selain itu, permainan  menara hanoi  juga termasuk  salah  satu  jenis  permainan  edukasi  sehingga  dapat  digunakan  untuk melatih kemampuan nalar dan logika seseorang 

BAB II

PEMBAHASAN

A.     KECERDASAN BUATAN 

Artificial Intelligence  (AI) atau kecerdasan buatan merupakan cabang  dari  ilmu  komputer  yang  berhubungan  dengan  pengautomatisasi  tingkah laku  cerdas.  Pernyataan  tersebut  juga  dapat  dijadikan  definisi  dari  AI. Definisi ini menunjukkan bahwa AI adalah bagian dari komputer sehingga   harus  didasarkan  pada  sound  theoretical   (teori  suara)  dan  prinsip-prinsip   aplikasi  dari  bidangnya.  Prinsip-prinsip  ini  meliputi  struktur  data  yang digunakan dalam representasi pengetahuan, algoritma yang diperlukan untuk mengaplikasikan  pengetahuan  tersebut, serta bahasa dan teknik pemrograman yang digunakan dalam mengimplementasikannya.   Dari beberapa perspektif, AI dapat dipandang sebagai: 

1)       Dari perspektif kecerdasan, AI adalah bagaimana membuat mesin yang  cerdas  dan  dapat  melakukan  hal-hal  yang  sebelumnya  hanya  dapat  dilakukan manusia.

2)      Dari  perspektif  bisnis,  AI  adalah  sekelompok  alat  bantu  (tools)   yang  berdayaguna  dan  metodologi  yang  menggunakan  alat-alat  bantu  tersebut untuk menyelesaikan masalah-masalah bisnis.

3)      Dari perspektif pemrograman, AI meliputi studi tentang pemrograman  simbolik, pemecahan masalah, dan proses pencarian  (search) . 

4)      Dari perspektif penelitian: 

a)      Riset  tentang  AI  dimulai  pada  awal  tahun  1960-an,  percobaan   pertama  adalah  membuat  program  permainan  catur,  membuktikan teori, dan  general problem solving . 

b)      Artificial intelligence  adalah nama pada akar dari studi area. 

Ada dua hal yang sangat mendasar mengenai penelitian-penelitian AI, yaitu  knowledge  representation   (representasi  pengetahuan)  dan  search (pelacakan).  Para  peneliti  AI  terus  mengembangkan  berbagai  jenis  teknik  baru dalam menangani sejumlah permasalahan yang tergolong ke dalam AI seperti  vision  dan percakapan, pemrosesan bahasa alami, dan permasalahan  khusus seperti diagnosa medis.  AI  seperti  bidang  ilmu  lainnya  juga  memiliki  sejumlah  sub-disiplin  ilmu  yang  sering  digunakan  untuk  pendekatan  yang  esensial  bagi 

penyelesaian  suatu  masalah  dan  dengan  aplikasi  bidang  AI  yang  berbeda. 

Setiap permainan memiliki aturan main. Hal ini mempermudah upaya menghasilkan  ruang  pencarian  dan  memberikan  kebebasan  pada  para   peneliti  dari  bermacam-macam  ambisi  dan  kompleksitas  sifat  serta   kurangnya struktur permasalahan. Papan konfigurasi yang digunakan untuk  memainkan  permainan  ini  mudah  direpresentasikan  pada  komputer  dan  tidak memerlukan bentuk yang kompleks.  Permainan  dapat  menghasilkan  sejumlah  besar  pencarian  ruang.  Hal  ini  cukup  besar  dan  kompleks  sehingga  membutuhkan  suatu  teknik  yang  tangguh untuk menentukan alternatif pengeksplorasian ruang permasalahan.

Teknik  ini  dikenal  dengan  nama  heuristik   dan  merupakan  area  utama  dari  penelitian tentang AI. Banyak hal yang biasanya dikenal sebagai kecerdasan  tampaknya  berada  dalam  heuristik   yang  digunakan  oleh  manusia  untuk  menyelesaikan permasalahannya.

B.     TEKNIK-TEKNIK DASAR PENCARIAN 

Pencarian  atau  pelacakan  merupakan  salah  satu  teknik  untuk  menyelesaikan  permasalahan  AI.  Keberhasilan  suatu  sistem  salah  satunya  ditentukan oleh kesuksesan dalam pencarian dan pencocokan. Teknik dasar  pencarian  memberikan  suatu  kunci  bagi  banyak  sejarah  penyelesaian  yang  penting dalam bidang AI. Ada beberapa aplikasi yang menggunakan teknik pencarian ini, yaitu:

·         Engineering 

·         Scientific Analysis 

·         Medical diagnosis 

·         Financial Analysis 

·         Mathematics 

·         Games 

·         Robotics 

·         Natural Language System 

STRATEGI PENCARIAN MENDALAM 

Pencarian boleh jadi merupakan hasil dari suatu solusi ruang keadaan  yang mungkin telah terkunjungi semua, tetapi tanpa penyelesaian. Pencarian yang mendalam  (Exchausting Search Strategy)   mungkin dilakukan dengan  menggunakan  strategi  Breadth  First  Search  atau  Depth  First  Search  (Iterative Deepening).  Kedua pencarian ini merupakan pencarian buta  (blind search) . 

1)      Breadth First Search 

Prosedur  Breadth  First  Search   merupakan  pencarian  yang dilakukan dengan mengunjungi tiap-tiap  node  secara sistematis pada  setiap  level  hingga  keadaan  tujuan  (goal  state)   ditemukan dengan  kata  lain,  penulusuran  yang  dilakukan  adalah  dengan   mengunjungi tiap-tiap  node  pada level yang sama hingga ditemukan  goal  state –nya

2)      Depth First Search 

Pencarian dengan metode ini dilakukan dari  node  awal secara  mendalam  hingga  yang  paling  akhir  (dead-end)   atau  sampai  ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih  dahulu dikunjungi. proses  pencarian  dilakukan  dengan  mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir.  Jika  tujuan  yang  diinginkan  belum  tercapai  maka  pencarian  dilanjutkan  ke  cabang  sebelumnya,  turun  ke  bawah  jika  memang masih  ada  cabangnya.  Begitu  seterusnya  hingga  diperoleh  tujuan  akhir  (goal) .  Depth First Search , seperti halnya  Breadth First Search , juga  memiliki  kelebihan  di  antaranya  adalah  cepat  mencapai  kedalaman  ruang pencarian. Jika diketahui bahwa lintasan solusi permasalahan akan  panjang  maka  Depth  First  Search   tidak  akan  memboroskan waktu  untuk  melakukan  sejumlah  besar  keadaan  dangkal  dalam permasalahan graf.  Depth First Search  jauh lebih efisien untuk ruang initial state .

jika  ada  lebih  dari  satu  solusi  maka  solusi  minimum akan ditemukan.  Namun  ada  tiga  persoalan  utama  berkenaan  dengan  Breadth  First Search  ini yaitu: 

a)      Membutuhkan  memori  yang  lebih  besar,  karena  menyimpan  semua  node  dalam satu pohon.

b)      Membutuhkan  sejumlah  besar  pekerjaan,  khususnya  jika lintasan  solusi  terpendek  cukup  panjang,  karena  jumlah  node   yang  perlu  diperiksa  bertambah  secara  eksponensial  terhadap  panjang lintasan.

c)      Tidak relevannya operator akan menambah jumlah  node  yang  harus diperiksa. Oleh  karena  proses  Breadth  First  Search   mengamati  node   di  setiap  level  graf  sebelum  bergerak  menuju  ruang  yang  lebih  dalam  maka  mula-mula  semua  keadaan  akan  dicapai  lewat  lintasan  yang  terpendek  dari  keadaan  awal.  Oleh  sebab  itu,  proses  ini  menjamin  ditemukannya  lintasan  terpendek  dari  keadaan  awal  ke  keadaan  tujuan  (akhir).  Lebih  jauh  karena  mula-mula  semua  keadaan  ditemukan melalui lintasan terpendek sehingga setiap keadaan yang  ditemui  pada  kali  kedua  didapati  pada  sepanjang  sebuah  lintasan  yang sama atau lebih panjang. Kemudian, jika tidak ada kesempatan ditemukannya  keadaan  yang  identik  pada  sepanjang  lintasan  yang  lebih baik maka algoritma akan menghapusnya

C.     PERMAINAN MENARA HANOI

Menara Hanoi merupakan salah satu diantara berbagai teka-teki dalam matematika. Teka-teki ini ditemukan Edouard Lucas, ahli matematika Perancis di tahun 1883. Teka-teki ini berdasarkan pada sebuah cerita legenda tentang candi Indian atau menara Benares di India yang memiliki tiga tiang dan salah satu tiangnya terdapat 64 tumpukan cakram emas. Para pendeta mendapat tugas untuk memindahkan cakram emas itu ke tiang yang lain sesuai dengan suatu aturan. Tidak jelas apakah ini benar-benar legenda, atau inspirasi dari Lucas sendiri. Konon, Dewa Brahma menciptakan tiga tiang pada candi tersebut. Pada salah satu tiang terdapat tumpukan cakram emas sebanyak 64 keping, dengan urutan keping yang terbesar terletak di bawah, makin ke atas makin kecil. Selanjutnya Dewa Brahma memerintahkan para pendeta untuk memindahkan keping-keping emas itu dengan aturan : setiap perpindahan hanya boleh memindah 1 cakram dan cakram yang besar tidak boleh diletakkan di atas cakram yang lebih kecil. Dalam legenda itu dikatakan bahwa dunia akan berakhir jika para pendeta tersebut selesai memindahkan ke 64 cakram.

 Identifikasi Ruang Keadaan

Permainan Menara Hanoi yang akan di bahas kali ini menggunakan 3 menara dan 4 piringan. Dimana ukuran piringan tersebut berbeda satu sama lain. Semua piringan berada pada menara asal dengan susunan secara berurutan, yang terbesar berada pada posisi paling bawah dan yang terkecil pada posisi paling atas seperti yang tampak pada gambar di bawah ini

Keadaan Awal dan Keadaan Tujuan

Dalam proses pemecahan masalah permainan Menara Hanoi perlu ditetapkan suatu keadaan awal dan keadaan tujuan untuk mempermudah penyelesaiannya.

1)      Keadaan Awal

Bila didefinisikan menara A sebagai menara asal, menara C sebagai menara tujuan dan menara B sebagai menara sementara, dengan 4 jumlah piringan yang masing-masing didefinisikan sebagai N1, N2 dan N3 dimana ukuran N4 > N3> N2> N1. Menara A berisi  4 piringan dengan susunan N4, N3, N2, N1 dari bawah ke atas. Sedangkan menara C dan B dalam kondisi tidak ada piringan (kosong).

2)      Keadaan tujuan

Menara A dan B kosong, sedangkan menara C berisi piringan N4, N3, N2, N1 tersusun dari bawah ke atas seperti yang terlihat.

Dasar Aturan (Rule Base)

Untuk mencapai keadaan tujuan maka dibuatlah aturan-aturan yang dapat memenuhi semua keadaan yang mungkin terjadi. Adapun aturan-aturan tersebut adalah sebagai berikut :

1. Jika B kosong atau N_B> N_A, pindahkan N_A ke B
2. Jika C kosong atau N_C > N_A, pindahkan N_A ke C
3. Jika A kosong atau N_A > N_B, pindahkan N_B ke A
4. Jika C kosong atau  N_C > N_B, pindahkan N_B ke C
5. Jika A kosong atau N_A > N_C, pindahkan N_c ke A
6. Jika B kosong atau N_B > N_C, pindahkan N_C ke B

Solusi

Salah satu metode yang dapat dipakai dalam proses pemecahan permasalahan pada Menara Hanoi yaitu dengan menggunakan metode DFS (Depth First Search) atau pencarian mendalam.

Metode DFS (Depth First Search) merupakan metode pencarian yang dilakukan pada suatu simpul dalam setiap level dari yang paling kiri. Jika pada level yang terdalam solusi belum ditemukan, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.

Kelebihan dari metode Depth First Search yaitu :

• Jika solusi yang dicari berada pada level yang dalam dan paling kiri maka DFS akan menemukannya dengan cepat.
• Jika diimplementasikan dalam program, penggunaan memori akan lebih sedikit karena hanya simpul-simpul pada lintasan yang aktif saja yang disimpan.

Adapun kelemahan dari metode Depth First Search yaitu :

• Jika pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga), maka tidak ada jaminan menemukan solusi. Artinya DFS tidak komplit.
• Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang paling baik. Artinya DFS tidak optimal.

Langkah-langkah pencarian solusi menggunakan metode DFS adalah   sebagai berikut:

1. Solusi dicari dengan membentuk lintasan dari akar sampai daun. Simpul-simpul yang sudah dilahirkan dinamakan simpul anak kiri dan simpul anak kanan.
2. Simpul yang dibentuk, terlebih dahulu simpul sebelah kiri dan mendalam sampai ditemukan solusi.
3. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi, maka lintasan yang sebelah kiri dihentikan disebut simpul mati dan dilanjutkan ke simpul anak kanan terdekat. Simpul yang sudah dihentikan (simpul mati) tidak akan pernah diperluas lagi.
4. Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan pembentukan ke simpul hidup terdekat. Selanjutnya simpul ini menjadi simpul hidup yang baru.
5. Lintasan baru dibangun kembali sampai lintasan tersebut membentuk solusi.

Solusi permasalahan untuk pemindahan seluruh piringan dari menara asal ke menara tujuan pada permainan Menara Hanoi dengan metode DFS dapat dilihat pada tabel dan gambar berikut ini.

Tabel Solusi Permainan Menara Hanoi

BAB III

PENUTUP

A.    Kesimpulan

Dengan metode DFS (Depth First Search), proses pemecahan masalah pada permainan Menara Hanoi dapat disimpulkan sebagai berikut:

• Metode DFS mampu menyelesaikan masalah pada permainan Menara Hanoi.
• Sesuai dengan kelebihan pada metode DFS, telah terbukti bahwa pemecahan permasalahan permainan Menara Hanoi dapat diselesaikan dengan beberapa solusi. Dimana solusi dari permasalahan tersebut yang terbaik adalah solusi yang paling cepat ditemukan dimana letak solusi yang dicari berada pada level yang dalam dan paling kiri.
• Untuk N buah piringan diperlukan pemindahan sebanyak 2ⁿ – 1 kali. Ternyata dengan menggunakan metode DFS  terbukti pula untuk 3 buah piringan dapat diselesaikan dengan 2 ⁴ – 1 langkah = 7 langkah.

DAFTAR REFERENSI

Atmavidya, Arif Nanda, Penerapan Algoritma Backtracking dalam Pencarian Solusi Menara Hanoi,  Institut Teknologi Bandung, 2008

Mukti, Garibaldy W, Berbagai Solusi Pemecahan Masalah Tower of Hanoi dan Representasi Grafnya, Institut Teknologi Bandung, 2008

Santosa, Insap, Struktur Data menggunakan Turbo Pascal, Andi Offset Yogyakarta, 2003

Suyanto, Artificial Intelligence, Informatika Bandung, 2007

Wikipedia, http://en.wikipedia.org/wiki/Tower_of_Hanoi, diakses 10 Desember 2008

http://rusdyana.wordpress.com/2009/

hidjah, khasnur dkk, penerapan metode depth first search (dfs)

Pada permainan menara Hanoi,UGM, Yogyakarta.2008