PENGANTAR TEKNOLOGI SISTEM CERDAS
DISUSUN OLEH
SYIFA ALYA NABILA
16115777
3KA12
UNIVERSITAS GUNADARMA
Game Theory atau Teori Permainan adalah suatu pendekatan matematis untuk merumuskan situasi persaingan dan konflik antara berbagai persaingan. Teori ini digunakan untuk menganalisa proses pengambilan keputusan dari situasi persaingan yang berbeda dan melibatkan dua atau lebih pesaing. Intinya, dari teori ini kita berbicara tentang bagaimana stategi dan taktik untuk memenangkan “game” persaingan ekonomi. Seperti game pada umumnya, setiap pesaing disini disebut pemain atau player. Setiap player mempunyai kepentingan-kepentingan untuk bersaing dalam permintaan. Anggapan yang digunakan adalah setiap pemain mempunyai kemampuan untuk mengambil keputusan secara bebas dan rasional. Setiap pelaku ekonomi terutama produsen atau agen pastinya saling bersaing untuk mewujudkan kepentingan-kepentingannya. Setiap pemain akan menggunakan berbagai strategi agar mendapatkan keuntungan yang optimal dan jika harus mengalami kerugian maka bagaimana caranya agar kerugian itu paling kecil.
Awalnya, teori ini ditemukan oleh ahli matematika Prancis Emile Borel pada tahun 1921. Kemudian dikembangkan oleh John Von Neeman dan Oskar Morgenstern sebagai tolak ukur untuk merumuskan perilaku ekonomi yang bersaing. Teori permainan ini dapat diklasifikasikan dalam beberapa model, contohnya model teori permainan antara lain seperti:
· Jumlah pemain
· Jumlah keuntungan dan kerugian
· Jumlah strategi yang digunakan dalam permainan
Unsur-unsur Dasar Teori Game
1. 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.
2. 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.
3. Strategi 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.
4. Titik Pelana (Saddle Point)
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.
Penyelesaian masalah teori permainan :
Untuk menyelesaikan masalah dalam teori permainan, dapat menggunakan karakteristik strategi murni dan strategi campuran.
1. Strategi Murni (Pure Strategy Game)
Hasil yang optimal dari suatu permainan yang mempunyai saddle point dapat diperoleh dengan menggunakan pure strategy. Yang dimaksud dengan saddle point adalah semacam titik keseimbangan antara nilai permainan kedua pemain. Dalam pure strategy digunakan kriteria maksimim dan minimaks. Maksimin adalah nilai maksimum dari nilai-nilai minimum, dan minimaks adalah nilai minimum dari nilai-nilai maksimum.
Contoh kasus :
Dua perusahaan yang memiliki produk yang relatif sama bersaing mendapatkan keuntungan. Perusahaan A menggunakan dua strategi dan perusahaan B menggunakan tiga strategi.
Langkah-langkah penyelesaian dengan pure strategy :
Identifikasi perusahaan yang berperan sebagai pemain kolom dan baris. Dalam kasus diatas, perusahaan A sebagai pemain baris dan perusahaan B sebagai pemain kolom. Lalu pilih nilai terkecil untuk setiap baris. Baris pertama memiliki nilai terkecil “1” dan baris kedua nilai terkecilnya “4”. Kemudian dari kedua nilai tersebut pilih nilai yang paling baik atau terbesar yaitu “4”. Nilai “4” inilah yang disebut nilai maksimin.
Untuk pemain kolom (perusahaan B), pilih nilai yang paling besar untuk setiap kolom, sehingga diperoleh angka “8” untuk kolom pertama, angka “9” untuk kolom kedua, dan angka “4” untuk kolom ketiga. Dari ketiga angka tersebut pilih angka terendah atau minimum yaitu “4”. Nilai “4” inilah yang disebut nilai minimaks.
Dari kedua langkah diatas, didapat angka “4” sebagai nilai permainan (saddle point) sehingga tercipta strategi yang optimal.
Yang di maksud hasil optimal disini adalah dimana masing-masing pemain memilih nilai 4 yang mengandung arti bahwa pemain A meskipun menginginkan keuntungan yang lebih besar, namun A hanya akan mendapat keuntungan maksimal sebesar 4, bila ia menggunakan strategi harga mahal (S2). Sedangkan pemain B, meskipun menginginkan kerugian yang dideritanya adalah sekecil mungkin, namun kerugian yang paling baik bagi B adalah sebesar 4, dan itu bisa diperoleh dengan merespon strategi yang digunakan A dengan juga menerapkan strategi harga mahal (S3).
2. Strategi Campuran (Mixed Strategy Game)
Strategi ini dilakukan apabila strategi murni tidak mampu menyelesaikan memberikan pilihan strategi yang optimal bagi masing masing pemain atau perusahaan atau dengan kata lain kasus game theory tidak mempunyai saddle point. Dalam strategi ini seorang pemain atau perusahaan akan menggunakan campuran lebih dari satu strategi untuk mendapatkan hasil yang maksimal.
Dalam strategi campuran ini ada beberapa metode yang biasa digunakan yaitu :
· Metode Analistis
· Metode Grafik
· Pemrograman Linier
Algoritma Minimax
Minimax yang merupakan salah satu metode penerapan (implementasi) pohon n-ary pada suatu game, menandakan bahwa implementasi struktur (pohon khusunya) sangatlah diperlukan pada pembuatan dan penerapan Artificial Intelligence, dan tidak menutup kemungkinan ilmu dan metode baru yang lebih canggih akan ditemukan di masa depan.
Gambar 1.1
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. 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 .
Gambar 1.2
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. 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. 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 . 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.
Fungsi heuristik yang digunakan algoritma ini adalah fungsi heuristik statis . Fungsi heuristik digunakan untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Dari nilai-nilai heuristik inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristik yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer. Untuk proses dan cara kerja algoritma yang lebih jelasnya lagi, dapat dilihat pada Gambar 1.2 yang merepresentasikan cara kerja algoritma Minimax.Fungsi heuristik yang digunakan algoritma ini adalah fungsi heuristik statis. Fungsi heuristik digunakan untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Dari nilai-nilai heuristik inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristik yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Transpotition Table and Memory
1. Algoritma dapat menggunakan tabel transposisi untuk menghindari melakukan pekerjaan ekstra dalam mencari posisi board yang sama beberapa kali
2. Memori kerja posisi board sudah dikenal
3. 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.
4. 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 dari sebuah cabang yang dipangkas
· Nilai akurat atau nilai gagal-rendah (alpha pruned), atau nilai gagal-tinggi (beta pruned)
SUMBER:
Tidak ada komentar:
Posting Komentar