PENERAPAN METODE PROBABILISTIC REASONING DALAM PERMAINAN “TERIMA ATAU TOLAK” Eza Budi Perkasa Teknik Informatika STMIK ATMA LUHUR PANGKALPINANG Jl. Jend. Sudirman, Selindung Lama, Pangkalpinang, Kepulauan Babel e-mail:
[email protected] Abstract “Terima Atau Tolak” is a game that is adapted from “Deal Or No Deal” game. The game is played by two people who have different role in. Every player has different way to play. The game is also a game that needs some strategy for its players. The strategy is needed so that the player gets the biggest score possible compared to his/her opponent. In this research, a method called probabilistic reasoning will be applied. The method is used by computer as its strategy in this game. Goal to be obtained is to look at the efficacy of the strategy that has been developed with the method. This research is done with prototype approaching. In the research, values of player’s victory probability will be calculated using certain algorithm. The values are compared with values got from some experiments. General conclusion obtained is that value of victory probability is depended on game condition and has inexact value. Users are wished to be able to narrow/expand the condition of the game to compare value of victory probability before and after changing. Keywords: Game, “Terima Atau Tolak”, probabilistic reasoning, strategy, victory probability
1.
dapat menjadi dasar untuk menentukan sebuah
Pendahuluan
keputusan. Manusia yang telah terlatih dapat dengan
1.1 Latar Belakang Di zaman yang serba canggih ini, komputer
cepat
mengambil
keputusan
dengan
tepat.
telah menjadi sebuah kebutuhan bagi manusia.
Permainan “Terima Atau Tolak” merupakan solusi
Tidak seperti dahulu kala ketika komputer masih
untuk dapat melatih pikiran manusia sehingga dapat
merupakan barang mewah sehingga sulit didapat.
berpikir
Sekarang,
komputer
reasoning
dimanapun, di supermarket, di instansi-instansi,
keputusan.
kita
bisa
menemukan
menggunakan dengan
metode
cepat
probabilistic
dalam
mengambil
bahkan kita sendiri dapat memilikinya dengan
Sebagaimana diketahui, terdapat cukup banyak
sangat mudah. Ini karena seperangkat komputer
variasi permainan komputer yang mempunyai genre
mampu mempermudah pekerjaan manusia, baik
yang berbeda-beda. Akan tetapi, hingga saat ini,
pekerjaan yang ringan sekalipun, maupun pekerjaan
masih jarang terdapat permainan yang dibuat di
berat
dapat
Indonesia. Selain itu, kebanyakan permainan
melakukannya. Bahkan, komputer dapat memiliki
bersifat closed source sehingga jika sang pemain
tingkat kecerdasan yang lebih tinggi dari manusia
sudah
yang merupakan pemiliknya.
menunggu versi selanjutnya untuk memainkan
yang
belum
tentu
manusia
menuntaskan
permainannya,
ia
harus
Salah satu kemudahan yang diberikan oleh
modus ataupun level baru. Apabila permainan
perangkat komputer saat ini adalah kemampuannya
tersebut bersifat open source, tentu pemain dapat
untuk menghibur penggunanya melalui permainan.
mengembangkan
Pada
keinginannya dan juga mempelajari algoritma yang
metode
probabilistic
reasoning,
setiap
pemikiran manusia diarahkan untuk dapat berpikir
permainan
terdapat di dalam permainan.
dengan menerima banyak kemungkinan. Hal ini 1
sesuai
dengan
Dari
permasalahan
yang
telah
diuraikan
c. Implementasi dan pengujian
sebelumnya, penulis bermaksud untuk merancang
1) Pengevaluasian prototype
permainan yang bersifat open source. Di samping
2) Perbaikan prototype
itu, penulis juga akan menguraikan algoritma dan metode permainan yang penulis rancang serta tahaptahap
pengimplementasiannya.
1.5 Tujuan Penulisan
Adapun
topik
Tujuan yang hendak penulis capai dalam
ambil
adalah
penulisan makalah ini adalah menerapkan metode
“Kecerdasan Buatan (Artificial Intelligence/AI)”
probabilistic reasoning sebagai strategi dalam
dan penulis memberi judul penelitian ini “Penerapan
permainan “Terima Atau Tolak”.
penelitian
yang
akan
penulis
Metode Probabilistic Reasoning Dalam Permainan ‘Terima Atau Tolak’”.
2.
Landasan Teori
2.1 Kecerdasan Buatan Kecerdasan buatan berasal dari bahasa Inggris
1.2 Rumusan Masalah a. Tahap-tahap penerapan metode probabilistic
“Artificial Intelligence” atau disingkat AI. Secara
reasoning dalam permainan “Terima Atau
harfiah, intelligence adalah kata sifat yang berarti
Tolak” dengan menggunakan algoritma tertentu.
cerdas,
sedangkan
artificial
berarti
buatan.
b. Penentuan nilai peluang kemenangan untuk tiap-
Kecerdasan buatan yang dimaksud merujuk pada
tiap kondisi dan pembandingannya untuk
mesin yang mampu berpikir, menimbang tindakan
menetapkan strategi terbaik.
yang akan diambil, dan mampu mengambil keputusan seperti yang dilakukan oleh manusia [1]. Kecerdasan buatan merupakan salah satu
1.3 Batasan Masalah a. Selama permainan berlangsung, pemain dapat
bagian ilmu komputer yang membuat agar mesin
menggunakan keyboard atau mouse sebagai
(komputer) dapat melakukan pekerjaan seperti dan
media input. Sementara outputnya ditampilkan
sebaik yang dilakukan oleh manusia. Pada awal
di monitor komputer dengan batasan resolusi
diciptakannya, komputer hanya difungsikan sebagai
minimum (1366 × 768 piksel).
alat hitung saja. Akan tetapi, seiring dengan
b. Terdapat
enam
modus
permainan
yang
perkembangan zaman, peran komputer semakin
disesuaikan dengan jumlah dan kebutuhan
mendominasi kehidupan umat manusia. Komputer
pemain. Jumlah pemain maksimum adalah dua
tidak lagi hanya digunakan sebagai alat hitung,
orang.
melainkan
c. Desain antarmuka permainan dibuat sesederhana
komputer
juga
diharapkan
untuk
mengerjakan segala sesuatu yang bisa dikerjakan
mungkin tanpa mengurangi maksud yang
oleh manusia [2].
hendak dicapai dalam permainan sehingga dapat menghemat ruang penyimpanan.
2.2 Soft Computing Soft computing adalah koleksi dari beberapa
1.4 Metode Penelitian
metodologi yang bertujuan untuk mengeksploitasi
a. Analisa dan pengumpulan kebutuhan
adanya
b. Perancangan
ketidakpastian, dan kebenaran parsial untuk dapat
toleransi
terhadap
ketidaktepatan,
1) Perancangan cepat
diselesaikan dengan mudah, robustness, dan biaya
2) Pembangunan prototype
penyelesaiannya murah. Definisi ini pertama kali
2
diungkapkan oleh Prof. Lotfi A. Zadeh pada tahun
2.4 Game Playing
1992.
Dalam beberapa tahun terakhir, AI telah
Soft computing merupakan inovasi baru dalam
menjadi garis depan dalam industri permainan
membangun sistem cerdas. Sistem cerdas ini
(game).
Hampir
semua
permainan
sekarang
merupakan sistem yang memiliki keahlian seperti
membutuhkan AI untuk membuat komputer seolah-
manusia pada domain tertentu, mampu beradaptasi
olah tampak cerdas. Konsep cerdas dibutuhkan
dan belajar agar dapat bekerja lebih baik jika terjadi
untuk mengontrol dan mengklasifikasi karakter
perubahan lingkungan.
pemain atau bukan.
Terdapat empat unsur pokok dalam soft
Program pertama yang dibuat AI adalah game
computing, yaitu Sistem Fuzzy (mengakomodasi
playing. Sejarah teori permainan dari tahun 1950,
ketidaktepatan), Jaringan Syaraf (menggunakan
ketika komputer mulai dapat diprogram. Permainan
pembelajaran),
Reasoning
pertama yang menggunakan AI adalah catur.
(mengakomodasi ketidakpastian), dan Evolutionary
Inisiator teori permainan dalam AI adalah Konard
Computing (optimasi). Keempat unsur tersebut
Zuse (penemu pertama komputer yang dapat
bukan merupakan pesaing antara satu dengan
diprogram dan bahasa pemrograman pertama),
lainnya, namun diantaranya bisa saling melengkapi.
Claude Shannon (penemu teori informasi), Norbert
Probabilistic
Wiener (pencipta teori kontrol modern), dan Alan Turing. Sejak saat itu, mulai ada kemajuan dalam
2.3 Algoritma Pencarian Langkah Terbaik Pencarian [3][4] adalah suatu proses mencari
standar
bermain
permainan,
sampai-sampai
solusi dari suatu permasalahan melalui sekumpulan
komputer dapat mengalahkan manusia dalam
kemungkinan ruang keadaan (state space). Ruang
permainan catur dan dalam banyak permainan
keadaan merupakan suatu ruang yang berisi semua
kompetitif lainnya [1].
keadaan yang mungkin. Dalam ilmu komputer, sebuah algoritma pencarian merupakan algoritma
2.5 Use Case Diagram
yang menerima masukan berupa sebuah masalah
Use
dan menghasilkan sebuah solusi untuk masalah
digunakan
tersebut yang biasanya didapat dari evaluasi
dibutuhkan pada sistem dan dilakukan pada saat
beberapa kemungkinan solusi. Himpunan semua
awal pembuatan sistem dan pada tahap analisis.
kemungkinan solusi dari sebuah masalah disebut
Diagram ini digunakan untuk membantu developer
ruang pencarian. Algortima pencarian brute-force
agar dapat mengerti fungsi yang dibutuhkan oleh
atau pencarian uninformed menggunakan metode
sistem tanpa khawatir tentang kebutuhan yang akan
yang sederhana dan sangat intuitif pada ruang
diimplementasikan [5]. Pada umumnya, Use Case
pencarian, sedangkan algoritma pencarian informed
Diagram mempunyai tiga bagian. Bagian-bagian
menggunakan
tersebut adalah sebagai berikut.
heuristik
untuk
menerapkan
Case
Diagram
untuk
adalah
menganalisa
model
yang
fungsi
yang
pengetahuan tentang struktur dari ruang pencarian
a. Actor, menggambarkan peran dari pemain atau
untuk berusaha mengurangi banyaknya waktu yang
sebuah alat yang berinteraksi langsung dengan
dipakai dalam pencarian.
sistem. Biasanya, actor digambar berupa stick figures.
3
b. Use case, merupakan aksi-aksi yang dapat
2.7 MySQL
dijalankan oleh actor. Use case biasanya
MySQL adalah sebuah sistem manajemen basis
berbentuk elips.
data relasi yang bersifat open source. Maksud dari
c. Association, menggambarkan hubungan antara
sifat ini adalah MySQL boleh diunduh oleh siapa
dua atau lebih objek, biasanya mewakilkan
saja, baik source code-nya ataupun program
hubungan yang diperbolehkan dalam proses di
executable-nya dan dapat digunakan secara (relatif)
suatu sistem. Association digambarkan dengan
gratis, baik untuk dimodifikasi sesuai dengan
garis lurus dan jika dibutuhkan, boleh ditambah
kebutuhan seseorang maupun sebagai suatu program
panah pada ujungnya untuk memberitahukan
aplikasi komputer [7].
arah koneksi tersebut. 3.
Metode Penelitian
3.1 Teknik Pengumpulan Data
Entry Pelanggan
a. Observasi:
Mengunduh
dan
memainkan
permainan yang sejenis, menganalisa algoritma
Entry Barang Pelanggan
yang digunakan, dan memperhatikan uraian dari Bagian Penjualan Entry Kendaraan
programmer permainan bersangkutan.
Supir
b. Studi pustaka: Entry Supir
Mencari referensi untuk
membantu proses implementasi permainan yang penulis rancang ke dalam bahasa pemrograman
Gambar 2.1 Contoh Use Case Diagram
yang penulis pilih. c. Angket (kuesioner):
2.6 Bahasa Pemrograman Visual Basic .NET
Memberikan kuesioner
kepada beta tester dan menganalisa hasilnya
Visual Basic .NET adalah sebuah alat untuk mengembangkan dan membangun aplikasi yang
untuk
bergerak di atas sistem .NET Framework, dengan
permainan selanjutnya.
menggunakan
bahasa
BASIC.
dijadikan
landasan
pengembangan
Dengan 3.2 Use Case Diagram
menggunakan alat ini, para programmer dapat membangun aplikasi Windows Forms, aplikasi web
Input nama pemain
berbasis ASP.NET, dan juga aplikasi command-line. Masuk menu modus permainan
Alat ini dapat diperoleh secara terpisah dari beberapa produk lainnya (seperti Microsoft Visual
Pilih lawan pemain
C++, Visual C#, atau Visual J#), atau juga dapat «extends»
diperoleh secara terpadu dalam Microsoft Visual User
Melihat nilai tertinggi
«extends»
Studio .NET. Bahasa Visual Basic .NET sendiri menganut
paradigma
bahasa
Melihat klasemen
Melihat profil pemain Melihat bantuan
pemrograman
berorientasi objek yang dapat dilihat sebagai evolusi
Keluar dari permainan
dari Microsoft Visual Basic versi sebelumnya yang
Gambar 3.1 Use Case Diagram
diimplementasikan di atas .NET Framework [6].
4
adalah jumlah kotak yang masih belum terbuka
3.3 Entity Relationship Diagram
(termasuk kotak yang dipegang kontestan).
Level Score
Party_Data 1
Save
Name
Wisdom Wisdom_Id Word Person
1
Player_Standing 1 1
Get
Get Name
1
Name Reg_Time Win Draw Lose 1
1
Get Name
Get Name
d. Penawaran Banker (Modus Arena)
Get Name
Name
Nilai penawaran ditentukan dengan persamaan M
High_Score_1v1 Score Round Time
M
M
M
High_Score_Arena
High_Score_Party
High_Score_Redenomination
Score Time
Score Round Level Time
Score Round Time
0; 𝑏 = 1 atau 𝑏 = 26 26 − 𝑏 𝑜n = {(10 × ⌈ ⌉ + 𝑛) % × ∑𝑚 3 ; 2 ≤ 𝑏 ≤ 25 𝑏
M
High_Score_Story Score Round Time
Gambar 3.2 Entity Relationship Diagram
Penawaran pada modus ini hanya dapat dilakukan apabila kontestan telah memegang
3.4 Algoritma Pencarian Langkah Terbaik
kotak uang.
a. Pemilihan Kotak Uang (Modus Selain Arena)
b. Pemilihan Kotak Uang (Modus Arena)
3.5 Rancangan Arena Permainan Jam dan tanggal sistem komputer
Modus Permainan Arahan permainan Sisa kotak yang harus dipilih
Ronde
99
Kumpulan kotak uang
99
Nama banker
Money tree (nilai kecil)
c. Penawaran Banker (Modus Selain Arena)
Penawaran sebelumnya 9.999.999.999 9.999.999.999 9.999.999.999 9.999.999.999 9.999.999.999 9.999.999.999 9.999.999.999
Tingkat
Gambar banker
Saya menawarkan kotak Anda dengan harga
Nama kontestan Kotak yang dipegang
Nilai penawaran ditentukan dengan persamaan Akhiri Permainan!
Bantuan?
Gambar 3.3 Rancangan Arena Permainan
dengan on adalah nilai penawaran (dibulatkan ke bilangan bulat terdekat), r adalah ronde berjalan, n adalah angka acak yang dipilih (0 hingga 5), Σm adalah jumlah nilai uang yang masih berada di money tree (nilai yang belum terpilih), dan b 5
Money tree (nilai besar)
Terima atau Tolak?
Nilai 99.999.999.999.999.999.999
(10 × 𝑟 + 𝑛)% × ∑𝑚 𝑜n = 𝑏
999
9.999.999.999
Gambar tumpukan uang
3.6 Rancangan Alur Proses
START
START
Start = False Pause = False Sisa Kotak = 26 Sisa Waktu = 60
Start = False Pause = False Sisa Kotak = 26 Ronde = 0 Sisa Kotak yang Terpilih = 1
Hitung mundur waktu
3 Pemilihan kotak uang
Ronde = 0
True
Pemilihan kotak uang
Start = True Ronde = 1 Sisa Kotak yang Terpilih = 3
False
Start = False Sisa Kotak yang Terpilih -= 1 Sisa Kotak -= 1
True
Start = True
False Sisa Kotak -= 1
False Sisa Kotak yang Terpilih = 0
False
True
Sisa Waktu = 0
Jeda permainan
True Jeda permainan Penawaran banker
Pause = True
1
Pause = True
Gambar 3.4 Alur Proses Modus Cerita, Satu Lawan Satu, Redenominasi, dan ???
Penawaran banker
1
Gambar 3.6 Alur Proses Modus Arena 1
START Tampilkan nilai penawaran
Mulai permainan dari tingkat tersimpan Start = False Pause = False Sisa Kotak = 26 Ronde = 0 Sisa Kotak yang Terpilih = 1
5 3
Akhir permainan
True
False
Terima Atau Tolak?
Terima
Letakkan kotak uang kontestan di sebelah kanan
Tolak
Tampilkan nilai kumulatif, tingkat, dan ronde terakhir selama permainan
Periksa ronde dan modus berjalan
2
Pemilihan kotak uang Ronde = 8 OR Modus = Arena
Start = True True Ronde = 0 Ronde = 1 Sisa Kotak yang Terpilih = 3 False
Lanjutkan atau akhiri permainan
False
Pause = False Ronde += 1
True Letakkan kotak uang kontestan di sebelah kiri
Sisa Kotak yang Terpilih -= 1 Sisa Kotak -= 1
4
False
Sisa Kotak yang Terpilih = 0 True Jeda permainan
Gambar 3.7 Alur Proses Penawaran Pause = True
Penawaran banker
1
Gambar 3.5 Alur Proses Modus Pesta
6
3
4
Buka kotak uang kontestan
4.
Hasil dan Pembahasan
4.1 Tampilan Arena Permainan
Bandingkan dengan nilai penawaran banker
Nilai uang dalam kotak > Penawaran banker
True
Periksa letak kotak uang
Letak kotak uang
Kanan
Status = Banker menang
Kiri False Status = Kontestan menang
A
Lanjutkan pembandingan nilai
Nilai uang dalam kotak < Penawaran banker
True
Periksa letak kotak uang
Letak kotak uang
Kanan
Status = Kontestan menang
Kiri False Status = Banker menang
Status = Seri
A
Modus = Pesta
True
Tingkat +=1
Gambar 4.1 Ronde 0
5
False 2
END
4.2 Hasil Uji Coba
Gambar 3.8 Alur Proses Akhir Permainan
Tabel 4.1 Perbandingan Peluang Kemenangan Banker Pada Modus Cerita dan Redenominasi
3.7 Tabel Peluang Kemenangan (TPK)
Percobaan
Secara teoritis, peluang kemenangan dalam
I II III IV V VI VII VIII IX
permainan adalah 50% (dengan mengabaikan hasil seri). Akan tetapi, pada kenyataannya, nilai ini tidak eksak. Untuk itu, penulis menggunakan Tabel Peluang Kemenangan (TPK) sebagai alat bantu penghitungan peluang kemenangan.
Peluang Kemenangan (%) Cerita Redenominasi 58,67834584 65,70170558 51,08753086 60,78497802 61,45700177 52,56498647 57,68437019 52,00559671 64,24566823 57,85534925 55,20079771 57,82502131 52,34867860 50,09874964 50,43478261 48,26086957 47,10144928 42,75362319
Gambar 4.2 Grafik Perbandingan Peluang Kemenangan Banker Pada Modus Cerita dan Redenominasi
Terlihat pada tabel dan grafik tersebut bahwa Gambar 3.9 Tabel Peluang Kemenangan
modus Cerita cenderung lebih unggul daripada modus Redenominasi, sehingga dapat dikatakan
Nilai peluang kemenangan pemain (pada penelitian
bahwa modus Redenominasi cocok untuk pemain
ini, penulis memilih banker yang merupakan AI
pemula yang baru berlatih. Apabila pemain tersebut
dalam permainan), wB, dapat dihitung menggunakan
menginginkan tantangan yang lebih besar, modus
rumus berikut.
lainnya dapat menjadi pilihan (dalam hal ini, modus
𝑤B =
Jumlah huruf B pada TPK × 100% 6×𝑏
Cerita).
7
4.3 Kelebihan dan Kekurangan Program
5.2 Saran
a.
a.
Kelebihan 1) Alur permainan tidak terlalu rumit dan
dijalankan lintas platform sehingga dapat
mudah untuk dipahami.
dibandingkan strategi AI pada masing-masing
2) Memiliki sistem penilaian yang membuat
platform yang berbeda.
pemain merasa tertantang.
b.
Membuat aplikasi permainan yang dapat
b.
Mempersempit
pencarian
nilai
peluang
3) Tampilan cukup menarik.
kemenangan dengan TPK yang di-prunning,
4) Digemari seluruh kalangan dan usia.
yaitu pencarian nilai peluang kemenangan yang
Kekurangan
dilakukan
1) Dibutuhkan waktu yang lama untuk
ditampilkan sehingga dalam TPK, hanya
menyelesaikan permainan.
tepat
ketika
nilai
penawaran
terdapat satu kolom saja.
2) Walaupun menarik, tampilan permainan
c.
masih perlu perbaikan.
Mengubah rumusan penawaran banker dan membandingkan nilai peluang kemenangan sebelum dan setelah pengubahan.
5.
Kesimpulan dan Saran
5.1 Kesimpulan a.
Metode
Daftar Pustaka
probabilistic
diterapkan
untuk
reasoning
menetapkan
dapat
[1]
Sutojo, T. dkk. 2011. Kecerdasan Buatan. Yogyakarta: Penerbit ANDI.
[2]
Kusumadewi, Sri. 2003. Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha Ilmu.
[3]
Nilson J., N. 1998. Artificial Intelligence: A New Synthesis. USA: Morgan Kaufmann Publisher.
[4]
Sigiro, Irma Y.N. 2011. Analisis dan Implementasi Penyelesaian Game Minesweeper Menggunakan Algoritma Greedy Best First Search [Skripsi]. Medan: Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara.
[5]
George J.F. et al. 2004. Object-Oriented System Analysis and Design: International Edition. USA: Pearson Education.
[6]
Wikipedia Indonesia. 2013. “Visual Basic .NET” http://id.wikipedia.org/wiki/Visual_Basic_.NET, diakses tanggal 13 November 2013.
[7]
Arbie. 2004. Manajemen Database Dengan MySQL. Yogyakarta: Penerbit ANDI.
peluang
kemenangan dengan cara memetakan tiap-tiap keadaan permainan dan kemudian menghitung nilai peluang kemenangan dengan algoritma tertentu. b.
Nilai peluang kemenangan teoritis untuk permainan ini adalah sama untuk setiap modus yang dipilih, yaitu 50%. Nilai ini didapat apabila hasil seri diabaikan.
c.
Nilai
peluang
kemenangan
sebenarnya
bergantung dari kombinasi nilai uang yang dapat diperoleh dan juga penawaran dari banker. d.
Nilai peluang kemenangan standar untuk penawaran
yang
diterima
adalah
40%.
Sedangkan nilai peluang kemenangan standar untuk penawaran yang ditolak adalah 60%. e.
Strategi AI dikatakan
dalam permainan ini dapat baik
apabila
nilai
peluang
kemenangannya berada di atas nilai standar.
8
