Board Game dan Algoritma Minimax



Nama              : Bayu Nanda Adi Saputra
Npm                : 51415293
Kelas               : 3IA21
Mata Kuliah  : Pengantar Teknologi Game
Nama Dosen  : Syefani Rahma Deski


Board Game dan Algoritma Minimax

Board game adalah bagian dari tabletop game yang didalamnya terdapat peraturan cara bermain yang dilengkapi dengan beberapa komponen seperti token, pion atau bidak yang dapat digerakkan diatas sebuah “papan” khusus. Contohnya seperti yang sudah umum diketahui, yaitu Catur. Sebuah permainan bagaimana mengatur strategi untuk “menangkap” pion Raja milik lawan. Seperti kriteria board game yang sudah disebutkan, Catur terdiri dari banyak pion (Raja, Ratu, Mentri, Kuda, dll) dan bisa digerakkan di atas papan-khusus dengan motif kotak-kotak. Manikmaya akan membahas tentang sejarah board game di lain kesempatan.


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.



Sumber :
https://dickaariptian17.blogspot.com/2016/03/teori-game-dan-algoritma-minimax.html

Komentar

Posting Komentar

Postingan populer dari blog ini

Gambar
TOKOH INSPIRATIF Biografi Bob Sadino Pengusaha Sukses Indonesia Beliau bernama lengkap Bob Sadino. Lahir di Lampung, tanggal 9 Maret 1933, wafat pada tanggal 19 Januari 2015. Beliau akrab dipanggil dengan sebutan 'om Bob'. Ia adalah seorang pengusaha asal Indonesia yang berbisnis di bidang pangan dan peternakan. Ia adalah pemilik dari jaringan usaha Kemfood dan Kemchick. Dalam banyak kesempatan, ia sering terlihat menggunakan kemeja lengan pendek dan celana pendek yang menjadi ciri khasnya. Bob Sadino lahir dari sebuah keluarga yang hidup berkecukupan. Ia adalah anak bungsu dari lima bersaudara. Sewaktu orang tuanya meninggal, Bob yang ketika itu berumur 19 tahun mewarisi seluruh harta kekayaan keluarganya karena saudara kandungnya yang lain sudah dianggap hidup mapan. Bob kemudian menghabiskan sebagian hartanya untuk berkeliling dunia. Dalam perjalanannya itu, ia singgah di Belanda dan menetap selama kurang lebih 9 tahun. Di sana, ia bekerja di Djaka...
Baca selengkapnya

SOFTSKILL (PENULISAN) DESAIN KOMUNIKASI VISUAL

Nama                : Bayu Nanda Adi Saputra NPM                : 51415293 Kelas                : 3IA21 Mata Kuliah     : Desain Pemodelan Grafik Dosen               : Syefani Rahma Deski Pengertian Desain Komunikasi Visual Desain Komunikasi Visual adalah ilmu yang mempelajari konsep komunikasi dan ungkapan kreatif, teknik dan media untuk menyampaikan pesan dan gagasan secara visual, termasuk audio dengan mengolah elemen desain grafis berupa bentuk gambar, huruf dan warna, serta tata letaknya, sehingga pesan dan gagasan dapat diterima oleh sasarannya. Sejarah Desain Komunikasi Visual Sejak jaman pra-sejarah manusia telah mengenal dan mempraktekkan komunikasi visual. Bentu...
Baca selengkapnya
Ilmu Budaya Dasar MANUSIA DAN PANDANGAN HIDUP A. Ideologi Jadi Ideologi mempunyai arti pengetahuan tentang gagasangagasan, pengetahuan tentang ide-ide, science of ideas atau ajaran tentang pengertian-pengertian dasar. Dalam pengertian sehari-hari menurut Kaelan ‘idea’ disamakan artinya dengan citacita. Dalam perkembangannya terdapat pengertian Ideologi yang dikemukakan oleh beberapa ahli. Istilah Ideologi pertama kali dikemukakan oleh Destutt de Tracy seorang Perancis pada tahun 1796. Menurut Tracy ideologi yaitu ‘science of ideas’, suatu program yang diharapkan dapat membawa perubahan institusional dalam masyarakat Perancis. 1. Pandangan Hidup Pandangan Hidup merupakan suatu dasar atau landasan untuk membimbing kehidupan jasmani dan rohani. Pandangan hidup ini sangat bermanfaat bagi kehidupan individu, masyarakat, atau negara. Semua perbuatan, tingkah laku dan aturan serta undang-undang harus merupakan pancaran dari pandangan hidup yang telah dirumuskan. Pandangan h...
Baca selengkapnya