Algoritma Minimax

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.

 

Gambar 2.10 Contoh Representasi Cara Kerja pada Algoritma Minimax

(Coppin, 2004)

Gambar 2.10 menunjukkan proses pencarian dimulai dari jalur paling kiri terlebih dahulu, sehingga DFS akan menelusuri simpul paling kiri bawah hingga paling kanan. DFS akan menelusuri simpul paling kiri bawah yaitu 5. Nilai 5 disimpan sebagai nilai maksimum sementara karena berada di level max, kemudian DFS melakukan backtrack dan menelusuri simpul yang bertetangga dengan simpul 5 yaitu simpul 2. Karena nilai 5 lebih besar dari nilai 2, maka nilai 2 tidak disimpan. Lalu DFS akan melakukan backtrack ke level min sehingga nilai 5 yang diperoleh akan disimpan sebagai nilai minimum sementara. Untuk simpul 1 dan 3, nilai 3 yang akan disimpan karena merupakan nilai maksimum di level max. Saat mencapai level min, sudah ada nilai minimum sementara yaitu 5, namun karena nilai 3 lebih kecil daripada nilai 5, maka nilai 5 akan digantikan dengan nilai 3. Nilai 3 akan disimpan sebagai nilai maksimum sementara di level paling atas karena merupakan level max. Lalu penelusuran jalur kanan akan dilakukan dengan cara yang sama seperti penelusuran jalur kiri sehingga diperoleh nilai 6. Karena nilai maksimum sementara pada level paling atas adalah nilai 3, maka nilai 3 akan digantikan dengan nilai 6 karena nilai 6 lebih besar daripada nilai 3. Dengan demikian, jalur yang akan dipilih menggunakan algoritma minimax adalah jalur sebelah kanan, karena level atas merupakan level max sehingga didapat nilai 6 sedangkan jika memilih jalur kiri, hanya akan didapat nilai 3.

Read More

Algoritma Pencarian

hem....sudah ada yang tahu tentang algoritma??? apa itu algoritma ?? berikut ini jawabannya

 Algoritma Pencarian

 Pencarian adalah suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Ruang keadaan merupakan suatu ruang yang berisi semua keadaan yang mungkin dari keadaan awal (initial state) menuju keadaan tujuan (goal state) (Sigiro, 2011). Ruang keadaan ini dapat digambarkan dengan menggunakan algoritma pencarian. Pada umumnya, algoritma pencarian bekerja dengan mengembangkan berbagai kemungkinan keadaan (state) yang mungkin dicapai dari keadaan sekarang (current state). Keadaan dalam proses pencarian biasa disebut dengan istilah simpul (node). Kumpulan simpul akan terus dikembangkan sampai ditemukan simpul yang merupakan keadaan tujuan atau bila sudah tidak ada lagi simpul yang dikembangkan. Rangkaian kumpulan simpul dari keadaan awal sampai keadaan  tujuan yang terbaiklah yang akhirnya diambil menjadi solusi.

Algoritma pencarian dikatakan penting untuk perencanaan dalam sebuah permainan, karena algoritma pencarian akan menuntun pemain dalam menyelesaikan permainan. Menurut Kusumadewi (2003), teknik pencarian terbagi dua yaitu pencarian buta (blind search) dan pencarian heuristik (heuristic search).

1.        Pencarian Buta (Blind Search).

Pencarian buta adalah pencarian solusi tanpa adanya informasi yang mengarahkan pencarian untuk mencapai keadaan tujuan dari keadaan sekarang. Informasi yang ada hanyalah definisi keadaan tujuan itu sendiri, sehingga algoritma hanya dapat mengenali keadaan tujuan bila menjumpainya. Dengan ketiadaan informasi, maka pencarian buta  dalam kerjanya memeriksa serta mengembangkan simpul dilakukan secara tidak terarah. Teknik pencarian ini kurang efisien untuk kebanyakan kasus karena banyaknya simpul yang dikembangkan. Beberapa algoritma yang termasuk pencarian buta antara lain adalah Pencarian Melebar Pertama (Breadth First Search) dan Pencarian Mendalam Pertama (Depth First Search).

2.        Pencarian Heuristik (Heuristic Search)

Kata heuristik berasal dari sebuah kata kerja Yunani heuriskein, yang berarti mencari atau menemukan. Heuristik juga merupakan suatu strategi untuk melakukan proses pencarian ruang masalah secara selektif, yang memandu proses pencarian yang disepanjang jalur yang memiliki kemungkinan sukses paling besar (Kusrini, 2006). Selain itu dalam dunia pemrograman, kata heuristik ini diartikan sebagai suatu proses yang mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu tepat (Suyanto, 2011).

Di dalam mempelajari algoritma pencarian ini, kata heuristik diartikan sebagai suatu fungsi yang memberikan suatu nilai berupa biaya perkiraan (estimated cost) dari suatu solusi yang membantu algoritma. Berbeda dengan pencarian buta, pencarian heuristik mempunyai informasi tentang biaya (cost) untuk mencapai keadaan tujuan dari keadaan sekarang. Dengan informasi tersebut, pencarian heuristik dapat melakukan pertimbangan untuk mengembangkan atau memeriksa simpul yang mengarah ke keadaan tujuan.

Setiap heuristik memiliki keunggulan dan kelemahan masing-masing sehingga pemilihan heuristik juga sangat penting dalam penyelesaian suatu masalah. Semakin bagus heuristik yang dipakai, semakin cepat dan akurat pula solusi yang didapat. Beberapa algoritma pencarian yang yang termasuk pencarian heuristik adalah Pembangkitan dan Pengujian (Generate and Test), Pencarian Terbaik Pertama (Best First Search), Algoritma Greedy Search, Algoritma A* (A Star), dan Pendakian Bukit (Hill Climbing Search), Algoritma Minimax, dan sebagainya.

Daftar pustaka :

Kusumadewi, Sri. 2003. Artificial Intelligence Teknik dan Aplikasinya. Yogyakarta: Graha Ilmu.  

Suyanto. 2011. Artificial Intelligence. Bandung: Informatika.

Read More