lisensi ini mengizinkan setiap orang untuk menggubah ...kc.umn.ac.id/5062/7/halaman awal.pdf ·...
Post on 09-Feb-2020
7 Views
Preview:
TRANSCRIPT
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 MONTE-CARLO TREE SEARCH
PADA SIMULASI PERMAINAN KARTU CARDFIGHT!! VANGUARD
SKRIPSI
Diajukan sebagai salah satu syarat untuk memperoleh gelar
Sarjana Komputer (S.Kom.)
Kevin Padawangi
14110110108
PROGRAM STUDI INFORMATIKA
FAKULTAS TEKNIK DAN INFORMATIKA
UNIVERSITAS MULTIMEDIA NUSANTARA
TANGERANG
2018
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
ii
LEMBAR PENGESAHAN SKRIPSI
IMPLEMENTASI ALGORITMA MONTE-CARLO TREE SEARCH
PADA SIMULASI PERMAINAN KARTU CARDFIGHT!! VANGUARD
Oleh
Nama : Kevin Padawangi
NIM : 14110110108
Fakultas : Teknologi Informasi dan Komunikasi
Program Studi : Teknik Informatika
Tangerang, 2 Agustus 2018
Ketua Sidang Dosen Penguji
Ir. Andrey Andoko, M.Sc. Marcel Bonar Kristanda, S.Kom.,
M.Sc.
Dosen Pembimbing I Dosen Pembimbing II
Farica Perdana Putri, S.Kom., M.Sc. Dr. Ir. P.M. Winarno, M.Kom.
Mengetahui,
Ketua Program Studi
Teknik Informatika
Seng Hansun, S.Si., M.Cs.
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
iii
PERNYATAAN TIDAK MELAKUKAN PLAGIAT
Dengan ini saya:
Nama : Kevin Padawangi
NIM : 14110110108
Fakultias : Teknik dan Informatika
Program Studi : Informatika
menyatakan bahwa skripsi yang berjudul ”Implementasi Algoritma Monte-
Carlo Tree Search pada Simulasi Permainan Kartu Cardfight!! Vanguard”
ini adalah karya ilmiah saya sendiri, bukan plagiat dari karya ilmiah yang ditulis
oleh orang atau lembaga lain, dan semua karya ilmiah orang atau lembaga lain
yang dirujuk dalam skripsi ini telah disebutkan sumber kutipannya serta
dicantumkan di Daftar Pustaka.
Jika di kemudian hari terbukti ditemukan kecurangan/penyimpangan, baik dalam
pelaksanaan skripsi maupun dalam penulisan laporan skripsi, saya bersedia
menerima konsekuensi dinyatakan TIDAK LULUS untuk mata kuliah Skripsi
yang telah saya tempuh.
Tangerang, 2 Agustus 2018
Kevin Padawangi
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
iv
PERNYATAAN PERSETUJUAN PUBLIKASI KARYA
ILMIAH UNTUK KEPENTINGAN AKADEMIS
Sebagai sivitas akademik Universitas Multimedia Nusantara, saya yang bertanda
tangan di bawah ini:
Nama : Kevin Padawangi
NIM : 14110110108
Program Studi : Informatika
Fakultas : Teknik dan Informatika
Jenis Karya : Skripsi
Demi pengembangan ilmu pengetahuan, menyetujui dan memberikan izin kepada
Universitas Multimedia Nusantara hak Bebas Royalti Non-eksklusif (Non-
exclusive Royalty-Free Right) atas karya ilmiah saya yang berjudul:
Implementasi Algoritma Monte-Carlo Tree Search pada Simulasi
Permainan Kartu Cardfight!! Vanguard
beserta perangkat yang diperlukan.
Dengan Hak Bebas Royalti Non-eksklusif ini, pihak Universitas Multimedia
Nusantara berhak menyimpan, mengalihmedia atau format-kan, mengelola
dalam bentuk pangkalan data (database), merawat, mendistribusi, dan
menampilkan atau mempublikasikan karya ilmiah saya di internet atau media lain
untuk kepentingan akademis, tanpa perlu meminta izin dari saya maupun
memberikan royalti kepada saya, selama tetap mencantumkan nama saya sebagai
penulis karya ilmiah tersebut.
Demikian pernyataan ini saya buat dengan sebenarnya untuk dipergunakan
sebagaimana mestinya.
Tangerang, 2 Agustus 2018
Kevin Padawangi
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
v
KATA PENGANTAR
Puji dan syukur kepada Tuhan yang Maha Kuasa, karena atas berkat dan
karunia-Nya sehingga penulis mampu menyelesaikan laporan tugas akhir
“Implementasi Algoritma Monte-Carlo Tree Search pada Simulasi Permainan
Kartu Cardfight!! Vanguard”. Penulis ingin mengucapkan terima kasih kepada
Universitas Multimedia Nusantara karena telah memberikan kesempatan bagi
penulis untuk menempuh pendidikan. Atas kesempatan yang diberikan penulis
telah memperoleh pengetahuan dan pengalaman.
Penyusunan laporan tugas akhir tidak terlepas dari bantuan berbagai pihak,
sehingga melalui kesempatan ini penulis ingin mengucapkan terima kasih kepada:
1. Dr. Ninok Leksono, selaku Rektor Universitas Multimedia Nusantara, yang
memberi inspirasi bagi penulis untuk berprestasi,
2. Seng Hansun, S.Si., M.Cs., selaku ketua program studi Informatika,
3. Farica Perdana Putri, S.Kom, M.Sc., selaku dosen pembimbing pertama
yang telah membimbing, mendidik, serta memberikan nasehat sehingga
laporan tugas akhir dapat selesai dengan baik.,
4. Dr. Ir. P.M. Winarno, M.Kom., selaku dosen pembimbing kedua yang juga
telah membimbing dan memberikan saran selama penulisan laporan tugas
akhir,
5. Seluruh rekan se-angkatan Informatika Universitas Multimedia Nusantara
tahun angkatan 2014 yang telah menemani, membantu, dan memberikan
dukungan selama penulisan tugas akhir,
6. Orang tua dan keluarga yang selalu menyemangati dan memberikan
dukungan kepada penulis,
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
vi
7. Pihak-pihak lain yang turut membantu penulis dalam menyelesaikan
laporan tugas akhir ini yang tidak dapat disebutkan satu per satu.
Penulis juga menyadari bahwa laporan tugas akhir ini masih jauh dari sempurna.
Oleh karena itu, penulis selalu siap menerima kritikan dan saran yang sifat
membangun bagi diri penulis. Semoga laporan tugas akhir ini dapat bermanfaat,
baik sebagai sumber informasi maupun sumber inspirasi, bagi para pembaca.
Tangerang, Agustus 2018
Kevin Padawangi
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
vii
IMPLEMENTASI ALGORITMA MONTE-CARLO TREE SEARCH
PADA SIMULASI PERMAINAN KARTU CARDFIGHT!! VANGUARD
ABSTRAK
Permainan Cardfight!! Vanguard memiliki banyak peminat di seluruh dunia.
Namun hingga saat ini, permainan Cardfight!! Vanguard memiliki keterbatasan
berupa tidak memiliki permainan dalam bentuk digital, sehingga penelitian
mengenai kecerdasan buatan untuk permainan kartu ini masih sangat terbatas.
Melalui penelitian ini, algoritma Monte-Carlo Tree Search diimplementasikan
pada strategi yang dapat digunakan oleh pemain untuk memilih kartu. Uji coba
dilakukan dengan cara menggunakan salah satu pemain untuk melawan pemain
lain dengan jenis strategi yang berbeda-beda yaitu strategi random, rule-based,
dan Monte-Carlo. Setelah diimplementasikan dalam simulasi permainan kartu
Cardfight!! Vanguard sebanyak 100 kali untuk tiap kecerdasan buatan, strategi
Monte-Carlo menghasilkan peningkatan persentase jumlah kemenangan sebesar
86.5% dan 3.9% dibandingkan dengan strategi random dan rule-based.
Kata Kunci: Cardfight!! Vanguard, Monte-Carlo Tree Search, strategi Random,
strategi Rule-Based, pemilihan kartu
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
viii
IMPLEMENTATION OF MONTE-CARLO TREE SEARCH
ALGORITHM ON SIMULATION OF CARDFIGHT!! VANGUARD
CARD GAMES
ABSTRACT
Cardfight!! Vanguard game has many enthusiasts around the world. But until
now, Cardfight!! Vanguard game has the limitations of not having a game in
digital form, so research on the artificial curiosity for this card game is still very
limited. Through this research, the Monte-Carlo Tree Search algorithm is
implemented on strategies that players can use to select cards. Testing is done by
using one player to fight against other players with different types of strategies:
random, rule-based, and Monte-Carlo strategies. Once implemented in
Cardfight!! Vanguard card game simulation as much as 100 times for each
artificial intelligence, Monte-Carlo strategy resulted in an increase in the
percentage of winning numbers by 86.5% and 3.9% compared with random and
rule-based strategies.
Keyword: Cardfight!! Vanguard, Monte-Carlo Tree Search, Random strategy,
Rule-Based strategy, card selection
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
ix
DAFTAR ISI
LEMBAR PERSETUJUAN ................................................................................. ii
PERNYATAAN TIDAK MELAKUKAN PLAGIAT ........................................ iii
PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH ................. iv
ABSTRAK ............................................................................................................ v
KATA PENGANTAR ........................................................................................ vii
DAFTAR ISI ....................................................................................................... ix
DAFTAR GAMBAR ............................................................................................ x
DAFTAR TABEL ................................................................................................ x
BAB I PENDAHULUAN ..................................................................................... 1
1.1 Latar Belakang .......................................................................................... 1
1.2 Rumusan Masalah ..................................................................................... 4
1.3 Batasan Masalah ....................................................................................... 4
1.4 Tujuan Penelitian ...................................................................................... 5
1.5 Manfaat Penelitian .................................................................................... 5
BAB II LANDASAN TEORI ............................................................................... 6
2.1 Simulasi Permainan .................................................................................. 6
2.2 Permainan Kartu Digital ........................................................................... 7
2.3 Permainan Cardfight!! Vanguard .............................................................. 9
2.4 Kecerdasan Buatan.................................................................................. 17
2.5 Monte-Carlo Tree Search ........................................................................ 18
2.6 Black-box Testing ................................................................................... 22
BAB III METODOLOGI DAN PERANCANGAN SISTEM ........................... 24
3.1 Metode Penelitian ................................................................................... 24
3.2 Arsitektur Sistem .................................................................................... 27
BAB IV IMPLEMENTASI DAN UJI COBA.................................................... 24
4.1 Spesifikasi Sistem ................................................................................... 24
4.2 Implementasi ........................................................................................... 24
4.3 Skenario Uji Coba ................................................................................... 46
4.4 Uji Coba Algoritma................................................................................. 52
BAB V KESIMPULAN DAN SARAN ............................................................. 54
5.1 Kesimpulan ............................................................................................. 54
5.2 Saran ....................................................................................................... 54
DAFTAR PUSTAKA ......................................................................................... 55
DAFTAR LAMPIRAN ...................................................................................... 57
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
x
DAFTAR GAMBAR
Gambar 1.1 Desain kartu dan kondisi lingkungan permainan kartu .................... 2
Gambar 1.2 Contoh permainan kartu digital, “Cardfight!! Online” ..................... 2
Gambar 2.1 Desain kartu Cardfight!! Vanguard ................................................ 10
Gambar 2.2 Jenis Skill Icons .............................................................................. 11
Gambar 2.3 Jenis Ability Icons .......................................................................... 12
Gambar 2.4 Jenis Special Actions Icons ............................................................. 13
Gambar 2.5 Jenis Cost Icons .............................................................................. 13
Gambar 2.6 Arena permainan Cardfight!! Vanguard ......................................... 14
Gambar 2.7 Empat tahap iterasi MCTS .............................................................. 20
Gambar 3.1 Tabel Strategi dalam percobaan Ward dan Cowling ...................... 26
Gambar 3.2 Flowchart Permainan ...................................................................... 27
Gambar 3.3 Flowchart Ride Phase ..................................................................... 29
Gambar 3.4 Flowchart Main Phase .................................................................... 30
Gambar 3.5 Flowchart Battle Phase ................................................................... 31
Gambar 3.6 Flowchart Guard Step ..................................................................... 33
Gambar 3.7 Flowchart Random Strategy ........................................................... 34
Gambar 3.8 Flowchart Rule-Based Strategy ...................................................... 35
Gambar 3.9 Flowchart Monte-Carlo Strategy .................................................... 36
Gambar 3.10 Inisialisasi Tree ............................................................................. 37
Gambar 3.11 Desain Antarmuka Tampilan Simulasi ......................................... 38
Gambar 4.1 Tampilan Simulasi Permainan ........................................................ 40
Gambar 4.2 Tampilan pada Console .................................................................. 40
Gambar 4.3 Potongan code class JsonHelper ..................................................... 41
Gambar 4.4 Potongan code Pengambilan Data Kartu ........................................ 41
Gambar 4.5 Potongan code First Vanguard Kedua Pemain ............................... 42
Gambar 4.6 Potongan code Draw Phase ............................................................. 42
Gambar 4.7 Potongan code Strategi Random saat Ride Phase ........................... 43
Gambar 4.8 Potongan code Strategi Rule-Based saat Ride Phase ...................... 44
Gambar 4.9 Potongan code Inisialisasi Tree Strategi MCTS ............................. 44
Gambar 4.10 Potongan code Perulangan Iterasi Strategi MCTS Ride Phase ..... 45
Gambar 4.11 Potongan code Main Phase ........................................................... 46
Gambar 4.12 Potongan code Guard Step saat Battle Phase ................................ 46
Gambar 4.13 First Vanguard Kedua Pemain ...................................................... 48
Gambar 4.14 Gambaran Tree Kartu Tangan ...................................................... 48
Gambar 4.15 Contoh Iterasi 0 MCTS pada Simulasi ......................................... 48
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
xi
Gambar 4.16 Contoh Iterasi 1 MCTS pada Simulasi ......................................... 49
Gambar 4.17 Contoh Iterasi 2 MCTS pada Simulasi ......................................... 50
Gambar 4.18 Keterangan Ride pada Kartu ......................................................... 50
Gambar 4.19 P2 Tidak Dapat Melakukan Call ................................................... 50
Gambar 4.20 Drive Check P1 pada Console ...................................................... 51
Gambar 4.21 Guard Step P2 pada Console ........................................................ 51
Gambar 4.22 Keterangan Hasil Simulasi ............................................................ 51
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
xii
DAFTAR TABEL
Tabel 4.1 Penggunaan Strategi Tiap Phase ......................................................... 43
Tabel 4.2 Daftar Kartu Cardfight!! Vanguard Trial Deck 01 ............................. 47
Tabel 4.3 Hasil Uji Coba Antar Strategi ............................................................. 52
Tabel 4.4 Perbandingan Monte-Carlo dan Random ........................................... 53
Tabel 4.5 Perbandingan Monte-Carlo dan Rule-Based ...................................... 53
Implementasi Algoritma Monte-Carlo..., Kevin Padawangi, FTI UMN, 2018
top related