IMPLEMENTASI ALGORITMA MINIMAX PADA PERMAINAN CATUR
Abstrak
Manusia ada makhluk ciptaan yang paling sempurna, memiliki otak yang cerdas untuk berfikir, masing-masing individu mempunyai kelebihan yang berbeda-beda, tapi manusia juga memiliki beberapa kelemahan seperi mudah lupa, mudah lelah, kurang teliti, malas dan lain sebagainya. Dari beberapa kelamahan itu munculah sebuah alat bantu kerja yang cepat dan akurat yaitu komputer. Semakin berkembangnya jaman, komputer bukan hanya dapat bertindak saja tapi juga dapat berfikir, dari situlah muncul istilah Artificial Intellegence (AI) atau Kecerdasan Buatan.
Salah satu contoh dari Kecerdasan Buatan adalah minimax, minimax adalah salah satu algoritma yang menggunakan teknik pencarian secara Depth-First Search (DFS). Salah satu media yang cocok dalam penggunaan teknik minimax ini adalah sebuah permainan sederhana yaitu Catur, beberapa alasan mengapa catur dapat menjadi media penerapan kecerdasan buatan antara lain catur sangat mungkin untuk dibandingkan dengan kemampuan manusia, mudah dimainkan dan dapat menentukan ukuran kesuksesan atau kegagalan.
1. Pendahuluan
1.1. Latar Belakang Masalah
Manusia adalah makhluk ciptaan Allah SWT yang paling sempurna, dianugrahi sebuah otak yang dapat berfikir melebihi makhluk ciptaan lainnya dan tidak bisa dibandingkan dengan komputer manapun.
Kemudian muncul sebuah ide untuk menciptakan komputer cerdas yang dapat berfikir. Dulu komputer diciptakan sebagai alat bantu kerja agar lebih cepat, akurat dan rapi. Komputer hanya bertindak jika ada perintah atau instruksi dari manusia. Seiring berkembangnya jaman, komputer tidak hanya bertindak melainkan dapat berfikir. Sehingga muncul istilah Artificial Intellgence (AI) atau Kecerdasan Buatan.
Ada beberapa alasan mengapa permainan catur ini digunakan sebagai media penerapan kecerdasan buatan, antara lain:
a. Sangat mungkin untuk dibandingkan dengan kemampuan manusia.
b. Dapat menentukan ukuran kesuksesan atau kegagalan.
c. Mudah dimainkan setiap orang.
d. Setiap pengguna mampu bermain dengan baik bersama komputer. Pemain hanya membutuhkan ketelitian dan logika berfikir yang baik.
Minimax menggunakan teknik pencarian Depth-First Search dengan kedalaman terbatas dan mempunyai fungsi evaluasi statis, dengan mengansumsikan bahwa lawan akan membuat langkah terbaik yang akan dilakukannya. Algoritma minimax cocok digunakan pada permainan catur, tic-tac-toe, go, othello dan sebagainya.
1. 2. Identifikasi Masalah
Beberapa masalah yang akan dibahas dalam penelitian ini adalah:
a. Bagaimana menerapkan algoritma minimax pada permainan catur.
b. Bagaimana cara membandingkan langkah komputer random dengan langkah komputer yang menggunakan algoritma minimax.
1. 3. Maksud dan Tujuan
Maksud dari penelitian ini adalah menerapkan dan mengimplementasikan algoritma minimax pada permainan catur, adapun tujuan penelitian ini yaitu:
a. Membandingkan langkah komputer random dan langkah komputer menggunakan algoritma minimax pada permainan catur.
b. Mengetahui hasil perbandingan langkah antara komputer random dengan komputer menggunakan algoritma minimax.
c. Untuk mengetahui solusi pencarian dan pelacakan yang dilakukan algoritma minimax pada permainan catur.
1. 4. Batasan Masalah
Penerapan kecerdasan buatan ini akan sangat kompleks dan rumit bila semua aspek dan kriteria harus terpenuhi. Agar penelitian ini mencapai sasaran yang jelas maka batasan masalah pada penelitian ini yaitu:
a. Permainan ini dilakukan oleh satu orang pemain melawan komputer.
b. Permainan ini tidak terkoneksi dengan jaringan.
c. Papan permainan berbentuk kotak persegi 8x8.
d. Algoritma yang digunakan dalam pencarian dan pelacakan adalah algoritma minimax.
2. Tinjauan Pustaka
2.1. Catur
Catur merupakan permainan two player strategy board game yang masih popular hingga saat ini. Catur adalah permainan mental dengan menggunakan pikiran yang dimainkan oleh dua orang. Sebelum bermain, pecatur terlebih dahulu memilih bidak atau biji catur yang akan ia mainkan. Terdapat dua warna untuk membedakan bidak catur, yaitu hitam dan putih. Pemegang bidak putih akan jalan terlebih dahulu diikuti oleh pemegang bidak hitam secara bergantian hingga permainan selesai[1].
2.2. Kecerdasan Buatan
Kecerdasan Buatan (AI) adalah kecerdasan mesin dan cabang ilmu computer yang bertujuan untuk menciptakan komputer cerdas yang dapat berfikir layaknya manusia. Buku AI mendefinisikan bidang ini sebagai “the study and design of intelligent agent” dimana agent cerdas adalah system yang merasakan lingkungannya dan mengambil tindakan untuk memaksimalkan peluang yang sukses. John McCarthy menciptakan istilah ini pada tahun 1956 yang di definisikan sebagai “ilmu dan teknik membuat mesin cerdas”[3]. AI sangat banyak digunakan pada aplikasi computer terutama pada aplikasi permainan. Pada two player board games strategy, AI digunakan untuk mengatur strategi dan memutuskan langkah yang dapat mengimbangi permainan player sehingga player yang memainkan aplikasi ini seakan – akan bermain dengan player lain.
2.3. Algoritma minimax
Algoritma minimax merupakan salah satu algoritma yang digunakan pada permainan dua player yang memiliki AI atau pada zero sum games seperti catur[2]. Pada algoritma minimax, pengecekan akan dilakukan untuk mencari semua kemungkinan yang ada. Pengecekan tersebut akan menghasilkan pohon permainan yang berisi semua kemungkinan tadi. Akan dibutuhkan resource dengan skala besar untuk menangani pencarian pohon solusi tersebut karena kombinasi kemungkinan pada permainan catur sangat banyak.
Pada algoritma minimax, komputer akan menganalisa semua pohon permainan sehingga komputer akan mengambil langkah yang dapat membuat lawan mendapatkan keuntungan minimum dan keuntungan maksimum pada komputer itu sendiri[2],[6]. Dalam penentuan keputusan tersebut dibutuhkan suatu nilai atau bobot yang dapat merepresentasikan kerugian atau keuntungan yang akan diperoleh pada setiap langkah, sehingga langkah yang memiliki nilai terbesar (keuntungan terbesar dan kerugian terkecil) akan dipilih.
3. Daftar Pustaka
[1] Catur - Wikipedia bahasa Indonesia, ensiklopedia bebas
[2] Minimax - Wikipedia, the free encyclopedia
[3] John McCarthy. (2007). "What Is Artificial Intellegence?"
[4] Ayuningtyas, Nadhira. (2008). “Algoritma minimax dalam permainan checkers”. Dalam Strategi Algoritmik 2008. Bandung, Indonesia: Institut Teknologi Bandung.
[5] Kusumadewi, Sri. (2003). Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha Ilmu.
[6] Silvia Garcia Diez, Jerrome Laforge, and Marco Saerens, "An Optimally Randomized Minimax Algorithm," February 2010.
Komentar
Posting Komentar