un — Geometri Penalaran Mesin: I

un

tamu

1 / ?

kembali ke pelajaran

Faktor Percabangan & Jumlah Node

Pohon permainan memodelkan setiap kemungkinan urutan langkah dari posisi awal. Setiap node mewakili keadaan papan. Setiap tepi mewakili satu gerakan yang sah. Struktur pohon menentukan apakah pencarian tetap dapat ditangani.

Parameter Kunci

Faktor percabangan b: jumlah gerakan yang sah tersedia pada posisi umum.

Kedalaman d: jumlah plies (setengah-gerakan) untuk melihat ke depan.

Jumlah node pada kedalaman d: b^d

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

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

Tic-Tac-Toe 4×4×4

Pohon permainan lengkap: b ≈ 64 (kotak legal), d = 64 (total gerakan). Jumlah node lengkap ≈ 64^64 ≈ 10^115. Alam semesta yang dapat diamati mengandung kira-kira 10^80 atom. Pencarian brute-force secara fisik tidak mungkin.

Game Tree & Alpha-Beta Pruning

Menghitung Ukuran Pohon

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

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

Pemangkasan Alfa-Beta: Mengurangi Eksponen

Pemangkasan alfa-beta menghilangkan subtree yang tidak dapat mempengaruhi hasil minimax. Wawasan utama: jika Anda sudah tahu satu cabang memberikan nilai V, Anda dapat memotong cabang saudara mana pun yang nilainya jelas jatuh di bawah V (untuk pemain yang memaksimalkan) atau di atas V (untuk pemain yang meminimalkan).

Geometri Kasus Terbaik

Dengan pengurutan langkah yang optimal (langkah terbaik dicari terlebih dahulu), alfa-beta mengurangi faktor percabangan efektif dari b menjadi √b. Kedalaman pencarian secara efektif berlipat ganda untuk anggaran node yang sama:

Pencarian lengkap: b^d node

Kasus terbaik alfa-beta: b^(d/2) node

Contoh: b=35, d=6. Lengkap: 35^6 ≈ 1,84 × 10^9. Alfa-beta: 35^3 = 42.875. Faktor pengurangan: ~43.000.

Dalam praktik, pengurutan gerakan tidak sempurna. Pengurangan umum: b^(d×0,75) — faktor percabangan setara ≈ b^0,75.

Untuk mesin catur dengan b = 35 & d = 8 plies, hitung jumlah node di bawah: (1) pencarian minimax lengkap, (2) pemangkasan alfa-beta sempurna (kasus terbaik). Berapa faktor pengurangannya? Tunjukkan semua perhitungan.

Dualitas Pusat-Sudut

Hamming mencatat dualitas geometri dalam kubus 4×4×4: ada inversi yang mengirim 8 posisi sudut ke 8 posisi pusat (kubus 2×2×2 bagian dalam) & sebaliknya, sambil mempertahankan semua 76 garis menang.

Menghitung Garis Melalui Posisi

Dalam kubus 4×4×4, posisi berbeda dalam jumlah garis menang yang melewatinya:

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

Posisi pusat tepi: 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-spot panas.'

Mengapa Spot-Spot Panas Penting Secara Geometri

Pemain yang mengendalikan lebih banyak posisi dengan jumlah garis tinggi mengendalikan lebih banyak garis menang potensial. Ini adalah argumen geometri langsung: maksimalisasi cakupan garis memandu pemilihan gerakan tanpa pencarian apa pun.

Kubus 4×4×4 memiliki 76 garis menang total & 64 posisi. 8 sudut masing-masing terletak pada 7 garis, 8 posisi pusat-badan masing-masing terletak pada 7 garis, 24 posisi pusat-wajah masing-masing terletak pada 6 garis, & 24 posisi tepi masing-masing terletak pada 4 garis. Verifikasi: apakah perhitungan ini konsisten? Hitung total jumlah insiden (posisi, garis) dari kedua sisi: dengan menjumlahkan posisi, & terpisah dengan menghitung 4 endpoint per garis. Apakah dua total setuju?

Fungsi Evaluasi

Setiap program pemain permainan memerlukan fungsi evaluasi: fungsi yang memetakan keadaan papan ke nilai numerik (positif = baik untuk pemain yang memaksimalkan, negatif = baik untuk pemain yang meminimalkan). Fungsi evaluasi menyediakan kondisi batas pada daun pohon pencarian.

Fungsi Evaluasi Linear

Fungsi evaluasi linear menetapkan berat w_i ke setiap fitur f_i dari posisi:

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

Untuk tic-tac-toe 4×4×4: fitur mungkin termasuk garis terbuka yang dikendalikan, posisi di kotak dengan jumlah garis tinggi, garpu yang diancam. Untuk catur: penghitungan material, kontrol pusat, keselamatan raja, struktur pion.

Ini adalah fungsi linear dalam ruang fitur — hyperplane di ℝ^n. Dua posisi dengan nilai fitur yang sama mendapatkan evaluasi yang sama terlepas dari semua perbedaan lainnya. Geometri fungsi evaluasi menentukan apa yang 'dilihat' program.

Program checker Samuel meningkat dengan menyesuaikan vektor berat w — gradient descent dalam ruang fungsi evaluasi linear.

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

Geometri & Batas Formalisasi

Pohon permainan memiliki struktur geometri yang bersih: pertumbuhan eksponensial pada kedalaman d, dapat dikurangi menjadi b^(d/2) oleh alfa-beta, lebih jauh dapat dikurangi dengan membatasi pada posisi bernilai tinggi (spot-spot panas mengurangi b efektif). Fungsi evaluasi mendefinisikan hyperplane dalam ruang fitur.

Semua ini bersih, presisi, formalmente lengkap. Ini menggambarkan pusat dari masalah bermain permainan — wilayah di mana struktur matematika memberikan panduan yang jelas.

Batas — kapan beralih dari penerapan aturan ke eksplorasi, kapan menukar keuntungan posisional untuk peluang taktis, bagaimana mengenali pola yang muncul di luar fungsi evaluasi — menolak formalisasi ini. Pengetahuan implisit Hamming hidup di batas itu.

Geometri memungkinkan Anda menghitung berapa banyak pencarian yang dapat Anda mampu. Ini tidak mengatakan apa yang harus dicari.

Refleksikan pada geometri yang tercakup dalam pelajaran ini. Formalisme pohon permainan (node b^d, pengurangan alfa-beta menjadi b^(d/2), fungsi evaluasi linear) memberikan deskripsi presisi tentang bagian *dapat ditangani* dari bermain permainan. Di mana geometri menemui kendala — & properti apa dari kecerdasan bermain permainan yang terletak di luar model geometri? Berikan jawaban spesifik, bukan pengamatan umum.