Tìm kiếm cây Monte Carlo
Tìm kiếm cây Monte Carlo
Khi cây quá lớn để duyệt và bạn cũng không có hàm lượng giá nào đáng tin, còn một đường: chơi thử tới cùng thật nhiều lần, rồi tin vào thống kê. Đây là chỗ nó chạy được, và chỗ nó nói dối.
Bài tìm kiếm đối kháng dừng lại ở hai chỗ hẹp, và chương này bắt đầu từ đúng hai chỗ đó. Thứ nhất, minimax tốn cỡ b^m, alpha-beta may mắn nhất cũng còn b^(m/2), nên với cờ vây thì cả hai đều vô vọng. Thứ hai, cách vá thông thường là cắt ở độ sâu giới hạn rồi gọi một hàm lượng giá Eval(s), mà hàm ấy phải do con người nghĩ ra: với cờ vua người ta đếm quân theo trọng số hậu 9, xe 5, tượng 3; với cờ vây thì suốt mấy chục năm không ai viết được hàm nào dùng nổi. Nhìn một bàn cờ vây giữa trận, ngay cả kỳ thủ chuyên nghiệp cũng khó nói thành công thức vì sao bên đen đang hơn.
Tìm kiếm cây Monte Carlo bỏ luôn hàm lượng giá. Thay vì hỏi "thế này tốt bao nhiêu", nó hỏi "nếu từ đây cứ chơi bừa tới hết trận thì bên ta thắng bao nhiêu phần trăm". Câu trả lời rất nhiễu, nhưng nó có ba tính chất mà Eval không có: không cần ai thiết kế, không cần biết gì về trò chơi ngoài luật, và chỉ cần chạy thêm là nó chính xác thêm.
Thử ngay: bốn nhịp trên một thế Nim
Trò chơi dưới đây là Nim, nhỏ đủ để minimax duyệt hết nên luôn có sẵn đáp án đúng để đối chiếu. Luật gọn: mỗi lượt lấy bao nhiêu hạt cũng được nhưng chỉ từ một đống, ai lấy hạt cuối cùng thì thắng. Thế mở bài là hai đống 2 và 4 hạt.
Hãy làm ba việc theo thứ tự. Kéo lượt đang mổ xẻ để xem bốn nhịp của từng lượt chạy trên cùng một cây. Kéo hằng số khám phá c từ 0 lên 3 và xem hình cây đổi. Rồi đổi hạt giống và chú ý bảng cuối: cùng hạt giống thì mọi con số y nguyên, đổi hạt giống thì khác ngay.
1 · Thế cờ, và chân lý để đối chiếu ✎ sửa được
Nim có công thức giải sẵn, và nó không dùng tới tìm kiếm: lấy XOR các đống, ở đây 2 ⊕ 4 = 6. Khác 0 thì bên đi trước thắng, và nước đúng là nước đưa XOR về 0. Công thức ấy có mặt ở đây làm nhân chứng thứ hai: cổng kiểm số so nó với minimax duyệt cạn trên toàn bộ lưới thế cờ, hai đường đi hoàn toàn khác nhau tới cùng một câu trả lời.
2 · Bốn nhịp của một lượt ✎ sửa được
- tầng 0 chọn lấy 1 ở đống B: UCT 1,381 so với nhánh nhì 1,348, nhánh này đã thăm 9 lần và đang thắng 44,4%
- tầng 1 chọn lấy 1 ở đống A: UCT 2,478 so với nhánh nhì 2,090, nhánh này đã thăm 2 lần và đang thắng 100,0%
A=1 B=1, đi ngẫu nhiên 2 nước tới khi hết hạt:- đối thủ lấy 1 ở đống B →
1-0 - bên ta lấy 1 ở đống A →
0-0
| nút trên đường đi | số lượt thăm | số ván thắng |
|---|---|---|
| tầng 0 · gốc | 53 → 54 | 34 → 34 |
| tầng 1 · lấy 1 ở đống B | 9 → 10 | 4 → 5 |
| tầng 2 · lấy 1 ở đống A | 2 → 3 | 2 → 2 |
| tầng 3 · lấy 2 ở đống B | 0 → 1 | 0 → 1 |
3 · Bảng UCT ở gốc sau khi chạy hết ✎ sửa được
| nước đi ở gốc | lượt thăm | ván thắng | tỉ lệ thắng | điểm UCT | minimax | phần lượt thăm |
|---|---|---|---|---|---|---|
| lấy 1 ở đống A | 23 | 8 | 34,8% | 1,067 | ✗ thua | |
| lấy 2 ở đống A | 21 | 7 | 33,3% | 1,086 | ✗ thua | |
| lấy 1 ở đống B | 61 | 40 | 65,6% | 1,098 | ✗ thua | |
| ▶ lấy 2 ở đống B | 262 | 231 | 88,2% | 1,095 | ✓ tối ưu | |
| lấy 3 ở đống B | 18 | 5 | 27,8% | 1,091 | ✗ thua | |
| lấy 4 ở đống B | 15 | 3 | 20,0% | 1,091 | ✗ thua |
UCT = q/n + c · căn(ln N / n). Phần đầu là tỉ lệ thắng đã biết, phần sau là phần thưởng cho nhánh còn ít lượt thăm: n nhỏ thì số hạng đó lớn, nên nhánh bị bỏ rơi tự được gọi lại. Ở trạng thái này N = 400, và mọi nhánh gốc có điểm UCT rất gần nhau, đó chính là dấu hiệu UCT đã cân xong: nhánh nào tỉ lệ thắng cao thì bị đòi thăm nhiều hơn cho tới khi điểm hai phần bù trừ nhau.
c nhỏ thì cây gầy và lượt chạy dồn vào một nhánh, c lớn thì cây bè ra và lượt chạy chia đều. Trên thế cờ nhỏ này chiều sâu bị chính trò chơi giới hạn (chỉ có 6 hạt nên ván dài nhất cũng chỉ 6 nước), nên chỗ dễ thấy hiệu ứng là số nút và phần lượt thăm. Đổi sang preset Nim 3-4-5 thì chiều sâu mới lộ ra.4 · Càng nhiều lượt càng chắc
| sau bao nhiêu lượt | MCTS sẽ chọn | lượt thăm của nó | tỉ lệ thắng | so với minimax |
|---|---|---|---|---|
| 1 | lấy 1 ở đống A | 1 | 100,0% | ✗ thua |
| 2 | lấy 1 ở đống A | 1 | 100,0% | ✗ thua |
| 4 | lấy 1 ở đống A | 1 | 100,0% | ✗ thua |
| 8 | lấy 1 ở đống A | 2 | 100,0% | ✗ thua |
| 16 | lấy 1 ở đống A | 3 | 66,7% | ✗ thua |
| 32 | lấy 2 ở đống A | 6 | 50,0% | ✗ thua |
| 64 | lấy 1 ở đống B | 15 | 53,3% | ✗ thua |
| 128 | lấy 2 ở đống B | 38 | 68,4% | ✓ tối ưu |
| 256 | lấy 2 ở đống B | 130 | 81,5% | ✓ tối ưu |
| 400 | lấy 2 ở đống B | 262 | 88,2% | ✓ tối ưu |
5 · Ngẫu nhiên, nhưng lặp lại được
0.1:23 0.2:21 1.1:61 1.2:262 1.3:18 1.4:150.1:23 0.2:21 1.1:61 1.2:262 1.3:18 1.4:150.1:23 0.2:22 1.1:53 1.2:269 1.3:17 1.4:166 · Hai luật cộng trừ của cây
| nút | lượt thăm | tổng lượt thăm các con | số lần là nơi mô phỏng bắt đầu | lệch |
|---|---|---|---|---|
| gốc | 400 | 400 | 0 | 0 |
| nhánh được chọn · lấy 2 ở đống B | 262 | 261 | 1 | 0 |
0 ở mọi nút, không riêng hai nút trên, và cổng kiểm số quét toàn cây.- Nó không chứng minh MCTS là công cụ đúng cho Nim. Ngược lại hẳn: Nim có công thức XOR giải trong một dòng, và minimax có ghi nhớ ở đây chỉ xét 15 thế cờ là xong. MCTS mở tới 124 nút mà vẫn chỉ đưa ra một câu trả lời thống kê. Nim ở đây được chọn vì nó nhỏ đủ để có chân lý đối chiếu, không phải vì nó là chỗ MCTS toả sáng.
- Mô phỏng ngẫu nhiên đều tay là lựa chọn tệ với Nim, và preset Nim 3-4-5 cho thấy tệ tới mức nào: nước đúng lại có tỉ lệ thắng ước lượng THẤP hơn nhiều nước sai, nên thêm lượt chạy cũng không cứu được trong ngân sách của một trình duyệt. Các hệ chơi cờ thật thay mô phỏng đều tay bằng chính sách học được, và đó là thứ sim này không có.
- Con số hội tụ là số đo trên một bộ hạt giống hữu hạn, không phải một định lý. Đổi bộ hạt giống thì con số đổi: trên thế mở bài nó là 156 với 12 hạt giống đầu và 186 nếu lấy 24 hạt.
- Ngẫu nhiên ở đây là ngẫu nhiên giả, sinh từ mulberry32 với hạt giống bạn tự đặt. Nhờ vậy mọi con số trên trang lặp lại được và cổng kiểm mới khoá được chúng, nhưng đừng dùng bộ sinh này cho bất cứ việc gì cần ngẫu nhiên thật.
Cột minimax trong bảng không phải trang trí. Nó là thứ duy nhất phân biệt được một lần chạy đã hội tụ với một lần chạy đang tự tin trả lời sai, và ở preset Nim 3-4-5 bạn sẽ thấy trường hợp thứ hai.
Bốn nhịp, và vì sao đúng bốn nhịp ấy
Một lượt MCTS gồm bốn việc, lặp lại hàng nghìn lần:
- Chọn theo cây. Từ gốc, đi xuống theo cây đã dựng được, mỗi tầng chọn nhánh có điểm UCT cao nhất, cho tới khi gặp một nút còn nước chưa thử.
- Mở rộng một nút. Thêm đúng một nút con cho một nước chưa thử. Một nút mỗi lượt, không hơn, nên cây lớn lên đều đặn thay vì nổ ra.
- Mô phỏng tới hết trận. Từ nút mới, hai bên đi ngẫu nhiên cho tới lúc phân thắng bại. Không có hàm lượng giá nào ở đây, chỉ có một ván chơi tới cùng.
- Truyền kết quả ngược. Đi ngược lên gốc, mỗi nút trên đường đi cộng một lượt thăm, và cộng một ván thắng nếu người vừa đi vào nút đó là người thắng ván mô phỏng.
Ở trạng thái mở bài, lượt 54 minh hoạ cả bốn nhịp. Nhịp chọn đi hai bước: từ gốc nó lấy lấy 1 ở đống B với điểm UCT 1,381 so với nhánh nhì 1,348, rồi từ đó lấy lấy 1 ở đống A với 2,478 so với 2,090. Nhịp mở rộng thêm nút số 47 cho nước lấy 2 ở đống B. Nhịp mô phỏng bắt đầu từ thế 1-1, đi hai nước là hết hạt, và bên ta thắng. Nhịp truyền ngược cập nhật đúng bốn nút trên đường đi: gốc từ 53 lên 54 lượt thăm, rồi 9 lên 10, rồi 2 lên 3, rồi 0 lên 1.
Hãy để ý cột ván thắng trong bảng nhịp 4: gốc giữ nguyên 34, nhánh lấy 1 ở đống B tăng từ 4 lên 5, nhánh lấy 1 ở đống A giữ nguyên 2, nút mới tăng từ 0 lên 1. Cứ một tầng được cộng thì tầng kế bên không được cộng, và điều đó không phải trùng hợp: hai bên đi xen kẽ, nên cùng một ván thắng là tin tốt cho tầng này và tin xấu cho tầng ngay dưới. Đây là chỗ dễ cài sai nhất của cả thuật toán, và cũng là chỗ cài sai xong mọi con số vẫn trông rất hợp lý.
Kéo lượt đang mổ xẻ xuống 6 rồi 7 để thấy nhịp chọn xuất hiện từ đâu. Gốc có sáu nước đi, nên sáu lượt đầu tiên chỉ mở rộng, chưa có gì để chọn; từ lượt 7 mới có quyết định UCT thật đầu tiên. Còn ở lượt 20 thì nhịp mở rộng không làm gì cả: đường chọn đã đi tới một ván đã hết hạt, không còn nước nào để thêm, nên lượt đó chỉ lấy luôn kết quả của ván đó rồi truyền ngược.
UCT: cân giữa cái đã biết và cái còn chưa biết
Công thức chọn nhánh là toàn bộ chỗ tinh tế của MCTS:
UCT = q/n + c · căn(ln N / n)
trong đó q là số ván thắng đã ghi cho nhánh, n là số lượt thăm của nhánh, N là số lượt thăm của nút cha, c là hằng số khám phá.
Số hạng đầu là cái đã biết: tỉ lệ thắng ước lượng của nhánh. Số hạng sau là phần thưởng cho cái còn chưa biết: n càng nhỏ thì nó càng lớn, nên một nhánh bị bỏ rơi tự được gọi lại. Chọn theo mỗi số hạng đầu là mù: một nhánh bị chấm điểm oan ngay ván mô phỏng đầu tiên sẽ không bao giờ được xét lại. Chọn theo mỗi số hạng sau thì thành chia đều lượt chạy cho mọi nhánh, tức bỏ hết những gì đã học được.
Ở trạng thái mở bài, sau 400 lượt thì sáu nhánh gốc có điểm UCT nằm rất sát nhau, từ 1,067 tới 1,098. Đó chính là dấu hiệu UCT đã cân xong: nhánh nào tỉ lệ thắng cao thì bị đòi thăm nhiều hơn, thăm nhiều thì số hạng sau tụt xuống, cho tới khi hai phần bù trừ nhau. Nhánh lấy 2 ở đống B được thăm 262 lần trong 400 lượt, thắng 231 ván, tức 88,2%, còn nhánh bị bỏ rơi nhất là lấy 4 ở đống B chỉ được thăm 15 lần với 20,0%.
Kéo c để thấy hình cây đổi. Với c = 0, cây teo lại còn 40 nút và 92,3% lượt chạy dồn vào đúng một nhánh gốc. Với c = 3, cây bè ra thành 157 nút và nhánh đông nhất chỉ còn 27,0%. Ở trạng thái mở bài c = 1,41 thì cây có 124 nút, chia theo tầng là 1, 6, 23, 49, 38, 7, và nhánh đông nhất giữ 65,5%.
Một điểm cần nói cho đúng: người ta thường mô tả c nhỏ là "đào sâu một nhánh" và c lớn là "trải rộng", nhưng trên thế cờ nhỏ đang mở thì chiều sâu không đổi, cả c = 0 và c = 3 đều cho cây sâu 5 tầng. Lý do là chính trò chơi chặn: hai đống cộng lại 6 hạt thì ván dài nhất cũng chỉ 6 nước. Hiệu ứng chiều sâu chỉ lộ ra khi trò chơi còn chỗ mà đào: đổi sang preset Nim 3-4-5, cùng 400 lượt, c = 0 cho cây sâu 9 tầng với 136 nút còn c = 4 chỉ sâu 3 tầng với 399 nút.
Càng nhiều lượt càng chắc, và mốc hội tụ là số ĐO được
Bảng "càng nhiều lượt càng chắc" cho thấy nước MCTS sẽ chọn nếu ta bắt nó dừng sớm. Sau 1, 2, 4, 8 và 16 lượt nó chọn lấy 1 ở đống A, sau 32 lượt chọn lấy 2 ở đống A, sau 64 lượt chọn lấy 1 ở đống B: cả ba đều là nước thua. Từ mốc 128 nó chọn lấy 2 ở đống B, tức nước duy nhất đúng, với tỉ lệ thắng ước lượng 68,4%; tới 256 lượt là 81,5% và tới 400 lượt là 88,2%. Ước lượng bò dần về phía sự thật, mà sự thật ở đây là con số tuyệt đối: minimax chứng minh nước ấy thắng chắc.
Nhưng một lần chạy đúng không chứng minh được gì, vì nó có thể chỉ là một hạt giống may. Nên sim quét cả một bộ hạt giống và đo con số này: từ lượt 156 trở đi, cả 12 hạt giống đều chọn nước tối ưu và không đổi ý nữa. Tiêu chí cố tình khắt khe, một hạt chỉ được tính là ổn định nếu mọi lượt từ đó tới trần 400 đều chọn đúng, vì nếu chỉ xem lượt cuối thì một lần chạy đang lung lay cũng bị chấm là đã hội tụ.
Con số 156 là số đo, không phải định lý, và nó phụ thuộc bộ hạt giống: lấy 24 hạt thay vì 12 thì mốc lùi ra 186. Bởi vậy mọi con số hội tụ phải nói kèm bộ hạt giống và trần đã dùng, còn không thì nó chỉ là đồ trang trí.
Preset c = 0 cho thấy cái bẫy ấy rõ nhất. Với hạt giống mở bài, c = 0 vẫn chọn đúng nước, nhìn qua thì tưởng chỉ khai thác cũng đủ. Nhưng bảng quét cho biết chỉ 8 trên 12 hạt giống ổn định, tức không có mốc nào để nói nó đã hội tụ. Ngược lại, c = 3 thì hội tụ nhưng chậm hơn, mốc lùi từ 156 ra 238, vì lượt chạy bị chia cho cả những nhánh đã biết là tệ.
Chỗ MCTS nói dối, và bài này không giấu
Đổi sang preset Nim 3-4-5. Thế này XOR bằng 2 nên bên đi trước thắng, và trong 12 nước chỉ đúng một nước giữ được thế thắng là lấy 2 ở đống A. Với 400 lượt, MCTS chọn lấy 3 ở đống A, một nước mà minimax chứng minh là thua. Tệ hơn con số sai: nước đúng chỉ được ước lượng thắng 42,3% với 26 lượt thăm, còn nước sai được 64,3% với 56 lượt thăm. Mô phỏng ngẫu nhiên xếp nước đúng thấp hơn nước sai, nên chạy thêm cũng không cứu, và bảng quét xác nhận: chỉ 3 trên 12 hạt giống ổn định trong 400 lượt.
Vì sao? Vì mô phỏng ngẫu nhiên đều tay là thước đo rất tệ cho Nim. Sau khi đi nước đúng, thế còn lại là 1-4-5, và bên đối thủ tuy đang ở thế thua vẫn còn rất nhiều đường thoát nếu ta chơi bừa; ngược lại một nước sai có thể để lại thế mà chơi bừa lại hay thắng. MCTS chỉ chữa được chuyện đó bằng cách để cây mọc đủ lớn để thay thống kê bằng lời giải chính xác, mà cây trò chơi đầy đủ của 3-4-5 có 1.038.768 nút, quá xa với vài trăm lượt.
Điều đó dẫn tới một so sánh cần nói thẳng: trên Nim, MCTS là lựa chọn tệ. Minimax có ghi nhớ thế trùng chỉ xét 15 thế cờ cho thế 2-4, và 120 thế cho 3-4-5, rồi trả về một câu trả lời chứng minh được. MCTS mở tới 124 nút mà chỉ đưa ra một câu trả lời thống kê. Nim ở đây được chọn vì nó nhỏ đủ để có chân lý đối chiếu, chứ không phải vì đây là chỗ MCTS toả sáng. Chỗ nó toả sáng là những trò chơi mà Eval không viết được và cây quá lớn để duyệt, và ở đó không ai kiểm tra được nó bằng minimax, nên tất cả các cạm bẫy bạn vừa thấy đều vẫn còn nguyên mà không ai phát hiện.
Các hệ chơi cờ thật vì thế không dùng mô phỏng đều tay. AlphaGo thay nó bằng một mạng chính sách để chọn nước trong lúc mô phỏng và một mạng giá trị để khỏi phải chơi tới hết trận, còn AlphaZero thì bỏ hẳn phần mô phỏng ngẫu nhiên. Bốn nhịp thì giữ nguyên, nhưng nhịp thứ ba đã đổi ruột.
So với minimax: được gì, mất gì
| minimax với alpha-beta | MCTS | |
|---|---|---|
| cần hàm lượng giá | cần, nếu không duyệt tới lá | không cần, chỉ cần luật chơi |
| dừng giữa đường | phải duyệt xong một tầng mới có câu trả lời dùng được | dừng lúc nào cũng có câu trả lời tốt nhất tới thời điểm đó |
| tính chất câu trả lời | chứng minh được, nếu duyệt tới lá | thống kê, đúng dần theo số lượt |
| phân bổ công sức | đều theo tầng | dồn vào nhánh đang hứa hẹn |
| bộ nhớ | cỡ b·m, rất tiết kiệm | phải giữ cả cây đã dựng |
| chỗ gãy | không có Eval tốt là hỏng | mô phỏng lệch là hỏng, và lệch rất khó thấy |
Tính chất "dừng lúc nào cũng dùng được" đáng nói thêm, vì đó là lý do MCTS được yêu thích trong thực tế. Cho nó một giây thì nó trả lời sau một giây, cho mười giây thì câu trả lời tốt hơn, không cần đổi gì trong thuật toán. Minimax theo tầng thì phải chờ xong một tầng, và một tầng của cờ vây thì không bao giờ xong.
Hai luật cộng trừ của cây, và một lần đặc tả sai
Mục 6 của sim in ra hai con số dễ bỏ qua nhưng là cách tốt nhất để biết phần cài đặt có đúng hay không.
Lượt thăm của gốc phải bằng đúng số lượt đã chạy, ở đây 400 = 400, vì mỗi lượt đi qua gốc đúng một lần.
Lượt thăm của một nút phải bằng tổng lượt thăm các con cộng số lần chính nó là nơi mô phỏng bắt đầu. Ở nhánh được chọn: 262 = 261 + 1. Mỗi lượt tới nút đó thì hoặc đi tiếp vào đúng một con, hoặc dừng lại ngay đó, không có lựa chọn thứ ba.
Câu thứ hai đáng dừng lại, vì bản mô tả ban đầu của bài này viết luật ấy thành "cộng số lần chính nó là nút vừa được mở rộng", tức cộng 1. Cách viết đó sai, và phản ví dụ đo được ngay trên trạng thái mở bài: một nút kết thúc bị nhịp chọn đi vào nhiều lần, mỗi lần lại lấy luôn kết quả ván đó rồi truyền ngược, nên nó là nơi mô phỏng bắt đầu tới 49 lần chứ không phải 1 lần; và trên cây 124 nút có 24 nút như vậy. Luật chỉ khít nếu đếm "số lần mô phỏng bắt đầu tại đây", và đó là con số engine đếm.
Ngẫu nhiên nhưng lặp lại được
MCTS là thuật toán ngẫu nhiên, mà một thuật toán ngẫu nhiên không lặp lại được thì không kiểm được: không có con số nào để khoá, và người học cũng không có cách nào tự thấy hai lần chạy "giống nhau" có thật giống nhau hay không. Nên phần ngẫu nhiên ở đây không lấy từ Math.random mà từ một bộ sinh số giả ngẫu nhiên có hạt giống, mulberry32, với hạt giống là một núm bạn tự đặt.
Mục 5 của sim in ba chữ ký: hai lần chạy cùng hạt giống, và một lần chạy với hạt giống kế tiếp. Hai chữ ký đầu giống nhau từng con số, chữ ký thứ ba khác. Cả hai nửa đều cần thiết: nửa đầu là tính lặp lại, nửa sau chứng minh hạt giống không phải một núm chết bày ra cho đẹp.
Cái giá phải nói rõ: đây là ngẫu nhiên giả. Nó đủ tốt để dạy và để khoá số, nhưng đừng dùng bộ sinh này cho việc gì cần ngẫu nhiên thật.
MCTS đổi một thứ rất cụ thể: nó bỏ hàm lượng giá và nhận lại một câu trả lời thống kê. Bốn nhịp mỗi lượt là chọn theo UCT, mở rộng một nút, mô phỏng tới hết trận, truyền kết quả ngược. Công thức UCT = q/n + c · căn(ln N / n) cân giữa tỉ lệ thắng đã biết và nhánh còn ít lượt thăm, và hằng số c quyết định hình cây: trên thế mở bài c = 0 cho cây 40 nút với 92,3% lượt dồn vào một nhánh, còn c = 3 cho 157 nút với nhánh đông nhất chỉ 27,0%. Chạy thêm thì đúng thêm, và trên thế Nim 2-4 thì từ lượt 156 mọi hạt giống trong bộ 12 hạt đều chọn đúng nước minimax chọn. Nhưng chỗ quan trọng nhất của bài là chỗ nó thất bại: trên thế Nim 3-4-5, mô phỏng ngẫu nhiên xếp nước đúng 42,3% còn nước sai 64,3%, nên MCTS chọn sai và chạy thêm cũng không cứu. Một câu trả lời thống kê tự tin trông giống y một câu trả lời đúng, và chỉ có chân lý ngoài lề mới phân biệt được hai thứ đó.
- 1Ở nhịp truyền ngược, một nút trên đường đi được cộng một ván thắng khi nào?
- 2Đặt hằng số khám phá c bằng 0 thì điều gì xảy ra?
- 3Trên thế Nim 3-4-5 với 400 lượt chạy, MCTS chọn một nước mà minimax chứng minh là thua. Kết luận đúng nhất là gì?
Tìm kiếm cây Monte Carlo giải bài toán mà minimax bó tay: cây quá lớn để duyệt và không có hàm lượng giá đáng tin. Mỗi lượt gồm bốn nhịp, chọn theo UCT, mở rộng một nút, mô phỏng ngẫu nhiên tới hết trận, truyền kết quả ngược. Công thức UCT = q/n + c · căn(ln N / n) cân tỉ lệ thắng đã biết với nhánh còn ít lượt thăm. Ưu điểm là không cần Eval, dừng lúc nào cũng có câu trả lời dùng được, và công sức tự dồn vào nhánh hứa hẹn. Nhược điểm là câu trả lời có tính thống kê chứ không phải chứng minh, phải giữ cả cây trong bộ nhớ, và chất lượng phụ thuộc hoàn toàn vào chất lượng mô phỏng: đó là lý do AlphaGo thay mô phỏng ngẫu nhiên bằng mạng chính sách và mạng giá trị.