lisensi ini mengizinkan setiap orang untuk menggubah ...kc.umn.ac.id/1752/1/halaman awal.pdfpada...

Team project ©2017 Dony Pratidana S. Hum | Bima Agus Setyawan S. IIP

Hak cipta dan penggunaan kembali:

Lisensi ini mengizinkan setiap orang untuk menggubah, memperbaiki, dan membuat ciptaan turunan bukan untuk kepentingan komersial, selama anda mencantumkan nama penulis dan melisensikan ciptaan turunan dengan syarat yang serupa dengan ciptaan asli.

Copyright and reuse:

This license lets you remix, tweak, and build upon work non-commercially, as long as you credit the origin creator and license it on your new creations under the identical terms.

IMPLEMENTASI ALGORITMA MINIMAX DAN OPTIMASI

ALPHA-BETA PADA PERMAINAN CATUR

SKRIPSI

Diajukan sebagai salah satu syarat untuk memperoleh gelar

Sarjana Komputer

UNIVERSITAS MULTIMEDIA NUSANTARA

TANGERANG

2014

Nama : Ronal Gorba Timothy

NIM : 09110110083

Fakultas : Teknologi Informasi dan Komunikasi

Program Studi : Teknik Informatika

ii

PENGESAHAN SKRIPSI

IMPLEMENTASI ALGORITMA MINIMAX DAN OPTIMASI

ALPHA-BETA PADA PERMAINAN CATUR

Oleh

Tangerang, 26 Februari 2014

Ketua Sidang Dosen Penguji

Dr. Ir. P. M. Winarno, M.Kom. Seng Hansun, S.Si., M.Cs.

Dosen Pembimbing Ketua Program Studi

Teknik Informatika

Dodick Z. S., S.Kom., B.App. Sc., M.T.I Maria Irmina P., S.Kom., M.T.


NIM : 09110110083



Implementasi Algoritma ..., Ronal Gorba Timothy, FTI UMN, 2014

iii

Lembar Pernyataan Tidak Melakukan Plagiat dalam

Penyusunan Skripsi

Dengan ini saya:


NIM : 09110110083



Menyatakan bahwa skripsi ini adalah karya ilmiah saya sendiri, bukan hasil

plagiat dari karya ilmiah yang ditulis oleh orang lain, dan semua karya ilmiah

orang lain atau lembaga lain yang dirujuk dalam skripsi ini telah disebutkan

sumber kutipannya serta dicantumkan di Daftar Pustaka.


Ronal Gorba Timothy


iv

Judul: Implementasi Algoritma Minimax dan Optimasi Alpha-Beta Pada

Permainan Catur

ABSTRAKSI

Pada permainan catur, jumlah seluruh kombinasi langkah yang mungkin terjadi

sangat banyak. Sebagai contoh, ada sekitar 300 miliar kemungkinan kombinasi

pembukaan pada permainan catur. Dengan adanya hal ini, maka muncul beberapa

metode yang telah dioptimalkan untuk membantu menyelesaikan masalah dalam

pencarian langkah-langkah yang begitu banyak pada permainan catur. Salah satu

solusi yang bisa dilakukan di antaranya adalah dengan menggunakan algoritma

minimax dengan optimasinya berupa algoritma Alpha-Beta. Skripsi ini akan

membahas implementasi kecerdasan buatan yang dibuat dengan algoritma

minimax dengan optimasi Alpha-Beta untuk menghasilkan keputusan yang efektif

pada permainan catur. Hasil penelitian menunjukkan bahwa penggunaan

algoritma minimax dengan optimasi Alpha-Beta dapat mempercepat waktu

pencarian langkah.

Kata kunci: Minimax Algorithm, Alpha-Beta Pruning, Catur, Kecerdasan Buatan.


v

Title: Implementation of Minimax Algorithm and Alpha-Beta Optimization

in Chess Game

ABSTRACT

In chess game, the total number of movement combinations that might happen is

too much. For example, there are approximately 300 billion possible

combinations of chess opening. In consequence of that, the methods that have

been optimized to help solve problems in searching that much movement in chess

game is gradually appear. One of possible solutions to this matter is using

minimax algorithm with its optimization algorithms such as Alpha-Beta. This

paper presents an implementation of artificial intelligence created by minimax

algorithm with Alpha-Beta optimization to make an effective decision in a chess

game. The results of this research indicate that using Alpha-Beta optimization

algorithm can accelerate the movement search time better.

Keywords: Minimax Algorithm, Alpha-Beta Pruning, Catur, Kecerdasan Buatan.


vi

KATA PENGANTAR

Dengan adanya skripsi ini, penulis berhasil mewujudkan satu langkah awal

yang menjadi fokus dukungan dari berbagai pihak selama ini. Skripsi ini disusun

dan diajukan sebagai salah satu syarat pemenuhan mata kuliah Skripsi yang

menjadi salah satu syarat kelulusan program studi S-1 Teknik Informatika di

Universitas Multimedia Nusantara.

Pada kesempatan kali ini, penulis ingin berterima kasih kepada pihak-

pihak yang telah banyak memberikan dukungan dan kontribusi kepada penulis

dalam proses penulisan skripsi ini.

1. Kedua orang tua penulis yang selalu memberikan dana, apresiasi, dan

semangat kepada penulis selama menyusun skripsi.

2. Bapak Dodick Zulaimi Sudirman selaku pembimbing skripsi penulis yang

senantiasa memberikan bimbingan, pengarahan dan koreksi-koreksi yang

positif bagi penyusunan skripsi ini.

3. Ibu Maria Irmina selaku Ketua Program Studi Teknik Informatika

Universitas Multimedia Nusantara atas dukungan, bantuan dan

kesempatan yang diberikan untuk penulis dalam mengejar ketertinggalan

dalam beberapa proses akademik selama penulis menyusun skripsi.

4. Maria Miracellia Bo selaku teman dekat penulis yang banyak

berkontribusi dalam memberikan saran dan dukungan serta hiburan selama

penulis menyusun skripsi ini.


vii

5. Denny Halim, salah satu teman penulis yang telah banyak membantu

penulis dalam memberikan masukan dan dukungan kepada penulis dalam

menyelesaikan skripsi ini.

6. Teman-teman Teknik Informatika angkatan 2009 UMN yang secara tidak

langsung memberikan inspirasi bagi penulis selama menjadi mahasiswa.

7. Bobby Fischer, salah satu pemain catur terkenal idola penulis yang

menjadi inspirasi penulis dalam menentukan ide skripsi.

8. Leonard Kleinrock dan Timothy “Tim” John Berners-Lee atas jasanya

yang begitu besar dalam menciptakan teknologi internet yang selalu

dipakai penulis untuk mencari informasi sebanyak-banyaknya dalam

penulisan skripsi.

9. Larry Page dan Sergey Brin atas jasanya menciptakan mesin pencari

“Google” sebagai satu-satunya mesin pencari di internet yang selalu

digunakan penulis selama berkuliah dan menyusun skripsi.

10. Pihak-pihak lain yang secara langsung maupun tidak langsung telah

berjasa dalam penyusunan skripsi ini yang tidak dapat penulis sebutkan

satu persatu.

”Tak ada gading yang tak retak”. Tidak ada manusia yang sempurna.

Karena itulah, penulis menyadari bahwa masih terdapat banyak kekurangan dalam

skripsi ini, baik dari sisi penulisan, diksi, penjelasan, maupun tata bahasanya.

Oleh karena itu, penulis sangat terbuka terhadap segala kritik maupun saran yang

membangun dari semua pihak demi menyempurnakan skripsi ini.


viii

Akhir kata, penulis mengucapkan terima kasih kepada siapa saja yang

telah meluangkan waktunya untuk membaca skripsi ini. Penulis berharap semoga

skripsi ini dapat menambah wawasan bagi para pembacanya, terutama dalam

bidang teknologi informasi dan komunikasi.


Penulis


ix

DAFTAR ISI

HALAMAN JUDUL ................................................................................................ i

HALAMAN PERSETUJUAN SIDANG SKRIPSI ................................................ ii

HALAMAN PERNYATAAN TIDAK MELAKUKAN PLAGIAT ..................... iii

ABSTRAKSI ......................................................................................................... iv

ABSTRACT ............................................................................................................... v

KATA PENGANTAR ........................................................................................... vi

DAFTAR ISI .......................................................................................................... ix

DAFTAR GAMBAR ............................................................................................. xi

DAFTAR TABEL ................................................................................................ xiii

BAB I PENDAHULUAN ........................................................................................ 1

1.1 Latar Belakang ................................................................................................ 1

1.2 Perumusan Masalah ........................................................................................ 3

1.3 Batasan Masalah ............................................................................................. 3

1.4 Tujuan Penelitian ............................................................................................ 3

1.5 Manfaat Penelitian .......................................................................................... 4

1.6 Sistematika Penulisan ..................................................................................... 4

BAB II LANDASAN TEORI .................................................................................. 6

2.1 Catur ............................................................................................................... 6

2.1.1 Dasar Permainan Catur ........................................................................... 6

2.2 Kecerdasan Buatan ....................................................................................... 10

2.2.1 Sejarah Kecerdasan Buatan ................................................................... 10

2.2.2 Konsep Dasar AI.................................................................................... 12

2.2.3 Implementasi Kecerdasan Buatan pada Game ...................................... 18

2.3 Algoritma ...................................................................................................... 23

2.3.1 Konsep Dasar Algoritma ....................................................................... 24

2.3.2 Konsep Dasar Algoritma Minimax ........................................................ 26

2.3.3 Implementasi Algoritma Minimax ........................................................ 26


x

2.3.4 Konsep Dasar Algoritma Alpha-Beta Pruning ...................................... 29

2.3.5 Implementasi Alpha-Beta Pruning ........................................................ 30

BAB III ANALISIS DAN PERANCANGAN APLIKASI ................................... 33

3.1 Metode Penelitian.......................................................................................... 33

3.2 Analisis Aplikasi ........................................................................................... 34

3.2.1 Flowchart Permainan Player vs AI ........................................................ 35

3.2.2 Algoritma Minimax Pada Analisis Permainan ...................................... 36

3.2.3 Alpha-Beta Pruning pada Optimasi Algoritma Minimax ...................... 42

3.3 Perancangan Aplikasi .................................................................................... 45

3.3.1 Struktur Navigasi Menu ......................................................................... 45

3.3.2 Desain Antarmuka Aplikasi................................................................... 47

BAB IV IMPLEMENTASI DAN UJI COBA ....................................................... 51

4.1 Spesifikasi Perangkat .................................................................................... 51

4.2 Implementasi Aplikasi .................................................................................. 53

4.3 Hasil Uji Coba .............................................................................................. 56

4.3.1 Pengujian Algoritma Minimax dengan Optimasi Alpha-Beta .............. 57

4.3.2 Pengujian Algoritma Minimax .............................................................. 58

BAB V KESIMPULAN DAN SARAN ................................................................. 59

5.1 Kesimpulan ................................................................................................... 59

5.2 Saran ............................................................................................................. 59

DAFTAR PUSTAKA ............................................................................................ 60

DAFTAR LAMPIRAN .......................................................................................... 63


xi

DAFTAR GAMBAR

Gambar 2.1 Posisi Awal Permainan Catur Sederhana ............................................. 7

Gambar 2.2 Posisi Pergerakan Raja ......................................................................... 7

Gambar 2.3 Posisi Pergerakan Benteng ................................................................... 8

Gambar 2.4 Posisi Pergerakan Ratu ......................................................................... 9

Gambar 2.5 Posisi Pergerakan Kuda ........................................................................ 9

Gambar 2.6 Penerapan Konsep AI dalam Komputer ............................................. 13

Gambar 2.7 Cara Kerja Komputer dengan Metode Konvensional dan AI ............ 17

Gambar 2.8 Spektrum Intelegensia atau “Kemampuan Arah” .............................. 18

Gambar 2.9 Daerah Utama Aplikasi AI ................................................................. 20

Gambar 2.10 Pohon Pencarian Algoritma Minimax .............................................. 27

Gambar 2.11 Pseudocode Algoritma Minimax ...................................................... 28

Gambar 2.12 Tree untuk Kondisi Awal Alpha-Beta Pruning ................................ 30

Gambar 2.13 Tree untuk Hasil Metode Alpha-Beta Pruning ................................. 31

Gambar 2.14 Pseudocode Algoritma Minimax dengan Optimasi Alpha-Beta

Pruning ................................................................................................................... 32

Gambar 3.1 Flowchart Gambaran Umum Program ............................................... 34

Gambar 3.2 Flowchart Player vs AI ....................................................................... 35

Gambar 3.3 Tree Permainan Catur Menggunakan Teknik Pencarian DFS ........... 37

Gambar 3.4 Tree yang Dibangun dengan Algoritma Minimax ............................. 39

Gambar 3.5 Flowchart Algoritma Minimax .......................................................... 41

Gambar 3.6 Pencarian pada Tree dengan Alpha-Beta Pruning.............................. 42

Gambar 3.7 Flowchart Algoritma Minimax dengan Optimasi Alpha-Beta ........... 43

Gambar 3.8 Potongan Kode Program Algoritma Minimax dengan Optimasi

Alpha-Beta ............................................................................................................. 44

Gambar 3.9 Struktur Navigasi Menu Aplikasi ....................................................... 45

Gambar 3.10 Desain Antarmuka Tampilan Utama ................................................ 47

Gambar 3.11 Desain Antarmuka Menu New Game .............................................. 48

Gambar 3.12 Desain Antarmuka Menu Setting ..................................................... 49


xii

Gambar 3.13 Desain Antarmuka Menu About ...................................................... 50

Gambar 4.1 Implementasi Tampilan Utama Aplikasi............................................ 53

Gambar 4.2 Implementasi Tampilan Antarmuka Menu New Game ..................... 54

Gambar 4.3 Implementasi Antarmuka Menu Setting ............................................ 55

Gambar 4.4 Implementasi Antarmuka Menu About .............................................. 56

Gambar 4.5 Hasil Ujicoba Permainan dengan Optimasi Algoritma Alpha-Beta... 57

Gambar 4.6 Hasil Ujicoba Permainan tanpa Optimasi Algoritma Alpha-Beta ..... 58


xiii

DAFTAR TABEL

Tabel 2.1 Perbedaan Komputasi AI dengan Komputasi Konvensional ................. 14


lisensi ini mengizinkan setiap orang untuk menggubah ...kc.umn.ac.id/1752/1/halaman awal.pdfpada...

Documents