APLIKASI PERMAINAN CONGKLAK DENGAN MENGGUNAKAN ALGORITMA MINIMAX DAN ALPHA.BETA PRUNING Mitha Miranda pratama, Frans panduwinata, Irene Lazarusli Teknik Informatika Universitas Pelita Harapan Jl. M.H. Thamrin Boulevard 1 100 Tangerang I 5 g I I Telp.: +6221-5460901 ext2205, e-mail:
[email protected],
[email protected]
Abstract Nowdays, digital game is played by many people around the world. On the contrary, most people no longer play the traditional game. In Indonesia, congklak is one of the popular traditional game. To promote a traditional game in this era we have to convert it into digital version, therefore the congklak game application is developed.
This application is developed with attractive design and in which
en
sekarang masih Aimmati adalah congklak. Agar permainan tradisional yang dimainkan secara non
digital dapat menarik minat kebanyakan orang kembali, permainan ini perlu dibuatkan versi digitalnya. Atas dasar pemikiran tersebut maka
aplikasi permainan congklak ini dibuat. Permainan congklak yang dimainkan seorang diri
memerlukan lawan bermain berupa komputer yang dilengkapi dengan suatu kecerdasan buatan (AI) di dalamnya. AI tersebut dapat dibuat dengan beberapa tingkat kesulitan untuk menguji keahlian seorang pemain.
player can play against the computer which applied artificial intelligence (AI) that can make the game more challenging because the opponent is also able to 'think'. The algorithm used in AI is the Minimax and Alpha-Beta Pruning. The application was developed using java programming language. Testing the bowl value is done to find the best bowl value to make the best AI and then testing the AI victory percentage. The results of testing the bowl value are 50,30,10, and the results of testing the AI victory were 460% (easy level), 600% (moderate level), and
System Development
72%
Perancangan perangkat lunak yang dilakukan juga
the
(dfficult level)
Kqtwords: minimax, alpha-beta pruning, game application.
1. PENDAIIULUAN Permainan dengan menggunakan komputer
(digital) telah medadi suatu gaya hidup bagi masyarakat sekarang ini. Tingginya ketertarikan masyarakat terhadap permainan komputer tersebut membuat para pembuat permainan berlomba - lomba untuk menciptakan berbagai jenis permainan yang dapat menarik minat pemainnya. Hal ini mernbuat permainan tradisional (non digital) semakin ditinggalkan meskipun masih ada yang memainkannya. Salah satu jenis permainan tradisional yang hingga
2.
METODE
Penelitian ini diawali dengan studi pustaka untuk mendapatkan berbagai informasi yang berhubungan dengan permainan congklak dan algoritma Minimax dan Alpha-Beta pruning, dilanjutkan dengan memasukkan unsur kecerdasan buatan ke dalam aplikasi permainan congklak, dan melakukan pengujian aplikasi
dengan metode pengujian Pengembagan perangkat lunak
ini
blackbox. menggunakan
Ltfe Cycle (SDLC).
meliputi penentuan fimgsi heuristik
pada
algoritma Minimax, penentuan pemotongan pada pohon pencarian berdasarkan algoritma AlphaBeta Pruning, dan penerapan kedua algoritma tersebut ke dalam aplikasi yang dibuat. Aplikasi permainan congklak dengan AI dibuat dengan tiga tingkat kesulitan, yaitu mudah, sedang, dan sulit. Pengujian nilai mangkuk dilakukan untuk mencari nilai manghtk terbaik agar membuat AI
yang terbaik kemudian mengujikan persentase kemenangan AI.
SDLC adalah suatu proses
untuk mengembangkan suatu sistem melalui tahapan-
tahapan tertentu. Tahap-tahap SDLC adalah perencanaan, analisis, perancangan, dan implementasi. SDLC sangat membantu di dalam pengembangan sebuah sistem. Hal ini
Aplikasi Permainan congklak ... (M. M. pratama, F. panduwinata, L Lazarusli)
211
dikarenakan SDLC memberikan pemahaman tentang bagaimana merancang sebuah sistem, membangun sistem tersebut hingga tahap penyampaian sistem tersebut kepada pengguna t1l.
dengan kemungkinan berhasil lebih besar dan mengabaikan kemungkinan berhasil lebih kecil.
Waktu pencarian menjadi lebih sedikit karena tidak melakukan pencarian terhadap semua kemungkinan yang ada. Karena tidak melakukan pencarian terhadap semua kemungkinan, mungkin
Permainan congklak adalah suatu permainan tradisional yang cukup populer di Indonesia. Permainan ini melibatkan dua orang pemain yang dimainkan pada papan dengan lubang berjumlah 16 buah yang terdiri atas 14lubang kecil saling berhadapan dan 2 lubang besar di kedua ujung
ini,
papan. Biasanya dalam permainan
sejenis
cangkang kerang digunakan sebagai bui congklak. Papan congklak dapat dilihat pada gambar 1 [a]. Dari beberapa aturan permainan dan cara bermain congklak yang ada, penelitian
ini
menggunakan cara bermain
dan
aturan
congklak Jawa atau dakon [a].
Kecerdasan buatan merupakan sebuah cabang studi ilmu komputer yang bertujuan membuat
komputer dapat menyelesaikan persoalanpersoalan yang sulit, sehingga terlihat komputer berlaku cerdas l2l. Seiring dengan semakin pesatnya perkembangan teknologi, perkembangan
dan pengunaan kecerdasan buatan pun ikut meningkat. Hal ini terbukti dari munculnya beberapa teknologi yang dibuat dengan harapan dapat menggantikan tugas-tugas manusia pada masa depan. Salah satu contohnya adalah jenis permainan komputef yang sebelurnnya dimainkan dengan teman secara langsung, tetapi sekarang dapat dimainkan seorang diri di komputer.
Fungsi Heuristik. Salah satu teknik pemecahan adalah dapat
menghasilkan solusi untuk suatu masalah dengan mengevaluasi beberapa alternatif solusi yang ada.
Terdapat beberapa algoritma pada teknik pencarian tersebut, namun penelitian ini menggunakan algoritma pencarian heuristik. Heuristik mengutamakan keseirnbangan antara kecepatan dan ketepatan penemuan solusi. Metode pencarian secara heuristik merupakan teknik pencarian yang mengutamakan pencarian
212
temyata jalur tersebut pada akhirnya memiliki nilai terbesar dibanding jalur lainnya. Oleh karena itu, semakin dalam tingkat pencarian yang dilakukan sebanding dengan semakin baik pengetahuan akan jalur. tersebut optimal atau
tidak. Metode heuristik tidak akan
selalu
mendapatkan solusi paling optimal, tetapi pasti akan mendapatkan solusi yang dianggap paling baik dalam waktu yang relatif cepat. Di dalam penentuan keputusan langkah minimum dan maksimum dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Oleh karena itu, algoritma Minimax menggabungkan fungsi heuristik dengan pengetahuan yang berupa strategi memenangkan permainan. Strategi ini juga akan diubah ke dalam bentuk fungsi heuristik, sehingga akan dihasilkan sebuah nilai untuk digunakan
Gambar 1. Papan congklak
masalah pada kecerdasan buatan pencarian. Teknik pencarian ini
saja jalur yang semula dianggap bukan merupakan kemungkinan solusi dibuang; tetapi
pada proses perhitungan nilai heuristik simpul. Keluaran proses perhitungan nilai heuristik adalah nilai untuk setiap simpul. Berdasarkan nilai-nilai heuristik ini, komputer dapat menentukan simpul yang akan dipilih, yaitu simpul dengan nilai heuristik yang dapat menuntun permainan ke hasil akhir yang menguntungkan komputer.
Algoritma Minimax merupakan basis semua permainan yarlg berbasis kecerdasan buatan seperti congklak [b]. Proses utama algoritma
Minimax adalah pencarian nilai
terbaik pada yang diberikan telah berdasarkan nilai-nilai pada setiap langkah. Nilai terbaik bisa terdapat posisi max, ataupttr posisi min. Posisi min btkan berarti akan terjebak dalam kondisi minimum, melainkan penandaan max dan min bertrtyuan untuk memberi identitas langkah pemain.
Di
dalam permainan congklak, min adalah pemain dan max adalah lawan atau dalam hal ini kecerdasan buatan komputer. Dengan asumsi bahwa pemain akan selalu mengambil langkah yang paling merugikan lawan, maka min akan
selalu mengambil nilai heuristik terkecil. Demikian juga dengan max yang mengambil langkah yang paling menguntungkan untuk
komputer, maka mox akan mengambil nilai heuristik terbesar.
Jurnal llmiah llmu Komputer, Vol. 9 No. 2 Maret 2013: 211-215
Alpha-Beta Pruning. Pada pohon pencarian
dengan Minimax dapat diketahui
bahwa
pencarian dilakukan terhadap seluruh node yang ada. Hal ini akan membuat waktu proses lama jika pohon pencarian memiliki ukuran yang besar. Oleh karena itu, diperlukan Alpha-Beta Pruning yang digunakan untuk mencari tahu jalur mana yang sudah tidak lagi berguna atau sudah pasti tidak akan lebih baik daripada jalur sebelumnya untuk kemudian tidak diperhitungkan jalumya, sehingga pencarian terhadap anak simpul tersebut
pun tidak perlu dilakukan. Hal ini
tentu
mempercepat proses pencarian [c].
akan menghitung kemungkinan langkah yang dapat dipilih oleh komputer dan lawan dengan total sebanyak dua langkah kedepan, masingmasing satu langkah. Berdasarkan kemungkinan yang ada, aplikasi akan memilih langkah yang menghasilkan keuntungan maksimal dan kerugian minimal untuk komputer.
Rancangan Algoritma Pada Permainan Congklak. Rancangan algoritma Minimax dan Alpha-Beta Pruning pada aplikasi permainan congklak yang dibuat ditunjukkan pada dua garnbar diagram alir b'erikut ini (gambar 3 dan gambar 4). Gambar 3 adalah diagram alir proses max. Sirnbol keempat di kolom tengah yang bertulisan "yal min(hole_cpy, alpha, beta, depth, maxDepth, val)" memanggil proses min yang dijelaskan pada gambar 4. Gambar 4 adalah diagram alir proses min. Simbol kelima di kolom tengah yang bertulisan "val : max(hole_cpy, alpha, beta, depth+1, maxDepth, val)" memanggil proses max pada gambar 3 untuk kasus kedalaman lebih dari satu.
* y'f ilp}u-Seta
Fq$rhry
3
? I
2. Pohon pencarian dengan algoritma Minimax dan Alpha-Beta _!runing
Gambar
Simpul A yang sementara bernilai 5 (berasal dari nilai simpul B dan E) menjadi nilai o. Setelah didapatkan nilai sementara simpul C yaitu 8
(berasal
dari nilai simpul F) dan
sebelum
melanjutkan pencarian pada simpul G, dilakukan pencarian terlebih dahulu. Karena nilai a:5 dan B:8, syarat o 2 B tidak terpenuhi; pencarian pun diteruskan. Nilai sementara simpul G yarrg berasal dari nilai simpul J, yaitu 9, menjadi nilai a karena simpul G bqrada pada garis MAX. Dengan nilai a:9 dan B:8, syarat o > B terpenuhi, maka
K beserta anak-anaknya dipotong dan dibuang dari memori. Walaupun menghasilkan solusi yang sama, waktu pencarian solusi dengan menggunakan Minimax dan Alpha-Beta Pruning lebih cepat dibandingkan dengan penggunaan algoritma Minimax saja. node
3.
DISKUSI
Rancangan Tingkat Permainan. Aplikasi yang menggunakan algoritma Minimax dan AlphaBeta Pruning ini dirancang dengan 3 tingkat kesulitan permainan, yaitu tingkat mudah, sedang, dan sulit yang dibedakan berdasarkan tingkat kedalaman pohon pencarian yaitu masing-masing 2, 4, dan 6. Contoh pada tingkat mudah, aplikasi
Gambar 3. Diagram
alr
proses
Aplikasi Perrhainan congklak ... (M. M. Pratama, F. panduwinata, L Lazarusli)
Max
213
Pengujian nilai mangkuk. Pengujian nilai mangkuk bertujuan untuk mencari bobot yang dirasa paling pas jika pemain atau komputer menjatuhkan biji terakhirnya ke mangkuk. Pada awal pembuatan aplikasi congklak ini, dari total 98 biji congklak yang ada (setengahnya yang sejumlah 49), maka nilai 50 sebagai nilai maagkuk awal merupakan nilai yang cukup tinggi agar komputer (AD dapat memilih langkah tersebut atau menghindari langkah yang menyebabkan pemain mendapatkan langkah tersebut. Nilai 50 tersebut hanya berlaku di kedalaman pertama karena semakin dalam perhitungan kemungkinan langkah, nilai congklak
Gambar 4. Diagram alir proses Min
4. HASIL Antar muka aplikasi. Gambar 5 dan 6 adalah gambar contoh tampilan antar muka aplikasi permainan congklak yang dibuat.
dapat semakin berkurang karena berpindahnya beberapa brji congklak ke dalam mangkuk pemain atau komputer. Oleh karena itu, nilai yang digunakan pada kedalaman berikutnya adalah 30 dan 10 untuk kedalaman ketiga. Jika nilai mangkuk 50,3 0, 1 0 dijumlahkan, maka didapatkan nilai 90 yang mendekati jumlah total brji congklak yang digunakan. Jadi, jika ada suatu langkah yang terdiri atas lubang penyebab biji terakhimya berhenti di mangkuk komputer pada masing-masing kedalaman (pada tingkat sulit), maka langkah tersebut memiliki nilai val yang bertambah 90. Nilai mangkuk awal yang telah ditentukan dengan alasan tersebut (50,30,10) kemudian pada pengujian ini dijadikan sebagai pembanding. Nilai mangkuk lain yang dipilih adalah 0,0,0; 50,50,50; 98,98,98; serta 20,10,5. Dasar pengujian ini adalah dengan melakukan 5 (lima) langkah awal yang sama dan tiga tingkat kesulitan untuk masing-masing langkah tersebut. Rangkuman hasil pengujian ditunjukkan pada tabel berikut ini: Tabel 1. Hasil pengujian nilai mangkuk
Gambar
5. Tampilan menu
"*HL
s0,30,r0 0,0'0 s0's0,s0 e8,e8'e8
Tingkat Mudah (%)
2o,to,s
100%
Tingkat Sedang (%)
20%
Tingkat sulit (%)
40%
Berdasarkan Tabel 1 di atas, dapat dilihat bahwa persentase kemenangan untuk masing-masing
tingkat tidak sebaik persentase nilai mangkuk 50,30,10. Oleh karena itu, ketiga nilai inilah yang Gambar 6. Tampilan saat permainan
214
digunakan pada aplikasi permainan congklak ini.
Jurnal"llmiah llmu Komputer, Vol. 9 No. 2 Maret 2013:211-215
Pengujian kemenangan AI. pengujian ini dilakukan untuk menguji kemampuan AI dengan 3 tingkat kesulitan yang ada, yaitu mudah, sedang, dan sulit. Pada tingkat mudah, pengujian dilakukan kepada 10 orang yang masing-masing bermain sebanyak 5 kali. Berdasarkan hasil pengujian pada tingkat mudah, dipilih pemain yang mendapatkan kemenangan lebih dari 50% (menang 3 kali atau lebih dari 5 pengujian yang telah dilakukan). Dari 10 pemain pada pengujian pertama, hanya 6 pemain yang melewati syarat tersebut. Kepada ke 6 pemain tersebut, pengujian
pada tingkat sedang
ini
dilakukan
dengan
melakukan pengujian sebanyak 8 kali dan satu orang sebanyak 10 kali agar didapatkan total 50 kali pengujian. Berdasarkan hasil pengujian pada tingkat sedang, dipilih pemain yang mendapatkan kemenangan lebih dari 40o/o (menang 4 kali atau lebih dari 8 pengujian yang telah dilakukan). Dari 6 pemain pada pengujian kedua, hanya 3 pemain
yang melewati syarat tersebut. Kepada ke
3
pemain tersebut, pengujian pada tingkat sulit ini dilakukan dengan melakukan penguj ian sebanyak 15 kali untuk dua orang dan satu orang lainnya melakukannya sebanyak 20 kali agar didapatkan
total 50 kali pengujian. Berikut adalah tabel rangkuman hasil pengujian kemenangan AI terhadap pemain (manusia).
Tabel2. Hasil pengujian kemenangan AI terhadap pemain (manusia) _. . Tingkat Mudah Sedans
oleh karena itu dapat disarankan untuk mencoba menggunakan algoritma lain seperti algoritma Greedy untuk kecerdasan buatan,
kemudian dapat dibandingkan dengan Minimax dan Alpha-Beta Pruning.
5.
DAFTAR PUSTAKA
U] A.Dennis,
B. H Wixom, D. Tegarden, System Analysis and Design with (IML version 2.0: An Object Oriented Approach, 2"d edition, John Wiley & Sons, Inc, United States of America,2005.
[2]
S. Russel and' P. Norvig, Artificiat
Intelligence: A Modern Approach, 2'd edition, Pearson Education, [rc, New Jersey, United States of America, 2003. Websites:
[a] Expat Web Site Association, "Congklak: Traditional Game of Indonesia", (2013), http
:
I / exp at.or. i d/info/congklak.
html
[b] Math 2033 at the University of
Arkansas,
"Von Neumann's Minimax Theorem", (2011), http I / math2O 3 3 .uark. edu/wiki/index. php/Von _Neumanno/o 2 7 s_M inimax_Theorem [c] Tsan-sheng Hsu, "Alpha-Beta Pruning: :
Algorithm and Analysis",
(2012);,
http://www.iis. sinica.edu.td-tshsl/t cgp\l lides/slideT.pdf
I/s
Sulii
Persentase
Aplikasi permainan congklak telah selesai dibuat dengan tampilan yang menarik dan menawarkan pilihan untuk dapat bermain dengan komputer yang menggunakan kecerdasan buatan dengan menerapkan algoritma Minimax dan Alpha-Beta Pruning. Dari hasil pengujian yang
telah dilakukan dapat disimpulkan bahwa nilai manglcuk yangi sesuai untuk membangun kecerdasan buatan pada aplikasi permainan congklak ini adalah 50, 30, 10. Kemudian persentase kemenangan AI (komputer) terhadap pemain (manusia) adalah 46% pada tingkat mudah, 600/o pada tingkat sedang, dm 72o/o pada tingkat sulit. Berdasarkan penurunan persentase pada pengujian kemenangan pemain atas AI, pemilihan tingkat kesulitan dan keahlian pemain berpengaruh terhadap menang atau kalahnya seorang pemain.
Penerapan algoritma Minimax dan AlphaBeta Pruning belum dapat dikatakan sebagai kombinasi algoritma terbaik untuk diterapkan pada aplikasi permainan yang membutuhkan AplikasiPerftrainan congklak .. (M.M.pratama, F. panduwinata, l. Lazarusli)
215
