Trung bình 1 đã giải Tỷ lệ chấp nhận 100.0%

Cắt tỉa Alpha-Beta

Đánh giá cây trò chơi bằng minimax có cắt tỉa alpha-beta và đếm xem việc tìm kiếm thực sự xét bao nhiêu lá.

Bạn sẽ học được gì

  • Theo dõi cận alpha và beta
  • Bỏ qua nhánh không thể thay đổi kết quả
  • Đo lượng công việc mà cắt tỉa tiết kiệm

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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á.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 1,183 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.