Apa gunanya nilai minimum pada pohon minimax?

Pertimbangkan pohon miniimax untuk masalah pencarian permusuhan. Misalnya, dalam gambar ini (pemangkasan alpha-beta):

Ketika menandai pohon dengan nilai bottom-up, pertama-tama kita melintasi simpul 3 dan menetapkan B. \ max = 3 . Kemudian kita melintasi 12 dan 8 dalam urutan ini, itu akan memastikan B.max = 3 .$[\min,\max]$$3$$B.\max = 3$$12$$8$$B.max = 3$

Tetapi mengapa $B.\min = 3$ ? Apa gunanya nilai itu?

Angka ini (yang sebenarnya benar) digunakan dalam penjelasan algoritma pemangkasan alpha-beta pada pohon minimax. Pemangkasan alfa-beta adalah metode yang digunakan untuk memangkas bagian-bagian pohon minimax dalam masalah pencarian permusuhan. Dalam konteks permainan tic-tac-toe, pohon minimax dimaksudkan untuk memungkinkan komputer untuk mencari melalui ruang semua papan permainan yang mungkin (konfigurasi x dan o) dengan asumsi gerakan pemain optimal. Hal ini memungkinkan komputer untuk membuat langkah yang memberikan hasil terbaik (inilah sebabnya permainan connect-four di komputer Anda sangat sulit dikalahkan!). Untuk deskripsi yang lebih lengkap, saya sangat menyarankan "AI Pendekatan Modern" oleh Stuart dan Norvig (hal 162-170 ish dalam edisi ke-2.).

Sekarang kita telah membersihkan beberapa kebingungan pada algoritma. Pemangkasan alfa-beta mencoba untuk menghindari perluasan sub pohon berdasarkan cara kerja algoritma minimax. Kita tahu bahwa simpul maksimal di tingkat atas akan mengambil nilai terbesar dari semua anak-anaknya. Jadi, simpul menemukan nilai , dan sejauh ini, ini adalah nilai maksimum yang bersedia dilewatkan ke induknya sehingga menempatkan nilai ini di slot MAX. Kemudian ditemukan . Ingat bahwa adalah simpul MIN, jadi ia ingin meminimalkan nilai yang diteruskannya ke induknya, sehingga ia menyimpan nilai dalam slot MAX. Lagi untuk . Ketika telah mencari semua anak-anaknya, ia tahu batas bawah maksimum ($B$$3$$12$$B$$3$$8$$B$$\alpha$) solusi dan solusi batas atas minimum ( ) dari subtree dan mempertahankan nilai-nilai tersebut dalam MIN ( ) dan MAX ( ) (seperti [3, 3]).$\beta$$\alpha$$\beta$

Catatan: min dan maks berlabel dalam gambar BUKAN nilai minimum dan maksimum subtree! Mereka (sangat membingungkan diberi label) batas alpha-beta dari solusi subtree (ingat ini adalah masalah pencarian yang berlawanan).

Berikutnya kita bergerak ke node . Di sini kita menemukan di posisi pertama. Node , yang ingin memilih nilai terendah dari subtreenya sekarang TAHU bahwa induknya tidak akan memilih nilainya karena simpul menemukan nilai yang lebih besar. Oleh karena itu, kita dapat memangkas sisa subtree dan melanjutkan ke .$C$$2$$C$$B$$D$

Akhirnya, untuk menjawab pertanyaan spesifik: Mengapa Min = 3? Nilai untuk (batas bawah maksimum solusi pada simpul ini) dan (batas atas minimum solusi pada simpul ini) dipertahankan pada setiap simpul untuk melakukan pemangkasan. Nilai-nilai ini mengikat kasus-kasus yang mungkin di mana nilai dari node (atau subtree-nya) dapat menjadi bagian dari solusi.$B$$\alpha$$\beta$

Dalam contoh ini, tampaknya tidak berperan, namun cobalah untuk melihat contoh yang lebih rumit (yaitu pohon dengan tinggi> 3) seperti ini dan lihat apakah Anda dapat memahaminya.

Saya tidak dapat melakukan keadilan untuk pemangkasan minimax atau alpha-beta di sini (sebagian besar karena saya belum menggunakannya selama bertahun-tahun), jadi jika Anda benar-benar ingin memahami ini, silakan baca buku tentang AI seperti yang ditulis oleh Stuart dan Norvig (yang halaman wikipedia secara mengejutkan juga tidak memiliki visualisasi).