Đề bài
Cắt tỉa alpha-beta cho cùng kết quả với minimax nhưng bỏ qua các nhánh không thể thay đổi kết quả. Nó theo dõi hai cận: alpha là điểm tốt nhất mà MAX đã chắc chắn có, và beta là điểm tốt nhất mà MIN đã chắc chắn có.
Cây trò chơi là cây đầy đủ: mỗi nút trong có branching con và mọi lá ở cùng độ sâu. leaves liệt kê điểm các lá từ trái sang phải. Gốc là nút MAX và các tầng xen kẽ MAX, MIN, MAX, …
Duyệt các con từ trái sang phải, bắt đầu với alpha = -∞ và beta = +∞:
- 'Ở nút MAX, sau mỗi con: best = max(best, value), rồi alpha = max(alpha, best).'
- 'Ở nút MIN, sau mỗi con: best = min(best, value), rồi beta = min(beta, best).'
- Ngay khi alpha ≥ beta, bỏ qua các con còn lại của nút đó.
Hãy viết alpha_beta(leaves, branching).
Đầu vào
leaves: Điểm các lá từ trái sang phải; độ dài là một lũy thừa của branching.
branching: Số con của mỗi nút trong.
Đầu ra
Trả về [value, evaluated]: giá trị minimax của gốc và số lá đã được đánh giá.
Ràng buộc
2 ≤ branching ≤ 5, độ dài leaves = branching^depth với 1 ≤ depth ≤ 8, tối đa 10.000 lá
-1.000 ≤ mỗi lá ≤ 1.000
Ví dụ
Đầu vào:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
Kết quả mong đợi:
expected = [3, 7]Đầu vào:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
Kết quả mong đợi:
std::vector<long long> expected = {3, 7};Đầu vào:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
Kết quả mong đợi:
long[] expected = new long[] {3, 7};Giải thích
Nút MIN thứ nhất xét 3, 12, 8 và trả về 3, nên alpha = 3. Nút MIN thứ hai xét 2, beta = 2 ≤ alpha, nên bỏ qua 4 và 6. Nút thứ ba xét 14, 5, 2 và trả về 2. Giá trị gốc là max(3, 2, 2) = 3 sau 7 trên 9 lá.
Đầu vào:
leaves = [5, 6, 7, 4]
branching = 2
Kết quả mong đợi:
expected = [5, 4]Đầu vào:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
Kết quả mong đợi:
std::vector<long long> expected = {5, 4};Đầu vào:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
Kết quả mong đợi:
long[] expected = new long[] {5, 4};Giải thích
Nút MIN bên trái đánh giá 5 và 6 rồi trả về 5, nên alpha = 5. Nút MIN bên phải đánh giá 7 (beta = 7), rồi 4 (beta = 4 ≤ 5). Cả 4 lá đều được đánh giá và giá trị là 5.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Duyệt cây trò chơi từ trái sang phải, đồng thời giữ các cận tốt nhất đã chắc chắn cho MAX và MIN.
Gợi ý 2
Dùng tìm kiếm minimax đệ quy, cập nhật cận hiện tại sau mỗi con và dừng khi hai cận cắt nhau.
Gợi ý 3
Lưu ý chỉ đếm các lá thực sự được thăm, và gốc bắt đầu là nút MAX.
Độ phức tạp mong đợi
O(b^d) time in the worst case, O(d) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.