IMPLEMENTASI ALGORITMA MINIMAX PADA PERMAINAN CATUR Anton Topadang1), Dedi Haryanto2) 1,2)
Jurusan Teknologi Informasi, Politeknik Negeri Samarinda Email:
[email protected]),
[email protected])
Abstrak Penelitian ini bertujuan untuk mengaplikasikan atau mengimplementasikan algoritma minimax pada permainan catur, khususnya pada langkah yang ada pada permainan catur. Algoritma minimax digunakan untuk menentukan seleksi sehingga dapat meminimalkan kemungkinan hilangnya nilai maksimum. Metodologi yang digunakan pada penelitian ini adalah metode waterfall yang terdiri atas pengumpulan data, analisa, rancangan, implementasi, dan pengujian. Hasil dari penelitian ini bahwa algoritma atau langkah yang digunakan mampu memblokir langkah terpendek dan memenangkan permainan catur. Kata kunci : catur, algoritma minimax
1. PENDAHULUAN Catur merupakan permainan taktik, strategi, kecerdasan dan keterampilan. Catur adalah permainan asah otak yang dimainkan oleh dua pemain diatas sebuah papan catur. Papan catur berbentuk bujur sangkar, terdiri dari 64 kotak yang berwarna hitam dan putih,untuk pembentukan Artificial Intelligence (AI) game ternyata digunakan pula algoritma minimax Kekuatan komputer yang mengandalkan proses komputasi yang sangat cepat. Algoritma minimax ini digunakan untuk menentukan pilihan agar memperkecil kemungkinan kehilangan nilai maksimal (Ayuningtyas, 2008). Di setiap tahap algoritma ini mengasumsikan bahwa pemain A mencoba untuk maximizing player(MAX). Di lain pihak, pada giliran berikutnya pemain B akan mencoba minimizing player(MIN) (Akbar, 2007). Algoritma minimax dalam permainan checkers masalah dimana AI tersebut tidak pernah kalah, penyebab algoritma minimax membuat yang dapat mencari dan menentukan keputusan terbaik dalam permainan, solusi menambahkan nilai alphabetaalgoritma minimax akan memilih pohon pencarian yang lebih singkat sehingga akan membutuhkan waktu singkat untuk melakukan aksinya(Ayuningtyas, 2008). Algoritmam minimax dalam pengambilan keputusan pada permainan Tic-Tac-Toe dimana masalah langkah yang diambil oleh pemain akan menghasilkan hasil yang berbeda-beda, penyebab AI sebagai teknik yang digunakan pada komputer atau video game untuk meproduksi ilusi atau kepintaran karakter yang bukan pemain,solusinya algoritma minimax merupakan algoritma yang sangat bagus dan cocok untuk pengambilan keputusan oleh AI, terutama dalam permainan n player(n>=2)(Akbar, 2007). Penelitian yang dilakukan oleh (Ayuningtias, 2008) algoritma minimax memiliki dasar berupa zero – sum game, dimana jikapemain mendapatkan nilai tertentu maka pemain lain akan kehilangan nilai yang sama dengan pemain tersebut. (Akbar, 2007) AI akan
selalu memilih langkah yang dapat meminimalisir kemungkinan pemain (manusia) untuk menang dengan memblok semua langkah kemenangan pemain. Game (bahasa Indonesia: permainan) adalah permainan yang mengunakan interaksi dengan antarmuka pengguna melalui gambar yang dihasilkan oleh piranti video. Permainan umumnya menyediakan sistem penghargaan, skor yang dihitung berdasarkan tingkat keberhasilan yang dicapai dalam menyelesakan tugas-tugas yang ada di dalam permainan. 2. DASAR TEORI 2.1 Game Game (bahasa Indonesia: permainan) adalah permainan yang mengunakan interaksi dengan antarmuka pengguna melalui gambar yang dihasilkan oleh piranti video. Permainan umumnya menyediakan sistem penghargaan, skor yang dihitung berdasarkan tingkat keberhasilan yang dicapai dalam menyelesakan tugas-tugas yang ada di dalam permainan. 2.2 Catur Catur merupakan permainan taktik, strategi, kecerdasan dan keterampilan. Catur adalah permainan asah otak yang dimainkan oleh dua pemain diatas sebuah papan catur. Papan catur berbentuk bujur sangkar, terdiri dari 64 kotak yang berwarna hitam dan putih. Setiap pemain memulai permainan dengan memgang buah putih dan buah hitam masing-masing enam belas buah : satu King (Raja), satu Queen (Ratu), dua Rook (benteng), dua Knight (kuda), dua Bishop (Gajah), dan delapan piont (Sharawati, 2016). 2.3 Algoritma Algoritma adalah sebuah strategi yang mengandalkan kemampuan berfikir secara logis untuk memecahkan suatu masalah. Dalam algoritma, kita mulai dengan berfikir apa yang kita miliki (kekuatan dan kelemahan), selanjutnya kita atur langkah (aksi) agar tujuan atau sasaran yang kita harapkan dapat terwujud.
Topadang dan Haryanto, IMPLEMENTASI ALGORITMA MINIMAX PADA PERMAINAN CATUR
Langkah-langkah pemecahan masalah bisa dilakukan dengan berbagai cara setiap cara tersebut juga bisa berbeda-beda antara satu orang dengan orang lainya. Karena setiap orang belum tentu memiliki latar belakang kehidupan yang sama dan belum tentu memiliki pemikiran yang sama atas suatu masalah (Wayudi, 2004). 2.4 Netbeans NetBeans merupakan salah satu proyek open source yang disponsori oleh Sun Microsystem. Proyek ini berdiri pada tahun 2000 dan platfrom. NetBeans IDE merupakan produk yang digunakan untuk melakukan pemrograman baik menulis kode, mengompilasi, mencari kesalahan, dan mendistribusikan program. Sedangkan platfrom adalah sebuah modul yang merupakan kerangka awal dalam membangun aplikasi desktop yang besar. 2.5 Algoritma Pencarian Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Keberhasilan suatu sistem salah satunya ditentukan oleh kesuksesan dalam pencarian dan pencocokan. Teknik dasar pencarian memberikan suatu kunci bagi banyak sejarah penyelesaian yang penting dalam bidang AI. Ada beberapa alpikasi yang menggunakan teknik pencarian ini, yaitu: Papan game dan puzzle (tictac-toe,catur,menara hanoi). Konsep pencarian untuk suatu solusi dalam ruang keadaan (state space) merupakan pusat AI. Pencarian adalah suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkianan ruang keadaan(state space). Ruang keadaan merupakan suatu ruang yang berisi semua keadaan yang mungkin. Secara umum proses pencarian dapat dilakukan sebagai berikut: 1. Memeriksa keadaan sekarang/awal. 2. Mengeksekusi aksi yang dibolehkan untuk memindahkan ke keadaan berikut. 3. Memeriksa jika keadaan baru merupakan solusinya. Jika tidak, keadaan baru tersebut menjadi keadaan sekarang dan proses ini diulangi sampai solusi ditemukan atau ruang keadaan habis terpakai. 2.6 Konsep Algoritma Minimax Algoritma minimax ini digunakan untuk menentukan pilihan agar memperkecil kemungkinan kehilangan nilai maksimal. Algoritma ini diterapkan dalam permainan yang melibatkan dua pemain, permainan mengunakan strategi atau logika lainnya. Hal ini permainan-permainan dapat dijelaskan sebagai suatu rangkaian aturan premis Algoritma ini mulai dikembangkan dari teori game zero-sum. Teori ini mendiskripsikan situasi dimana jika terdapat pemain yang mengalami pendapatan, dan pemain lain akan kehilangn dengan nilai yang sama dari pendapatan tersebut, dan sebaliknya (Ayuningtyas, 2008).
Gambar 1. Pohon pencarian algoritma minimax
Jika langkah tersebut dipilih anggaplah ada 2 pemain A dan B. Jika pemain A menang dalam 1 langkah, maka langkah tersebut adalah langkah kemenang. Jika pemain B mengetahui bahwa langkah tersebut akan mengarah ke hasil akhir dimana pemain A akan menang, dan di lain kondisi ada langkah lain yang akan mengarahkan ke hasil akhir seri, maka langkah terbaik untuk pemain B adalah langkah yang akan mengarah hasil akhir permainan ke hasil seri. Di setiap tahap algoritma ini mengasumsikan bahwa pemain A mencoba untuk memaksimalkan peluang menang. Di lain pihak, pada giliran berikutnya pemain B akan mencoba meminimalisir peluang menang untuk pemain A. Oleh karena itu , A disebut juga MAX dan B disebut juga MIN (Akbar, 2007). 3. HASIL DAN PEMBAHASAN 3.1 Membuat papan catur Pada tahap ini, papan catur dibuat dengan ukuran 8 x 8. Papan yang sudah di rancang bisa dilihat pada Gambar 2.
Gambar 2. Papan Catur
3.2 Perancangan letak bidak catur Tahap perancagan ini menampilkan letak-letak bidak pada game catur. Papan sudah dirancang bisa dilihat pada Gambar 3.
29
JUST TI, Volume 9 Nomor 1, Januari 2017: 28 - 32
Gambar 5. Papan dan bidak catur Gambar 3. Perancangan Letak bidak Catur
Pada gambar 5 menunjukan contoh papan catur yang sudah menerapkan proses algoritma minimax, terdapat 2 pemain dalam permainan catur pemain A mewakili user dan pemain B mewakili computer. Pada saat pemain A mengerakan sebuah bidak ke suatu petak, maka computer langsung membalas langkah tersebut. Maka langkah-langkah algoritma yang diambil pemain A dan pemain B adalah: 1. Mulai. 2. Memilih level permainan dan memilih warna bidak catur. 3. Pemain A memilih bidak catur warna putih dan pemain B memilih bidak catur warna hitam. 4. Pemain A memilih langkah D2 ke D3 dan pemain B memilih langkah B8 ke C6. 5. Tampilkan output langkah empat. 6. Pemain A memilih langkah G1 ke H3 dan pemain B memilih langkah G8 ke F6. 7. Tampilkan output langkah enam. 8. Pemain A memilih langkah A2 ke A4 dan pemain B memilih langkah D7 ke D6. 9. Tampilkan output langkah delapan. 10. Pemain A memilih langkah C1 ke D2 dan pemain B memilih langkah C8 ke H3. 11. Tampilkan output langkah sepuluh. 12. Pemain A memilih langkah G2 ke H3 dan pemain B memilih langkah E7 ke E6. 13. Tampilkan output langkah dua belas. 14. Selesai.
3.3 Membuat interface pada permainan catur Komponen-komponen NetBeans yang diperlukan untuk membangun form pada permainan catur ini antara lain Jpanel, Jlabel, JSlider, JButton. Desain JPanel tersebut secara umum sebagai berikut:
Gambar 4. Menu Utama
Pada Gambar 4 JPanel menu utama permainan catur merupakan menu tampilan awal ketika permainan ini dijalankan. Terdapat dua button(tombol) yang berfungsi menampilkan pilihan New Game,dan Quit. 3.4
Algoritma Minimax pada permainan catur Setelah perancangan membuat papan catur, perancangan letak bidak catur, membuat interface pada permainan catur dan implementasi langkah-langkah catur. Maka proses implementasi algoritma minimax untuk mengoptimalkan langkah – langkah catur pada computer dapat dilaksanakan.
Tabel 1. Trace dari langkah-langkah algoritma catur.
No langkah
30
Pemain A
Pemain B
Pion 2 -
Pion 3 -
Kuda 1 -
Kuda 1 -
Gajah
4
Pion 1 D3
5
D3
-
-
-
6
D3
-
-
7
D3
-
-
output
Pion 2 -
Pion 3 -
Kuda 1 C6
Kuda 2 -
Gajah
-
Pion 1 -
-
-
-
-
-
-
-
C6
-
-
H3
-
-
-
-
-
C6
F6
-
Gambar 4.13 -
H3
-
-
-
-
-
C6
F6
-
Gambar 4.14
Topadang dan Haryanto, IMPLEMENTASI ALGORITMA MINIMAX PADA PERMAINAN CATUR
8
D3
A4
-
H3
-
-
D6
-
-
C6
F6
-
-
9
D3
A4
-
H3
-
-
D6
-
-
C6
F6
-
Gambar 4.15
10
D3
A4
-
-
-
D2
D6
-
-
C6
F6
H3
11
D3
A4
-
-
-
D2
D6
-
-
C6
F6
H3
12
D3
A4
H3
-
-
D2
D6
E6
-
C6
F6
-
13
D3
A4
H3
-
-
D2
D6
E6
-
C6
F6
-
3.5 Pengujian Algoritma Minimax Algoritma minimax dipanggil ketika papan catur yang digunakan berhasil dijalankan, minimax berhasil memanggil pohon solusi dari awal permainan hingga akhir. a. Pengujian Game Pada awal tampilan ada beberapa tombol pilihan yaitu new game dan quit. Fungsinya tombol new game akan menampilkan JPanel, pemain memilih level permainan dan warna bidak, papan catur akan ditampilkan.
Gambar 4.16 Gambar 4.17
Pengujian dilakukan pada NetBeans saat aplikasi pertama kali di-run maka akan menampilkan menu utama seperti pada Gambar 7. Tabel 2. Pengujian game
No 1
Pengujian Menu Utama
Hasil Berhasil
2
Papan catur
Berhasil
3
Letak bidak catur
Berhasil
4
Langkah – langkah catur Minimax
Berhasil
5
Berhasil
Keterangan Berhasil menampilkan menu utama permainan catur Papan catur berhasil di tampilkan di layar Berhasil disusun untuk bidak papan catur Penerapan berhasil dilakukan pada bidak catur Penerapan berhasil dilakukan pada langkah dan bidak catur
Gambar 6. Menu Permainan
Papan catur yang disediakan berjumlah satu, papan catur awalnya terisi oleh bidak catur dengan menerapkan algoritma minimax tiap – tiap langkah yang dilakukan computer dari awal permainan hingga akhir permainan. Dalam tahapan ini dilakukan pengujian pada game yang sudah dirancang hasil pengujian bisa dilihat pada tabel 2.
Setelah tombol New Game diklik maka akan menampilkan Jpanel options, pemain memilih level permainan dan warna bidak, papan catur secara langsung bidak catur tersusun sesuai letaknya. Contoh options dan papan catur yang sudah melakukan langkah ditunjukan pada Gambar 7. Pada Gambar 7 JPanel options dan langkah minimax berhasil dijalankan pada langkah pertama sampai dengan akhir permainan.
Gambar 7 Langkah-langkah permainan catur
31
4.
KESIMPULAN Berdasarkan hasil penelitian pengamatan selama perancangan, implementas dan proses pengujian yang telah dilakukan, diperoleh simpulan bahwa Algoritma Minimax bisa diterapkan dalam langkah – langkah pada permainan catur. Aplikasi ini sudah diuji coba pada NetBeans. Minimax akan selalu memilih langkah yang meminimalisir kemungkinan dari langkah yang diambil pemain untuk menang dan memblok semua langkah kemenangan hingga permainan mengarahkan ke hasil akhir berupa kekalahan atau seri Beberapa kekurang masih terdapat dalam permainan ini yang dapat digunakan sebagai masukan untuk pengembangan lebih lanjut diantarnya: 1. Menambahkan algoritma optimasi untuk mempercepat perhitungan simpul pohon pencarian 2. Jumlah menu yang terbatas, memungkinkan untuk menambahkan beberapa tombol. REFERENSI [1] Akbar, K.S.R., (2007). Algoritma Minimac Dalam Pengambilan Keputusan pada Permainan Tic-Tac-Toe. MAKALAH IF2251 STRATEGI ALGORITMATIK. [2] Ayuningtyas, N. (2008). Algoritma Minimax Dalam Permainan Checkers. [3] Desiani, A, & Arhami, M. (2006). Konsep kecerdasan buatan.Yogyakarta:Andi. [4] Fikri, R dkk. (2005). Pemrograman java.Yogyakarta:Andi. [5] Firmansyah, D.H.,(2009). Implementasi Algoritma Minimax Pada Permainan Tic-Tac-Toe skala 9X9,Makalah Seminar Akademik Universitas Komputer Indonesia. [6] Rijaul, F dkk. (2005). Pemrograman java. Yogyakarta:Andi. [7] Sharaswati, A. (2016). Taktik dan strategi menang bermain catur. Yokyakarta: Pustaka Diantara. [8] Wahudi, B. (2004). Pengantar struktur data dan Agoritma. Yogyakarta:Andi.
