Volume 3, Nomor 2, Desember 2021 e-ISSN 2685-998X DOI 10.30865/json.v3i2.3586

## Penerapan Algoritma Simplified Memory Bounded A* Pada Permainan Hangman Indonesia

## Muhammad Yusuf Batubara*, Mesran, Yasir Hasan
Prodi Teknik Informatika, Fakultas Ilmu Komputer dan Teknologi Informasi, Universitas Budi Darma, Medan, Indonesia Email: 1* myusufbb33@gmail.com, 2 mesran.skom.mkom@gmail.com Email Penulis Korespondensi: myusufbb33@gmail.com Submitted: 04/12/2021 ; Accepted: 15/12/2021 ; Published: 31/12/2021
Abstrak− Permainan Pembelajaran merupakan alat atau pasilitas tambahan yang digunakan untuk menghibur dan menambah wawasan bagi pengguna. Penggunaan permainan pembelajaran atau education games sangat cocok untuk anak-anak, remaja dan orangtua bahkan di semua umur. Edukasi game ini sangat mudah untuk di jangkau dan digunakan karena sudah ada di genggaman setiap orang yaitu HandphonePermainan Hangman adalah sebuah permainan kata yang bertujuan untuk menebak kata apa yang dimaksud oleh penanya dengan menebak huruf satu per satu sehingga tersusun menjadi sebuah kata. Permainan Hangman dahulunya hanya dibuat dari selembar kertas atau di papan tulis di depan para siswa dan menayakan satu persatu kepada si penjawab (siswa) sehingga dengan aktivitas ini jadilah sebuah permainan hangman. Permainan Hangman berbasis android smardphone dari beberapa komponen yang bisa di jalankan di dalam aplikasi  seperti papan huruf, aktor, tiang gantung, tali gantung, kolom jawaban. Penelitian ini menghasilkan aplikasi permianan hangman bertujuan untuk Pembelajaran yang di terapkan di perangkat samartpone android dan untuk di kembangkan di kemudian hari.
Kata Kunci: Permainan Hangman Indonesia, Android, Simplified Memory Bounded A*
Abstract− Learning Games are additional tools or facilities used to entertain and add insight to users. The use of learning games or education games is very suitable for children, teenagers and parents even at all ages. This educational game is very easy to reach and use because it is already in everyone's grasp, Hangman Game Mobile is a word game that aims to guess what the questioners mean by guessing the letters one by one so that they are arranged into a word. The Hangman game used to be only made from a piece  of paper  or  on the blackboard  in front of the students and asked the answer  one by one to the students (students) so that with this activity there was a hangman game. Hangman game based on Android smartphone from several components that can be run inside the application such as letters, actors, hanging poles, ropes, answer columns. This research resulted in a Hangman game application aimed at Learning which was applied on an Android samartpone device and to be developed at a later date.
Keywords : Hangman Indonesia Game; Android; Simplified Memory Bounded A*

## 1. PENDAHULUAN
Indonesia adalah Negara ke-4 yang menduduki peringkat terbanyak yang menggunakan game mobile android. Di era yang semakin berkembang dalam bidang teknologi. Penggunaan perangkat smartphone di kalangan masyarakat sudah seperti kebutuhan pokok yang harus dipenuhi. Lembaga riset digital marketing Emarketer memperkirakan pada 2018 jumlah pengguna aktif smartphone di Indonesia lebih dari 100 juta orang. Dengan jumlah sebesar itu, Indonesia akan menjadi negara dengan pengguna aktif smartphone terbesar ke-empat di Dunia setelah Cina, India, dan Amerika. Smartphone tidak hanya berfungsi sebagai media komunikasi saja tetapi juga sebagai media hiburan, salah  satunya  adalah  aplikasi.  Namun  sayangnya,  dengan  semakin  majunya  teknologi  khususnya  smartphone membuat masyarakat semakin malas untuk berfikir, bergerak dan menjalin komunikasi dengan yang lainnya. Hal itu  terjadi  karena  dalam  smartphone  semua  kebutuhan  sudah  tersedia  tanpa  harus  keluar  rumah.  Seiring perkembangan teknologi smartphone, berbagai fasilitas dan dukungan hardware yang lebih modern menciptakan kinerja smartphone yang lebih kompleks [1].
Sebuah  gambar  orang-orangan  atau  gambar  tubuh  manusia  dalam  sebuah  permainan  di  selembar  kertas sebagai kandidat penjawab pertanyaan, sedangkan seorang kandidat penaya, di sebuat juga sebagai Algojo. Setiap pertanyaan yang diberikan Algojo kepada si penjawab akan mendapatkan sangsi jika salah dalam menebak huruf pada satu kata yang akan disusun maka si penjawab akan mendapatkan hukuman pertama sampai sampai ke-lima di barengi dengan mengumpulkan organ kedua tangan, kedua kaki kepala. Permainan Hangman merupakan sebuah permainan  kata  yang  bertujuan  untuk  menebak  kata  apa  yang  dimaksud  penanya  dengan  menebak  huruf  satu- persatu atau permainan penyusunan huruf untuk mencari kata dan kata-kata yang disusun dalam bentuk array dua dimensi atau yang lebih dikenal dengan matriks. Huruf-huruf tersebut dapat disusun dan membentuk sebuah kata. Permasalahan  yang  dihadapi  adalah  bagaimana  system  dapat  menemukan  semua  huruf  yang  teracak  di  dalam papan keybord.
Sebuah  penelitian  di  bidang  pendidikan  dalam  bentuk  penelitian  tindakan  kelas  tentang  penerapan permainan tebak kata Hangman di Sekolah Menengah Pertama (SMPN 4) Tamiang Layang. Penelitian bertujuan untuk  meningkatkan  kemampuan  kosakata  bahasa  Inggris  siswa  kelas  VIIIB  SMPN  4,  Tamiang  Layang  tahun ajaran  2013-2014  dengan  menggunakan  metode  permainan  hangman.  Penelitian  ini  menggunakan  rancangan penelitian  tindakan  kelas  dengan  2  siklus.  Masing-masing  siklus  terdiri  dari  tahapan  perencanaan,  pelaksanaan tindakan,  observasi  dan  refleksi.  Instrumen  penelitian  berupa  lembar  observasi  aktivitas  guru  dan  siswa,  test kosakata, dan questionnaire [2].
Volume 3, Nomor 2, Desember 2021 e-ISSN 2685-998X DOI 10.30865/json.v3i2.3586
Metode pancarian kata sebelum penelitian ini dibuat sebagian peneliti lain sudah ada menggunakan metode dan aplikasi lain, seperti metode pencarian arti dari sebuah kata yang berbahasa lain disebut juga dengan aplikasi kamus,  pencarian  kata  yang  teracak  dalam  bentuk  papan  permainan  (Puzzle),  dan  masih  banyak  penelitian sebelumnya yang menggunakan motode pencarian kata.
Algoritma Simplified Memory Bounded A* (SMA*) adalah salah satu algoritma pathfinding yang dapat digunakan  untuk  melakukan  pencarian  kata,  algoritma  Simplified  Memory  Bounded  A*  (SMA*)  memiliki kelebihan pada penggunaan memory yang lebih sedikit, hal ini dikarenakan penggunaan memory dibatasi hingga jumlah simpul tertentu. Berdasarkan hasil pengujian bahwa semakin panjang karakter pada kata yang dicari maka waktu pencarian akan semakin lama dan penggunaan memori juka akan semakin besar. Semakin banyak simpul yang  tersedia  untuk  melakukan  pencarian  maka  waktu  pencarian  akan  semakin  cepat,  dimana  persentase peningkatan kecepatan pencarian dengan penambahan  simpul sebanyak 100% dapat meningkat hingga 21,99% dibandingkan dengan tidak ada penambahan simpul [3].
Dari perkembangan teknologi informasi tersebut, penulis akan menerapkan algoritma Simplified Memory Bounded A* (SMA*) yang dapat melakukan pencarian terhadap kata pada aplikasi permainan.

## 2. METODOLOGI PENELITIAN

## 2.1 Simplified Memory Bounded A*
Algoritma SMA* ( Simplified Memory Bounded A* ) adalah sebuah algoritma yang dikembangkan dari algoritma A* (A star). Algortima A* sendiri adalah variasi dari algoritma Branch and Bound . Jadi secara tidak langsung, algoritma SMA* itu sendiri merupakan salah satu variasi pengembangan dari algoritma Branch and Bound . Menggunakan  algoritma  SMA*  berarti  memperhitungkan  jumlah  sebenarnya  ditambah  dengan  jumlah perkiraan. Jumlah sebenarnya dinotasikan dengan g(n). sedangkan jumlah perkiraan dinotasikan dengan h(n). Jadi memperhitungkan g(n) + h(n). Dalam algoritma Simplified Memory Bounded A * yang digunakan untuk mencari nilai yang efisien. Ini dibutuhkan sebuah Queue yang digunakan untuk memanipulasi antrian simpul yang terurut berdasrkan  f-cost-nya. F-cost  itu sendiri adalah g(n)+h(n)[3]. Penggunaan Algoritma SMA*  memiliki beberapa keuntungan diantaranya sebagai berikut:
a. Algoritma ini bekerja dengan heuristik, seperti Algoritma A*
b. Proses dapat diselesaikan jika memory yang tersedia banyak untuk menyimpan solusi
c. Optimal  jika  memori  diperbolehkan  cukup  tinggi  untuk  menyimpan  solusi  optimal,  selain  itu  akan mengembalikan solusi terbaik yang sesuai dalam memori diperbolehkan
d. Untuk menghindari kondisi berulang selama memori masih terhubunng
e. Akan menggunakan memori yang tersedia
f. Memperbesar memori untuk algoritma yang akan mempercepat perhitungan.
g. Bila tersedia cukup memori untuk menampung seluruh pohon pencarian, maka perhitungannya memiliki kecepatan yang optimal

## 2.2 Permainan
Permainan  atau  game  adalah  suatu  cara  belajar  dengan  menganalisa  dengan  sekelompok  pemain  maupun individual dengan menggunakan strategi-strategi yang rasional. Teori permainan dapat diklasifikasikan kedalam beberapa bagian, yaitu:
1. Number of Players
Permainan papan hanya terbatas untuk dua pemain. Biasanya yang menggunakan sistem pencarian langkah.
2. Plies, Move and Turns
Pemain  pasti  akan  mendapatkan  giliran,  sebagai  suatu  lapisan  didalam  suatu  permainan  dan  melakukan gilirannya dalam satu putaran.
3. The Goal of  the Game
Tujuan utama adalah untuk mendapatkan kemenangan. Pemenang hanya diraih oleh satu pemain dengan kata lain kemenangan pemain adalah kekalahan bagi pemain lainnya. (Zero-sum).
4. Information
Artinya pemain  mengetahui  semua aturan-aturan dan  hal  lain dalam permainan. Contonya adalah catur, Go dan Reverse. Setiap langkah yang diambil akan berpengaruh pada permainan sesudahnya oleh karena itu harus benar-benar mengetahui aturan permainan dari awal.

## 2.3 Hangman
Hangman pada dasarnya merupakan sebuah permainan kertas dan pensil sederhana untuk dua atau lebih pemain. Seorang memikirkan huruf untuk ditebak dan yang lain mencoba menebak kata apa yang dipikirkan si pembuat soal.  Namun  dewasa  ini,  permainan Hangman berkembang  menjadi  permainan  yang  menggunakan  desktop sebagai  media  utama  permainan.  Dengan  komputer  sebagai  pembuat  soal  yang  di-generate  secara  random  dan pemain yang berusaha menebak kata yang di-generate[5].
Volume 3, Nomor 2, Desember 2021 e-ISSN 2685-998X DOI 10.30865/json.v3i2.3586

## 3. HASIL DAN PEMBAHASAN

## 3.1 Analisa Masalah
Permainan Hangman yang akan dirancang ini adalah sebuah aplikasi permainan Hangman yang berbasis android . Dalam peneltian ini untuk input soal di permainan Hangman adalah nama-nama buah yang terdiri dari :
1. Durian
2. Duku
3. Delima
4. Anggur
5. Apel
6. Salak
7. Pisang
8. Nanas
9. Semangka
10. Kurma
Nama-nama buah selanjutnya akan di lampirkan di halaman lampiran dalam skripsi ini. Proses yang akan terjadi dalam permaina hangman adalah apabila kolom subjek sudah di tentukan dan selanjutnya menebak kata dengan menyusun satu per satu huruf yang cocok diantara huruf A sampai dengan Z sehingga terbentuk kata jika benar,  jika  salah  makan  satu  per  satu  akan  muncul  tiang  gantung,  tali  gantung  dan  komponen-komponen berikutnya sehingga tersusun menjadi orang yang di gantung dan permaina dinyatakan gagal.
Batas nyawa yang di tetapkan dalam permainan Hangman ini adalah delapan tahap yaitu :
1. Garis tiang samping
2. Garis tali gantung
3. Kepala
4. Badan
5. Tangan kanan
6. Tangan kiri
7. Kaki kanan
8. Kaki kiri
Sedangkan  level  dalam  permainan hangman ini  tidak  dibuat  karena  dalam  masa  pengujian.  Permaina dinyatakan  berakhir  apabila  penebak  tidak  dapat  melengkapi  garis  dengan  huruf  yang  tepat  dan  penebak dinyatakan berhasil apabila sudah tersusun menjadi kata yang terdapat dalam kolom jawaban sehingga kata yang dimaksud diketahui.
Perancangan akan dilakukan dengan menggunakan software IDE Eclipse sebagai editor kode program dan yang  diperlukan  untuk  memulai  mengembangkan  aplikasi  pada platform android menggunakan  bahasa pemrograman Android  Development  Tools (ADT)  sebagai plugin yang  didesain  untuk IDE Eclipse yang memberikan kemudahan dalam mengembangkan aplikasi android . Setelah dibuat source code pada eclipse galileo dan aplikasi bisa dijalankan pada emulator di laptop, maka untuk menjadikannya menjadi suatu aplikasi yang bisa dijalankan pada android Apk yang ada pada tempat penyimpanan aplikasi yang dirancang di instal pada mobile android . Aplikasi Permainan Hangman ini hanya bisa dijalankan pada smarthphone dan tablet PC dengan sistem operasi android, seperti Samsung Galaxy , Oppo dan lain-lain dari jenis smarthphone . Permainan Hangman pada umumnya dalam bentuk tulisan kertas di dalam buku dan papan tulis di depan para  siswa.  Dengan  adanya  aplikasi  Permainan Hangman berbasis android maka  para  siswa  dan  anak-anak ataupun orang-orang awam  yang  ingin  menghibur diri dan  menambah wawasan pengetahuan tambahan dengan sangat mudah, cepat dan sederhana.
3.1.1. Penerapan Algortima Simplified Memory Bounded A*
Penerapan algoritma yang akan dirancang akan menggunakan algoritma simplified memory bounded a* sebagai solusi dalam penyelesaian masalah penebakan kata, seperti halnya dalam permainan Hangman. Untuk  melaukan penebakan kata pada permainan Hangman dapat menggunakan algoritma path  finding . Terdapat beberapa kata algortma path finding yang bisa digunakan. Algoritma yang digunakan adalah algoritma Simplified Memory Bounded A*. Algoritma SMA* merupakan pengembangan dari algoritma A* . Algortima ini mengatasi  kelemahan  yang dimiliki oleh algoritma A*  yaitu penggunaan  memori  yang besar. Okeh karena  itu, yang akan diteliti untuk mengukur efektifitas penggunaan  algoritma SMA* adalah sebagai berikut:
Jumlah simpul yang dibagikan dan dihapus selama proses penebakan. Dalam penggunaan algoritma Simplified Memory Bounded A* pada pencarian pattern. Penelitian ini akan melakukan pencarian pattern pada teks “DURIAN”. Teks : DURIAN Berikut ini adalah langkah-langkah penyelesaian menggunakan algortima Simplified Memory Bounded A* :
Volume 3, Nomor 2, Desember 2021 e-ISSN 2685-998X DOI 10.30865/json.v3i2.3586
Gambar 1. Pencarian Kata Tahap 1
Gambar 2. Langkah 1 Pada Pencarian Kata
Pattern  tidak  ditemukan  pada  teks  sehingga  akan  melakukan  pencarian  kepada  teks  lain.  Setelah  tidak mendapatkan kecocokan pattern, Maka akan melakukan ke tahap 2, Yang dapat kita lihat pada gambar 3.
Gambar 3. Langkah 2 Pada Pencarian Kata
Pattern  tidak  ditemukan  pada  teks  sehingga  akan  melakukan  pencarian  kepada  teks  lain.  Setelah  tidak mendapatkan kecocokan pattern, proses tersebut dilakukan hingga sampai tahap terakhir
Gambar 4. Langkah 4 Pada Pencarian Kata
Pattern Telah ditemukan pada teks sehingga otomatis tersimpan pada kolom jawaban, dan akan melakukan pencarian untuk karakter lain yang terdapat dalam kolom permainan hangman
Volume 3, Nomor 2, Desember 2021 e-ISSN 2685-998X DOI 10.30865/json.v3i2.3586
Gambar 6. Langkah Terakhir Pada Pencarian Kata
Pattern Telah ditemukan pada huruf sehingga otomatis tersimpan pada kolom jawaban, permainan selesai karena kolom jawaban sudah terisi dengan jumlah kolom yang sudah ditentukan dari nama buah yang tersimpan di dalamm database. Maka akan melakukan ke tahap selanjutnya yaitu melakukan pencarain nama buah yang lain.

## Gambar 7. Hasil Jawaban

## 3.2. Implelemtasi
Tahapan penerapan algoritma simplified memory bounded a* adalah tahapan dimana pembuatan perangkat lunak yang  berbasis Android ,  tahapan  ini  merupakan  lanjutan  dari  tahapan  perancangan  berdasarkan  hasil  analisis pengujian dalam bahasa yang di mengerti oleh komputer serta penerapan perangkat lunak pada program android dan keadaan  yang sebenarnya.  Aplikasi  ini dijalankan dengan  menggunakan perangkat keras ( Hardware )  yang direkomendasikan sebagai berikut : 1. AMD Dual Core
2. Memory 2 GB
3. Keyboard dan mouse
4. 320 GB HDD
5. Monitor
Adapun sistem operasi yang direkomendasikan untuk menjalankan aplikasi tersebut adalah :
1. Sistem operasi windows 7, 32 bit 2. Eclipse 403
3. Menggunakan dengan program mobile Android
4. Smartphone
Aplikasi permainan hangman Indonesia yang telah dirancang merupakan aplikasi berbasis mobile Android , dimana  aplikasi  tersebut  dapat  dijalankan  pada hand phone berbasis android. Aplikasi  Permainan hangman Indonesia  ini  di  jalankan  dengan  bahasa  pemrograman java dan  untuk  menjalankan  programnya  penulis menggunakan Eclipse . Form Menu Utama pada Permaina Hangman Indonesia yang dirancang dan akan tampil pada saat membuka icon aplikasi  Permaina Hangman Indonesia.  Form  menu  utama  ini  terdiri  dari  tiga  pilihan  yaitu  Yuk  Bermain ( Play ),  Pengaturan  dan  Keluar.  Dari form menu  utama  dapat  diuraikan  dalam  urutan  langkah-langkah  sebagai berikut :
Volume 3, Nomor 2, Desember 2021 e-ISSN 2685-998X DOI 10.30865/json.v3i2.3586
Tahapan  ini  merupakan  tampilan  yang  menjelaskan  proses  Aktifitas  Permaina Hangman Indonesia. Menekan botton Yuk Bermain untuk menampilkan halaman ini Mulai dari papan keyboard untuk pengetikan huruf yang cocok dengan jenis dan cirri-ciri subyek, kolom atau form jawaban, kolom subyek yang menyimpan nama- nama  buah  di  dalam database ,  Tampilan  nyawa  yang  akan  berbentuk  karakter  bayangan  manusia  sehingga bayangan  tersusun  menjadi  bayangan  yang  sempurna  seperti  bayangan  manusia  dengan  tali  pengikan  di  leher kepala  keatas  tiang  maka  akan  selesai  permainan  dan  dianggap  gagal  dalam  bermain hangman Indonesia  dan sebaliknya jika tersusun huruf dalam kolom jawaban menjadi nama buah  maka permainan berhasil di selesaikan dan akan melanjutkan dengan nama buah lainnya.
Gambar 9. Aktivitas Permainan Hangman Indonesia
Proses menekan keyboard karakter Benar “ i ” di dalam database sudah tersimpan dalam setiap nama buah seperti  durian,  delima,  pisang  dan  sebagainya.  Karena  yang  ditanyakan  di  dalam database Subyek  adalah  kata “DURIAN”, maka “i” yang akan muncul kolom hasil dan di kolom ke-4.
Gambar 10. Hasil Ketikan Benar I Permainan Hangman Indonesia
Proses  menekan keyboard karakter  Salah  “  x,  y,  z,  m,  c,  p,  q  dan  f  ”  atau  yang  tidak  ada  dalam  kata DURIAN, makan akan muncul Nyawa hangman berurutan mulai dari berbentuk tiang gantung, tali, kepala, badan, tangan kanan, tangan kiri, kaki kanan dan kaki kiri.
Volume 3, Nomor 2, Desember 2021 e-ISSN 2685-998X DOI 10.30865/json.v3i2.3586
Seperti  sebelumnya  yang  di  jelaskan  dalam  tampilan  aktivitas  permainan hangman Indonesia form ini adalah tampilan hasil dari jawaban penebakan huruf di papan keyboard yang akan muncul di dalam kolom jawaban dan tersusun menjadi kata buah.
Gambar 12. Hasil Permainan Hangman Indones ia

## 4. KESIMPULAN
Berdasarkan hasil penelitian, analisa, perancangan aplikasi dan penerapan Algoritma Simplified Memory Bounded A*  Pada  Permainan  Hangman  dapat  ditarik  beberapa  kesimpulan  Algoritma  Simplified  Memory  Bounded  A* dapat  diterapkan  dalam  aplikasi  Permainan  Hangman  Indonesia  sehingga  dapat  menghibur  pengguna  untuk mencari kata yang sudah ditanyakan dalam kolom subyek. Aplikasi Permainan Hangman telah selesai dirancang dengan  menggunakan  Software  Eclipse  ,  Software  Development  Kit  (SDK)  sebagai  platform  dan  telah  dapat dijalankan  pada  perangkat  mobile  android.  Aplikasi  permainan  Hangman  hanya  berbentuk  garis-garis  yang  di kumpulkan menjadi sebuah karakter dan kolom-kolom.

## REFERENCES
[1] F. F. C. Gutman Togatorop, Aan Erlansari, “IMPLEMENTASI ALGORITMA ZHU-TAKAOKA PADA APLIKASI KAMUS ISTILAH MUSIK BERBASIS ANDROID,” J. Rekursif, 2017.
[2] U. K. I. Andi Juansyah, “Pembangunan Aplikasi Child Tracker Berbasis Asisted-Global Positioning System (A-GPS) Dengan Platfoam Android,” J. Ilm. Tek. Inform., p. 2, 2015.
[3] R. M. Mokhamad Syaroni, “PENCOCOKAN STRING BERDASARKAN KEMIRIPAN UCAPAN (PHONETIC STRING MATCHING) DALAM BAHASA INGGRIS,” Semin. Nas. Apl. Teknol. Inf., 2005.
[4] H. Y. NELLI HINDRIANI, NARWEN, “IMPLEMENTASI ANTRIAN DENGAN MENGGUNAKAN ARRAY,” J. Mat. UNAND.
[5] G. P. H. Indra Griha Tofik Isa, “Perancangan Aplikasi Koperasi Simpan Pinjam Berabasis Web (Studi Kasus Koperasi Mitra Setia),” Ilm. Ilmu Ekon., 2017.