BAB 1 PENDAHULUAN 1.1 Latar Belakang Masalah Artificial Intelligence atau kecerdasan buatan merupakan sub bidang ilmu komputer yang mengkonsentrasikan diri pada otomatisasi kecerdasan tingkah laku1. Salah satu bentuk demonstrasi komputer tentang kecerdasan buatan tersebut adalah dengan menerapkannya kedalam suatu permainan yang membutuhkan pemikiran dan strategi khusus. Biasanya jenis permainan tersebut adalah permainan berjenis Board Games atau permainan papan, dimana permainan ini merepresentasikan bentuk yang sangat abstrak dan murni dari kompetisi dua pemain atau lebih yang sangat jelas membutuhkan kecerdasan. Sampai saat ini telah banyak metode kecerdasan buatan yang diterapkan dalam permainan berjenis board games, salah satunya adalah algoritma Minimax yang ditemukan oleh John Von Neumann, seorang pakar artificial intelligence pada tahun 1945. Algoritma ini kemudian menjadi metode konvensional untuk permainan dengan jenis dua orang pemain atau Two Player Game. Namun seiring dengan perkembangan artificial intelligence terutama pada bidang permainan, telah memunculkan banyak metode-metode baru yang patut untuk dipertimbangkan keefektifannya. Beberapa diantaranya adalah penyempurnaan dari algoritma minimax, yaitu algoritma negamax dan teknik alpha beta pruning. Namun beberapa diantaranya adalah algoritma baru seperti salah satunya adalah algoritma Proof Number Search. Algoritma Proof Number Search ditemukan pada tahun 1994 oleh Victor Allis, seorang pakar artificial intelligence dari Belanda. Setelah diimplementasikan pada beberapa jenis permainan, algoritma ini dianggap cukup sukses dalam menangani masalahmasalah yang ada dalam jenis permainan two player board games.
1
George F. Luger, William A. Stubblefield, Artificial Intelligence and the Design of Expert Systems, The Benjamin/Cummings, 1989, Hal 1
1
Oleh karena itu dengan adanya metode baru tersebut maka penulis ingin membandingkannya dengan metode terdahulu yaitu algoritma minimax, kedalam suatu permainan yang membutuhkan pemikiran dan strategi khusus. Salah satu permainan yang pantas untuk dijadikan demonstrasi dari implementasi kedua metode kecerdasan buatan tersebut adalah permainan Five Stones. Five stones merupakan permainan yang dimainkan oleh dua orang pemain dengan cara melatakkan batu hitam atau putih secara bergantian pada sebidang papan permainan dengan ukuran 19 x 19 kotak . Adapun tujuan dari permainan ini adalah membentuk deretan lima batu sewarna tanpa terputus baik secara horizontal, vertikal maupun diagonal. Karena pada permainan ini memiliki banyak sekali kemungkinan maka sangat dibutuhkan strategi dalam penyelesaiannya. Oleh karena itu dari beberapa algoritma yang diterapkan diharapkan dapat ditemukan algoritma yang paling tepat untuk kasus permainan five stones. Disamping itu kehadiran lawan main manusia tentunya akan lebih membuat permainan ini lebih menarik, karena pola kecerdasan manusia yang rumit sehingga membuat lebih banyaknya unsur ketidak pastian akan langkah selanjutnya.
1.2
Perumusan Masalah Berdasarkan latar belakang diatas maka penulis merumuskan permasalahan yang
harus dipecahkan dalam kasus permainan five stones ini adalah : ·
Mengimplementasikan algoritma Minimax, Negamax, Negamax Alpha Beta Pruning dan Proof Number Search dalam rangka menemukan langkah terbaik bagi pemain komputer.
·
Menemukan algoritma terbaik dari beberapa algoritma yang diterapkan dengan jalan melakukan pertandingan antara komputer melawan komputer.
·
Menghasilkan permainan yang dapat dimainkan oleh dua orang pemain pada jaringan komputer lokal..
·
Menghasilkan visualisasi pohon pencarian dari algoritma yang digunakan.
2
1.3
Batasan Masalah Adapun batasan masalah pada program aplikasi permainan five stones ini adalah
sebagai berikut : ·
Permainan terdiri atas dua pemain dengan menggunakan batu hitam dan batu putih.
·
Papan permainan berupa matriks 19 x 19 kotak dan tidak dapat diubah-ubah.
·
Kemenangan dicapai dengan cara menciptakan pola lima deret batu sewarna tanpa putus baik secara horizontal, vertikal maupun diagonal.
·
Bila semua tempat di papan sudah penuh dan belum ada pemain yang berhasil mencapai kemenangan, maka permainan akan dianggap seri atau draw.
·
Permainan hanya dapat dimainkan oleh 2 orang pemain manusia dalam suatu jaringan lokal(LAN).
·
Permainan dapat dimainkan dengan cara pemain manusia melawan pemain komputer.
·
Permainan dapat berbentuk pemain komputer melawan pemain komputer, dengan menerapakan algoritma yang berbeda pada masing-masing komputer.
·
Pemain komputer dapat menampilkan visualisasi tree dari algoritma yang diterapkan.
·
1.4
Batas maksimal kedalaman pencarian untuk pemain komputer adalah 10 level.
Tujuan Penulisan Tugas Akhir Adapun tujuan yang akan didapat dari penulisan tugas akhir ini adalah sebagai
berikut : ·
Dapat menerapkan ilmu yang telah diperoleh dari perkuliahan dengan membuat suatu aplikasi permainan yang menerapkan kecerdasan buatan.
·
Menghasilkan sebuah program permainan five stone dengan implementasi algoritma Minimax, Negamax, Negamax Alpha Beta Pruning dan Proof Number Search pada pemain komputer.
3
·
Dapat menemukan algoritma yang paling tepat untuk permainan five stones dari beberapa algoritma yang ditentukan dengan penggunaan sistem komputer melawan komputer.
·
Menghasilkan sebuah program permainan five stone yang dapat dimainkan oleh dua orang pemain manusia melalui jaringan komputer lokal.
·
Untuk memenuhi sebagian syarat-syarat dan kewajiban guna menyelesaikan program S1 di Fakultas Teknik Jurusan Informatika Universitas Kristen Duta Wacana Yogyakarta.
1.5
Metodologi Penelitian Dalam penulisan tugas akhr ini, metode penelitian yang penulis gunakan adalah
gabungan dari studi literatur, pembuatan program dan penulisan laporan. 1. Studi literatur yang dilakukan penulis bertujuan untuk mengumpulkan data-data dan bahan-bahan dengan mempelajari pustaka-pustaka referensi yang berhubungan dengan masalah yang dihadapi guna menunjang perancangan dan pengkodean serta untuk penulisan tugas akhir. 2. Pembuatan program dilakukan dengan mempelajari metode-metode pencarian seperti Depth First Search, Breadth First Search, Best First Search, Minimax, Negamax, Alpha Beta Pruning dan Proof Number Search, kemudian mempelajari dan menerapkan masalah yang ada kedalam bahasa pemrograman, setelah itu mulai dilakukan perancangan dan pembuatan program disertai dengan pengujian dan perbaikan. Setelah pembuatan program selesai maka akan dilakukan penyusunan laporan.
1.6
Sistematika Penulisan Penulisan laporan tugas akhir ini terbagi ke dalam 5 bab utama yang dimulai dari
Bab 1 yang mengemukakan tentang hal-hal yang mendasari penulisan laporan tugas akhir
4
ini, yang meliputi latar belakang masalah, batasan masalah, rumusan masalah, tujuan dan manfaat tugas akhir, spesifikasi sistem, metode penelitian dan sistematika penulisan. Kemudian pada bab 2 diberikan uraian tentang teori-teori pendukung yaitu tentang sejarah kecerdasan buatan, algoritma pencarian, deskripsi permainan, referensi sekilas algoritma Depth First Search, Best First Search, Minimax, Negamax, Alpha Beta Pruning dan Proof Number Search dan penerapannya pada permainan five stones, aturan permainan, dan sekilas penjelasan tentang jaringan komputer. Alasan pemilihan bahasa pemrograman yang digunakan, rancangan masukan dan proses, serta rancangan keluaran program dijelaskan pada bab 3. Setelah itu dilakukan implementasi rancangan sistem dan evaluasi unjuk kerja sistem secara keseluruhan yang akan ditulis pada bab 4. Setelah dilakukan imlementasi dan evaluasi maka pada bab 5 ditulis tentang kesimpulan dari perancangan, implementasi dan evaluasi unjuk kerja sistem, serta saran untuk pengembangan sistem di masa yang akan datang.
5
