Algoritma Min Max dalam AI: Komponen, Properti, Keuntungan & Keterbatasan

Algoritma min max di AI, yang dikenal sebagai minimax, adalah algoritma backtracking yang digunakan dalam pengambilan keputusan, teori permainan, dan kecerdasan buatan (AI). Ini digunakan untuk menemukan gerakan optimal seorang pemain, dengan asumsi bahwa lawan juga bermain secara optimal. Komputer dua pemain populer atau game online seperti Catur, Tic-Tac-Toe, Checkers, Go, dll. menggunakan algoritme ini.

Algoritma backtracking digunakan untuk menemukan solusi untuk masalah komputasi sedemikian rupa sehingga kandidat secara bertahap dibangun menuju solusi, satu langkah pada satu waktu. Dan kandidat yang gagal menyelesaikan solusi langsung ditinggalkan.

Bagaimana cara kerjanya?

Dalam algoritma min max di AI, ada dua pemain, Maximiser dan Minimiser. Kedua pemain ini memainkan permainan sebagai salah satu mencoba untuk mendapatkan skor tertinggi atau keuntungan maksimal sementara lawan mencoba untuk mendapatkan skor terendah atau keuntungan minimum.

Setiap papan permainan memiliki skor evaluasi yang ditetapkan untuknya, jadi Maximiser akan memilih nilai maksimal, dan Minimiser akan memilih nilai yang diminimalkan dengan gerakan balasan. Jika Maximiser unggul, maka skor papan akan bernilai positif, dan jika Minimiser unggul, maka skor papan akan bernilai negatif.

Ini didasarkan pada konsep zero-sum game di mana skor utilitas total dibagi antara dua pemain. Dengan demikian, peningkatan skor satu pemain menyebabkan penurunan skor pemain lawan, membuat skor total selalu nol. Jadi, agar satu pemain menang, yang lain harus kalah.

Bergabunglah dengan kursus Sertifikasi Pembelajaran Mesin & AI online dari Universitas top dunia. Hasilkan Master, PGP Eksekutif, atau ACP untuk mempercepat karier Anda.

Memecah algoritme min max di AI

Pohon permainan lengkap dieksplorasi dengan algoritma pencarian mendalam pertama dalam algoritma min max di AI. Ini berjalan sepenuhnya ke simpul terminal pohon dan kemudian mundur melalui pohon.

Tujuannya adalah untuk menemukan langkah terbaik bagi seorang pemain. Hal ini dapat dilakukan dengan memilih node dengan nilai evaluasi terbaik. Pilihan terbaik akan dibuat setelah mengevaluasi semua potensi gerakan lawan. Algoritme melihat ke depan pada semua nilai yang mungkin sampai akhir dan membuat keputusan untuk pemain.

Sumber

Pohon permainan di atas adalah struktur data bersarang yang digunakan untuk mengevaluasi gerakan. Di sini simpul akar adalah Level 0, yang bercabang menjadi Level 1 atau simpul induk, yang selanjutnya bercabang menjadi Level 2 atau simpul anak. Percabangan dapat berlanjut ke banyak level, memiliki potensi level tak terbatas. Level 0 seperti keadaan papan saat ini, sedangkan Level 1 adalah semua kemungkinan keadaan papan tergantung pada langkah selanjutnya.

Jadi, jika Pemain 2 telah bergerak, kita dapat mengasumsikan bahwa simpul akar adalah status papan saat ini, menunggu langkah Pemain 1. Node Level 1 berisi semua kemungkinan gerakan untuk Pemain 1, dan node Level 2 berisi semua kemungkinan gerakan untuk Pemain 2 berdasarkan setiap kemungkinan gerakan Pemain 1.

Pertimbangkan contoh di mana ada empat status akhir dan jalur untuk mencapainya adalah dari akar ke empat daun pohon. Nilai keempat daun tersebut adalah 3, 6 di sebelah kiri dan 4, 7 di sebelah kanan. Giliran Maximiser/Player 1 untuk bergerak. Untuk menjalankan algoritma, asumsi untuk setiap gerakan harus dibuat.

Jika Player 1 memilih ke kiri, Minimiser/Player 2 harus memilih yang paling sedikit antara 3 dan 6, jadi mereka akan memilih 3. Sedangkan jika Player 1 memilih kanan, Player 2 akan memilih 4, yang merupakan minimum dari dua nilai, 4 dan 7. Jadi, Level 1 sekarang memiliki nilai 3 dan 4.

Karena ini adalah giliran Player 1/Maximiser, mereka harus memilih node Level 1 maksimum. Dengan demikian, mereka akan memilih 3. Kemudian pilihan yang optimal adalah ke kiri.

Langkah-langkah untuk algoritma min max dalam AI dapat dinyatakan sebagai berikut:

1. Buat seluruh pohon permainan.
2. Evaluasi skor untuk simpul daun berdasarkan fungsi evaluasi.
3. Mundur dari daun ke simpul akar:

Untuk Maximizer, pilih node dengan skor maksimum.

Untuk Minimizer, pilih node dengan skor minimum.

4. Di simpul akar, pilih simpul dengan nilai maksimum dan pilih langkah masing-masing.

Baca Juga: Ide Proyek Pembelajaran Mesin

Properti algoritma min max di AI

• Algoritme selesai, artinya dalam pohon pencarian yang terbatas, solusi pasti akan ditemukan.
• Ini optimal jika kedua pemain bermain secara optimal.
• Karena Depth-First Search (DFS) untuk pohon permainan, kompleksitas waktu dari algoritma adalah O(b m ), di mana b adalah faktor percabangan dan m adalah kedalaman maksimum pohon.
• Seperti DFS, kompleksitas ruang dari algoritma ini adalah O(bm).

Keuntungan

• Sebuah penilaian menyeluruh dari ruang pencarian dilakukan.
• Pengambilan keputusan dalam AI sangat mudah dilakukan.
• Mesin baru dan pintar dikembangkan dengan algoritma ini.

Keterbatasan

• Karena faktor percabangan yang besar, proses pencapaian tujuan menjadi lebih lambat.
• Evaluasi dan pencarian semua node dan cabang yang mungkin menurunkan kinerja dan efisiensi mesin.
• Kedua pemain memiliki terlalu banyak pilihan untuk diputuskan.
• Jika ada batasan ruang dan waktu, tidak mungkin menjelajahi seluruh pohon.

Tetapi dengan Pemangkasan Alfa-Beta, algoritme dapat ditingkatkan.

Kesimpulan

Artikel ini menjelaskan semua aspek dari algoritma min-max di AI. Pertama, pengenalan teori diberikan dengan contoh di mana itu digunakan, setelah itu ada deskripsi tentang cara kerja algoritma dalam sebuah game.

Algoritme dipecah untuk menjelaskan bagaimana keputusan untuk membuat langkah optimal diambil berdasarkan gerakan dan gerakan balasan para pemain. Properti dari algoritma kemudian terdaftar. Terakhir, keuntungan dan kerugian dari algoritma disediakan.

Jika Anda tertarik untuk mempelajari lebih lanjut tentang pembelajaran mesin, lihat Program PG Eksekutif IIIT-B & upGrad dalam Pembelajaran Mesin & AI yang dirancang untuk para profesional yang bekerja dan menawarkan 450+ jam pelatihan ketat, 30+ studi kasus & tugas, IIIT -B Status Alumni, 5+ proyek batu penjuru praktis & bantuan pekerjaan dengan perusahaan-perusahaan top.