Page 1Page 2Page 3Page 4Page 5Page 6Page 7Page 8

Page 1 of 8
next >

Jurnal Ilmiah Komputer dan Informatika (KOMPUTA)

99

Vol. 5, No. 2, Oktober 2016, ISSN : 2089-9033

SOLUSI LANGKAH PADA GAME CONGKLAK MENGGUNAKAN

METODE NEGASCOUT

Rangga Darmawan

1

, Galih Hermawan

2

Teknik Informatika – Universitas Komputer Indonesia

Jl. Dipatiukur 112-116 Bandung

E-mail : dar.rangga@gmail.com

1

, galih.hermawan@email.unikom.ac.id

2

ABSTRAK

Permainan congklak merupakan permainan

tradisional Indonesia. Permainan ini sebenarnya

bukanlah permainan asli Indonesia melainkan

permainan dari luar Indonesia yang sudah diadaptasi

berdasarkan budaya Indonesia. Pada permainan

congklak diperlukan perhitungan matematis dalam

memilih biji yang akan dimainkan dengan tepat dan

dalam waktu yang cepat agar mendapatkan hasil yang

optimal

atau

dalam

kondisi

yang

paling

menguntungkan.

Pada penelitian ini aplikasi game congklak yang

menerapkan Algoritma Negascout, dibangun dengan

tujuan

untuk

mengetahui

kinerja

Algoritma

Negascout pada proses pencarian solusi game

congklak. Kinerja algoritma akan dilihat dari segi

tingkat kemenangan, waktu pemrosesan, dan jumlah

langkah pencarian.

Berdasarkan hasil pengujian aplikasi secara

keseluruhan, maka dapat disimpulkan bahwa akurasi

dari perhitungan Negascout secara manual dan oleh

aplikasi adalah 100%, tingkat kemenangan algoritma

minimax lebih unggul dari algorima Negascout

dengan presentase kemenangan 71% untuk minimax

dan 57% untuk Negascout, tingkat kecepatan

algoritma Negascout lebih baik dari algoritma

minimax dengan perbandingan jumlah keseluruhan

langkah

pencariannya

2:5

dan

perbandingan

keseluruhan waktu proses pencariannya 1:10691,42.

Kata kunci :

1. PENDAHULUAN

Permainan congklak merupakan permainan

tradisional Indonesia. Permainan ini sebenarnya

bukanlah permainan asli Indonesia melainkan

permainan dari luar Indonesia yang sudah diadaptasi

berdasarkan budaya Indonesia. Congklak dimainkan

oleh dua orang, dalam permainan ini biasanya

menggunakan papan dengan 16 lubang yang terdiri

dari 7 lubang kecil setiap sisinya dan 2 buah lubang

besar. Setiap lubang kecil yang ada akan diisi dengan

biji congklak masing-masing 7 buah.

Pada permainan congklak diperlukan perhitungan

matematis dalam memilih biji yang akan dimainkan

dengan tepat dan dalam waktu yang cepat agar

mendapatkan hasil yang optimal atau dalam kondisi

yang paling menguntungkan. Penelitian yang

dilakukan oleh Galih Hermawan [1], teknik

penentuan langkah menggunakan algoritma Greedy

disertai dengan mekanisme pemilihan langkah secara

dinamis. Yaitu pilihan untuk mengambil keuntungan

sebesar-besarnya atau lebih menyelamatkan lubang

yang berisi biji dengan jumlah relatif besar.

Sedangkan pada penelitian Citra Anindya [2], metode

penentuan langkah yang digunakan adalah algoritma

Minimax. Dalam penelitian ini telah ditemukan solusi

yang cukup optimal; dalam artian dari percobaan 21

kali bermain, agen komputer dapat memenangkan

permainan sebanyak 15 kali dengan asumsi lawan

human

terampil dalam bermain congklak.

Adapun penelitian yang dilakukan oleh Sarah

Nurhasanah [3], terfokus hanya pada mencari solusi

yang optimal tanpa mempertimbangkan waktu

komputasi yang dibutuhkan untuk mencari solusi.

Dalam penelitian tersebut mencoba menerapkan

Alpha-Beta Pruning optimasi dari algoritma Minimax

untuk meningkatkan kecepatan komputasinya. Dari

hasil

penelitiannya

menunjukkan

bahwa

kompleksitas algoritma Minimax dari penelitian Citra

adalah T(n)=n, waktu pemrosesan yang dibutuhkan

pada kondisi papan 7 lubang dengan isi lubang kecil

masing-masing 3 biji adalah 27,8301 detik dan

langkah pencarian yang dibutuhkan adalah 430

langkah. Dalam buku J. Mandziuk [4] ada algoritma

lain yang dikemukakan oleh Alexander Reinefeld

yaitu Algoritma Negascout yang merupakan optimasi

dari algoritma Minimax. Dalam bukunya disebutkan

Algoritma ini bisa melakukan pencarian solusi yang

lebih cepat dan mendapatkan solusi yang lebih

optimal.

Berdasarkan penjelasan tersebut, maka dalam

penelitian ini akan mengimplementasikan algoritma

Negascout pada game congklak. Diharapkan dengan

adanya penelitian ini proses pencarian solusi bisa

dilakukan dengan lebih cepat dalam artian

kompleksitas algoritma, waktu pemrosesan dan

langkah pencarian yang dibutuhkannya memiliki

nilai yang lebih kecil dari algoritma Minimax, dan

solusi yang didapatkan lebih optimal dalam artian