BOARD GAME
1.
Game Theory
Menururt Dimiyati (1992), teori permainan
(game theory) adalah bagian dari ilmu pengetahuan yang berkaitan dengan
pembuatan keputusan pada saat ada dua pihak atau lebih berada dalam kondisi
persaingan atau konflik. Pihak-pihak yang bersaing ini disumsikan bersifat
rasional dan cerdas, artinya masing-masing pihak akan melakukan strategi
tindakan yang rasional untuk memenangkan persaingan itu, dan masing-masing
pihak juga mengetahui strategi pihak lawannya. Selanjutnya pihak ini disebut
pemain.
Menurut Ayu
(1996), game theory merupakan suatu pendekatan matematis untuk merumuskan
situasi persaingan dan konflik antara berbagai kepentingan. Game theory
melibatkan dua atau lebih pengambil keputusan atau yang disebut pemain. Setiap
pemain dalam game theory mempunyai keinginan untuk menang. Tujuan teori ini
adalah menganalisa proses pengambilan keputusan dari persaingan yang
berbeda-beda dan melibatkan dua atau lebih pemain/kepentingan. Kegunaan dari
teori permainan adalah metodologi yang disediakan untuk menstruktur dan
menganalisa masalah pemilihan strategi. Menggunakan teori permainan, maka
langkah pertama adalah menentukan secara explicit pemain, strategi yang ada,
dan juga menentukan preferensi serta reaksi dari setiap pemain. Terdapat dua
jenis strategi permainan yang dapat digunakan pada game theory, yaitu pure
strategy (setiap pemain mempergunakan strategi tunggal) dan mixed strategy
(setiap pemain menggunakan campuran dari berbagai strategi yang berbeda-beda).
Pure strategy digunakan untuk jenis permainan
yang hasil optimalnya mempunyai saddle point (semacam titik keseimbangan antara
nilai permainan kedua pemain). Sedangkan mixed strategy digunakan untuk mencari
solusi optimal dari kasus game theory yang tidak mempunyai saddle point.
Unsur-Unsur dasar game theory:
·
Jumlah pemain
Permainan diklasifikasikan menurut jumlah kepentingan atau tujuan yang
ada dalam permainan tersebut. Dalam hal ini perlu dipahami, bahwa pengertian
“jumlah pemain” tidak selalu sama artinya dengan “jumlah Orang” yang terlibat
dalam permainan. jumlah pemain disini berarti jumlah kelompok pemain
berdasarkan masing-masing kepentingan atau tujuannya. Dengan demikian dua orang
atau lebih yang mempunyai kepentingan yang sama dapat diperhitungkan sebagai
satu kelompok pemain.
·
Ganjaran/pay off
Ganjaran / pay-off adalah hasil akhir yang terjadi pada akhir permainan
berkenaan dengan ganjaran ini, permainan digolongkan menjadi 2 macam kategori,
yaitu permainan jumlah-nol (zero-sum games) dan permainan jumlah-bukan-nol
(non-zero-sum games). permainan jumlah-nol terjadi jika jumlah ganjaran dari
seluruh pemain adalah nol, yaitu dengan memperhitungkan setiap keuntungan
sebagai bilangan positif dan setiap kerugian sebagai bilangan negatif. Selain dari
itu adalah permainan jumlah – bukan-nol. Dalam permainan jumlah-nol setiap
kemenangan bagi suatu pihak pemain merupakan kekalahan bagi pihak pemain lain.
letak arti penting dari perbedaan kedua kategori permainan berdasarkan ganjaran
ini adalah bahwa permainan jumlah-nol adalah suatu sistem yang tertutup.
Sedangkan permainan jumlah-bukan-nol tidak demikian halnya. Hampir semua
permainan pada dasarnya merupakan permainan jumlah-nol. Berbagai situasi dapat
dianalisis sebagai permainan jumlah-nol.
·
Strategi
permainan
Strategi permainan dalam teori permainan adalah suatu siasat atau rencana
tertentu dari seorang pemain, sebagai reaksi atas aksi yang mungkin dilakukan
oleh pemain yang menjadi saingannya. permainan diklasifikasikan menurut jumlah
strategi yang tersedia bagi masing-masing pemain. Jika pemain pertama memiliki
m kemungkinan strategi dan pemain kedua memiliki n kemungkinan strategi, maka
permainan tersebut dinamakan permainan m x n. letak arti penting dari perbedaan
jenis permainan berdasarkan jumlah strategi ini adalah bahwa permainan
dibedakan menjadi permainan berhingga dan permainan tak berhingga. Permainan
berhingga terjadi apabila jumlah terbesar dari strategi yang dimiliki oleh
setiap pemain berhingga atau tertentu, sedangkan permainan tak berhingga
terjadi jika setidak-tidaknya seorang pemain memiliki jumlah strategi yang tak
berhingga atau tidak tertentu.
·
Matriks
Permainan
Setiap permainan yang dianalisis dengan teori permainan selalu dapat
disajikan dalam bentuk sebuah matriks permainan. matriks permainan disebut juga
matriks ganjaran yaitu sebuah matriks yang semua unsur berupa ganjaran dari
para pemain yang terlibat dalam permainan tersebut. Baris-barisnya melambangkan
strategi –strategi yang dimiliki pemain pertama, sedangkan kolom-kolomnya
melambangkan strategi-strategi yang dimiliki pemain lain. dengan demikian,
permainan berstrategi mxn dilambangkan dengan matriks permainan m x n . Teori
permainan berasumsi bahwa strategi yang tersedia bagi masing-masing pemain
dapat dihitung dan ganjaran yang berkaitan dengannya dapat dinyatakan dalam
unit, meskipun tidak selalu harus dalam unit moneter. Hal ini penting bagi
penyelesaian permainan, yaitu untuk menentukan pilihan strategi yang akan
dijalankan oleh masing-masing pemain, dengan menganggap bahwa masing masing
pemain berusaha memaksimumkan keuntungannya yang minimum (maksimin) atau
meminimumkan kerugiannya yang maksimum (minimaks). Nilai dari suatu permainan
adalah ganjaran rata-rata / ganjaran yang diharapkan dari sepanjang rangkaian
permainan, dengan menganggap kedua pemain selalu berusaha memainkan strateginya
yang optimum. Secara konvensional, nilai permainan dilihat dari pihak pemain
yang strategistrateginya dilambangkan oleh baris-baris matriks ganjaran, dengan
kata lain dilihat dari sudut pandang pemain tertentu. pemain dikatakan adil
(fair) apabila nilainya nol, dimana takseorang pemain pun yang memperoleh
keuntungan atau kemenangan dalam permainan yang tidak adil (unfair) seorang
pemain akan memperoleh kemenangan atas pemain lain, yaitu jika nilai permainan
tersebut bukan nol, dalam hal ini nilai pemain adalah positif jika pemain
pertam (pemain baris) memperoleh kemenangan, sebaliknya nilai permainan negatif
jika pemain lain (pemain kolom) memperoleh kemenangan.
·
Titik pelana
Titik pelana adalah suatu unsur didalam matriks permainan yang sekaligus
sebagai maksimin baris dan minimaks kolom. permainan dikatakan bersaing ketat
(Strictly determined) jika matriksnya memiliki titik pelana. Strategi yang
optimum bagi masing-masing pemain adalah strategi pada baris dan kolom yang
mengandung titik pelana tersebut. dalam hal ini baris yang mengandung titik
pelana merupakan strategi optimum bagi pemain pertama, sedangkan kolom yang
mengandung titik pelana merupakan strategi optimum bagi pemain lain. Langkah
pertama penyelesaian sebuah matriks permainan adalah memeriksa ada atau
tidaknya titik pelana. Bila terdapat titik pelana permainan dapat segera
dianalisis untuk diselesaikan. Untuk menentukan titik pelana biasanya dilakukan
dengan menuliskan nilai-nilai minimum dan Maksimum masing-masing kolom,
kemudian menentukan maksimun diantara minimum baris dan minimum diantara
maksimum kolom. jika unsur maksimum dari minimum baris sama dengan unsur
minimum dari maksimum kolom, atau jika maksimin = minimaks, berarti unsur
tersebut merupakan titik pelana. Teori permainan dapat diterapkan dalam
berbagai bidang, meliputi kemiliteran, bisnis, social, ekonomi dan ekologi.
Sebagai contoh pada dunia bisnis, seorang direktur suatu perusahaan didalam
memperkenalkan sebuah produk baru berusaha mengetahui kemungkinan strategi
paling baik atau suatu kombinasi strategi untuk merebut market share yang lebih
besar, sementara saingannya juga mencoba meperkenalkan produk sejenis dengan
strategi yang berbeda dengan direktur pemasaran tersebut, antara lain:
penurunan harga, pemberian hadiah, peningkatan mutu produk, memilih media
advertasi yang efektif. Disinilah peranan teori permainan untuk menentukan
strategi mana yang akan diputuskan oleh dirktur pemasaran tersebut untuk
merebut pasar.
2.
Algoritma Minimaxing
Algoritma
minimax merupakan basis dari semua permainan berbasis AI seperti permainan
catur misalnya. AI permainan catur tentunya sudah sangat terkenal dimana AI
tersebut bahkan dapat mengalahkan juara dunia sekalipun. Pada algoritma
minimax, pengecekan akan seluruh kemungkinan yang ada sampai akhir permainan
dilakukan. Pengecekan tersebut akan menghasilkan pohon permainan yang berisi
semua kemungkinan tersebut. Tentunya dibutuhkan resource yang berskala besar
untuk menangani komputasi pencarian pohon solusi tersebut berhubung kombinasi
kemungkinan untuk sebuah permainan catur pada setiap geraknya sangat banyak
sekali. Keuntungan yang didapat dengan menggunakan algoritma minimax yaitu
algoritma minimax mampu menganalisis segala kemungkinan posisi permainan untuk
menghasilkan keputusan yang terbaik karena algoritma minimax ini bekerja secara
rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian
minimum. Semua strategi lawan akan dihitung dengan algoritma yang sama dan
seterusnya. Ini berarti, pada langkah pertama komputer akan menganalisis
seluruh pohon permainan. Dan untuk setiap langkahnya, komputer akan memilih
langkah yang paling membuat lawan mendapatkan keuntungan minimum, dan yang
paling membuat komputer itu sendiri mendapatkan keuntungan maksimum. Dalam
penentuan keputusan tersebut dibutuhkan suatu nilai yang merepresentasikan
kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih.
Untuk itulah disini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai
sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika
langkah tersebut dipilih. Biasanya pada permainan tic tac toe ini digunakan
nilai 1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang, seri, dan
kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana
dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih
tersebut adalah simpul dengan nilai heuristic yang akan menuntun permainan ke
hasil akhir yang menguntungkan bagi komputer.
Algoritma minimax merupakan algoritma
yang diterapkan dalam game yang melibatkan dua pemain yang saling bergantian,
seperti tic-tac-toe, chess, go, othello dan game yang menggunakan strategi atau
logika lainnya (Wijaya, 2010). Persamaan antara semua game tersebut yaitu semua
merupakan game logika dan game dengan informasi yang lengkap. Ini berarti bahwa
game merupakan sekumpulan aturan main dan dasar pemikiran yang logis. Adanya
aturan main dan dasar pemikiran yang logis tersebut, maka nantinya setiap
pemain dapat mengetahui semua langkah yang mungkin dari pemain lawannya,
sehingga pemain bisa tetap “memantau” kondisi permainan sewaktu game sedang
berlangsung (Akbar, 2011).
Algoritma minimax merupakan salah satu algoritma yang sering digunakan
untuk game kecerdasan buatan yang menggunakan teknik depth first search (DFS)
dalam pencariannya pada pohon dengan kedalaman terbatas (Kusumadewi, 2003).
Algoritma minimax digunakan untuk memilih langkah terbaik, dimana kedua pemain
akan saling berusaha untuk memenangkan
permainan. Selain itu, algoritma minimax ini bekerja secara rekursif dengan
mencari langkah yang akan membuat lawan mengalami kerugian minimum. Algoritma
minimax mendeskripsikan kondisi apabila terdapat pemain yang mengalami
keuntungan, pemain lain akan mengalami kerugian senilai dengan keuntungan yang
diperoleh lawan dan sebaliknya.
Algoritma minimax akan melakukan
pengecekan pada seluruh kemungkinan yang ada, sehingga akan menghasilkan pohon
permainan yang berisi semua kemungkinan permainan tersebut (Jannah, 2010).
Dengan pohon permainan ini setiap pemain mengetahui langkah-langkah yang
mungkin diberikan pada situasi permainan saat ini. Sehingga untuk setiap langkah
dan semua langkah selanjutnya dapat diketahui. Dalam repersentasi pohon pada
algoritma minimax, terdapat dua jenis simpul, yaitu simpul min dan simpul max.
Max akan memilih langkah dengan nilai tertinggi dan min akan memilih langkah
dengan nilai terendah (Kusumadewi, 2003). Dalam penentuan keputusan max/min
tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan
yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini
digunakan sebuah fungsi heuristik.
3.
Table Transposition and Memory
Algoritma dapat menggunakan tabel
transposisi untuk menghindari melakukan pekerjaanekstra dalam mencari posisi
board yang sama beberapa kali
·
Memori kerja posisi board sudah dikenal
·
Menggunakan fungsi hash khusus desiderata: sebarkan
posisi-posisi yang mirip seluas mungkin melalui kisaran nilai hash nilai hash
yang banyak berubah saat berpindah dari papan bergerak mengalami perubahan yang
sangat sedikit.
·
Kunci
zobrist adalah sekumpulan bit acak dari fixed-length pola yang tersimpan untuk
setiap kemungkinan keadaan dari setiap lokasi yang mungkin ada pada board.
Contoh: Catur memiliki 64 kotak, dan masing-masing persegi bisa kosong atau ada
1 dari 6 potongan berbeda di atasnya, masing-masing dua warna mungkin.Zobrist
kunci harus seperti berikut : 64 2 (6 + 1) = 832 bit-string yang berbeda.
·
Kunci
Zobrist perlu diinisialisasi dengan bit-string acak dengan ukuran yang sesuai.
·
Untuk setiap kotak yang tidak kosong, tombol
Zobrist adalah mendongak dan XORed dengan jumlah hash yang berjalan.
·
Zobrist
Key dapat diperbarui secara bertahap
Apa yang harus disimpan?
·
Tabel hash menyimpan nilai yang terkait dengan
posisi board • Gerakan terbaik dari posisi masing-masing board.
·
Kedalaman digunakan untuk menghitung nilai
·
Nilai yang akurat, atau kita dapat juga
menyimpan nilai "fail-soft" yang dihasilkan darisebuah cabang yang
dipangkas
·
Nilai
akurat atau nilai gagal-rendah (alpha pruned), atau nilai gagal-tinggi (beta
pruned)
4.
Optimisasi Optimisasi
merupakan suatu upaya sistematis untuk memilih
elemen terbaik dari suatu kumpulan elemen yang ada. Didalam kontek matematika,
optimisasi ini bisa diyatakan sebagai suatu usaha sistematis untuk mencari
nilai minimum atau maksimum dari suatu fungsi. Dengan kata lain, optimisasi
merupakan proses mencari nilai terbaik berdasarkan fungsi tujuan dengan daerah
asal yang telah didefinisikan. Fungsi ini secara sederhana dapat dinyatakan
dengan: min/max f(x) sebagai contoh adalah fungsi kuadrat f(x) = x2 dimana x
anggota bilangan real ( x Є R). di dalam contoh ini, f(x) = x2 merupakan fungsi
tujuannya, sedangkan x adalah daerah asal yang di definisikan sebagai anggota
bilangan real. Konsep optimisasi sudah dipakai sejak jaman prasejarah. Hal ini
dapat dibuktikan dengan adanya saluran-saluran air yang ditemukan di
situs-situs presejarah. Saluran-saluran air ini dipakai untuk mengoptimalkan
penggunaan air. Hal ini mengindikasikan bahwa konsep optimisasi merupakan
bagian dari kehidupan manusia sejak lama. Permasalahan pengaturan air masih
dijumpai dalam masyarakat masa kini, hanya saja penyelesaiannya sudah
menggunakan metode optimisasi yang modern. Meskipun konsep optimisasi sudah
sangat lama digunakan, tetapi metode optimisasi pertama, yang mengacu pada
teknik yang terstruktur, yang diakui adalah steepest descent. Istilah
optimisasi diperkenalkan oleh George Dantzig yang mengembangkan algoritma
simplex untuk menyelesaikan masalah linear programming. Istilah programming
disini tidak mengacu pade pemrograman komputer, tetapi lebih pada program
pelatihan dan penjadwalan logistik yang diadakan oleh pihak militer Amerika
dimana masalah-masalah tersebut menjadi focus riset yang dilakukan oleh
Dantzig. Linear programming sendiri merupakan metode untuk menyelesaikan fungsi
linear, baik fungsi tujuan maupun fungsi batasannya (constraint). Dalam
perkembangan selanjutnya, optimisasi sangat berkaitan dengan perkembangan
komputer karena proses optimisasi ini umumnya dijalankan di komputer. Di
awal-awal perkembangannya, penelitian optimisasi hanya dilakukan secara itensif
untuk menyelesaikan permasalahan-permasalahan penting dibidang militer yang
melibatkan teknologi tinggi. Tetapi ketika harga komputer semakin terjangkau,
penelitian di bidang optimasi berkembang sangat pesat. Dalam dua decade
terakhir, banyak sekali metode optimisasi baru yang lahir. Optimisasi dipakai
di hampir semua bidang ilmu antara lain bidang teknik, sains, ilmu social,
ekonomi dan bisnis. Banyak permasalahan di bidang teknik, sains dan ekonomi
yang dapat dinyatakan sebagai permasalahan optimisasi seperti meminimalkan
biaya, waktu dan resiko atau memaksimalkan keuntungan dan kualitas. Optimisasi
seringkali menjadi focus utama dalam pengambilan keputusan misalnya untuk
meningkatkan daya saing suatu produk, maka perusahaan harus bisa memaksimalkan kualitas
dari produk tersebut dengan meminimalkan
biaya produksi. Pengambilan keputusan terdiri dari beberapa langkah (Talbi,
2009):