## Implementasi Penyelesaian Permasalahan Algoritma Ascent Hill Climbing Pada Puzzle-8
Yopy Mardiansyah 1* , Sestri Novia Rizki 2 1 Institut Teknologi Batam, Indonesia
2 Akademi Manajemen Informatika dan Komputer (KOSGORO), Indonesia e-mail: yopi@iteba.ac.id, noviasestri@gmail.com
Abstract
Puzzle is an arrangement of numbers consisting of nine squares that are neatly arranged in a sequence  of  numbers  1  to  number  8.  Puzzle  games  are  interesting,  fun  games  and  improve cognitive abilities, how to think quickly and are able to  develop  children's brains to  increase their grasping power in solving a problem. . The problem that occurs in this study is the lack of children's  ability  to  solve  the  logic  of  compiling  puzzles,  so  make  rules  and  steps  to  quickly complete  this  game.  The  main  purpose  of  this  research  is  to  help  children  improve  their thinking patterns so they can arrange numbers 1 to 8 with fast time and solutions. The method used  is the Best First Search algorithm in finding the Final Goal quickly and easily. The final result of this research, after several stages of eating, the final result is that the puzzle sequence has fulfilled the final goal according to the initial data. The basic concept of solving the Best First  Search  Algorithm  must  follow  the  rules  that  have  been  set  by  running  the  process  in accordance  with  existing  procedures.  If  in  the  search  process  an  unsuitable  arrangement  is found,  then  proceed  with  the  next  search  until  it  finds  the  correct  position  in  the  form  of  a sequence of numbers 1 to 8. If it is found, the search algorithm is stopped.
Keywords: Artificial Intelligence, Searching, Best First Search Algorithm, Puzzle-8, Goal State

## Abstrak
Puzzle merupakan susunan angka yang terdiri dari Sembilan Kotak yang tersusun rapi dengan urutan  angka  1  sampai  angka  8.  Permainan  puzzle  merupakan  permainan  yang  menarik, menyenangkan  dan  meningkatkan  kemampuan  kognitif  cara  berfikir  secara  cepat  serta mampu  mengasa  otak  anak  anak  untuk  meningkatkan  daya  tangkap  dalam  menyelesaikan sebuah  permasalahan.  Permasalahan  yang  terjadi  dalam  penelitian  ini  yaitu  kurangnya kemampuan anak anak dalam menyelesaikan logika penyusunan puzzle, sehingga buat aturan serta  langkah  langkah  agar  cepat  menyelesaikan  permainan  game  ini.  Tujuan  Utama penelitian ini membantu anak anak meningkatkan pola pikir anak-anak agar bisa menyusun susunan angka 1 sampai 8 dengan waktu dan solusi yang cepat. Metode yang digunakan yaitu algoritma Best First Search dalam pencarian Goal Akhir dengan cepat dan mudah. Hasil akhir penelitian  ini  setelah  dilakukan  dari  beberapa  tahap  makan  diperoleh  hasil  akhir  bahwa urutan  Puzzle  sudah  menepati  Goal  akhir  sesuai  dengan  data  awal.  Konsep  dasar penyelesaikan  Algoritma  Best  First  Search  harus  mengikuti  aturan  yang  sudah  ditetapkan dengan  menjalankan  proses  sesuai  dengan  prosedur  yang  ada.  Jika  dalam  proses  pencarian ditemukan susunan yang tidak sesuai maka dilanjutkan dengan pencarian selanjutkan sampai menemukan posisi yang benar dalam bentuk urutan angka 1 sampai 8. Jika sudah ditemukan makan pencarian algoritma dihentikan.
Kata kunci : Kecerdasan Buatan, Searching, Algoritma Best First Search, Puzzle-8, Goal State

## 1. PENDAHULUAN
Artificial Intelligence (AI)  atau  kecerdasan  Buatan  dapat  didefinisikan sebagai  cabang  ilmu  komputer  yang  mempelajari  otomatisasi  tingkah  laku
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume 6 Nomor 1, Maret 2022, pp. 583-590 ISSN: 2548-9771/EISSN: 2549-7200 https://tunasbangsa.ac.id/ejurnal/index.php/jsakti
cerdas  ( intelligence )  atau  dengan  kata  lain Artificial  Intelligence (AI) merupakan sub bidang pengetahuan komputer yang khusus ditujukan untuk membuat software dan hardware yang sepenuhnya bisa menirukan beberapa fungsi otak manusia. Dengan demikian diharapkan komputer bisa membantu manusia di dalam memecahkan berbagai masalah yang lebih rumit[1]. Puzzle merupakan  sebuah  permainan  sederhana  yang  berbentuk  teka-teki. Puzzle dirancang  sebagai  media  hiburan  dengan  menyajikan  kesulitan  yang  harus diselesaikan  dengan  kecerdikan  dan  kesabaran  [2].  Salah  satu  permainan untuk  meningkatkan  kemampuan  membilang  anak  adalah  dengan menggunakan puzzle. Puzzle merupakan bentuk permainan yang menantang daya  kreativitas  dan  ingatan  anak  lebih  mendalam  dikarenakan  munculnya motivasi  untuk  senantiasa  mencoba  memecahkan  masalah,  namun  tetap menyenangkan  sebab  dilakukan  dengan  cara  diulang-ulang.  Tantangan permainan  ini  selalu  memberikan  efek  ketagihan  untuk  selalu  mencoba, mencoba dan terus mencoba hingga berhasil. Pada saat bermain, setiap anak sangat  menikmati  permainannya  tanpa  terkecuali[3].  Pertama  kali  puzzle yang  dibuat  adalah  jigsaw  puzzle.  Pada  tahun  1766  oleh  John  Spilsbury seorang  ahli  pembuat  peta,  jigsaw  puzzle  tercipta  melalui  idenya  yaitu menggambar  sebuah  peta  pada  lembaran  kayu  dan  dipotong-potong berdasarkan batas garis negaranya. Puzzle ini dibuat untuk membantu dalam pelajaran [4][5].
Metode yang dipakai pada penelitian ini adalah Simple hill climbing dan Ascent  Hill  Climbing.Proses  penyelesaian  penelitian  ini  dengan caramencari,mengumpulkan,serta  mempelajari  dan  menganalisi  contoh karya  penelitian  yang  terdahulu  serta  mencari  buku  dan  sumber  sumber yang  akurat  agar  memperoleh  penelitian  yang  bagus.  Dari  beberapa  Jurnal yang dipelajari sangat berkaitan dengan penelitian saat ini, karena penelitian terdahulu  juga  membahas  cara  penyelesaian  untuk  metode  Hill  Climbing dalam  kasus  Puzzle  8  [6].  Metode steepest  ascent  hill  climbing merupakanmetode  algoritma  yang  banyak  digunakan  untuk  permasalahan optimasi.  Salah  satu  penerapannya  adalah  untuk  mencari  rute  yang terpendek  dengan  cara  memaksimumkan  atau  meminimumkan  nilai  dari fungsi optimasi yang ada. Fungsi optimasi yang dimaksud yaitu penggantian titik pengguna, sehingga mempengaruhi rute terpendek yang dicari. Metode steepest  ascent  hill  climbing dapat  memberikan  rute  menuju  fasilitas pelayanan  darurat  di  kota  Bogor.  Metode steepest  ascent  hill  climbing digunakan pada penelitian ini untuk penyelesaian masalah rute optimal antar tempat  wisata  di  kota  Bandung  dengan  memperhatikan  aspek  jarak  yang optimal [7].
Analisa  awal  pada  permainan  Puzzle  8  yaitu  mengikuti  aturan  yang sudah  ada  pada  metode  Ascent  Hill  Climbing  dengan  mengikuti  4  Aturan yaitu:
a) Geser posisi Kotak kesebelah Kanan;
b) Geser posisi Kotak kesebelah Kiri;
c) Geser posisi Kotak ke Atas.
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume 6 Nomor 1, Maret 2022, pp. 583-590 ISSN: 2548-9771/EISSN: 2549-7200 https://tunasbangsa.ac.id/ejurnal/index.php/jsakti

## d) Geser posisi Kotak ke Bawah
Setelah  itu  lihat  keadaan  awal  atau  data  mentah  dan  bandingkan dengan  tujuan  akhir,  maka  langkah  selanjutnya  nya  adalah  proses  data dengan  mengikuti  empat  tahap  aturan  yang  sudah  ada.  Untuk  lebih  mudah buat  gambar  puzzel  secara  sistematis  agar  proses  pencarian  mudah menemukan solusi [9].  Pada berbagai referensi, ada beberapa nilai heuristic yang  dapat  dijadikan  acuan  untuk  permasalahan  8-Puzzle.  Salah  satu  yang cukup terkenal adalah Manhattan Distance. Manhattan Distance didefinisikan sebagai penjumlahan jarak masingmasing kotak 8-Puzzle terhadap posisinya yang  benar  pada  kondisi goal .  Sehingga,  pada  kondisi goal , heuristic pasti akan bernilai 0, karena semua kotak sudah pada posisinya masing-masing (jarak  dengan  posisinya  yang  benar  =  0).  Cara  pendekatan  seperti  ini  telah cukup  dianggap admissible atau masuk akal [8].
Perbedaan Simple  Hill  Climbing ,  secara  sederhana,  langsung  memilih new state yang memiliki jalur yang lebih baik (“curam”) daripada jalur-jalur sebelumnya  tanpa  memperhitungkan  jalur-jalur  lain  yang  lebih  “curam”. Sedangkan Steepest  Ascent  Hill  Climbing ,  sesuai  dengan  namanya,  akan mengevaluasi  semua state yang  berada  dibawah current state dan  memilih state dengan  jalur  paling  “curam”[9].  Algoritma  ini  memeriksa  titik  (node), yaitu  biaya  ( cost )  yang  dibutuhkan  untuk  mencapai  sebuah  node  dan heuristik  node/  h(n)  yaitu cost yang  didapat  dari  node  ke  tujuan.  Sehingga dapat dirumuskan  sebagai berikut : f(n)   = h(n) f(n)   = perkiraan total cost terendah dari setiap path yang akan dilalui dari node n ke node tujuan.
h(n)   = perkiraan heuristik atau cost atau path dari node n ke tujuan. Metode steepest ascent hill climbing ini merupakan pengembangan dari metode simple hill climbing . Bedanya adalah simple hill climbing menentukan next  state dengan  membandingkan current  state (titik  awal)  dengan  satu successor (titik persimpangan) dan successor pertama yang lebih baik akan dipilih  menjadi next state .  Sedangkan steepest ascent akan  membandingkan current  state dengan  semua succesor yang  ada  didekatnya  sehingga  dalam steepest ascent hill climbing , next statenya merupakan successor yang  paling baik  atau  paling  mendekati  tujuan.  Berikut  adalah  perbandingan  algoritma steepest ascent hill climbing dengan hill climbing :
a) Evaluasi state awal,  jika state awal  sama  dengan  tujuan,  maka  proses berhenti.  Jika  tidak  sama  dengan  tujuan  maka  lanjutkan  proses  dengan membuat state awal sebagai state sekarang.
b) Kerjakan langkah berikut sampai solusi ditemukan atau sampai tidak ada lagi operator baru yang dapat digunakan dalam state sekarang :
1) Cari  sebuah  operator  yang  belum  pernah  digunakan  dalam state sekarang dan gunakan operator tersebut untuk membentuk state baru.
2) Evaluasi state baru.
i. Jika state baru adalah tujuan, maka proses berhenti;
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume 6 Nomor 1, Maret 2022, pp. 583-590 ISSN: 2548-9771/EISSN: 2549-7200 https://tunasbangsa.ac.id/ejurnal/index.php/jsakti
ii. Jika state baru  tersebut  bukan  tujuan  tetapi state baru  lebih  baik dari  pada state sekarang,  maka  buat state baru  menjadi state sekarang;
iii. Jika state baru  tidak  lebih  baik  dari  pada state sekarang,  maka lanjutkan ke langkah Algoritma steepest ascent hill climbing.
c) Evaluasi  keadaan  awal  ( Initial  State ).  Jika  keadaan  awal  sama  dengan tujuan  ( Goal  state )  maka  kembali  pada initial  state dan  berhenti berproses.  Jika  tidak  maka initial state tersebut  jadikan  sebagai current state .
d) Mulai dengan current state = initial state .
e) Dapatkan semua pewaris ( successor ) yang dapat dijadikan next state pada current state nya  dan  evaluasi successor tersebut  dengan  fungsi  evaluasi dan beri nilai pada setiap successor tersebut. Jika salah satu dari successor tersebut mempunyai nilai yang lebih baik dari current state maka jadikan successor dengan nilai yang paling baik tersebut sebagai new current state . Lakukan  operasi  ini  terus  menerus  hingga  tercapai current state = goal state atau tidak ada perubahan pada current statenya[10] .
. 2. METODOLOGI PENELITIAN
Metodelogi  Penelitian  merupakan  gambaran  dalam  menyelesaikan sebuah  Goal.  Dalam  penyelesaian  kasus  ini    dibutuhkan  langkah  langkah sebagai berikut:

## Gambar 1. Metodelogi Penelitian
a) Identifikasi Masalah.
Mengidentifikasi  bagaimana  cara  menyelesaikan  permasalahan  pada Puzzle 8 agar menemukan goal Akhir.
b) Study Literatur. Mencari  sumber  sumber  ilmu  yang  berhubungan  dengan  kecerdasan buatan,  searching  dan  Puzzle-8,  baik  dari  buku,  jurnal,  dan  informasi lainnya.
c) Analisa Data. Menganalisa data Puzzle-8 dari keadaan awal sampai state akhir dengan memperhatika prosedur untuk memperoleh hasil akhir.
d) Perancangan Metode Ascent Hill Climbing. Merancang proses algoritma yang telah dilakukan.
e) Pengujian. Pengujian ini bertujuan untuk memastika apakah hasil goal penelitian ini sudah benar.

## 3. HASIL DAN PEMBAHASAN
Hasil  Algoritma  Ascent  Hill  Climbing  diperoleh  dari  beberapa  tahap seleksi dari masing masing iterasi yang dilakukan. Jika ditemukan nilai posisi yang  benarnya  sama  maka  harus  dicari  masing  masing  nilai  tersebut. Bandingkan mana hasil yang mendekati Goal Akhir.

## 3.1. Algoritma Ascent Hill Climbing
Bentuk Penyelesaian Ruang keadaan Contoh:       x= baris =[ 1.2.3]           y = Kolom = [1.2.3]. Dengan  demikian  diumpamakan    ruang  keadaan  =  seluruh  kemungkinan posisi  kota  pada  puzzle  8  Kita  masukkan  posisi  puzzle  pada  angkat  7  yang berada pada keadaan awal dengan posisi 3.1.
Aturan aturan yang harus dilewati diantaranya: Posisi kotak awal kosong(x,y) X= Baris kotak yang masih kosong Y= Kolom kotak yang masih kosong
1) Aturan  dasar  yang  harus  dikerjakan  berupa  gerakkan  kotak  kosong  ke atas Puzzle dimana if x>1 then (x-1,y);
2) Aturan  dasar  yang  harus  dikerjakan  berupa  gerakkan  kotak  kosong  ke bawah Puzzle  if x<3 then (x+1,y);
3) Aturan  dasar  yang  harus  dikerjakan  berupa  gerakkan  kotak  kosong  ke kanan Puzzle  if x<3 then (x,y+1);
4) Aturan  dasar  yang  harus  dikerjakan  berupa  gerakkan  kotak  kosong  ke kiri Puzzle  if x>1 then (x,y-1);
a) Tahap Pencarian Pertama
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume 6 Nomor 1, Maret 2022, pp. 583-590 ISSN: 2548-9771/EISSN: 2549-7200 https://tunasbangsa.ac.id/ejurnal/index.php/jsakti
b) Tahap Pencarian Kedua
c) Tahap Pencarian Ketiga
d) Tahap Pencarian Kempat
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume 6 Nomor 1, Maret 2022, pp. 583-590 ISSN: 2548-9771/EISSN: 2549-7200 https://tunasbangsa.ac.id/ejurnal/index.php/jsakti
e) Tahap Pencarian Kelima
f) Tahap Pencarian Goal State
1 2 3 8 4 7 6 5
Posisi Benar = 8 Pencarian dihentikan

## 3.2. Penyelesaian
Untuk menyelesaikan algoritma harus mengikuti prosedur yang sudah ditetapkan.  Dalam  setiap  pencarian  akan  ditemukan  Solusi  nilai  Keadaan posisi  Benar  sudah  banyak  dari  nilai  posisi  keadaan  yang  salah.  Hasil perbandingan dapat dilihat pada Tabel dibawah ini :
Tabel 1. Proses perhitungan Nilai No Proses Goal Akhir Nilai Jumlah 1 B+B+B+S+S+S+S+S 1+1+1+0+0+0+0+0 3 2 B+B+B+S+S+S+S+S 1+1+1+0+0+0+0+0 3 3 B+B+B+S+S+S+S+S 1+1+1+0+0+0+0+0 3 4 B+B+B+S+S+S+S+B 1+1+1+0+0+0+0+1 4 5 B+B+B+S+S+S+B+B 1+1+1+0+0+0+1+1 5 6 B+B+B+S+S+B+B+B 1+1+1+0+0+1+1+1 6 7 B+B+B+S+B+B+B+B 1+1+1+0+1+1+1+1 7 8 B+B+B+B+B+B+B+B 1+1+1+1+1+1+1+1 8
Dari  gambar  di  atas  dapat  dijelaskan  bahwa  dalam  menyelesaikan kasus  ini  dibutuhkan  5  tahap  untuk  memperoleh Goal  Akhir.  Nilai  1  atau  B menjelaskan  bahwa  posisi  Benar,  dan  Nilai  0  atau  S  menjelaskan  Posisi Puzzle  yang  salah.  Dari  gambar  diatas  juga  dapat  diartikan  bahwa  semakin banyak  proses  iterasi  maka  semakin  banyak  peluang  posisi  Puzzle  yang benar.  Jika  susunan  Puzzle  sudah  sesuai  dengan  keadaan  awal  maka pencarian  dihentikan,  dan  Goal  sudah  memenugi  syarat  untuk  hasil  akhir Algoritma Ascent Hill Climbing.
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume 6 Nomor 1, Maret 2022, pp. 583-590 ISSN: 2548-9771/EISSN: 2549-7200 https://tunasbangsa.ac.id/ejurnal/index.php/jsakti

## 4. SIMPULAN
Berdasarkan  hasil  akhir  yang  diperoleh  dalam  penelitian  ini  maka dapat  disimpulkan  bahwa  Algoritma  Ascent  Hill  Climbing  mampu menyelesaikan kasus Puzzle-8 dengan proses iterasi sebanyak 5 kali dengan proses yang cepat sehingga  bisa memperoleh Goal state Akhir, Algoritma ini bisa  dijadikan  acuan  dalam  menyelesaikan  kasus  searching  dengan  syarat mengikuti aturan yang sudah ditetapkan. Jika saat pencarian ditemuan nilai Benar yang sama, maka harus dilakukan pencarian ke dua nilai tersebut, Pilih nilai  mana  yang  mendekati  Goal.  Diharapkan  penelitian  ini  bisa dikembangkan lebih dalam dalam kasus yang berbeda.

## DAFTAR PUSTAKA
[1] Muhammad Aqil Arviansyah, dkk. 2019. “Aplikasi Game Battle Puzzle Dengan.” Aplikasi Game Battle Puzzle Dengan Metode Best First Search 3 (April): 60–65.
[2]   Hermawan, Deny Prasetia,  Darlis Herumurti, dan Imam Kuswardayan. 2017. “Efektivitas Penggunaan Game Edukasi Berjenis Puzzle, RPG dan Puzzle RPG Sebagai  Sarana  Belajar  Matematika.” JUTI:  Jurnal Ilmiah  Teknologi Informasi 15 (2): 195. https://doi.org/10.12962/j24068535.v15i2.a663.
[3]    Nari,  Nola,  Yulia  Akmay,  dan  Dewi  Sasmita.  2020.  “Penerapan  permainan puzzle  untuk  meningkatkan  kemampuan  membilang.” Jurnal  Pembangunan Pendidikan: Fondasi dan Aplikasi 7 (1): 44–52. https://doi.org/10.21831/jppfa.v7i1.26499.
[4]   Engel.  2014.  “Permainan  Edukatif  Dengan  Media  Puzzle  Mengembangkan Kemampuan Kognitif Anak Usia 4 - 5 Tahun Tk Islamiyah Mahardikha,.” Paper Knowledge . Toward a Media History of Documents .
[5]      Auditya,  Luthfie,  Condro  Kartiko,  dan  Citra  Wiguna.  2020.  “Jurnal  Edik Informatika  Jurnal  Edik  Informatika.” Penelitian Bidang  Komputer  Sains  dan Pendidikan Informatika 7 (1): 9–18.
[6]     Febri,  Mike,  dan  Mayang  Sari.  2021.  “Penerapan  Algoritma  Ascent  Hill Climbing  Pada  Game  Edukasi  Penyusunan  Deretan  Angka  Puzzle-8.” Jurnal Sistem Komputer dan Informatika (JSON) 3 (2): 141–46.
https://doi.org/10.30865/json.v3i2.3612.
[7]    Afero,  Yosdarso.  2021.  “Artificial  Intelegence  Penerapan  Kasus  Algoritma Ascent  Hill  Climbing  Dalam  Permainan  Puzzle  8.” Elkom : Jurnal Elektronika dan Komputer 14 (2): 325–31. https://doi.org/10.51903/elkom.v14i2.508.
[8]    Abraham, David, dan Indra W Permana. 2016. “Penyelesaian Masalah 8-Puzzle dengan  Algoritma  Steepest-Ascent  Hill  Climbing.” Setrum :  Sistem  Kendali- Tenaga-elektronika-telekomunikasi-komputer 4 (1): 40. https://doi.org/10.36055/setrum.v4i1.465. [9] Adharani, Yana, Emi Susilowati, dan Eko Purwanto. 2017. “Penerapan Metode Simple  Hill  Climbing  Search  Untuk  Pencarian  Lokasi  Terdekat  Sekolah Menengah  Atas  Muhammdiyah.” Sistem Informasi, Teknologi Informatika dan Komputer 7 (2): 15.
[10] Anam,  Hairul,  Feby  Sabilhul  Hanafi,  dan  Ahmad  Fauzal  Adifia.  2018. “Penerapan Metode Steepest Ascent Hill Climb pada Permainan Puzzle” 3 (2): 36–40.