un

guest
1 / ?
back to lessons

Faktor Cabang & Hitungan Node

Pohon permainan menggambarkan setiap pola kemungkinan serangkaian gerakan dari posisi awal. Setiap node mewakili posisi papan. Setiap edgenya mewakili satu gerakan legal. Struktur pohon menentukan apakah pencarian tetap mungkin.

Parameter Kunci

Faktor Cabang b: jumlah gerakan legal yang tersedia pada posisi tipikal.

Kedalaman d: jumlah plies (setengah gerakan) untuk mencari maju.

Hitungan node pada kedalaman d: b^d

Total node di seluruh kedalaman: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)

Untuk b dan d besar, totalnya ≈ b^d (dipengaruhi oleh level daun).

Tic-Tac-Toe 4×4×4

Pohon permainan penuh: b ≈ 64 (kotak legal), d = 64 (gerakan total). Hitungan node penuh ≈ 64^64 ≈ 10^115. Universo yang teramati mengandung sekitar 10^80 atom. Pencarian brute-force tidak mungkin.

Pohon Permainan & Pengurangan Alpha-Beta

Menghitung Ukuran Pohon

Catur memberikan angka yang lebih realistis. Faktor cabang rata-rata b ≈ 35. Pencarian 6-ply (3 gerakan setiap sisi) membutuhkan sekitar 35^6 node.

Hitung jumlah node daun untuk pencarian catur dengan kedalaman d = 6 plies dengan faktor cabang b = 35. Kemudian hitung yang sama untuk d = 10 plies. Tunjukkan kedua perhitungan secara eksplisit.

Pengurangan Alpha-Beta: Mengurangi Eksponen

Pemangkasan alpha-beta menghapus cabang-cabang yang tidak dapat mempengaruhi hasil minimax. Insight kunci: jika Anda sudah tahu satu cabang memberikan nilai V, Anda dapat memangkas cabang saudara yang nilai provably jatuh di bawah V (untuk pemain maksimum) atau di atas V (untuk pemain minimum).

Geometri Terbaik

Dengan urutan gerak optimal (gerak terbaik dicari terlebih dahulu), alpha-beta mengurangi faktor cabang efektif dari b menjadi √b. Kekuatan pencarian efektif ganda untuk node anggaran yang sama:

Pencarian penuh: b^d node

Alpha-beta kasus terbaik: b^(d/2) node

Contoh: b=35, d=6. Penuh: 35^6 ≈ 1,84 × 10^9. Alpha-beta: 35^3 = 42,875. Faktor pengurangan: ~43,000.

Pada praktiknya, urutan gerak tidak sempurna. Pengurangan tipikal: b^(d×0,75) — faktor cabang sebanding ≈ b^0,75.

Untuk mesin catur dengan b = 35 dan d = 8 gerak, hitung jumlah node di bawah: (1) pencarian minimax penuh, (2) pemangkasan alpha-beta sempurna (kasus terbaik). Apa faktor pengurangan? Tunjukkan semua perhitungan.

Dualitas Center-Corner

Hamming mencatat dualitas geometris pada kubus 4×4×4: ada inversi yang mengirim posisi sudut ke posisi pusat (kubus inner 2×2×2) dan sebaliknya, sambil mempertahankan semua 76 garis kemenangan.

Menghitung Garis Kemenangan Melalui Posisi

Pada kubus 4×4×4, posisi berbeda dalam jumlah garis kemenangan yang melewati mereka:

Posisi sudut: 7 garis masing-masing (4 diagonal wajah, 2 garis sisi, 1 diagonal ruang)

Posisi pusat-sisi: 4 garis masing-masing

Posisi pusat-wajah: 6 garis masing-masing

Posisi pusat-badan (inner 2×2×2): 7 garis masing-masing

Dualitas memetakan sudut (7 garis) ke pusat-badan (7 garis). Kedua set membentuk 'spot panas.'

Mengapa Spot Panas Penting Geometris

Seorang pemain yang mengendalikan lebih banyak posisi dengan hitungan garis tinggi mengendalikan lebih banyak garis kemenangan potensial. Ini adalah argumen geometris langsung: optimalisasi penutupan garis mengarahkan pemilihan gerakan tanpa pencarian apa pun.

Kubus 4×4×4 memiliki 76 garis menang total dan 64 posisi. 8 sudut masing-masing berada pada 7 garis, posisi pusat tubuh masing-masing berada pada 7 garis, 24 posisi pusat wajah masing-masing berada pada 6 garis, dan 24 posisi sisi masing-masing berada pada 4 garis. Verifikasi: apakah hitungan ini konsisten? Hitung jumlah total (posisi, garis) kejadian dari kedua sisi: dengan menghitung total dari kedua sisi: dengan mengjumlahkan over posisi, dan terpisah dengan menghitung 4 ujung per garis. Apakah dua total setuju?

Fungsi Evaluasi

Setiap program permainan membutuhkan fungsi evaluasi: sebuah fungsi yang menerjemahkan keadaan papan menjadi nilai numerik (positif = bagus untuk pemain maksimum, negatif = bagus untuk pemain minimaks). Fungsi evaluasi memberikan kondisi batas pada daun pohon pencarian.

Fungsi Evaluasi Linier

Fungsi evaluasi linier mengasignkan bobot w_i kepada setiap fitur f_i dari posisi:

E(posisi) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n

Untuk 4×4×4 tic-tac-toe: fitur mungkin termasuk garis terbuka yang dikendalikan, posisi di kotak persegi dengan jumlah garis tinggi, ancaman kerumitan. Untuk catur: hitungan material, kontrol pusat, keamanan raja, struktur pion.

Ini adalah fungsi linier dalam ruang fitur — hiperpola di ℝ^n. Dua posisi dengan nilai fitur yang sama mendapatkan evaluasi yang sama meskipun berbeda dalam segala hal lain. Geometri fungsi evaluasi menentukan apa yang program 'lihat.'

Program catur Samuel ditingkatkan dengan mengatur ulang vektor bobot w — turun naik gradien dalam ruang fungsi evaluasi linier.

Fungsi evaluasi 4×4×4 tic-tac-toe yang sederhana menggunakan dua fitur: (1) f_1 = jumlah garis terbuka Anda (garis di mana Anda memiliki potongan dan lawan memiliki tidak ada), (2) f_2 = jumlah garis terbuka lawan. Evaluasi: E = w_1 × f_1 − w_2 × f_2. Jika w_1 = 2 dan w_2 = 3, hitung E untuk posisi di mana Anda memiliki 12 garis terbuka dan lawan memiliki 8. Lalu: jika E > 0 berarti posisi menguntungkan Anda, apa yang dikatakan hasil ini tentang posisi?

Geometri & Batas Formalisasi

Pohon permainan memiliki struktur geometri yang bersih: pertumbuhan eksponensial pada kedalaman d, dapat diringkas menjadi b^(d/2) oleh alpha-beta, dapat diringkas lebih lanjut dengan membatasi posisi yang bernilai tinggi (titik panas mengurangi b efektif). Fungsi evaluasi menentukan hiperpola dalam ruang fitur.

Semua ini bersih, tepat, dan lengkap secara formal. Ini menggambarkan pusat masalah bermain game — region di mana struktur matematis memberikan petunjuk yang jelas.

Percabangan batas — di mana harus beralih dari penerapan aturan ke eksplorasi, kapan harus menukar keuntungan posisi untuk kesempatan taktis, bagaimana mengenali pola yang muncul di luar fungsi evaluasi — tidak dapat di formalisasi. Pengetahuan tak tersurat Hamming hidup di batas ini.

Geometri memungkinkan Anda menghitung seberapa banyak pencarian yang bisa Anda tanggung. Ini tidak memberitahu Anda apa yang harus dicari.

Refleksikan geometri yang dibahas dalam les ini. Formalisme pohon permainan (b^d node, pengurangan alpha-beta menjadi b^(d/2), fungsi evaluasi linear) memberikan deskripsi yang tepat tentang bagian yang *terukur* dari bermain game. Di mana geometri mengalami kegagalan - dan apa properti kecerdasan bermain game yang berada di luar model geometri? Berikan jawaban yang khusus, bukan observasi umum.