Branching Factor & Số Nút
Cây trò chơi mô hình hóa mọi chuỗi nước đi có thể từ một vị trí bắt đầu. Mỗi nút biểu thị một trạng thái bàn cờ. Mỗi cạnh biểu thị một nước đi hợp pháp. Cấu trúc cây quyết định xem tìm kiếm có vẫn khả thi hay không.
Các Thông số Chính
Branching factor b: số nước đi hợp pháp có sẵn tại một vị trí điển hình.
Depth d: số ply (nửa nước đi) để tìm kiếm trước.
Số nút ở depth d: b^d
Tổng số nút trên tất cả depths: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Đối với b & d lớn, tổng ≈ b^d (được chi phối bởi mức leaf).
Tic-Tac-Toe 4×4×4
Cây trò chơi đầy đủ: b ≈ 64 (ô hợp pháp), d = 64 (tổng nước đi). Số nút đầy đủ ≈ 64^64 ≈ 10^115. Vũ trụ có thể quan sát được chứa khoảng 10^80 nguyên tử. Tìm kiếm brute-force là không thể về mặt vật lý.
Tính Kích Thước Cây
Chess cung cấp những con số thực tế hơn. Branching factor trung bình b ≈ 35. Tìm kiếm 6-ply (3 nước đi mỗi bên) đòi hỏi khoảng 35^6 nút.
Alpha-Beta Pruning: Giảm Exponent
Alpha-beta pruning loại bỏ các cây con không thể ảnh hưởng đến kết quả minimax. Công cụ chính là: nếu bạn đã biết một nhánh cho giá trị V, bạn có thể cắt bất kỳ nhánh anh em nào có giá trị chứng minh rơi dưới V (cho người chơi tối đa hóa) hoặc trên V (cho người chơi tối thiểu hóa).
Best-Case Geometry
Dưới sắp xếp nước đi tối ưu (nước đi tốt nhất được tìm kiếm trước), alpha-beta giảm branching factor hiệu dụng từ b thành √b. Depth tìm kiếm tăng gấp đôi cho cùng ngân sách nút:
Tìm kiếm đầy đủ: b^d nút
Alpha-beta best case: b^(d/2) nút
Ví dụ: b=35, d=6. Đầy đủ: 35^6 ≈ 1.84 × 10^9. Alpha-beta: 35^3 = 42,875. Hệ số giảm: ~43,000.
Trong thực tế, sắp xếp nước đi không hoàn hảo. Giảm điển hình: b^(d×0.75) — branching factor hiệu dụng ≈ b^0.75.
Center-Corner Duality
Hamming chỉ ra một duality hình học trong lập phương 4×4×4: có một inversion gửi 8 vị trí góc đến 8 vị trí trung tâm (lập phương 2×2×2 bên trong) & ngược lại, trong khi vẫn giữ tất cả 76 đường winning.
Đếm Dòng Qua một Vị trí
Trong lập phương 4×4×4, vị trí khác nhau về bao nhiêu đường winning đi qua chúng:
Vị trí góc: 7 dòng mỗi (4 đường chéo mặt, 2 đường cạnh, 1 đường chéo không gian)
Vị trí edge-center: 4 dòng mỗi
Vị trí face-center: 6 dòng mỗi
Vị trí body-center (lập phương 2×2×2 bên trong): 7 dòng mỗi
Duality ánh xạ góc (7 dòng) đến body-centers (7 dòng). Cả hai tập hợp tạo thành 'hot spots.'
Tại sao Hot Spots Quan trọng Hình học
Một người chơi kiểm soát nhiều vị trí high-line-count kiểm soát nhiều đường winning tiềm năng. Đây là một lập luận hình học trực tiếp: tối đa hóa line coverage hướng dẫn chọn nước đi mà không bất kỳ tìm kiếm nào.
Evaluation Functions
Mọi chương trình chơi trò chơi đều cần một evaluation function: một hàm ánh xạ trạng thái bàn cờ thành giá trị số (dương = tốt cho người chơi tối đa hóa, âm = tốt cho người chơi tối thiểu hóa). Evaluation function cung cấp điều kiện biên ở lá của cây tìm kiếm.
Linear Evaluation Functions
Một linear evaluation function gán trọng số w_i cho mỗi feature f_i của vị trí:
E(position) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Đối với tic-tac-toe 4×4×4: các feature có thể bao gồm dòng mở được kiểm soát, vị trí trong hình vuông high-line-count, forks bị đe dọa. Đối với chess: đếm tài liệu, điều khiển trung tâm, an toàn vua, cấu trúc quân tốt.
Đây là một hàm tuyến tính trong không gian feature — một hyperplane trong ℝ^n. Hai vị trí có cùng giá trị feature nhận được cùng một đánh giá bất kể tất cả các khác biệt khác. Hình học của evaluation function xác định những gì chương trình 'thấy.'
Chương trình checker của Samuel được cải thiện bằng cách điều chỉnh vector trọng số w — gradient descent trong không gian của linear evaluation functions.
Hình học & Biên giới của Hình thức hóa
Cây trò chơi có một cấu trúc hình học sạch sẽ: tăng trưởng exponential ở depth d, có thể giảm xuống b^(d/2) bằng alpha-beta, tiếp tục có thể giảm bằng cách giới hạn trong các vị trí high-value (hot spots giảm effective b). Evaluation function xác định một hyperplane trong feature space.
Tất cả điều này là sạch sẽ, chính xác, hoàn chỉnh về mặt hình thức. Nó mô tả trung tâm của vấn đề chơi trò chơi — khu vực nơi cấu trúc toán học cung cấp hướng dẫn rõ ràng.
Biên giới — nơi chuyển từ quy tắc áp dụng thành khám phá, khi nào thay đổi lợi thế vị trí cho cơ hội kỹ thuật, cách nhận ra các pattern mới nổi vượt ra ngoài evaluation function — chống lại sự hình thức hóa này. Kiến thức ngầm của Hamming tồn tại ở biên giới đó.
Hình học cho phép bạn tính toán bao nhiêu tìm kiếm bạn có thể chi trả. Nó không cho bạn biết cái gì để tìm kiếm.