lisensi ini mengizinkan setiap orang untuk menggubah ...kc.umn.ac.id/5062/7/halaman awal.pdf ·...

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



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.


iii

PERNYATAAN TIDAK MELAKUKAN PLAGIAT

Dengan ini saya:


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.


Kevin Padawangi


iv

PERNYATAAN PERSETUJUAN PUBLIKASI KARYA

ILMIAH UNTUK KEPENTINGAN AKADEMIS

Sebagai sivitas akademik Universitas Multimedia Nusantara, saya yang bertanda

tangan di bawah ini:


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.


Kevin Padawangi


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,


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


vii



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


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


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


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


xi



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


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


lisensi ini mengizinkan setiap orang untuk menggubah ...kc.umn.ac.id/5062/7/halaman awal.pdf ·...

Documents