Ảnh chụp bởi Johann Siemens

Phương pháp duyệt cây Monte Carlo, viết tắt là MCTS, được AlphaGo Zero sử dụng để tiến hành việc chọn lựa bước đi tiếp theo trong trò chơi Go.

MCTS thực hiện tìm kiếm tất cả các bước đi có thể có và ghi lại kết quả vào cây tìm kiếm. Khi việc tìm kiếm được thực hiện càng nhiều lần, cây tìm kiếm này sẽ càng mở rộng lớn hơn cùng với nhiều dự đoán chính xác hơn. Sau 1.600 lượt tìm kiếm, nó sẽ chọn bước đi tiếp theo mà có cơ hội chiến thắng là cao nhất.

Nguồn

Tổng quan về phương pháp duyệt cây Monte Carlo

Hãy xem cách nó chọn a3 cho vị trí s3.

Nguồn

Trong MCTS, một nút sẽ đại diện cho một vị trí ở trên bàn cờ và một cạnh mũi tên tương ứng với một bước đi.

Bắt đầu với vị trí s3, nó sẽ thực hiện tìm kiếm các bước đi có thể có và sử dụng mạng học sâu f để đánh giá.

Chiến thuật p, kiểm soát các hành động nào nên được thực hiện tiếp theo. Để mô hình hóa tính bất định, chiến thuật sẽ là một phân phối xác suất.
Hàm giá trị V, đánh giá khả năng giành chiến thắng ở một vị trí s.

Trong ví dụ dưới đây sẽ áp dụng một mạng học sâu f (bao gồm các lớp tích chập) trên vị trí s’3 để tính toán chiến thuật p và các hàm giá trị V.

Nguồn

Tiếp theo, nó sẽ mở rộng cây tìm kiếm bằng cách thực hiện một bước đi. Điều này sẽ thêm một vị trí mới trong bảng và các bước đi tương ứng vào trong cây tìm kiếm.

Nguồn

Một thuật ngữ khác được gọi là hàm giá trị của hành động Q. Nó đo lường giá trị khi thực hiện một hành động nào đó. Trong hình (a) dưới đây sẽ thực hiện bước đi theo đường màu đỏ (a3) và có kết quả là 0,9 khả năng chiến thắng. Vậy Q là 0,9. Trong hình (b), nó thực hiện thêm một bước đi và có kết quả là 0,6 khả năng chiến thắng. Bước đi a3 được thực hiện hai lần, visit count N = 2. Giá trị Q sẽ là giá trị trung bình của các kết quả trước đó, tức là. W = (0,9 + 0,6), Q = W / 2 = 0,75. Trong hình (c), nó tìm ra một đường đi khác. Bây giờ, a3 sẽ được chọn 3 lần và giá trị Q sẽ là (0,9 + 0,6 + 0,3) / 3 = 0,6.

Nguồn

Giá trị Q cũng thực hiện cùng một mục đích tương tự với chiến thuật p được tính bởi mạng học sâu f. Tuy nhiên, khi việc tìm kiếm thực hiện nhiều hơn, cây tìm kiếm sẽ phát triển lớn hơn. Nếu nó tiếp tục thực hiện, các giá trị nhiễu trong p sẽ triệt tiêu lẫn nhau. Vì vậy, Q sẽ ngày càng chính xác hơn khi thực hiện các bước đi nhiều hơn.

Nguồn

Tuy nhiên, không gian cho việc tìm kiếm trong trò chơi Go là rất lớn, chúng ta cần ưu tiên cho việc tìm kiếm có kết quả tốt hơn. Có 2 yếu tố cần quan tâm là khai thác và thăm dò.

Khai thác: thực hiện các tìm kiếm mà có khả năng kết quả hứa hẹn (nghĩa là giá trị Q cao).
Thăm dò: thực hiện các tìm kiếm mà ít khi được thăm dò (tức là giá trị visit count N thấp).

Nguồn

Về mặt toán học, nó chọn các bước đi đi theo công thức sau:

$a_{t}=argmax_{a}(Q(s,a)+u(s,a))$

Trong đó u là:

$u(s,a)\infty \frac{P(s,a)}{1+N(s,a)}$

Trong phương trình này, Q điều khiển việc khai thác và u điều khiển việc thăm dò. Bắt đầu từ gốc của cây, nó sử dụng chiến thuật (cây chiến thuật) để chọn đường đi mà nó muốn tìm kiếm.

Nguồn

Ban đầu, MCTS sẽ tập trung nhiều hơn vào việc thăm dò nhưng khi số vòng lặp tăng lên, hầu hết các tìm kiếm sẽ đều là khai thác và Q sẽ càng chính xác hơn.

AlphaGo Zero lặp lại các bước trên 1.600 lần để mở rộng cây. Nó sử dụng cây tìm kiếm để tạo một chiến thuật π cho việc chọn bước đi tiếp theo cho vị trí s3.

Nguồn

Nó không sử dụng Q để tính toán cho chiến thuật π. Thay vào đó, π được lấy từ giá trị visit count N.

$\pi_{a}\infty N(s,a)^{1/ \tau}$

$\pi(a|s)=N(s,a)^{1/ \tau} / \sum_{b}N(s,b)^{1/ \tau}$

Sau các vòng lặp đầu tiên, các bước đi có giá trị Q cao hơn sẽ được duyệt qua thường xuyên hơn. Nó sử dụng giá trị vistit count để tính toán cho chiến thuật. $\tau$ là mức độ kiểm soát mức thăm dò. Khi $\tau$ bằng 1, nó sẽ chọn các bước đi dựa trên giá trị visit count. Khi $\tau$ tiến tới giá trị 0, chỉ có các bước đi có giá trị visit count cao nhất sẽ được chọn. Vì vậy $\tau = 1$ cho phép việc thăm dò trong khi $\tau$ tiến về giá trị 0 thì không cho phép thực hiện việc thăm dò.

CHÚ Ý: Với vị trí s, MCTS tính toán chiến thuật $\pi$ chính xác hơn để quyết định bước đi tiếp theo.

Nguồn

MCTS cải thiện phương pháp đánh giá chiến thuật (cải thiện giá trị Q) và nó sử dụng phương pháp đánh giá mới để cải thiện chiến thuật. Sau đó nó áp dụng lại chiến thuật này để đánh giá chiến thuật một lần nữa. Những lần lặp đi lặp lại phương pháp đánh giá chiến thuật và cải thiện chiến thuật này được gọi là phương pháp vòng lặp chiến thuật trong học tăng cường (RL). Sau khi tự học việc chơi nhiều các trò chơi, cả phương pháp đánh giá chiến thuật và cải thiện chiến thuật sẽ được tối ưu hóa đến mức mà có thể đánh bại những người chơi giỏi nhất.

Phương pháp duyệt cây Monte Carlo (MCTS)

MCTS bao gồm 4 bước chính:

Bước (a) thực hiện việc chọn một đường đi (một chuỗi các bước di chuyển) mà nó muốn tìm kiếm nhiều hơn.

Bước (b) thực hiện việc mở rộng cây tìm kiếm bằng cách thực hiện thêm một bước nữa.

Bước (c) thực hiện cập nhật đường đi hiện tại quay trở lại dựa trên mức độ mà đường đi đó có kết quả hứa hẹn.

Sau khi lặp lại từ bước (a) đến bước (c) 1.600 lần, nó sử dụng cây tìm kiếm để tạo chiến thuật $\pi 3$ cho vị trí s3. Trong bước (d), nó sẽ lấy mẫu các bước đi tiếp theo từ chiến thuật $\pi 3$ .

Bước chọn

Bước đầu tiên là chọn một đường đi từ cây tìm kiếm để tiếp tục thăm dò thêm. Giả sử cây tìm kiếm của chúng ta trông giống như bên dưới.

Nguồn

Nó bắt đầu từ gốc và lựa chọn các bước đi dựa trên phương trình dưới đây:

$a_{t}=argmax_{a}(Q(s,a)+u(s,a))$

$u(s,a)=c_{puct}P(s,a)\frac{\sqrt{\sum_{b}N(s,b)}}{1+N(s,a)}$

$(P(s,a),v)=f_{\theta}(s)$

Trong đó, u kiểm soát việc thăm dò. Nó phụ thuộc vào giá trị visit count N, P là chiến thuật từ mạng học sâu f, c là một siêu tham số kiểm soát mức độ thăm dò. Q kiểm soát việc khai thác là hàm giá trị của hành động được tính toán từ phương pháp MCTS.

Bước mở rộng và đánh giá

Với đường đi đã chọn được quyết định, một nút lá sẽ được thêm vào cây tìm kiếm. Nó sử dụng mạng học sâu f để tính toán chiến thuật p và V.

Nguồn

Nút lá được mở rộng với các cạnh (s, a). Mỗi cạnh được khởi tạo bằng công thức sau:

$(p,v)=f_{\theta}$

${N(s_{L},a)=0, W(s_{L},a)=0,Q(s_{L},a)=0,P(s_{L},a)=p_{a}}$

Nó đặt giá trị 0 cho visit count N, giá trị của hành động được tích lũy W và giá trị của hành động Q. P được khởi tạo bởi v, được tính từ mạng học sâu f.

Backup

Nguồn

Sau khi p và v được tính cho nút lá, chúng ta sẽ lưu trữ v để cập nhật giá trị của hành động Q cho mọi cạnh (s, a) trong đường đi đã được chọn.

$(p,v)=f_{\theta}$

$N(s,a)=N(s,a)+1$

$W(s,a)=W(s,a) + v$

$Q(s,a)=\frac{W(s,a)}{N(s,a)}$

Thực hiện

Nguồn

Để quyết định bước đi tiếp theo, AlphaGo Zero sẽ lấy mẫu một bước đi $\alpha$ dựa trên công thức:

$\pi(a|s)=N(s,a)^{1/ \tau}/ \sum_{b}N(s,b)^{1/ \tau}$

$a\sim \pi$

Bước đi đã chọn $\alpha$ sẽ trở thành nút gốc của cây tìm kiếm với tất cả các nút con của nó được giữ nguyên trong khi các nút khác sẽ bị loại bỏ. Sau đó, thực hiện lại phương pháp MCTS một lần nữa cho bước đi tiếp theo.

Đến đây là kết thúc của bài này. Mọi người hãy tiếp tục theo dõi các phần tiếp theo nhé!

P/s: Mong mọi người luôn ủng hộ tek4 nhé!

« Trước

Mục lục

Tin tức liên quan

Leave a Reply Cancel Reply

Chuyên mục

Tin đọc nhiều

Phương pháp duyệt cây Monte Carlo – Học tăng cường

Tổng quan về phương pháp duyệt cây Monte Carlo

Phương pháp duyệt cây Monte Carlo (MCTS)

Bước chọn

Bước mở rộng và đánh giá

Backup

Thực hiện

Tin tức liên quan

Leave a Reply Cancel Reply

Chuyên mục

Tin đọc nhiều