## PENERAPAN ALGORITMA MINIMAX DALAM PERMAINAN DAKON PADA SD NEGERI 04 PONDOK RANJI
Trisna Ayu Suryatin Dwi Putri 1) , Joko Christian Chandra 2)
Teknik Informatika,Fakultas Teknologi Informasi, Universitas Budi Luhur Jl. Raya Ciledug, Petukangan Utara, Kebayoran Lama, Jakarta Selatan 12260 E-mail : 1411501834@student.budiluhur.ac.id 1) , joko.christian@budiluhur.ac.id 2)

## Abstrak
Dakon  atau  yang  biasa  disebut  congklak  adalah  sebuah  permainan  tradisional  yang  termasuk  salah  satu permainan strategi. Dakon dimainkan dengan menggunakan sebuah papan dakon dan biji dakon yang berjumlah 14 x 7 buah.Pemenang dapat ditentukan dari jumlah biji yang terkumpul pada lumbung pemain. Permainan ini dapat melatih kemampuan berfikir bagi pemain, akan tetapi saat ini sebagian besar orang kurang tertarik untuk memainkan permainan tradisional seperti dakon, karena sudah banyak yang beralih pada permainan digital dan elektronik  yang  dirasa  lebih  praktis,  sehingga  hal-hal  tradisional  mulai  tersisihkan.  Seiring  dengan  pesatnya kemajuan  teknologi  terutama  pada  smartphone  ,  maka  dikembangkan  permainan  tradisional  dakon  berbasis android agar lebih praktis untuk dimainkan kapanpun dan dimanapun. Dengan bantuan artificial intelligence (AI) , komputer akan bisa bermain dan berpikir untuk mengalahkan lawannya  sebaik manusia. Algoritma Minimax dapat diterapkan pada permainan dakon ini karena mampu menganalisaberbagai kemungkinan posisi permainan untuk  menghasilkan  langkah  terbaik.  Penulis  menambahkan  algoritma  Alpha  Beta  Pruning  untuk  mengurangi ruang pencarian sekaligus sebagai optimasi dalam permainan dakon. Permainan dakon ini dibangun pada sistem operasi  Android.  Hasil  yang  diperoleh  dari  aplikasi  yang  dibangun  yaitu,  dari  30  responden  diperoleh  96,7% siswa SD Negeri 04 Pondok Ranji menyatakan bahwa permainan dakon menarik dan mudah dimainkan.
Kata Kunci : Permainan, Dakon, Minimax, Alpha Beta Pruning, Android

## 1. PENDAHULUAN
Permainan  dakon  merupakan  permainan tradisional  Indonesia,  namun  permainan  ini sebenarnya  berasal  dari  negara  Mesir,  Suriah  dan Lebanon  yang  kemudian  di  adaptasi  berdasarkan budaya Indonesia. Dakon dimainkan oleh dua orang, dalam permainan ini biasanya menggunakan papan dengan 16 lubang yang terdiri dari 7 lubang kecil di setiap  sisinya  dan  2  buah  lubang  besar.  Setiap lubang  kecil  yang  akan  diisi  dengan  biji  dakon masing-masing 7 buah. Kecerdasan buatan (Artificial  Intelligence)  adalah  bagian  dari  bidang ilmu  yang  dapat  menirukan  tingkah  laku  dan kecerdasan manusia. Hal inilah yang menyebabkan lahirnya  berbagai  teknologi  yang  biasa  disebut cerdas,  seperti  pada  perkembangan  game  modern saat  ini.  Dengan  adanya  game  berbasis  AI  ini, membuat  para  pemain  terlibat  untuk  mengatur strategi demi mengalahkan AI tersebut.
Seiring  berkembangnya  pengetahuan  dan teknologi,  kecerdasan  buatan  dalam  permainan dapat dikembangkan menggunakan berbagai macam algoritma. Salah satu algoritma yang sering digunakan dalam pengembangan kecerdasan buatan untuk permainan adalah algoritma minimax. Algoritma  minimax  bekerja  secara  rekursif  atau beraturan  dengan  mencari  langkah  yang  akan membuat lawan mengalami keuntungan minimum
dan  komputer  mendapat  keuntungan  maksimum, pada langkah pertama komputer akan menganalisis seluruh  pohon  permainan.  analisa  akan  dilakukan menurut rule yang ada sehingga akan menghasilkan pohon  permainan  yang  berisi  semua  kemungkinan dari  permainan  tersebut.Penulis  menambahkan algoritma  Alpha  Beta  Pruning  untuk  mengurangi ruang  pencarian  sekaligus  sebagai  optimasi  dalam permainanyang berfungsi untuk mengurangi jumlah simpul yang dieksplorasi dalam algoritma minimax sehingga  waktu  eksekusi  akan  lebih  efisien  karena memiliki  banyak  pruning  dan  proses  yang  dirasa tidak  dibutuhkan  tidak  akan  ditelusuri.    Penulis mengangkat  judul  “Penerapan  Algoritma Minimax dalam Permainan Dakon pada SD Negeri 04 Pondok Ranji”  sebagai  salah  satu  syarat  kelulusan  jenjang strata  satu  Teknik  Informatika  –  Universitas  Budi Luhur.
2. METODE PENELITIAN
2.1 Studi Literatur
Kegiatan  studi  literatur  dilakukan  dengan mengumpulkan, mempelajari, dan membaca berbagai referensi baik dalam bentuk buku, e-book, laporan penelitian, jurnal ilmiah, artikel internet dan lain-lain.  Tujuan  studi  literatur  adalah  untuk memperoleh  kajian  teoritis  yang  digunakan  dalam pengembangan  sistem  yang  berupa  pengumpulan teori-teori  yang  berkaitan  dengan  algoritma  DFS
(Depth  First  Search) Minimax  dan  Alpha-Beta Pruning.

## 2.2 Identifikasi Masalah
Permainan dakon merupakan permainan papan tradisional yang sudah mulai dilupakan. Oleh sebab itu,  penulis  ingin  memperkenalkan  kembali permainan  dakon  berbasis  Android  kepada  siswa- siswi  SD  Negeri  04Pondok  Ranji.Selain  itu permainan dakon terdapat unsur kegiatan yang dapat melatih kemampuan logika.

## 2.3 Metode Pengembangan
Pengembangan sistem ini merujuk pada model
Waterfall yang  memaparkan  bahwa  terdapat  lima tahap  utama  dalam  metode  pengembangan  ini. Tahapan  pada  model Waterfall secara  ringkas menurut Pressman (1997) adalah sebagai berikut : a. Analisis Pada tahap ini dilakukan analisis bagamaina  mengimplementasikanpermainan dakon  berbasis  android  dengan  algoritma minimax.
b. Design Merancang  alur  program  dan  desain tampilan permainan dakon yang akan dikembangkan.
c. Koding Pada tahap ini akan dilakukan pengkodean dan menerapkan perancangan aplikasi tersebut ke  dalam  bahasa  pemrograman  java  dengan menggunakan  Android  Studio  2.3  sebagai tools untuk membuat program.
d. Pengujian Pada tahap ini dilakukan pengujian aplikasi
permainan  dakon  apakah  berjalan  sesuai dengan  tujuan  penelitian  atau  tidak  dan memperbaiki kesalahan-kesalahan yang terjadi.
e. Pemeliharaan Tahapan ini dilakukan ketika sistem sudah dioperasikan yang meliputi proses monitoring, evaluasi dan perubahan bila diperlukan.

## 2.4 Minimax
Algoritma Minimax adalah suatu metode yang telah  banyak  digunakan  dalam  permainan  strategi. Metode  ini  digunakan  untuk  memilih  langkah terbaik yang diberikan, dimana kedua pemain saling berusaha  untuk  memenangkan  permainan.Setiap pemain  dapat  mengetahui  langkah-langkah  yang mungkin diberikan pada situasitertentu saat pemain tidak  dapat  langkahnya  sendiri.  Sehingga  untuk setiap  langkah dan semua  langkah selanjutnyaakan dapat  diketahui[1].  Minimax  merupakan  algoritma yangdigunakan  untuk  menentukan  pilihan  agar memperkecil kemungkinan kehilangan nilaimaksimal.
Algortima  Minimax  dapat  menghasilkan pilihan  langkah  yang  baik  denganmengasumsikan
bahwasanya pemain lawan atau manusia akan selalu memilih langkah terbaik untuk dirinya dan langkah terburuk  bagi  computer  (AI).  Prinsip  dasar  pada algoritma Minimax ini adalah jalur yang akan dipilih oleh  komputer  merupakan  jalur  maksimum  ( max node )  yang  akan  menghasilkan  nilai  maksimum  di jalur  tersebut,  dan  saat  pemain  yang  bermain  akan meminimalkan  ( min  node )  nilai  komputer.  Jadi, komputer bertujuan untuk memaksimalkan kemungkinan  nilai  paling  rendah  yang  akan diperoleh computer (AI).
Jika pemain  menentukan suatu langkah, maka pemain  akan  menentukan  langkah  yang  dapat menghasilkan  suatu  posisi  yang  baik.  Kita  dapat mengasumsikan  bahwa  pemain  akan  memilih langkah  yang  dapat  menuntunnya  pada  posisi terbaik. Dengan kata lain, ketika pemain  mendapat giliran  bermain  maka  pemain  akan  mencoba memaksimalkan  nilainya.  Ketika  lawan  mendapat giliran bermain, pemain akan mengganggap bahwa lawan akan memilih langkah yang dapat memberikan pemain posisi terburuk. Lawan sedang berusaha  meminimalkan  nilai  dari  pemain.  Untuk mengetahui  proses  dan  cara  kerja  yang  lebih  jelas, dapat dilihat pada gambar berikut[2]:
Gambar 1: Cara Kerja Algoritma Minimax
Langkah-langkah  cara  kerja  algoritma  Minimax adalah sebagai berikut:
a. Hampiri node pertama pada leaf dengan nilai 5, naik  ke  parent  pada  level  2(MAX)  masukkan nilai 5, hampiri 2. Karena 2<5 maka nilai parent tidak perludiganti.
b. Setelah kedua leaf pertama dihampiri, naik lebih tinggi lagi ke level 1 (MIN)masukkan nilai 5.
c. Hampiri  node  ketiga  pada  leaf  dengan  nilai  1, naik  ke  parent  pada  level  2(MAX)  masukkan nilai 1. Kemudian hampiri leaf keempat dengan nilai 3.Karena 3>1 maka ganti parent pada level 2 (MAX) dengan nilai 3.
d. Karena  3<5  maka  ganti  parent  pada  level  1 (MIN) dengan nilai 3.
e. Setelah  keempat  leaf  pertama  dihampiri,  naik lebih  tinggi  lagi  ke  level  0(MAX)  masukkan nilai 3.
f. Begitu  seterusnya  hingga  kita  dapatkan  hasil akhir dari tree di atas adalah 6.
2.5 Alpha-Beta Pruning Pada dasarnya, algoritma Minimax sangat ahli untuk  menyelesaikan  segala  masalah  dalam
pencarian  langkah  terbaik  untuk  permainan komputer dengan jumlah kemungkinanpenyelesaian yang  kecil.  Tetapi,  jika  algoritma  Minimax digunakan pada permainan dengan jumlah kemungkinan  penyelesaian  yang  lebih  besar, algoritma  Minimax  ini  akan  memerlukan  waktu yang  lama  untuk  membangun  satu  pohon penyelesaian.
Oleh sebab itu, beberapa metode yangmelanjutkan  algoritma  Minimax  ini  telah dikembangkan  untuk  membatasi  meningkatnya jumlah simpul dalam pembangunan pohon penyelesaian. Berbagai jenis metode telah ditemukan  untuk  meningkatkan  kinerja  algoritma Minimax, salah satunya adalah Alpha Beta Pruning . Dengan menggunakan metode ini maka diharapkan sistem  dapat  bekerja  lebih  baik  lagi.  Untuk  proses dan  cara  kerja  algoritma Alpha  Beta  Pruning yang lebih jelas, dapat dilihat pada gambar berikut[3]:
Gambar 2: Cara Kerja Algoritma Alpha Beta Pruning
Langkah-langkah  cara  kerja  algoritma Alpha  Beta Pruning adalah sebagai berikut:
a. Hampiri node pertama pada leaf dengan nilai 4, naik  ke  parent  pada  level  2  (MAX)  masukkan nilai 4, hampiri 1. Karena 1<4 maka nilai parent tidak diganti.
b. Setelah kedua leaf pertama dihampiri, naik lebih tinggi lagi ke level 1 (MIN) masukkan nilai 4.
c. Hampiri  node  ketiga  pada  leaf  dengan  nilai  8, naik  ke  parent  pada  level  2  (MAX)  masukkan nilai  8.  Jika  kita  menghampiri  leaf  berikutnya, kita  mencari  nilai  yang  lebih  tinggi  dari  8, sementara pada level 1 (MIN) kita mencari yang lebih  kecil  dari  4.  Maka  leaf  keempat  (5)  kita potong (tidak kita hampiri).
d. Setelah  keempat  leaf  pertama  dihampiri,  naik lebih  tinggi  lagi  ke  level  0  (MAX)  masukkan nilai 4.
e. Begitu  seterusnya  hingga  kita  dapatkan  hasil akhir dari tree di atas adalah 4.
3. HASIL DAN PEMBAHASAN
3.1 Spesifikasi Perangkat
a. Perangkat Keras Perangkat keras komputer yang digunakan dalam  mengembangkan  sistem  ini  terdiri  dari satu  buah  laptop  dan smartphone dengan spesifikasi sebagai berikut : 1) Prosesor : Intel® Core™i3-2310M CPU@ 2.10GHz 2.10 2) Memori : 6GB DDR3 3) Semua  jenis  Mobile  Android  dengan minimum RAM 512MB
4) SDK minimum : Android 4.0.3 (IceCreamSandwich) 5) Target SDK : Android 7.1.1 (Nougat)
b. Perangkat Lunak (Software) Perangkat  lunak  yang  digunakan  untuk mengembangkan  sistem  ini  adalah  sebagai berikut :
1) Sistem Operasi  :  Windows  7  Ultimate (64-bit) 2) Editor : Android Studio 2.3 3.2 Alur Proses Arsitektur Sistem Aplikasi Proses keseluruhan aplikasi ini dapat diuraikan sebagai berikut:
a. User memulai  permainan  dengan  memilih salah  satu  metode  permainan  yaitu single player (pemain  vs komputer)atau multiplayer (pemain vs pemain).
b. Metode single player yang dipilih user dibagi menjadi  tiga  tingkat  kesulitan  yakni easy, medium dan hard.
c. Setelah  memilih  salah  satu  tingkat  kesulitan, kemudian user akan  memulai  giliran  main terlebih  dahulu  dengan  memilih  salah  satu lubang dari papan permainan hingga bijiterakhir berhenti pada lubang kosong milik lawan atau melakukan langkah tembak.
d. Setelah user tidak  bisa  melangkah  lagi,  maka giliran  komputer  untuk  melangkah  dengan melakukan analisis terlebih dahulu melalui AI dari  algoritma  minimax  yang  dioptimasi dengan alpha beta pruning untuk menemukan langkah terbaik.
e. Begitu seterusnya hingga permainan berakhir, pemain  dengan  jumlah  biji  di  lubang  besar terbanyak adalah pemenangnya.
Untuk  memahami  konsep  sistem  yang  akan dikembangkan  nantinya  dapat  mengacu  pada arsitektur sistem yang dijabarkan pada Gambar 3 di bawah ini. Arsitektur sistem menggambarkan secara garis besar proses dari keseluruhan sistem.
Gambar 3: Arsitektur Sistem Permainan Dakon

## 3.3 Rancangan Layar Aplikasi Dakon
Gambar 4  merupakan rancangan  layar Dakon dimana  setiap  permainan  dimulai  atau  dijalankan. Terdapat image  view berupa  tampilan  board  dari permainan  dakon.  Permainan  dapat  dimulai  dan dijalankan  sesuai  dengan  giliran  pada  saat keterangan di toast muncul. Kemudian pemain jalan dengan cara  memilih  biji pada  lubang-lubang  yang telah disediakan.

## Gambar 4: Papan Permainan Dakon

## 3.4 Uji Coba Program
Tampilan  layar  aplikasi  permainan  dakon  di awal  permainan,  selama  permainan  dan  akhir permainan disajikan seperti gambar 5.
(a)
(b)
Gambar 5: Tampilan layar aplikasi permainan dakon di (a)awal permainan (b)akhir permainan

## 3.5 Hasil Evaluasi Program
Evaluasi  program  yaitu  salah  satu  hal  yang harus  dilakukan  dalam  setiap  pengembangan  suatu aplikasi  yang  bertujuan  untuk  menganalisis  dan mengetahui  hasil  yang  telah  dicapai  oleh  sistem aplikasi  yang  telah  dikembangkan  tersebut.  Tabel 4.1 berikut merupakan hasil dari 10 kali percobaan pada  tingkat  kesulitan easy yang  telah  dilakukan. Pemain berasal dari anak didik tingkat SD kelas VI SD Negeri 04 Pondok Ranji.
Tabel 1:  Hasil Percobaan Tingkat Kesulitan Easy
Uji ke- Nama Pemain Skor Pemenang Pemain Komputer 1 Silvia 22 34 Komputer 2 Habibah 24 32 Komputer 3 Nadia 23 33 Komputer 4 Gea 30 26 Pemain 5 Janwar 28 28 Seri 6 Desta 20 36 Komputer 7 Silvia 29 27 Pemain 8 Hannah 36 20 Pemain 9 Syauqi 35 21 Pemain 10 Aziil 28 28 Seri
Tabel 2:  Hasil Percobaan Tingkat Kesulitan Medium
Uji ke- Nama Pemain Skor Pemenang Pemain Komputer 1 Jendinar 19 51 Komputer 2 Vita 13 57 Komputer 3 Ilham 10 60 Komputer 4 Mutiara 12 58 Komputer 5 Ibnu 35 35 Seri 6 Ahmad 16 54 Komputer 7 Fawaz 21 49 Komputer 8 Zidan 44 26 Pemain 9 Maulan 29 41 Komputer 10 Dimas 52 18 Pemain Tabel 3:  Hasil Percobaan Tingkat Kesulitan Hard Nama Skor Pemenang
Uji ke- Pemain Pemain Komputer 1 Warohman 16 82 Komputer 2 Fidelia 14 84 Komputer 3 Nadia 21 77 Komputer 4 Rifky 42 56 Komputer 5 Nia 23 75 Komputer 6 Wynona 17 81 Komputer 7 Amelda 38 60 Komputer 8 Qeisya 48 50 Komputer 9 Raihan 68 30 Pemain 10 Diaz 49 49 Seri
Dalam  tahap  evaluasi  tersebut,  ditemukan beberapa kelebihan dan kelemahan dari aplikasipermainan  dakon  yang  dikembangkan. Adapun  kelebihan  dan  kekurangan  permainan tersebut adalah sebagi berikut :
a. Kelebihan Program Kelebihan  program  aplikasi  permainan mancala  berdasarkan  atas  uji  coba  program yang  di  lakukan  terhadap  siswa-siswi  SD Negeri 04 Pondok Ranji :
1) Memiliki  tiga  pilihan  tingkat  kesulitan, yaitu easy,  medium dan hard sehingga pemain  dapat  memilih  tingkat  kesulitan sesuai dengan kemampuannya.
2) Memiliki  2  pilihan  mode  permainan  yaitu single  player dan multiplayer, dimana pemain  dapat  bermain  sendiri  dengan lawan  komputer  pada  mode single  player atau  bermain  bersama  dengan  teman dengan mode multiplayer.
3) Terdapat  fasilitas background musik  agar permainan terlihat lebih menarik.
4) Terdapat fasilitas informasi riwayat langkah (History) dari kedua pemain.
5) Memiliki fasilitas rules permainan sebagai petunjuk  aturan  main  agar  pemain  lebih mudah dalam memainkanya.
6) Terdapat  fasilitas Hint untuk  membantu pemain dalam mencari langkah terbaik.
b. Kekurangan Program Kelebihan  program  aplikasi  permainan mancala  berdasarkan  atas  uji  coba  program yang  di  lakukan  terhadap  siswa-siswi  SD Negeri 04 Pondok Ranji :
1) Belum ada fasilitas menyimpan permainan dan  fasilitas load untuk  memudahkan pemain  dalam  melanjutkan  permainan yang telah dilakukan.
2) Aplikasi permainan belum dapat dimainkan  secara multiplayer  online maupun multiplayer bluetooth.
4. KESIMPULAN

## 4.1 Kesimpulan
Berdasarkan  hasil  analisis  yang  dilakukan terhadap permasalahan dan pengujian aplikasi yang telah  dikembangkan,  maka  dapat  disimpulkan sebagai berikut :
a. Algoritma minimax dengan optimasi alpha beta pruning yang digunakan pada aplikasi permainan dakon, menunjukan hasil yang baik dalam menentukan langkah yang terbaik untuk AI. Dari 10 kali percobaan yang dilakukan pada masing-masing  tingkat  kesulitan,  komputer dapat  memainkan  permainan  sebanyak  4  kali pada tingkat kesulitan easy, 7 kali pada tingkat kesulitan medium , 8 kali pada tingkat kesulitan hard, 2  kali  seri  pada  tingkat  kesulita easy ,  1 kali  seri  pada  tingkat  kesulitan medium dan1 kali pada tingkat kesulitan hard.
b. Aplikasi permainan dakon yang sudah dikembangkan akan  melatih pola pikir pemain dalam  mengatur  strategi  untuk  memenangkan permainan,  dimana  dalam  hal  ini  lawan (AI) menggunakan  algoritma  minimax  dengan optimasi alpha beta pruning untuk menentukan langkah terbaik.
c. Dari hasil survey terhadap 30 siswa SD Negeri 04 Pondok Ranji, 28 dari 30 siswa mengetahui permainan  dakon,  27  dari  30  siswa  pernah memainkanya sedangkan 5 dari 30 siswa belum pernah  memainkanya  dan  2  diantaranya  tidak pernah mengenal permainan dakon sama sekali. Hasil  penilaian  aplikasi  yang  diberikan  oleh siswa-siswa SD Negeri 04 Pondok Ranji  yaitu 29  dari  30  siswa  menyatakan  bahwa  aplikasi permainan yang dikembangkan mudah dimainkan, seru dan menyenangkan, sementara 1  dari  30  siswa  menyatakan  kesulitan  dalam memainkanya.

## 4.2 Saran
Aplikasi  permainan  dakon  masih  banyak memiliki kekurangan dan keterbatasan, oleh karena itu  pemain  yang  akan  menggunakan  aplikasi  ini perlu  memahami  beberapa  kekurangan  tersebut.
Untuk pengembangan selanjutkan, penulis menyarankan beberapa hal seperti berikut :
a. Pengembangan  aplikasi  yang  dapat  dimainkan secara multiplayer  online maupun multiplayer bloetooth.
b. Pengembangan aplikasi menggunakan algoritma pencarian yang lebih cepat.
c. Pengembangan  fasilitas  penyimpanan  dan fasilitas load untuk  melanjutkan  permainan yang telah dilakukan.
d. Pada  aplikasi  permainan  congklak  ini  penulis tidak  memberikan  batasan  waktu  bagi  pemain untuk  berpikir  mengambil  langkah  permainan. Sehingga  untuk  penelitian  selanjutnya  dapat dikembangkan  dengan  memberikan  batas
waktu bagi pemain serta memberikan pesan jika pemain  salah  mengambil  langkah  dalam permainan.  Dan  aplikasi  permainan  congklak yang dibangun dibatasi hanya satu kali putaran permainan  saja.  Sehingga  untuk  penelitian selanjutnya  aplikasi  permainan  congklak  ini dapat  dikembangkan  sampai  beberapa  putaran permainan.
e. Diharapkan pengembangan aplikasi selanjutnya dapat di integrasi ke google play.

## 5. DAFTAR PUSTAKA
[1] B. Sumali and I. Michael Siregar,
“Implementation of Minimax with Alpha-Beta
Pruning as Computer Player in Congklak,” J.
Tek. Inform. dan Sist. Inf. , vol. 2, pp. 2443– 2229, 2016.
[2] Ėnn Kharalʹdovich Tyugu, Algorithm and Architectures of Artificial Intelligence .
Estonia:Tallinn University of Technology, 2007.
[3] B. Coppin, Artificial Intelligence Illuminated .
2004.