ai-096Đọc toàn bộ đề miễn phí
Bộ Chọn Nhánh Cây Tìm Kiếm Monte Carlo PUCT (AlphaGo Zero / AlphaZero)
a* = argmaxa ∈ A [ Q(s, a) + U(s, a) ]
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: markov-decision-process-value-iteration.
Nội dung đề bài
Mục tiêu kiến thức
- Trong cờ vua, cờ vây và bài toán suy luận phức tạp (như mô hình OpenAI o1), việc chỉ dùng mạng nơ-ron đánh giá tức thời là không đủ. Hệ thống cần "suy nghĩ/tìm kiếm cây" (Search / Reasoning at Test-Time).
- Thuật toán AlphaZero (Silver et al. 2017) sử dụng công thức PUCT (Polynomial Upper Confidence Trees) tại mỗi nút cha s để cân bằng giữa Khai thác (Exploitation - chọn hành động có điểm Q cao) và Thám hiểm (Exploration - thử hành động có xác suất tiên nghiệm cao nhưng chưa được thăm nhiều):
a* = argmaxa ∈ A [ Q(s, a) + U(s, a) ] Trong đó số hạng thám hiểm Upper Confidence Bound là: U(s, a) = cpuct · P(s, a) · √(N(s))1 + N(s, a)
- N(s) = ∑b N(s, b): Tổng số lượt thăm nút cha s.
- N(s, a): Số lượt thăm nhánh con hành động a.
- P(s, a): Xác suất tiên nghiệm do mạng Policy Network πθ(a | s) dự đoán ban đầu.
- Q(s, a): Giá trị trung bình ước lượng của nhánh con từ mạng Value Network hoặc các mô phỏng trước.
- cpuct: Hằng số điều khiển mức độ thám hiểm (thường cpuct ∈ [1.0, 2.5]).
Yêu cầu
Viết hàm:
def select_best_puct_action(
node_visit_count: int,
child_visit_counts: np.ndarray,
child_prior_probs: np.ndarray,
child_q_values: np.ndarray,
c_puct: float = 1.0
) -> int:
passnode_visit_count: Số nguyên tổng lượt thăm N(s).child_visit_counts: Mảng 1D số nguyên/float(A,)chứa N(s, a).child_prior_probs: Mảng 1D float(A,)chứa P(s, a) (tổng bằng 1.0).child_q_values: Mảng 1D float(A,)chứa Q(s, a).- Trả về số nguyên chỉ số hành động a* = argmaxa (Q(s, a) + U(s, a)). Nếu có nhiều hành động hòa điểm, chọn hành động có chỉ số nhỏ nhất.
Input
- Hàm
select_best_puct_action(node_visit_count,child_visit_counts,child_prior_probs,child_q_values,c_puct): Các tham số đầu vào chứa dữ liệu Tensor/mảng NumPy hoặc giá trị siêu tham số tương ứng.
Output
- Hàm
select_best_puct_action: Trả về kết quả kiểuinttheo đúng đặc tả kỹ thuật và kích thước quy định.
Ràng buộc
- Thời gian chạy tối đa: 2000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
N_parent = 100
N_child = np.array([100.0, 0.0, 0.0])
prior = np.array([0.2, 0.6, 0.2])
Q = np.array([0.8, 0.5, 0.1])
c_puct = 2.0
best = select_best_puct_action(N_parent, N_child, prior, Q, c_puct=c_puct)Output
1Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
Ví dụ 2
Input
'Test that denominator is N_child + 1, not N_child.\n \n With N_child = [1, 2, 3] (all > 0), wrong_01 (no +1) gives different PUCT scores.\n We choose Q/prior values where the +1 changes the ranking.\n \n Correct PUCT (with +1):\n N_parent = 4, c_puct = 5.0, prior = [0.9, 0.1, 0.1], Q = [0.0, 0.5, 0.0]\n sqrt_N = sqrt(4) = 2.0\n U[0] = 5 * 0.9 * 2/(1+1) = 5 * 0.9 * 1.0 = 4.5 -> score = 4.5\n U[1] = 5 * 0.1 * 2/(2+1) = 5 * 0.1 * 0.667 = 0.333 -> score = 0.5 + 0.333 = 0.833\n U[2] = 5 * 0.1 * 2/(3+1) = 5 * 0.1 * 0.5 = 0.25 -> score = 0.25\n Winner: action 0\n \n Wrong PUCT (without +1):\n U[0] = 5 * 0.9 * 2/1 = 9.0 -> score = 9.0\n U[1] = 5 * 0.1 * 2/2 = 0.5 -> score = 1.0\n Winner: action 0 (same! so need different params)\n \n Try: N_child=[1,1,1], prior=[0.1, 0.8, 0.1], Q=[0.0, 0.0, 0.0]\n Correct (+1): U = c * prior * sqrt(N) / 2 -> all proportional to prior -> winner = 1\n Wrong (no +1): U = c * prior * sqrt(N) / 1 -> still proportional to prior -> winner = 1\n \n The real distinguisher: use visited nodes where +1 changes the relative U values.\n N_child=[1,2], prior=[0.5,0.5], Q=[0.0, 0.0], N_parent=4, c=1\n Correct: U[0]=1*0.5*2/2=0.5, U[1]=1*0.5*2/3=0.333 -> winner=0\n Wrong: U[0]=1*0.5*2/1=1.0, U[1]=1*0.5*2/2=0.5 -> winner=0 (same)\n \n Better: N_child=[3,1], Q=[0, 0.4], N_parent=9, prior=[0.3,0.1], c=3\n Correct: U[0]=3*0.3*3/4=0.675, U[1]=3*0.1*3/2=0.45 -> scores: [0.675, 0.85] -> winner=1\n Wrong: U[0]=3*0.3*3/3=0.9, U[1]=3*0.1*3/1=0.9 -> tie -> argmax=0 -> winner=0 or 1\n Need: wrong picks 0, correct picks 1.\n \n Final design:\n N_child=[4,1], Q=[0.5, 0.2], N_parent=16, prior=[0.1, 0.8], c=2\n sqrt_N = 4\n Correct: U[0]=2*0.1*4/5=0.16, score=0.66; U[1]=2*0.8*4/2=3.2, score=3.4 -> winner=1\n Wrong: U[0]=2*0.1*4/4=0.2, score=0.7; U[1]=2*0.8*4/1=6.4, score=6.6 -> winner=1\n \n # Need wrong_01 to pick action 0:\n N_child=[1,4], Q=[0.6, 0.0], N_parent=4, prior=[0.5, 0.5], c=1\n sqrt_N=2\n Correct: U[0]=1*0.5*2/2=0.5, score=1.1; U[1]=1*0.5*2/5=0.2, score=0.2 -> winner=0\n Wrong: U[0]=1*0.5*2/1=1.0, score=1.6; U[1]=1*0.5*2/4=0.25, score=0.25 -> winner=0\n \n Key insight: use N_child where +1 causes a denominator jump from 1->2.\n N_child=[0, 0, ...] but with 0 in denominator -> inf for wrong but finite for correct.\n The existing test already covers this case (wrong_01 gives inf which accidentally picks correct answer).\n \n Actual failure mode of wrong_01: when N_child has 0s, division by 0 gives inf, \n which accidentally gives the right answer (most explored node is avoided).\n The test_puct_denominator_precision test below creates a scenario where the specific\n value of +1 changes which action wins.\n '
N_parent = 9
N_child = np.array([2.0, 1.0])
prior = np.array([0.1, 0.9])
Q = np.array([0.8, 0.0])
c_puct = 3.0
best = select_best_puct_action(N_parent, N_child, prior, Q, c_puct=c_puct)Output
1Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.