Dicka's Blog

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.

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 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.



Pada sebuah game pasti memiliki algoritma, salah satu dari algoritma yaitu Algoritma Minimax.
Apa itu Algoritma Minimax?

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.


Fungsi heuristik yang digunakan algoritma ini adalah fungsi heuristik statis (Kusumadewi, 2003). 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 (Akbar, 2007). Untuk proses dan cara kerja algoritma yang lebih jelasnya lagi, dapat dilihat pada Gambar 2.10 yang merepresentasikan cara kerja algoritma Minimax.Fungsi heuristik yang digunakan algoritma ini adalah fungsi heuristik statis (Kusumadewi, 2003). 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 (Akbar, 2007).


Refrensi:
https://id.wikipedia.org/wiki/Teori_permainan
https://id.wikipedia.org/wiki/Minimax
http://www.catatanfadil.com/2014/03/teori-game.html
http://majalah1000guru.net/2011/07/teori-permainan-game-theory/
https://sutrisnoadityo.wordpress.com/2013/10/12/teori-permainan-game-theory/
http://rinaforall.blogspot.co.id/2013/04/algoritma-minimax.html