PENERAPAN KONSEP ALGORITMA MINIMAX DENGAN MENGGUNAKAN BREADTH-FIRST SEARCH (BFS) PADA PERMAINAN REVERSI
SKRIPSI
SURYA WIJAYA 061401052
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PENERAPAN KONSEP ALGORITMA MINIMAX DENGAN MENGGUNAKAN BREADTH-FIRST SEARCH (BFS) PADA PERMAINAN REVERSI
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer
SURYA WIJAYA 061401052
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PENERAPAN KONSEP ALGORITMA MINIMAX DENGAN MENGGUNAKAN BREADTH-FIRST SEARCH (BFS) PADA PERMAINAN REVERSI : SKRIPSI : SURYA WIJAYA : 061401052 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan,
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Amer Sharif, S.Si, M.Kom NIP
Drs Marihat Situmorang, M.Kom NIP 196312141989031001
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Prof. Dr. Muhammad Zarlis NIP 195707011986011003
Universitas Sumatera Utara
PERNYATAAN
PENERAPAN KONSEP ALGORITMA MINIMAX DENGAN MENGGUNAKAN BREADTH-FIRST SEARCH (BFS) PADA PERMAINAN REVERSI
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 3 September 2010
Surya Wijaya 061401052
Universitas Sumatera Utara
PENGHARGAAN
Puji syukur saya ucapkan kehadirat Tuhan Yang Maha Esa yang telah memberikan rahmat dan hidayahnya, sehingga saya dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi S1 Ilmu Komputer Departemen Ilmu Komputer Universitas Sumatera Utara. Ucapan terima kasih penulis sampaikan kepada Drs Marihat Situmorang, M.Kom selaku pembimbing pertama dan Amer Sharif, S.Si, M.Kom selaku pembimbing kedua yang telah banyak meluangkan waktunya dalam memberikan masukan-masukan kepada penulis. Ucapan terima kasih juga ditujukan kepada Drs. James P. Marbun, M. Kom dan Ade Candra, ST, M. Kom yang telah bersedia menjadi dosen penguji. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Ilmu Komputer, Prof. Dr. Muhammad Zarlis dan Syahriol Sitorus, S.Si, MIT, Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen serta pegawai di Program Studi S1 Ilmu Komputer Departemen Ilmu Komputer FMIPA USU. Skripsi ini terutama saya persembahkan untuk kedua orang tua dan keluarga saya yang telah memberikan dukungan dan motivasi, ayahanda Tjioe Kim Poei dan ibunda Tan Kwie Kie yang selalu sabar dalam mendidik saya. Untuk kedua abang saya, Handy Ciu Dedy dan Indra Wijaya yang selalu memberikan dorongan kepada saya selama menyelesaikan skripsi ini. Terima kasih saya ucapkan kepada teman-teman yang selalu memberikan dukungan, Dennis Suryawijaya, Rury Handayani, Anggarani Novitasari, Stefan Chang, Denny, Rudy Tanaka serta teman-teman RCS. Sekali lagi penulis mengucapkan terima kasih kepada semua pihak yang membantu dalam penyelesaian tugas akhir ini yang tidak dapat disebutkan satu persatu, terima kasih atas ide, saran dan motivasi yang diberikan. Semoga Tuhan Yang Maha Esa akan membalasnya.
Universitas Sumatera Utara
ABSTRAK
Reversi merupakan salah satu permainan papan yang murni berbasis strategi dan dimainkan oleh dua pemain pada papan yang berukuran 8 baris dan 8 kolom dan setiap pemain memiliki bidak yang berbeda warna (biasanya hitam dan putih). Saat ini, permainan Reversi dapat ditemukan dengan mudah dalam bentuk aplikasi. Penerapan Kecerdasan Buatan menggunakan konsep algoritma Minimax dan algrotima BFS ini dapat mengefisienkan waktu eksekusi program dan memungkinkan agen cerdas untuk mengalahkan manusia. Pembuatan aplikasi ini bertujuan untuk mengetahui cara kerja suatu agen cerdas pada permainan Reversi. Aplikasi ini dikembangkan menggunakan metode perancangan UML dan bahasa pemrograman Java.
Universitas Sumatera Utara
IMPLEMENTATION THE CONCEPT OF MINIMAX ALGORITHM USING BREADTH-FIRST SEARCH (BFS) ON REVERSI GAME
ABSTRACT
Reversi is a board game based on pure strategy and played by two player on a board with 8 rows and 8 coloumns and a set of distinct discs (usually used black and white). Nowadays, Reversi has been found easily as a computer-game. Implementation the AI on Reversi game using the concept of Minimax algorithm and BFS algorithm could efficiently reduce the execution time and have a chance to defeat human. The main purpose of developing this Reversi game is to find out the process of the AI. This application was developed using UML and Java programming language.
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv v vi vii ix x
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penulisan Tugas Akhir 1.5 Manfaat Penulisan Tugas Akhir 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
1 1 3 3 3 3 4 4
Bab 2 Landasan Teori 2.1 Permainan Reversi 2.1.1 Aturan Permainan Reversi 2.2 Agen Cerdas 2.2.1 Struktur Agen Cerdas 2.2.1.1 Simple Reflex Agents 2.2.1.2 Model-Based Reflex Agents 2.2.1.3 Goal-Based Agents 2.2.1.4 Utility-Based Agents 2.2.2 Karakteristik Lingkungan Agen 2.3 Pohon Permainan 2.4 Algoritma Pencarian (Penelusuran) 2.4.1 Depth-First Search 2.4.2 Breadth-First Search 2.5 Algoritma Minimax
6 6 7 8 9 11 11 12 13 14 17 19 19 21 23
Bab 3 Analisis dan Perancangan 3.1 Analisis Algoritma Breadth-First Search 3.1.1 Kompleksitas Algoritma Breadth-First Search 3.1.2 Fungsi Evaluasi 3.1.3 Pemotongan (Cut-Off) 3.1.4 Struktur Data 3.2 Analisis Konsep Algoritma Minimax 3.3 Pemodelan Visual Menggunakan UML
26 26 26 27 29 31 31 33
Universitas Sumatera Utara
3.3.1 Identifikasi Use Case Diagram 3.3.1.1 Use Case Mulai Baru 3.3.1.2 Use Case Letak Koin 3.3.1.3 Use Case Undo Langkah 3.3.1.4 Use Case Minta Bantuan 3.3.2 Perancangan Class Diagram Reversi 3.3.3 Sequence Diagram 3.3.3.1 Sequence Diagram Untuk Method BFS 3.3.3.2 Sequence Diagram Untuk Method konsepMinimax
34 36 38 40 42 43 45 46 47
Bab 4 Implementasi dan Pengujian 4.1 Implementasi 4.1.1 Konfigurasi Perangkat Keras 4.1.2 Konfigurasi Perangkat Lunak 4.1.3 Hasil Eksekusi Aplikasi 4.2 Metode Singkat BFS 4.3 Metode konsepMinimax 4.4 Pengujian Agen Cerdas 4.5 Pengujian Terhadap Responden
48 48 48 49 49 54 55 56 63
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
65 65 66
Daftar Pustaka
67
Lampiran A: Listing Program
68
Universitas Sumatera Utara
DAFTAR TABEL
Halaman Tabel 2.1 Contoh Tipe Agen dengan Kesan, Tindakan, Tujuan dan Lingkungan Tabel 2.2 Contoh Lingkungan dan Karakteristiknya Tabel 3.1 Dokumentasi Naratif Use Case Mulai Baru Tabel 3.2 Dokumentasi Naratif Use Case Letak Koin Tabel 3.3 Dokumentasi Naratif Use Case Undo Langkah Tabel 3.4 Dokumentasi Naratif Use Case Minta Bantuan Tabel 3.5 Penjelasan Kelas-Kelas Pada Class Diagram Reversi Tabel 4.1 Data Antrian Tingkat 4 Sampel 1 Tabel 4.2 Pencarian Nilai Optimal Sampel 1 Tabel 4.3 Data Antrian Tingkat 4 Sampel 2 Tabel 4.4 Pencarian Nilai Optimal Sampel 2 Tabel 4.5 Data Antrian Tingkat 4 Sampel 3 Tabel 4.6 Pencarian Nilai Optimal Sampel 3 Tabel 4.7 Hasil Pengujian Terhadap Responden
10 17 36 38 40 42 45 57 58 60 60 61 62 64
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 2.1 Agen awal permainan Reversi Gambar 2.2 Kotak yang mungkin (giliran langkah hitam) Gambar 2.3 Agen berinteraksi dengan lingkungan Gambar 2.4 Agen refleks sederhana Gambar 2.5 Agen refleks berbasis model Gambar 2.6 Agen refleks berbasis tujuan Gambar 2.7 Agen refleks berbasis kegunaan Gambar 2.8 Pohon permainan Tic-Tac-Toe Gambar 2.9 Penelusuran pohon permainan dengan DFS Gambar 2.10 Penelusuran pohon permainan dengan BFS Gambar 2.11 Illustrasi cara kerja algoritma Minimax Gambar 3.1 Strategi peletakkan koin pada kotak Gambar 3.2 Kotak-kotak unik pada papan permainan Reversi Gambar 3.3 Kondisi yang menghasilkan cut-off Gambar 3.4 Pohon permainan dengan BFS dan DFS Gambar 3.5 Penelusuran BFS dan konsep algoritma Minimax Gambar 3.6 Use case diagram Reversi Gambar 3.7 Activity diagram Mulai Baru Gambar 3.8 Activity diagram Letak Koin Gambar 3.9 Activity diagram Undo Langkah Gambar 3.10 Activity diagram Minta Bantuan Gambar 3.11 Class diagram Reversi Gambar 3.12 Sequence diagram BFS Gambar 3.13 Sequence diagram konsepMinimax Gambar 4.1 Halaman awal Gambar 4.2 Tampilan agen berpikir Gambar 4.3 Jendela mulai baru Gambar 4.4 Tampilan minta bantuan Gambar 4.5 Tampilan akhir permainan dan papan telah penuh Gambar 4.6 Tampilan akhir permainan dan papan belum penuh Gambar 4.7 Sampel posisi 1 (giliran langkah putih) Gambar 4.8 Sampel posisi 2 (giliran langkah putih) Gambar 4.9 Sampel posisi 3 (giliran langkah hitam)
6 7 8 11 12 13 14 18 20 22 25 28 29 30 30 32 35 37 39 41 43 44 46 47 49 51 51 52 53 53 56 60 61
Universitas Sumatera Utara
