Pengantar Komputasi Modern

KOMPUTASI GRID

REDUCE MAP & NO SQL

QUANTUM GATES

dan

DISTRIBUTED COMPUTATION

dalam

CLOUD COMPUTING

Pengantar Komputasi Modern

Disusun oleh:

Putri Nurhasanah Dewi          (58414617)

Rahmat Tri Laksono               (58414812)

Reyka Firdhaulisia J               (59414130)

Yulianti Lestari                       (5C414553)

Dosen : Lely Prananingrum, Skom, MMSI

FAKULTAS TEKNOLOGI INDUSTRI

JURUSAN TEKNIK INFORMATIKA

UNIVERSITAS GUNADARMA

2018

DISTRIBUTED COMPUTATION

DALAM

CLOUD COMPUTING

Merupakan kumpulan beberapa komputer yang terhubung untuk melakukan pendistribusian, seperti mengirim dan menerima data serta melakukan interaksi lain antar komputer yang dimana membutuhkan sebuah jaringan agar komputer satu dan lainnya bisa saling terhubung dan melakukan interaksi. Hal ini semua dilakukan dengan cloud computing yang seperti diketahui memberikan layanan dimana informasinya disimpan di server secara permanen dan disimpan di komputer secara temporary.

Komputasi terdistribusi merupakan salah satu tujuan dari cloud computing, karena menawarkan pengaksesan sumber daya secara paralel, para pengguna juga bisa memanfaatkannya secara bersamaan (tidak harus menunggu dalam antrian untuk mendapatkan pelayanan), terdiri dari banyak sistem sehingga jika salah satu sistem rusak, sistem lain tidak akan terpengaruh, dapat menghemat biaya operasional karena tidak membutuhkan sumber daya.

Cloud computing mempunyai tiga tingkat layanan, yaitu:

1.      Infrastructure as a service: meliputi grid untuk virtualized, storage & network.

2.      Platform as a service: memfokuskan pada aplikasi dimana seorang developer tidak perlu memikirkan hardware dan tetap fokus pada pembuatan aplikasi tanpa harus mengkhawatirkan sistem operasi, infrastructure scaling, load balancing dan lain-lain.

3.      Software as a service: memfokuskan pada aplikasi dengan Web-based interface yang diakses melalui Web Service dan Web 2.0.

Kelebihan cloud computing yaitu:

1.      Menghemat biaya investasi awal untuk pembelian sumber daya.

2.      Menghemat waktu sehingga perusahaan bisa langsung fokus ke profit dan berkembang dengan cepat.

3.      Membuat operasional dan manajemen lebih mudah karena sistem pribadi maupun perusahaan yang tersambung dalam satu cloud dapat dimonitor dan diatur dengan mudah.

4.      Menjadikan kolaborasi yang terpercaya dan lebih ramping.

5.      Menghemat biaya operasional pada saat realibilitas ingin ditingkatkan dan kritikal sistem informasi yang dibangun.

Kekurangan cloud computing yaitu:

1.      Tidak dapat dilakukan jika tidak terhubung ke internet.

2.      Apabila koneksi internet yang lambat, maka cloud computing tidak lagi optimal untuk digunakan.

3.      Fitur yang ditawarkan tidak selengkap aplikasi desktop.

4.      Data yang disimpan dalam cloud secara umum tidaklah aman karena diperbanyak di beberapa mesin.

5.      Satu pusat serangan. Penempatan semua server dalam satu komputer akan menjadikannya sebagai target serangan.

MAP REDUCE DAN NO SQL

Map Reduce adalah model pemrograman rilisan Google yang ditujukan untuk memproses data berukuran raksasa secara terdistribusi dan paralel dalam cluster yang terdiri atas ribuan komputer. Dalam memproses data, secara garis besar Map Reduce dapat dibagi dalam dua proses yaitu proses Map dan proses Reduce. Kedua jenis proses ini didistribusikan atau dibagi-bagikan ke setiap komputer dalam suatu cluster (kelompok komputer yang saling terhubung) dan berjalan secara paralel tanpa saling bergantung satu dengan yang lainnya.

Berikut ini ilustrasi untuk mendapatkan gambaran tentang proses map dan reduce.

Tahapan Proses Map Reduce

Map reduce terdiri atas tiga tahap, yaitu tahap map, tahap shuffle dan terakhir tahap reduce. Untuk tahapan shuffle dan reduce digabungkan ke dalam satu tahap besarannya yaitu tahap reduce.

1.      Tahap map, memproses data inputan yang umumnya berupa file yang tersimpan dalam HDFS. Inputan tersebut kemudian diubah menjadi tuple yaitu pasangan antara key dan value-nya.

2.      Tahap reduce, memproses data inputan dari hasil proses map, yang kemudian dilakukan tahap shuffle dan reduce yang hasil data set baru-nya disimpan di HDFS kembali.

Nosql

Nosql adalah sebuah memcache dari bagian database sederhana yang berisi key dan value. Database ini bersifat struktur storage dimana sistem databasenya yang berbeda dengan sistem database relasional. Nosql tidak membutuhkan skema table dan menghindari operasi join dan berkembang secara horizontal.

Quantum Gates

Quantum Gates adalah sebuah gerbang kuantum yang dimana berfungsi mengoperasikan bit yang terdiri dari 0 dan 1 menjadi qubits. dengan demikian Quantum gates mempercepat banyaknya perhitungan bit pada waktu bersamaan.

Quantum Gates / Gerbang Quantum merupakan sebuah aturan logika / gerbang logika yang berlaku pada quantum computing. Prinsip kerja dari quantum gates hampir sama dengan gerbang logika pada komputer digital. Jika pada komputer digital terdapat beberapa operasi logika seperti AND, OR, NOT, pada quantum computing gerbang quantum terdiri dari beberapa bilangan qubits, sehingga quantum gates lebih susah untuk dihitung daripada gerang logika pada komputer digital.

Untuk memanipulasi sebuah qubit, maka menggunakan Quantum Gates (Gerbang Kuantum). Cara kerjanya yaitu sebuah gerbang kuantum bekerja mirip dengan gerbang logika klasik. Gerbang logika klasik mengambil bit sebagai input, mengevaluasi dan memproses input dan menghasilkan bit baru sebagai output.

Quantum gerbang logika yang diwakili oleh matriks kesatuan. Gerbang kuantum yang paling umum beroperasi pada ruang satu atau dua qubit, seperti biasa klasik gerbang logika beroperasi pada satu atau dua bit. Ini berarti bahwa sebagai matriks, gerbang kuantum dapat dijelaskan oleh 2 × 2 atau 4 × 4 matriks kesatuan.

Komputasi Grid

Komputasi Grid merupakan cabang dari pendistribusian komputer yang terpisah baik secara lokal maupun secara geografis untuk melakukan suatu proses komputasi dalam skala besar. Komputasi grid disimulasikan dengan menggabungkan banyak komputer yang diimplementasikan menggunakan jaringan sebagai media transportasi data yang diolah.

Beberapa konsep dasar dari grid computing :

1. Sumber daya dikelola dan dikendalikan secara lokal.
2. Sumber daya berbeda dapat mempunyai kebijakan dan mekanisme berbeda, mencakup Sumber daya komputasi dikelola oleh sistem batch berbeda, Sistem storage berbeda pada node berbeda, Kebijakan berbeda dipercayakan kepada user yang sama pada sumber daya berbeda pada Grid.
3. Sifat alami dinamis: Sumber daya dan pengguna dapat sering berubah
4. Lingkungan kolaboratif bagi e-community (komunitas elektronik, di internet)
5. Tiga hal yang di-sharing dalam sebuah sistem grid, antara lain : Resource, Network dan Proses. Kegunaan / layanan dari sistem grid sendiri adalah untuk melakukan high throughput computing dibidang penelitian, ataupun proses komputasi lain yang memerlukan banyak resource komputer.

Elemen grid computing adalah berikut :

1. Hardware

Berupa media penyimpanan, server, dan perangkat keras lainnya.

2. Software

Berupa sistem operasi, layanan informasi, pengaturan data, aplikasi dan lain-lain.

3. Brainware

Adalah pengguna dan pemelihara software dan hardware yang digunakan.

Perbedaan grid dengan cloud computing adalah komputasi grid dilakukan dengan cara men-sharing perosoalan yang ada dan dikerjakan bersama-sama dan dibagikan kembali secara merata. Sedangkan untuk komputasi cloud dilakukan secara langsung seperti tatap muka dimana setiap persoalan dilakukan oleh perseorangan yang jika sudah selesai satu persoalan, yang lain baru dapat meneruskan perosoalan yang baru sebagian selesai.

Cloud yang secara harfiah adalah awan, namun dalam ilmu komputer diartikan sebagai suatu server yang dikhususkan dan memiliki lalu lintas yang dianggap sedikit sehingga dapat mempermudah saat proses unggah persoalan yang dikerjakan.

Sumber

https://id.wikipedia.org/wiki/Komputasi_terdistribusi

https://azizazkink.wordpress.com/2014/05/09/distributed-computation-dalam-cloud-computing/

http://putrifebiani.blogspot.co.id/2014/05/distributed-computation-dalam-cloud.html

http://ridwanraa.blogspot.co.id/2015/10/distributed-computation-dalam-cloud.html

http://noviardisyamsuir.blogspot.co.id/2016/03/hadoop-mapreduce-adalah.html

http://putrifebiani.blogspot.co.id/2014/05/map-reduce-dan-nosql.html

https://www.quantiki.org/wiki/quantum-gates

http://timothyayoseph.blogspot.co.id/2016/05/quantum-gates.html

http://wikepedia.com

http://nasyasora.blogspot.com/

https://madluke.wordpress.com/2011/04/15/grid-computing/

http://stackoverflow.com/questions/1067987/what-is-the-difference-between-cloud-computing-and-grid-computing

Penulisan Teknik Solusi Statis

Penulisan

Pengertian dari :

Teknik Solusi Statis dan Dominasi lemah

Nash Equilibrium

Strategi Campuran Nash Equilibrium

Teknik Solusi untuk Memecahkan Game Statis.

Solusi untuk permainan adalah prediksi tentang apa yang akan dilakukan oleh setiap pemain dalam permainan itu. Ini mungkin merupakan prediksi yang sangat tepat, di mana solusi memberikan satu strategi optimal untuk setiap pemain. Ketika ini terjadi, solusinya dikatakan unik. Namun, sering terjadi bahwa solusi untuk permainan tertentu kurang tepat, bahkan sejauh tidak ada strategi yang tersedia yang dikesampingkan. Seperti yang diharapkan banyak teknik solusi yang berbeda telah diusulkan untuk berbagai jenis permainan.

Untuk permainan statis, dua teknik solusi yang luas telah diterapkan. Set pertama teknik solusi mengandalkan konsep dominasi. Di sini solusi untuk permainan ditentukan dengan mencoba untuk mengesampingkan strategi orang yang rasional tidak akan pernah dimainkan. Argumen berdasarkan dominasi berusaha untuk menjawab pertanyaan "Strategi apa yang akan pemain rasional tidak pernah dimainkan?" Set kedua teknik solusi didasarkan pada konsep kesetimbangan. Dalam permainan non-kooperatif keseimbangan terjadi ketika tidak ada pemain, bertindak secara individual, memiliki insentif untuk menyimpang dari solusi yang diprediksi. Dengan teknik solusi ini, sebuah permainan diselesaikan dengan menjawab pertanyaan “Properti apa yang perlu agar menjadi solusi keseimbangan?”.

Pada bagian berikut ini kita memeriksa berbagai teknik dominan yang dapat diterapkan untuk permainan statis, dan dua konsep kesetimbangan.

a.      Dominasi Ketat

Sebuah strategi dikatakan didominasi secara ketat jika strategi lain selalu memberikan imbalan yang lebih baik apa pun yang dilakukan pemain lain dalam permainan. Teknik solusi ini membuat asumsi yang masuk akal bahwa seorang pemain rasional tidak akan pernah memainkan strategi yang benar-benar didominasi. Jika seorang pemain dengan sengaja memainkan strategi yang sangat didominasi, mereka tidak dapat memaksimalkan imbalan yang mereka harapkan, mengingat keyakinan mereka tentang apa yang akan dilakukan pemain lain.

Dalam pengertian ini seorang pemain yang memainkan strategi yang sangat didominasi dikatakan irasional. Menerapkan prinsip aturan dominasi ketat dari jenis perilaku irasional ini. Untuk mengilustrasikan teknik ini, kita menggunakannya untuk memecahkan permainan dilema tahanan. Dalam menerapkan prinsip dominasi yang ketat, kita memeriksa setiap pemain secara bergantian dan mengecualikan semua strategi yang benar-benar didominasi. Proses ini mungkin mengesampingkan semua kecuali satu strategi untuk setiap pemain. Ini berlaku untuk game dilema tahanan, dan teknik ini menghasilkan solusi unik untuk game ini.

Pertimbangkan pertama dilema yang dihadapi tahanan 1. Haruskah dia mengaku atau haruskah dia tetap diam berharap tahanan lain melakukan hal yang sama. Prinsip dominasi ketat berpendapat bahwa tahanan 1 harus mengaku. Alasannya adalah bahwa tahanan apa pun yang memutuskan untuk melakukan tahanan 1 selalu lebih baik mengaku. Ini berarti tidak mengaku benar-benar didominasi dan tampaknya masuk akal untuk menganggapnya tidak akan dimainkan. Logika yang sama berlaku sama untuk narapidana 2 dan dominasi yang begitu ketat meramalkan bahwa ia juga akan mengaku. Solusi untuk permainan ini berdasarkan dominasi ketat adalah bahwa kedua tahanan mengaku meskipun keduanya akan lebih baik jika tidak mengaku. Setidaknya salah satu pemain dalam permainan ini dapat, dengan hasil yang berbeda, dibuat lebih baik tanpa pemain lain yang dibuat lebih buruk dari solusi ini dikatakan tidak efisien Pareto. (Kenyataannya jika kedua pemain tidak mengakui keduanya akan lebih baik.) Ini adalah fitur yang sangat umum dari banyak permainan yang digunakan dalam ekonomi, dan itu akan diilustrasikan dalam banyak konteks di seluruh buku ini.

Perlu dicatat di sini bahwa penyebab inefisiensi Pareto bukanlah bahwa para pemain tidak dapat berkomunikasi, melainkan bahwa mereka tidak dapat berkomitmen pada hasil yang efisien Pareto. Bahkan jika kedua narapidana itu setuju sebelum ditangkap, tak satu pun dari mereka akan mengaku, setelah ditahan, adalah demi kepentingan pribadi mereka untuk melakukan yang sebaliknya. Ini menggambarkan perbedaan antara teori permainan non-kooperatif dan kooperatif. Dalam teori permainan kooperatif, kedua narapidana bisa masuk ke dalam perjanjian yang mengikat dan dapat dilaksanakan untuk tidak mengaku dan menjadi lebih baik. Ini tidak mungkin dalam teori permainan non-kooperatif.

b.      Dominasi Lemah

Suatu strategi dikatakan didominasi secara lemah jika strategi lain membuat orang itu lebih baik dalam beberapa situasi dan membuat mereka tidak peduli pada yang lain. Sekali lagi, tampaknya masuk akal untuk mengasumsikan bahwa seorang pemain rasional tidak akan memainkan strategi yang didominasi lemah, karena mereka bisa melakukan setidaknya juga, dan mungkin bahkan lebih baik, dengan memainkan strategi dominan. Pertimbangkan permainan bentuk normal yang ditunjukkan pada Gambar 2.3.

Dalam game ini ada dua pemain masing-masing dengan dua kemungkinan strategi. Pemain 1 dapat bergerak "naik" atau "turun", dan pemain 2 dapat bergerak "kiri" atau "kanan". Imbalan diberikan dalam matriks, di mana angka pertama adalah bayaran untuk pemain 1 dan angka kedua adalah hasil untuk pemain 2. Untuk permainan ini tidak ada strategi yang tersedia dikesampingkan menggunakan prinsip dominasi ketat. Ini karena tidak ada strategi yang membuat pemain itu semakin buruk dalam semua keadaan. Sebagai contoh, jika pemain 1 memainkan "naik" maka pemain 2 adalah acuh tak acuh antara "kiri" dan "kanan". Demikian pula jika pemain 2 memainkan "kiri" pemain 1 adalah acuh tak acuh antara "atas" dan "bawah".

Meskipun kita tidak dapat mengajukan banding kepada prinsip dominasi ketat untuk mengesampingkan salah satu strategi yang tersedia, kita dapat menerapkan prinsip dominasi yang lemah.

Gambar 2.3 Penerapan dari Dominasi Lemah

Menurut prinsip dominasi pemain yang lemah 1 tidak akan pernah bermain "turun" dan ini dapat dikesampingkan. Demikian pula pemain 2 tidak akan pernah bermain "benar", dan ini juga dapat dikesampingkan. Ini hanya menyisakan satu strategi tersisa untuk setiap pemain. Hasil yang diprediksi adalah pemain 1 akan bergerak "naik" dan pemain 2 akan bergerak "kiri". Sekali lagi ini adalah solusi tidak efisien Pareto. Ini karena hasil "down / left" membuat pemain 2 lebih baik dan pemain 1 tidak lebih buruk. Alasan pemain 1 tidak beralih ke bermain "turun", meskipun ini mengarah pada peningkatan Pareto, adalah bahwa itu memerlukan risiko yang lebih besar untuk pemain ini. Jika pemain 2 bermain "benar" maka pemain 1 pasti lebih buruk bergerak "turun" bukannya "naik". Unsur untuk menghindari risiko yang tidak perlu ini tercermin dalam prinsip dominasi yang lemah.

c.       Iterasi Dominasi Ketat

Iterasi dominasi yang ketat mengasumsikan bahwa dominasi yang ketat dapat diterapkan berturut-turut untuk pemain yang berbeda dalam permainan. Misalnya, jika satu pemain mengesampingkan strategi tertentu, karena didominasi oleh yang lain, maka diasumsikan pemain lain mengenali ini dan bahwa mereka juga percaya pemain lain tidak akan memainkan strategi yang didominasi ini. Ini pada gilirannya dapat menyebabkan mereka mengecualikan strategi yang didominasi, dan seterusnya. Dengan cara ini dimungkinkan untuk mengecualikan semua kecuali satu strategi untuk setiap pemain, dan sehingga membuat prediksi unik untuk permainan yang sedang dianalisis. Pertimbangkan permainan yang ditunjukkan pada Gambar 2.4.

Gambar 2.4 Penerapan dari Iterasi Dominasi Ketat

Dalam game ini pemain 1 memiliki dua kemungkinan strategi, "naik" dan "turun", dan pemain 2 memiliki tiga kemungkinan strategi, "kiri", "tengah" dan "kanan". Awalnya tidak "naik" atau "turun" secara ketat didominasi oleh yang lain untuk pemain 1. Namun untuk pemain 2 "kanan" secara ketat didominasi oleh "tengah". Menarik dominasi ketat kita dapat beralasan bahwa pemain 2 tidak akan pernah bermain "benar".

Jika pemain 1 juga tahu bahwa pemain 2 adalah rasional dan tidak akan bermain "benar", maka "naik" sekarang sangat mendominasi "turun" untuk pemain 1. Iterasi dominasi ketat sekarang memprediksi bahwa "turun" tidak akan dimainkan. Akhirnya jika pemain 2 tahu bahwa pemain 1 tidak akan pernah bergerak "turun", maka dominasi yang ketat memprediksi bahwa pemain 2 akan bermain "tengah". Solusi unik untuk permainan ini didasarkan pada dominasi yang kuat berturut-turut atau iterasi karena itu "up / tengah".

                  d.      Iterasi Dominasi Lemah.

Teknik dominasi terakhir adalah dominasi yang lemah. Ini sama dengan dominasi yang ketat, kecuali di sini dominasi lemah yang diterapkan secara berturut-turut untuk pemain yang berbeda dalam permainan. Sekali lagi ada kemungkinan bahwa teknik ini dapat menghasilkan solusi unik untuk permainan tertentu. Satu masalah dengan dominasi yang lemah, yang tidak dibagi dengan dominasi yang ketat, adalah bahwa solusi yang diprediksi dapat bergantung pada urutan di mana strategi pemain dihilangkan. Ini benar untuk permainan yang ditunjukkan pada Gambar 2.5. Jika kita mulai dengan menerapkan dominasi lemah untuk pemain 1 maka kita memprediksi bahwa para pemain akan memilih solusi unik "atas / tengah". Jika kita pertama kali menerapkan dominasi lemah untuk pemain 2 maka yang bisa kita simpulkan adalah bahwa pemain 2 tidak akan bermain "benar". Jelaslah urutan di mana kita menerapkan dominasi lemah secara signifikan mempengaruhi hasil prediksi permainan. Sayangnya untuk sebagian besar game pilihan ini sepenuhnya sewenang-wenang.

Gambar 2.5 Penerapan dari Iterasi Dominasi Lemah.

Perlu dicatat bahwa dalam menerapkan argumen dominasi beralasan kita mengasumsikan versi rasionalitas yang lebih kuat daripada yang kita lakukan dengan dominasi belaka. Dengan dominasi kita mengasumsikan bahwa pemain yang rasional tidak akan memainkan strategi yang didominasi. Dengan dominasi berulang kita berasumsi bahwa pemain yang rasional tidak akan memainkan strategi yang didominasi, dan juga bahwa pemain beranggapan bahwa pemain lain adalah rasional dan tidak akan melakukan ini. Untuk dominasi berulang untuk memprediksi secara akurat orang tidak hanya harus rasional tetapi menganggap bahwa orang lain juga rasional, dan persyaratan ini perlu diperkuat dengan setiap iterasi. (Sebagai contoh, saya perlu berasumsi bahwa Anda percaya bahwa saya percaya bahwa Anda percaya bahwa saya rasional, dan sebagainya. Jika urutan penalaran ini tak terbatas kita memiliki asumsi yang sering digunakan tentang pengetahuan umum tentang rasionalitas.) iterasi menjadi besar asumsi tambahan ini menjadi semakin meragukan.Contoh permainan di mana prinsip pengulangan dominasi yang ketat diambil secara ekstrem adalah permainan kelabang Rosenthal (1981).

Jika sebuah permainan menghasilkan solusi unik dengan menerapkan dominasi yang ketat, lemah atau iterasi maka permainan itu dikatakan sebagai dominasi yang dapat dipecahkan. Masalah utama dengan semua teknik solusi ini adalah seringnya mereka memberikan prediksi yang sangat tidak tepat tentang suatu permainan. Pertimbangkan permainan yang ditunjukkan pada Gambar 2.6. Dalam argumen permainan ini berdasarkan dominasi mengarah pada prediksi yang sangat tidak tepat bahwa apa pun bisa terjadi! Jika solusi yang lebih spesifik untuk jenis permainan ini diperlukan maka teknik solusi yang lebih kuat harus diterapkan. Ini mengarahkan kita pada teknik solusi yang didasarkan bukan pada dominasi tetapi pada konsep keseimbangan.

Gambar 2.6 Ilustrasi Masalah Teknik Dominasi.

                  e.       Nash Equilibrium

Sebagaimana dinyatakan dalam pengantar untuk argumen bagian ini berdasarkan dominasi mengajukan pertanyaan “Strategi apa yang pemain rasional tidak pernah mainkan? "Berbeda dengan konsep ekuilibrium Nash yang dimotivasi oleh pertanyaan" Sifat apa yang harus dimiliki ekuilibrium? Jawaban untuk pertanyaan ini dari John Nash (1951), berdasarkan pada karya sebelumnya oleh Cournot (1838), adalah bahwa dalam ekuilibrium setiap strategi yang dipilih pemain adalah optimal mengingat setiap pemain lain memilih strategi kesetimbangan. Jika ini tidak terjadi maka setidaknya satu pemain akan ingin memilih strategi yang berbeda dan jadi kita tidak bisa berada dalam kesetimbangan. Sekali lagi konsep ini berusaha untuk menerapkan asumsi ekonom bahwa individu bersifat rasional dalam arti bahwa mereka berusaha untuk memaksimalkan kepentingan diri mereka sendiri.

Menemukan kesetimbangan Nash untuk permainan apa pun melibatkan dua tahap. Pertama, kita mengidentifikasi strategi optimal setiap pemain sebagai respons terhadap apa yang mungkin dilakukan pemain lain. Ini melibatkan bekerja melalui setiap pemain secara bergantian dan menentukan strategi optimal mereka. Ini dilakukan untuk setiap kombinasi strategi oleh pemain lain. Kedua, kesetimbangan Nash diidentifikasi ketika semua pemain memainkan strategi optimal mereka secara bersamaan.

Tegasnya metodologi di atas hanya mengidentifikasi strategi murni Nash equilibria. Itu tidak mengidentifikasi strategi campuran Nash equilibria. Sebuah keseimbangan strategi murni adalah di mana setiap pemain memainkan satu strategi spesifik. Ekuilibrium strategi campuran adalah tempat setidaknya satu pemain dalam permainan mengacak beberapa atau semua strategi murni mereka. Ini berarti bahwa pemain menempatkan distribusi probabilitas atas strategi alternatif mereka. Misalnya, pemain mungkin memutuskan untuk memainkan masing-masing dari dua strategi murni yang tersedia dengan probabilitas 0,5, dan tidak pernah memainkan strategi lain. Oleh karena itu, strategi murni adalah a membatasi strategi campuran dengan kemungkinan satu diberikan kepada strategi yang dipilih, dan nol untuk semua yang lain. Konsep strategi campuran Nash ekuilibrium dibahas kemudian di bagian ini.

Untuk mengilustrasikan metodologi dua tahap untuk menemukan keseimbangan (strategi murni) Nash, kita menerapkannya pada permainan dilema narapidana. Ini ditunjukkan pada Gambar 2.7.

Gambar 2.7. Nash Equilibrium pada Permainan Dilema Tersangka

Tahap satu.

Pertama-tama kita perlu mengidentifikasi strategi optimal untuk setiap tahanan, tergantung pada apa yang mungkin dilakukan tahanan lain. Jika tahanan 1 mengharapkan tahanan 2 untuk mengaku maka strategi terbaik narapidana 1 juga untuk mengaku (-6 lebih baik daripada -9). Hal ini ditunjukkan pada Gambar 2.7 dengan menggarisbawahi elemen pembayaran ini untuk napi 1 di sel yang sesuai dengan kedua narapidana mengaku. Jika tahanan 1 mengharapkan narapidana 2 tidak mengaku, maka strategi terbaik narapidana masih untuk mengaku (saat ini 0 lebih baik dari -1). Sekali lagi kita menunjukkan ini dengan menggarisbawahi elemen pembayaran ini untuk narapidana 1. Analisis yang sama dilakukan untuk napi 2 dan imbalan strategi terbaiknya digarisbawahi.

Tahap Dua.

Selanjutnya kita menentukan apakah kesetimbangan Nash ada dengan memeriksa terjadinya strategi optimal yang diidentifikasi sebelumnya. Jika semua imbalan dalam sel digarisbawahi maka sel tersebut sesuai dengan ekuilibrium Nash. Ini benar menurut definisi, karena dalam kesetimbangan Nash semua pemain memainkan strategi optimal mereka mengingat bahwa pemain lain juga memainkan strategi optimal mereka. Dalam permainan dilema tahanan hanya satu sel yang semua elemennya digarisbawahi. Ini sesuai dengan kedua narapidana mengaku, dan jadi ini adalah equilibrium Nash yang unik untuk game ini.

Prediksi untuk game dilema tahanan ini sama dengan yang diturunkan menggunakan dominasi ketat. Sebenarnya memang benar bahwa solusi dominasi yang unik dan unik adalah ekuilibrium Nash yang unik. Kebalikan dari pernyataan ini, bagaimanapun, tidak selalu benar. Kesetimbangan Nash yang unik tidak selalu merupakan solusi dominan yang unik dan unik. Dalam pengertian ini, ekuilibrium Nash adalah konsep solusi yang lebih kuat daripada dominasi yang ketat. Untuk alasan ini konsep ekuilibrium Nash dapat memprediksi solusi unik untuk permainan di mana dominasi yang ketat tidak. Ini diilustrasikan dalam permainan yang digunakan sebelumnya untuk menunjukkan bahwa permainan mungkin tidak dapat dipecahkan. Permainan ini ditunjukkan pada Gambar 2.6 yang direproduksi di bawah ini pada Gambar 2.8. Sebagaimana dinyatakan sebelumnya argumen berdasarkan dominasi yang diterapkan pada game ini memprediksi bahwa apa pun bisa terjadi. Menggunakan dua tahap metodologi untuk menemukan (strategi murni) Nash equilibrium namun menghasilkan prediksi unik bahwa pemain 1 akan memilih "turun" dan pemain 2 akan memilih "benar". Konsep ekuilibrium Nash dapat sangat berguna ketika argumen dominasi tidak memberikan solusi yang unik.

Gambar 2.8. Penerapan Lebih Dalam dari Nash Equilibrium

Salah satu hasil penting dari teori permainan adalah bahwa untuk setiap permainan terbatas (yaitu permainan dengan sejumlah pemain dan strategi terbatas) selalu ada setidaknya satu ekuilibrium Nash. Sebelum berpikir bahwa hasil ini berarti bahwa kita selalu dapat membuat prediksi pasti tentang apa yang akan dilakukan orang-orang dalam game apa saja, dua kualifikasi berikut perlu dinyatakan.

Pertama, hasil di atas hanya benar jika kita memasukkan strategi campuran, serta strategi murni. Ini berarti bahwa kita tidak dapat selalu menyatakan dengan pasti apa yang semua pemain dalam permainan akan lakukan, tetapi sebaliknya kita mungkin hanya dapat memberikan probabilitas untuk berbagai hasil yang terjadi. Kemungkinan ini dibahas di bawah ini.

Kedua, hasil di atas tidak mengesampingkan kemungkinan beberapa ekuilibrium Nash. Memang banyak permainan yang menunjukkan banyak kesetimbangan Nash. Dengan beberapa kesetimbangan, masalahnya adalah bagaimana memilih satu ekuilibrium dari banyak orang. Sebagai jawaban atas pertanyaan ini, banyak penyempurnaan dari ekuilibrium Nash yang telah diusulkan untuk mencoba membatasi sekumpulan kemungkinan kesetimbangan. Beberapa penyempurnaan ini dibahas dalam bab-bab selanjutnya.

f.        Strategi Campuran Nash Equilibrium.

Untuk mengilustrasikan bahwa mungkin ada beberapa kesamaan Nash dengan permainan tertentu, dan juga ide strategi campuran, kita melihat permainan klasik lain yang disebut "Battle of the Sexes". Dalam permainan ini seorang suami dan istri sedang mencoba memutuskan ke mana harus pergi untuk keluar malam. Sementara mereka harus memilih untuk pergi ke pertandingan tinju, atau ke balet. Kedua pemain lebih suka pergi ke mana saja bersama-sama, tetapi mengingat ini pria lebih memilih tinju dan wanita balet. (Permainan ini diusulkan pada tahun 1950-an, yang sebagian menjelaskan pandangan stereotipnya.) Preferensi ini direpresentasikan dalam permainan bentuk normal yang ditunjukkan pada Gambar 2.9.

Gambar 2.9 Pertarungan Antar Gender dalam Bentuk Normal.

Menerapkan metode dua tahap untuk mengidentifikasi strategi kesetimbangan Nash murni kita dapat melihat bahwa permainan di atas memiliki dua kesetimbangan seperti itu. Ini adalah bahwa keduanya akan pergi ke tinju atau keduanya akan pergi ke balet. Ini berarti bahwa setiap orang akan pergi ke mana pun mereka berpikir orang lain akan pergi. Ini tidak terlalu membantu, karena tidak memberitahu pemain apa yang mungkin dilakukan orang lain. Karena tidak ada strategi murni yang unik, Nash tidak memiliki pemain yang dapat dengan yakin memprediksi apa yang akan dilakukan orang lain. Bermain strategi campuran adalah respons terhadap ketidakpastian ini. Strategi campuran adalah ketika pemain mengacak beberapa atau semua strategi murni yang tersedia. Ini berarti bahwa pemain menempatkan distribusi probabilitas atas strategi alternatif mereka. Ekuilibrium strategi campuran adalah di mana setidaknya satu pemain memainkan strategi campuran dan tidak ada yang memiliki insentif untuk menyimpang secara sepihak dari posisi itu.

Kunci dari strategi campuran Nash equilibrium adalah bahwa setiap strategi murni yang dimainkan sebagai bagian dari strategi campuran memiliki nilai yang diharapkan sama. Jika ini tidak benar, seorang pemain akan memainkan strategi yang menghasilkan nilai tertinggi yang diharapkan untuk mengesampingkan semua yang lain. Ini berarti situasi awal tidak bisa menjadi keseimbangan. Di sini kita menunjukkan bagaimana mengidentifikasi strategi campuran Nash keseimbangan untuk pertempuran permainan jenis kelamin.

Biarkan pr (tinju) H adalah probabilitas bahwa suami pergi ke pertandingan tinju, dan pr (tinju) W probabilitas bahwa istri pergi ke pertandingan tinju. Sama halnya dengan pr (balet) H adalah probabilitas bahwa pria pergi ke balet, dan pr (balet) W probabilitas bahwa wanita pergi ke balet. Karena ini adalah satu-satunya dua alternatif, harus benar bahwa pr (tinju) + pr (balet) = 1 untuk suami dan istri. Mengingat probabilitas ini kita dapat menghitung nilai yang diharapkan dari setiap tindakan yang mungkin dilakukan oleh setiap orang.

Dari permainan bentuk normal, nilai pembayaran yang diharapkan untuk istri jika dia memilih untuk pergi ke pertandingan tinju diberikan sebagai

EV boxing () W = pr tinju (1) () H + pr (balet) (0) W

= pr (tinju) H

Demikian pula nilai hasil yang diharapkan jika dia pergi ke balet adalah EV

ballet () W = pr tinju (0) () H + pr ballet (2) () H

= 2 pr ballet () H

Dalam ekuilibrium, nilai yang diharapkan dari kedua strategi ini harus sama dan kita dapatkan

EV boxing () W = EV ballet () W

∴ pr tinju () H = 2 pr (balet) H

∴ −1 pr (balet) H = 2 pr (balet) H

∴ = 1 3 pr (balet) H 1 2

∴pr (balet) H = 1/3 dan pr (tinju) H = 2/3

Ini berarti bahwa dalam strategi campuran keseimbangan suami akan pergi ke balet dengan probabilitas 1/3 dan tinju dengan probabilitas 2/3. Kita dapat melakukan perhitungan yang sama untuk hasil yang diharapkan suami dan mendapatkan hasil yang sama bahwa dalam kesetimbangan istrinya akan pergi ke balet dengan probabilitas 2/3 dan tinju dengan probabilitas 1/3. Dengan probabilitas individu ini kita dapat menghitung bahwa keduanya akan pergi ke tinju dengan probabilitas 2/9, keduanya pergi ke balet dengan probabilitas 2/9, dan pergi ke acara terpisah dengan probabilitas 5/9.

Kombinasi dari strategi campuran ini merupakan equilibrium Nash ketiga untuk game ini. Secara intuitif ini tampaknya merupakan ekuilibrium Nash yang paling masuk akal dari ketiganya, karena secara eksplisit memperhitungkan ketidakpastian yang melekat dalam permainan. Perlu dicatat bahwa memainkan strategi campuran tidak berarti bahwa pemain melempar koin atau melempar dadu untuk membuat keputusan. Melainkan memainkan strategi campuran adalah respons rasional terhadap ketidakpastian tentang apa yang akan dilakukan pemain lain.

Salah satu aspek penasaran dari keseimbangan strategi campuran adalah karena masing-masing strategi murni yang dipilih dalam strategi campuran memiliki nilai pembayaran yang diharapkan sama, setiap pemain acuh tak acuh mengenai strategi mana yang sebenarnya dia mainkan. Ekuilibrium strategi campuran adalah, karenanya, dikatakan sebagai keseimbangan yang lemah karena tidak ada pemain yang dibuat lebih buruk jika mereka meninggalkan strategi campuran mereka, dan memainkan salah satu dari komponen strategi murni dari strategi campuran mereka. Fitur dari strategi campuran Nash keseimbangan ini telah menyebabkan penerapannya dalam ekonomi menjadi kontroversial. Secara khusus teknik solusi ini telah dikritik sebagai memaksakan kendala yang tidak dapat diterima pada keyakinan pemain.

Softskill Pengantar Teknologi Game

Sumber :

http://www.opim.wharton.upenn.edu/~sok/papers/r/graham-romp/romp-chapter2

Bentuk Normal dan Bentuk Luas (Ekstensive) dalam Permainan dan Permainan Dinamis Satu Kali

BAB 2

Teori Permainan Statis

Dalam bab ini kita akan melihat bagaimana permainan statis dapat direpresentasikan, dan memeriksa beberapa cara yang telah disarankan untuk bagaimana cara menyelesaikannya. Solusi untuk game adalah prediksi tentang apa yang akan dilakukan oleh setiap pemain dalam game tersebut. Dalam permainan statis para pemain membuat gerakan mereka dalam isolasi tanpa mengetahui apa yang telah dilakukan pemain lain. Ini tidak selalu berarti bahwa semua keputusan dibuat pada saat yang bersamaan, tetapi hanya seolah-olah keputusan dibuat pada saat yang bersamaan.

Contoh permainan statis adalah satu kali lelang, penawaran ditutup. Dalam jenis lelang ini, setiap pemain hanya mengajukan satu tawaran, tanpa mengetahui apa yang dimiliki pemain lain. Tawaran tertinggi kemudian diterima sebagai harga pembelian. Berbeda dengan permainan statis, permainan dinamis memiliki urutan-urutan bermain dan pemain mengamati cara pemain lawannya. Contoh permainan dinamis salah satunya disebut lelang Inggris. Dimana pemain secara terbuka menawar harga suatu objek. Dan tawaran akhir dan tertinggilah yang diterima sebagai harga pembelian.

2.1. Bentuk Normal dan Bentuk Ekstensif dalam Permainan.

Dalam teori permainan non-kooperatif ada dua cara alternatif di mana game dapat diwakili. Tipe pertama disebut permainan bentuk normal atau permainan bentuk strategis. Tipe kedua disebut permainan bentuk yang luas. Keduanya banyak digunakan di bidang ekonomi dan kita memeriksa masing-masing secara bergantian.

a.      Permainan Bentuk Normal.

Permainan bentuk normal adalah permainan apa saja yang dapat mengidentifikasi tiga hal berikut:

(i) Para pemain.

Pemain dalam permainan adalah individu yang membuat keputusan yang relevan. Agar ada interdependensi, kita harus memiliki setidaknya dua pemain dalam game. Di sebagian besar aplikasi yang kita lihat di sana hanya akan ada dua pemain. Dalam beberapa permainan "Nature" dianggap sebagai pemain lebih lanjut, yang berfungsi untuk menentukan hasil dari peristiwa acak tertentu, seperti cuaca atau "tipe" pemain dalam permainan.

(ii) Strategi yang tersedia untuk setiap pemain.

Strategi adalah deskripsi lengkap tentang bagaimana seorang pemain bisa memainkan permainan. Ini tidak selalu hanya daftar tindakan alternatif pemain. Sebaliknya itu menggambarkan bagaimana tindakan pemain tergantung pada apa yang dia amati pemain lain dalam permainan yang telah dilakukan. Sebagai contoh, jika saya berpikir tentang menjual mobil saya, maka tindakan saya terbatas untuk menjualnya atau menjaganya. Strategi yang saya pilih, memberi tahu saya bagaimana tindakan ini yang mungkin tergantung pada apa yang dilakukan orang lain. Jika seseorang menawarkan saya Rp. 50.000.000 atau lebih untuk mobil saya, saya pasti akan menjualnya. Jika mereka menawarkan saya kurang dari Rp. 50.000.000, maka saya tidak akan menjual mobil saya.

Dalam permainan dinamis seperti ini, satu set strategi pemain akan jauh lebih besar daripada tindakannya yang mungkin dilakukan. Dalam permainan statis, keduanya sama. Ini karena dalam keputusan permainan statis diambil dalam isolasi dan sehingga pemain tidak dapat membuat tindakan mereka tergantung pada apa yang dilakukan pemain lain. Dalam contoh saya mencoba menjual mobil saya, ini akan sesuai dengan permainan yang sangat aneh di mana saya harus menerima atau menolak tawaran seseorang tanpa mengetahui apa itu! Dalam hal ini, strategi saya sama dengan tindakan saya: menjual atau tidak menjual. (Dalam diskusi ini kita telah mengabaikan kemungkinan pemain mengadopsi strategi campuran. Ini akan dibahas nanti di bab ini.)

(iii) Imbalannya.

Imbalan adalah apa yang akan diterima pemain di akhir permainan bergantung pada tindakan semua pemain dalam permainan. Permainan bentuk normal menunjukkan imbalan untuk setiap pemain, kecuali sifat alami, untuk setiap kemungkinan kombinasi dari strategi yang tersedia. Ini kemudian diwakili dalam bentuk matriks atau matriks. Imbalannya ditentukan sehingga pemain dalam permainan selalu lebih memilih pembayaran yang lebih tinggi hingga lebih kecil. Misalnya, imbalan dapat sesuai dengan hadiah uang, seperti laba, atau utilitas yang diperoleh setiap pemain pada akhir permainan. Seorang pemain dikatakan rasional ketika ia berusaha memaksimalkan ganjarannya. Jika seorang pemain tidak memiliki tujuan ini, mereka dikatakan tidak rasional, karena mereka tidak bertindak untuk kepentingan diri sendiri.

Untuk membuat ide-ide yang dibahas lebih spesifik, kita akan melihat satu game statis terkenal yang disebut "The Prisoners’ Dilemma ". Dalam game ini polisi telah menangkap dua tersangka kejahatan. Namun mereka tidak memiliki bukti yang cukup untuk menghukum salah satu dari mereka kecuali setidaknya satu dari mereka mengakui. Polisi menahan kedua tersangka dalam sel terpisah dan menjelaskan konsekuensi dari tindakan yang mungkin mereka lakukan. Jika tidak mengakui maka keduanya akan dihukum karena pelanggaran ringan dan dijatuhi hukuman satu bulan penjara. Jika keduanya mengakui akan dikirim ke penjara selama enam bulan. Akhirnya, jika hanya satu dari mereka yang mengakui, maka tersangka itu akan segera dibebaskan sementara yang lainnya akan dijatuhi hukuman sembilan bulan penjara - enam bulan untuk kejahatan dan tiga bulan lagi karena menghalangi jalannya keadilan.

Deskripsi permainan di atas memenuhi tiga persyaratan permainan bentuk normal. Kita memiliki dua pemain, masing-masing memiliki dua strategi (yang dalam permainan statis ini sama dengan tindakan para tersangka, mengakui atau tidak mengakui), dan terdapat hadiah untuk setiap kemungkinan kombinasi strategi. Bentuk normal untuk game ini ditunjukkan pada Gambar 2.1. Imbalannya ditunjukkan sebagai angka negatif untuk kurungan penjara dalam hitungan bulan, untuk setiap hasil dan untuk setiap tersangka. Ini mengasumsikan bahwa setiap tersangka, jika rasional, berusaha untuk meminimalkan jumlah waktu yang dihabiskan di penjara. Dengan konvensi, pembayaran pertama yang tercantum di setiap sel mengacu pada pemain tersangka 1 dalam baris, dan hasil kedua mengacu pada pemain tersangka 2 dalam kolom.

Gambar 2.1 Permainan Dilema Tersangka pada Permainan Bentuk Normal

b.      Permainan Bentuk Ekstensif.

Dalam bentuk permainan yang luas, perhatian yang lebih besar ditempatkan pada waktu keputusan yang akan dibuat, serta pada jumlah informasi yang tersedia untuk setiap pemain ketika keputusan harus dibuat. Jenis permainan ini tidak diwakili dengan matriks tetapi dengan keputusan, atau permainan, pohon. Bentuk ekstensif untuk dilema tersangka ditunjukkan pada Gambar 2.2.

Gambar 2.2 Permainan Dilema Tersangka pada Permainan Bentuk Luas

Mulai di sebelah kiri diagram lingkaran terbuka mewakili keputusan pertama yang dibuat dalam game. Ini diberi label 1 untuk menunjukkan bahwa tersangka 1 yang membuat keputusan ini. Cabang-cabang yang keluar dari node awal ini mewakili tindakan yang tersedia untuk pemain pada saat itu dalam permainan.

Tersangka 1 dapat mengakui kejahatan atau tidak mengakuinya. Di ujung cabang ini ada simpul yang merepresentasikan keputusan tersangka 2. Sekali lagi tersangka ini dapat mengakui kejahatan atau tidak mengakui, seperti yang diberikan oleh cabang-cabang yang datang dari simpul keputusannya. Namun tersangka 2 membuat keputusan ini tanpa mengetahui apa yang telah dilakukan tersangka 1. Ini ditunjukkan dengan menggabungkan node keputusan tersangka 2 dengan garis putus-putus. Garis putus-putus ini menunjukkan bahwa simpul-simpul yang terhubung berada dalam kumpulan informasi yang sama. Ini berarti tersangka 2 tidak dapat membedakan mana dari dua simpul yang ada, pada saat keputusan ini dibuat. Ini karena dia tidak tahu apakah tersangka 1 mengakui atau tidak mengakui kejahatan. Akhirnya di akhir permainan kita mendapat imbalan untuk setiap pemain. Ini lagi-lagi tergantung pada apa yang telah dilakukan setiap tersangka dalam permainan, dan mereka tercantum dalam urutan pemain dalam gim, yaitu pembayaran tersangka 1 adalah yang pertama, dan pembayaran tersangka 2 adalah yang kedua.

Generalisasi dari Gambar 2.2 kita dapat menyatakan bahwa permainan formulir yang luas memiliki empat elemen berikut yang sama:

Akar.

Ini adalah posisi dalam permainan di mana salah satu pemain harus membuat keputusan. Posisi pertama, yang disebut node awal, adalah titik terbuka, semua sisanya diisi. Setiap node diberi label sehingga dapat mengidentifikasi siapa yang membuat keputusan.

Ranting.

Ini mewakili pilihan alternatif yang dihadapi orang tersebut, dan sesuai dengan tindakan yang tersedia.

Vektor.

Ini mewakili hadiah untuk setiap pemain, dengan hadiah yang tercantum dalam urutan pemain. Ketika kita mencapai hasil akhir permainan berakhir. Ketika vektor hasil ini adalah pengetahuan umum, permainan dikatakan sebagai salah satu informasi lengkap. (Informasi adalah pengetahuan umum jika diketahui oleh semua pemain, dan setiap pemain tahu itu diketahui oleh semua pemain, dan setiap pemain tahu bahwa diketahui bahwa semua pemain mengetahuinya, dan seterusnya tak terhingga.) Namun, jika pemain tidak yakin tentang hasil yang dapat diterima pemain lain, maka itu adalah permainan informasi yang tidak lengkap.

Kumpulan Informasi.

Ketika dua atau lebih node bergabung bersama dengan garis putus-putus, ini berarti bahwa pemain yang keputusannya tidak tahu node mana dia berada. Ketika ini terjadi, game ini dicirikan sebagai salah satu informasi yang tidak sempurna. Ketika setiap node keputusan adalah informasi sendiri mengatur permainan dikatakan menjadi salah satu informasi yang sempurna, karena semua pemain tahu hasil dari keputusan sebelumnya.     Asumsi mendasar dari teori permainan adalah bahwa struktur permainan adalah pengetahuan umum. Ini menempatkan tiga persyaratan khusus pada set informasi. Yang pertama adalah bahwa pemain selalu ingat apakah mereka telah pindah sebelumnya di dalam game. Namun, ini tidak berarti bahwa mereka selalu ingat keputusan apa yang mereka buat sebelumnya, hanya keputusan yang dibuat. Syarat kedua adalah node dalam set informasi yang sama memiliki pemain yang sama bergerak. Kondisi terakhir adalah simpul dalam kumpulan informasi yang sama memiliki kemungkinan tindakan yang sama dari mereka. Jika ini tidak benar, pemain dapat membedakan antara node dengan memeriksa tindakan yang tersedia. Sekali lagi generalisasi dari Gambar 2.2 kita dapat menyatakan satu persyaratan lebih lanjut yang selalu puas untuk permainan bentuk yang luas:

Setiap node memiliki setidaknya satu cabang yang menunjukkannya (beberapa tindakan tersedia untuk pemain) dan paling banyak satu cabang yang menunjuk ke dalamnya. (Simpul awal tidak memiliki cabang yang menunjuk ke sana.).

Ini berarti bahwa pada simpul mana pun kita mulai di sana, hanya ada satu jalur yang mungkin kembali ke simpul awal dan kita tidak pernah berputar kembali ke simpul yang kita mulai. Karena alasan ini, permainan bentuk yang luas selalu terlihat seperti pohon. Dari simpul awal kita selalu bercabang dan cabang tidak pernah tumbuh kembali ke dalam dirinya sendiri.

Kita sekarang telah melihat bahwa ada dua cara berbeda untuk mewakili permainan yang sama, baik sebagai permainan bentuk normal atau sebagai permainan bentuk yang luas. Bentuk normal memberikan jumlah minimum informasi yang diperlukan untuk menggambarkan permainan. Ini daftar pemain, strategi yang tersedia untuk setiap pemain, dan hasil yang dihasilkan untuk setiap pemain. Bentuk ekstensif memberikan detail tambahan tentang gim menyangkut waktu keputusan yang akan dibuat dan jumlah informasi yang tersedia untuk setiap pemain ketika setiap keputusan harus dibuat. Jelas kedua bentuk ini terkait erat dan kita dapat menyatakan dua hasil berikut:

Untuk setiap permainan bentuk yang luas ada satu dan hanya satu permainan bentuk normal yang sesuai.

Untuk setiap permainan bentuk normal ada, secara umum, beberapa permainan bentuk yang sesuai.

Alasan kurangnya ini korespondensi satu-ke-satu antara bentuk permainan normal dan permainan bentuk yang luas adalah bahwa, seperti yang dijelaskan di atas, permainan bentuk yang luas termasuk informasi tambahan. Ini menyiratkan bahwa berbagai bentuk yang berbeda dapat ditarik dari permainan bentuk normal yang sama, tergantung pada apa yang diasumsikan tentang rincian tambahan dari permainan ini.

Bab 3

Teori Permainan Dinamis.

Di bab sebelumnya kita fokus pada game statis. Namun untuk banyak aplikasi ekonomi penting, kita perlu memikirkan permainan yang dimainkan selama beberapa periode waktu, membuatnya dinamis. Permainan bisa dinamis karena dua alasan. Pertama, interaksi antar pemain itu sendiri dapat bersifat dinamis. Dalam situasi ini pemain dapat mengamati tindakan pemain lain sebelum memutuskan respons optimalnya. Sebaliknya gim statis adalah gim yang bisa dipikirkan pemain yang melakukan gerakannya secara bersamaan. Kedua, gim bersifat dinamis jika gim satu kali diulangi beberapa kali, dan pemain mengamati hasil dari gim sebelumnya sebelum bermain di kemudian hari. Pada bagian 3.1, kita mempertimbangkan game dinamis satu-off, dan di bagian 3.2 kita menganalisis game yang diulang.

3.1. Permainan Dinamis Satu kali.

Fitur penting dari semua permainan dinamis adalah bahwa beberapa pemain dapat mengkondisikan tindakan optimal mereka pada apa yang telah dilakukan pemain lain di masa lalu. Ini sangat meningkatkan strategi yang tersedia untuk pemain tersebut, karena ini tidak lagi setara dengan tindakan yang mungkin mereka lakukan. Untuk mengilustrasikan ini kita memeriksa dua periode permainan entri dinamis berikut, yang merupakan versi modifikasi dari gim statis yang digunakan dalam Latihan 2.4.

Ada dua perusahaan (A dan B) yang mempertimbangkan ya atau tidak untuk memasuki pasar baru. Sayangnya pasar hanya cukup untuk mendukung salah satu dari dua perusahaan. Jika kedua perusahaan memasuki pasar maka keduanya akan mengalami kerugian sebesar Rp. 10.000.000. Jika hanya satu perusahaan yang masuk ke pasar, perusahaan itu akan mendapat untung sebesar Rp. 50.000.000, dan perusahaan lain hanya akan mencapai titik impas. Untuk membuat dinamika permainan ini kita mengasumsikan bahwa perusahaan B mengamati apakah perusahaan A telah memasuki pasar sebelum memutuskan apa yang harus dilakukan. Permainan ini dapat diwakili oleh diagram form luas yang ditunjukkan pada Gambar 3.1.

Gambar 3.1 Permainan Entri Dinamis pada Bentuk Luas

Dalam periode waktu 1 perusahaan A membuat keputusannya. Hal ini diamati oleh perusahaan B yang memutuskan untuk masuk atau tetap keluar dari pasar pada periode 2. Dalam perusahaan game bentuk yang luas ini, simpul keputusan B adalah kumpulan informasi terpisah. (Jika mereka berada di kumpulan informasi yang sama mereka akan dihubungkan oleh garis putus-putus.) Ini berarti bahwa perusahaan B mengamati tindakan perusahaan A sebelum membuat keputusan sendiri. Jika kedua perusahaan itu membuat gerakan mereka secara bersamaan maka perusahaan B hanya memiliki dua strategi. Ini akan baik masuk atau tetap keluar dari pasar. Namun karena perusahaan B pada awalnya mengamati keputusan perusahaan A, keputusan itu dapat membuat keputusannya tergantung pada apa yang perusahaan A lakukan. Karena perusahaan A memiliki dua kemungkinan tindakan, dan begitu juga perusahaan B, ini berarti bahwa perusahaan B memiliki empat (2 x 2) strategi. Kita bisa daftar ini sebagai:

Selalu masuki pasar apa pun yang dilakukan perusahaan A.

Selalu berada di luar pasar apa pun yang dilakukan perusahaan A.

Lakukan hal yang sama dengan perusahaan A.

Lakukan kebalikan dari perusahaan A.

Menyadari bahwa perusahaan B sekarang memiliki empat strategi ini, kita dapat mewakili permainan di atas dalam bentuk normal. Ini ditunjukkan pada Gambar 3.2. Setelah mengkonversi bentuk permainan yang luas menjadi permainan bentuk normal, kita dapat menerapkan metode dua tahap untuk menemukan strategi murni Nash equilibria, seperti yang dijelaskan dalam bab sebelumnya. Pertama, kita mengidentifikasi strategi optimal masing-masing pemain dalam menanggapi apa yang mungkin dilakukan pemain lain. Ini melibatkan bekerja melalui setiap pemain secara bergantian dan menentukan strategi optimal mereka. Ini diilustrasikan dalam bentuk permainan normal dengan menggarisbawahi hasil yang relevan. Kedua, kesetimbangan Nash diidentifikasi ketika semua pemain memainkan strategi optimal mereka secara bersamaan.

Gambar 3.2 Permainan Entri Dinamis pada Bentuk Normal

Seperti yang ditunjukkan pada Gambar 3.2 permainan entri dinamis ini memiliki tiga strategi murni Nash equilibria. Dalam ketiga situasi ini setiap perusahaan bertindak secara rasional berdasarkan keyakinannya tentang apa yang mungkin dilakukan oleh perusahaan lain. Kedua perusahaan itu memaksimalkan laba mereka tergantung pada apa yang mereka yakini sebagai strategi perusahaan lain. Salah satu cara untuk memahami hasil yang mungkin ini adalah memikirkan perusahaan B yang membuat berbagai ancaman atau janji, dan tegas A bertindak sesuai dengan itu. Oleh karena itu kita dapat menafsirkan tiga equilibria Nash sebagai berikut:

1.      Perusahaan B mengancam untuk selalu memasuki pasar terlepas dari apa yang perusahaan A lakukan.

Jika perusahaan A percaya ancaman ini akan tetap keluar dari pasar.

2.      Perusahaan B berjanji untuk selalu menjauhi pasar terlepas dari apa yang perusahaan A lakukan. Jika firma A percaya janji ini, pasti akan memasuki pasar.

3.      Perusahaan B berjanji untuk selalu melakukan kebalikan dari apa yang perusahaan A lakukan. Jika firma A percaya bahwa janji ini akan masuk lagi ke pasar.

Dalam dua tindakan pertama Nash equilibria perusahaan B tidak tergantung pada apa yang dilakukan perusahaan lain. Di perusahaan ekuilibrium Nash yang ketiga, B memang mengadopsi strategi bersyarat. Sebuah strategi bersyarat adalah di mana satu pemain mengkondisikan tindakan mereka pada tindakan setidaknya satu pemain lain dalam gim. Konsep ini sangat penting dalam permainan berulang, dan dianggap lebih detail di bagian berikutnya.

Di masing-masing perusahaan kesetimbangan A bertindak secara rasional sesuai dengan keyakinannya. Namun analisis ini tidak mempertimbangkan mana dari keyakinannya itu sendiri rasional. Hal ini menimbulkan pertanyaan yang menarik, “Mungkinkah perusahaan A tidak mengabaikan beberapa ancaman atau janji perusahaan B sebagai hanya gertakan?” Hal ini menimbulkan masalah kredibilitas yang penting. Konsep kredibilitas datang ke pertanyaan "Apakah ancaman atau janji dapat dipercaya?" Dalam teori permainan, sebuah ancaman atau janji hanya kredibel jika dalam minat pemain untuk melaksanakannya pada waktu yang tepat. Dalam pengertian ini beberapa pernyataan perusahaan B tidak dapat dipercaya.

Sebagai contoh, perusahaan B dapat mengancam untuk selalu memasuki pasar terlepas dari apa yang perusahaan A lakukan, tetapi ini tidak kredibel. Hal ini tidak dapat dipercaya karena jika perusahaan A memasuki pasar maka perusahaan tertarik untuk tetap keluar. Demikian pula janji untuk selalu keluar dari pasar tidak dapat dipercaya karena jika perusahaan A tidak masuk maka itu adalah kepentingan perusahaan B untuk melakukannya. Dengan asumsi bahwa pemain itu rasional, dan bahwa ini adalah pengetahuan umum, tampaknya masuk akal untuk menganggap bahwa pemain hanya percaya pada pernyataan yang kredibel. Ini menyiratkan bahwa pernyataan luar biasa tidak akan berpengaruh pada perilaku pemain lain. Ide-ide ini dimasukkan ke dalam konsep ekuilibrium alternatif ke ekuilibrium Nash (atau penyempurnaannya) yang disebut subgame equilibrium Nash sempurna.

Softskill Pengantar Teknologi Game

Sumber :

http://www.opim.wharton.upenn.edu/~sok/papers/r/graham-romp/romp-chapter2

http://opim.wharton.upenn.edu/~sok/papers/r/graham-romp/romp-chapter3.pdf

Review Game

Review 2 buah game

Game Slither.io

Game Slither.io adalah permainan console dimana dalam permainan tersebut pemain diharuskan untuk  mengendalikan seekor cacing yang harus terus mencari elemen titik berwarna-warni yang diinisialkan sebagai skor untuk pemain dan perubah ukuran dari cacing tersebut, dimana jika skor semakin banyak, makan ukuran cacing tersebut juga semakin besar. Teori yang digunakan pada permainan ini, menurut saya adalah menggunakan teori payoff non-zero-sum games, karena pemain harus melawan ai ataupun pemain lain (bergantung tipe permainannya). Ilustrasi permainannya adalah dengan cara menabrakkan cacing pemain lawan ke cacing milik kita, contoh cacing pemain A sudah mengumpulkan skor sebanyak 1500 dan pemain B sudah mengumpulkan skor sebanyak 5000, pastinya pemain B menginginkan skor yang lebih besar, maka bagaimanapun caranya, pemain B harus bisa membuat agar cacing pemain A menabrakkan cacing nya ke badan cacing pemain B.

Gambar 1. Cacing yang menabrak.

Seperti pada gambar 1, ketika terjadi tabrakan, maka cacing A akan hilang yang mengartikan skornya menjadi nol lagi, dan pemain B bertambah skor nya seiring cacing pemain B menagmbil seluruh poin dari cacing A yang menjadi alur akhir bagaiamana cacing pemain A tadi menabrak badan cacing pemain B.

Game Pacman

Pacman adalah sebuah permainan video arkade yang cukup terkenal. Cara bermainnya mudah yaitu pemain (pacman) diharuskan memakan makanan (berbentuk titik-titik kecil) dan sebuah bulatan besar (energizer) sampai habis di dalam sebuah labirin. Tidak hanya menghabiskan makanan tersebut, pemain juga harus menghindari 4 ‘hantu’ yang berkeliaran secara acak untuk menangkap pemain. Jika pemain bertemu dengan hantu-hantu tersebut maka pemain dinyatakan gagal dan harus mengulangi dari awal lagi. Tetapi pemain bisa mengalahkan hantu tersebut dengan memakan energizer yang terdapat di pojokkan labirin. Jika pemain memakan titik besar tersebut, maka para hantu akan ketakutan dan berusaha menjauh dari pemain. Dalam hal ini pemain bisa memakan hantu tersebut dan mendapatkan bonus yang besar, tetapi para hantu yang termakan tidak mati begitu saja, mereka kembali ke posisi semula dan kembali mengejar pemain. Pemain dinyatakan menang jika semua makanan habis tak tersisa dan pemain akan memasuki level berikutnya.

Pergerakan para hantu ini dipengaruhi oleh kecerdasan buatan atau Artificial Intelligence (AI), dimana para hantu diberi kecerdasan untuk menentukan langkah dan mengambil keputusan akan bergerak kemana dengan menentukan rute yang paling pendek (minimum), tujuannya adalah menangkap pemain. Setiap hantu harus memiliki pemikiran berbeda dan memiliki kemampuan bekerja sama untuk mengejar pemain, sehingga permainan akan tampak lebih menarik.

             Menurut saya, teori yang digunakan untuk permainan pacman ini adalah teori strategi-permainan yang mengharuskan pemain untuk memakan seluruh makanan (titik) yang ditentukan serta harus menghindar dari hantu dengan ai yang diberikan.

Sumber :

http://abdanniputri.blogspot.co.id/2012/04/analisa-game-pacman.html

https://gcube.id/wp-content/uploads/2017/12/gcube-slither-kalah.jpg