&nbsp;
Phương ph&aacute;p duyệt c&acirc;y Monte Carlo, viết tắt l&agrave; MCTS, được AlphaGo Zero sử dụng để tiến h&agrave;nh việc chọn lựa bước đi tiếp theo trong tr&ograve; chơi Go.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/542ec6f4-b47b-4053-b01f-5ac9ff6caeaf" alt="" width="600" height="514" />
MCTS thực hiện t&igrave;m kiếm tất cả c&aacute;c bước đi c&oacute; thể c&oacute; v&agrave; ghi lại kết quả v&agrave;o c&acirc;y t&igrave;m kiếm. Khi việc t&igrave;m kiếm được thực hiện c&agrave;ng nhiều lần, c&acirc;y t&igrave;m kiếm n&agrave;y sẽ c&agrave;ng mở rộng lớn hơn c&ugrave;ng với nhiều dự đo&aacute;n ch&iacute;nh x&aacute;c hơn. Sau 1.600 lượt t&igrave;m kiếm, n&oacute; sẽ chọn bước đi tiếp theo m&agrave; c&oacute; cơ hội chiến thắng l&agrave; cao nhất.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/46e0b6bb-c319-473b-af79-f75336131db9" alt="" width="600" height="301" />
<h1 style="text-align: justify;">Tổng quan về&nbsp;phương ph&aacute;p duyệt c&acirc;y Monte Carlo</h1>
H&atilde;y xem c&aacute;ch n&oacute; chọn a3 cho vị tr&iacute; s3.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/e0b00224-53f5-4434-bfc0-c2ff1540e75d" alt="" width="600" height="61" />
Trong MCTS, một n&uacute;t sẽ đại diện cho một vị tr&iacute; ở tr&ecirc;n b&agrave;n cờ v&agrave; một cạnh mũi t&ecirc;n tương ứng với một bước đi.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/6dbc4613-9a08-47f1-ab39-b206a91e68af" alt="" width="600" height="368" />
Bắt đầu với vị tr&iacute; s3, n&oacute; sẽ thực hiện t&igrave;m kiếm c&aacute;c bước đi c&oacute; thể c&oacute; v&agrave; sử dụng mạng học s&acirc;u f để đ&aacute;nh gi&aacute;.
<ul style="text-align: justify;">
<li>Chiến thuật p, kiểm so&aacute;t c&aacute;c h&agrave;nh động n&agrave;o n&ecirc;n được thực hiện tiếp theo. Để m&ocirc; h&igrave;nh h&oacute;a t&iacute;nh bất định, chiến thuật sẽ&nbsp;l&agrave; một ph&acirc;n phối x&aacute;c suất.</li>
<li>H&agrave;m gi&aacute; trị V, đ&aacute;nh gi&aacute; khả năng gi&agrave;nh chiến thắng ở một vị tr&iacute; s.</li>
</ul>
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/4f092531-393f-4662-8186-04e98addd0f6" alt="" width="600" height="358" />
Trong v&iacute; dụ dưới đ&acirc;y sẽ &aacute;p dụng một mạng học s&acirc;u f (bao gồm c&aacute;c lớp t&iacute;ch chập) tr&ecirc;n vị tr&iacute; s&rsquo;3 để t&iacute;nh to&aacute;n chiến thuật p v&agrave; c&aacute;c h&agrave;m gi&aacute; trị V.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/74d867f8-788a-4e9e-869c-08f87f5dc9b9" alt="" width="600" height="432" />
Tiếp theo, n&oacute; sẽ mở rộng c&acirc;y t&igrave;m kiếm bằng c&aacute;ch thực hiện một bước đi. Điều n&agrave;y sẽ th&ecirc;m một vị tr&iacute; mới trong bảng v&agrave; c&aacute;c bước đi tương ứng v&agrave;o trong c&acirc;y t&igrave;m kiếm.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/6b48a6d1-455d-44a8-bde2-045033a53a43" alt="" width="600" height="220" />
Một thuật ngữ kh&aacute;c được gọi l&agrave; h&agrave;m gi&aacute; trị của h&agrave;nh động Q. N&oacute; đo lường gi&aacute; trị khi thực hiện một h&agrave;nh động n&agrave;o đ&oacute;. Trong h&igrave;nh (a) dưới đ&acirc;y sẽ thực hiện bước đi theo đường m&agrave;u đỏ (a3) v&agrave; c&oacute; kết quả l&agrave; 0,9 khả năng chiến thắng. Vậy Q l&agrave; 0,9. Trong h&igrave;nh (b), n&oacute; thực hiện th&ecirc;m một bước đi v&agrave; c&oacute; kết quả l&agrave; 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&aacute; trị Q sẽ l&agrave; gi&aacute; trị trung b&igrave;nh của c&aacute;c kết quả trước đ&oacute;, tức l&agrave;. W = (0,9 + 0,6), Q = W / 2 = 0,75. Trong h&igrave;nh (c), n&oacute; t&igrave;m ra một đường đi kh&aacute;c. B&acirc;y giờ, a3 sẽ được chọn 3 lần v&agrave; gi&aacute; trị Q sẽ l&agrave; (0,9 + 0,6 + 0,3) / 3 = 0,6.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/ccc7efc3-1be3-46fa-9810-fc918086460d" alt="" width="600" height="225" />
Gi&aacute; trị Q cũng thực hiện c&ugrave;ng một mục đ&iacute;ch tương tự với chiến thuật p được t&iacute;nh bởi mạng học s&acirc;u f. Tuy nhi&ecirc;n, khi việc t&igrave;m kiếm thực hiện nhiều hơn, c&acirc;y t&igrave;m kiếm sẽ ph&aacute;t triển lớn hơn. Nếu n&oacute; tiếp tục thực hiện, c&aacute;c gi&aacute; trị nhiễu trong p sẽ triệt ti&ecirc;u lẫn nhau. V&igrave; vậy, Q sẽ ng&agrave;y c&agrave;ng ch&iacute;nh x&aacute;c hơn khi thực hiện c&aacute;c bước đi nhiều hơn.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/010874d3-47f3-46d8-a813-0eebd3027b00" alt="" width="600" height="264" />
Tuy nhi&ecirc;n, kh&ocirc;ng gian cho việc t&igrave;m kiếm trong tr&ograve; chơi Go l&agrave; rất lớn, ch&uacute;ng ta cần ưu ti&ecirc;n cho việc t&igrave;m kiếm c&oacute; kết quả tốt hơn. C&oacute; 2 yếu tố cần quan t&acirc;m l&agrave; khai th&aacute;c v&agrave; thăm d&ograve;.
<ul style="text-align: justify;">
<li>Khai th&aacute;c: thực hiện c&aacute;c t&igrave;m kiếm m&agrave; c&oacute; khả năng kết quả hứa hẹn (nghĩa l&agrave; gi&aacute; trị Q cao).</li>
<li>Thăm d&ograve;: thực hiện c&aacute;c t&igrave;m kiếm m&agrave; &iacute;t khi được thăm d&ograve; (tức l&agrave;&nbsp;gi&aacute; trị visit count N thấp).</li>
</ul>
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/f8214f98-1d95-41f6-9b54-7653c319873a" alt="" width="600" height="165" />
Về mặt to&aacute;n học, n&oacute; chọn c&aacute;c bước đi đi theo c&ocirc;ng thức sau:
[latexpage]\[a_{t}=argmax_{a}(Q(s,a)+u(s,a))\]
Trong đ&oacute; u l&agrave;:
[latexpage]\[u(s,a)\infty&nbsp;\frac{P(s,a)}{1+N(s,a)}\]
Trong phương tr&igrave;nh n&agrave;y, Q điều khiển việc khai th&aacute;c v&agrave; u điều khiển việc thăm d&ograve;. Bắt đầu từ gốc của c&acirc;y, n&oacute; sử dụng chiến thuật&nbsp;(c&acirc;y chiến thuật) để chọn đường đi m&agrave; n&oacute; muốn t&igrave;m kiếm.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/295cd4cb-033f-464c-9d86-7980a28b7f7a" alt="" width="600" height="382" />
Ban đầu, MCTS sẽ tập trung nhiều hơn v&agrave;o việc thăm d&ograve; nhưng khi số v&ograve;ng lặp tăng l&ecirc;n, hầu hết c&aacute;c t&igrave;m kiếm sẽ đều l&agrave; khai th&aacute;c v&agrave; Q sẽ c&agrave;ng ch&iacute;nh x&aacute;c hơn.
AlphaGo Zero lặp lại c&aacute;c bước tr&ecirc;n 1.600 lần để mở rộng c&acirc;y. N&oacute; sử dụng c&acirc;y t&igrave;m kiếm để tạo một chiến thuật &pi; cho việc chọn bước đi tiếp theo cho vị tr&iacute; s3.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/d133632d-d2ad-4cf2-b436-c4ba03a43787" alt="" width="600" height="165" />
N&oacute; kh&ocirc;ng sử dụng Q để t&iacute;nh to&aacute;n cho chiến thuật &pi;. Thay v&agrave;o đ&oacute;, &pi; được lấy từ gi&aacute; trị visit count N.
[latexpage]\[\pi_{a}\infty N(s,a)^{1/ \tau}\]
[latexpage]\[\pi(a|s)=N(s,a)^{1/ \tau} / \sum_{b}N(s,b)^{1/ \tau}\]
Sau c&aacute;c v&ograve;ng lặp đầu ti&ecirc;n, c&aacute;c bước đi c&oacute; gi&aacute; trị Q cao hơn sẽ được duyệt qua thường xuy&ecirc;n hơn. N&oacute; sử dụng gi&aacute; trị vistit count để t&iacute;nh to&aacute;n cho chiến thuật. [latexpage]$\tau$ l&agrave; mức độ kiểm so&aacute;t mức thăm d&ograve;. Khi [latexpage]$\tau$ bằng 1, n&oacute; sẽ chọn c&aacute;c bước đi dựa tr&ecirc;n gi&aacute; trị visit count. Khi [latexpage]$\tau$ tiến tới gi&aacute; trị 0, chỉ c&oacute; c&aacute;c bước đi c&oacute; gi&aacute; trị visit count cao nhất sẽ được chọn. V&igrave; vậy [latexpage]$\tau = 1$ cho ph&eacute;p việc thăm d&ograve; trong khi [latexpage]$\tau$ tiến về gi&aacute; trị 0 th&igrave; kh&ocirc;ng cho ph&eacute;p thực hiện việc thăm d&ograve;.
CH&Uacute; &Yacute;: Với vị tr&iacute; s, MCTS t&iacute;nh to&aacute;n chiến thuật [latexpage]$\pi$ ch&iacute;nh x&aacute;c hơn để quyết định bước đi tiếp theo.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/025ff35a-4f4c-43ef-96d7-0bc38f1f549a" alt="" width="600" height="209" />
MCTS cải thiện phương ph&aacute;p đ&aacute;nh gi&aacute; chiến thuật (cải thiện gi&aacute; trị Q) v&agrave; n&oacute; sử dụng phương ph&aacute;p đ&aacute;nh gi&aacute; mới để cải thiện chiến thuật. Sau đ&oacute; n&oacute; &aacute;p dụng lại chiến thuật n&agrave;y để đ&aacute;nh gi&aacute; chiến thuật một lần nữa. Những lần lặp đi lặp lại phương ph&aacute;p đ&aacute;nh gi&aacute; chiến thuật v&agrave; cải thiện chiến thuật n&agrave;y được gọi l&agrave; phương ph&aacute;p v&ograve;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&aacute;c tr&ograve; chơi, cả phương ph&aacute;p đ&aacute;nh gi&aacute; chiến thuật v&agrave; cải thiện chiến thuật sẽ được tối ưu h&oacute;a đến mức m&agrave; c&oacute; thể đ&aacute;nh bại những người chơi giỏi nhất.
<h1 style="text-align: justify;">Phương ph&aacute;p duyệt c&acirc;y Monte Carlo (MCTS)</h1>
MCTS bao gồm 4 bước ch&iacute;nh:
Bước (a) thực hiện việc chọn một đường đi (một chuỗi c&aacute;c bước di chuyển) m&agrave; n&oacute; muốn t&igrave;m kiếm nhiều hơn.
Bước (b) thực hiện việc mở rộng c&acirc;y t&igrave;m kiếm bằng c&aacute;ch thực hiện th&ecirc;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&ecirc;n mức độ m&agrave; đường đi đ&oacute; c&oacute; kết quả hứa hẹn.
<img class="aligncenter wp-image-6351 size-full" src="https://tek4.vn/public_files/a04039f0-740c-43f1-a124-02f554e24e94" alt="Phuong-phap-duyet-cay-Montecarlo" width="1104" height="576" />
Sau khi lặp lại từ bước (a) đến bước (c) 1.600 lần, n&oacute; sử dụng c&acirc;y t&igrave;m kiếm để tạo chiến thuật [latexpage]$\pi 3$ cho vị tr&iacute; s3. Trong bước (d), n&oacute; sẽ lấy mẫu c&aacute;c bước đi tiếp theo từ chiến thuật [latexpage]$\pi 3$.
<h2 style="text-align: justify;">Bước chọn</h2>
Bước đầu ti&ecirc;n l&agrave; chọn một đường đi từ c&acirc;y t&igrave;m kiếm để tiếp tục thăm d&ograve; th&ecirc;m. Giả sử c&acirc;y t&igrave;m kiếm của ch&uacute;ng ta tr&ocirc;ng giống như b&ecirc;n dưới.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/a23b62aa-aa5b-420e-a668-db2f9920633f" alt="" width="600" height="313" />
N&oacute; bắt đầu từ gốc v&agrave; lựa chọn c&aacute;c bước đi dựa tr&ecirc;n phương tr&igrave;nh dưới đ&acirc;y:
[latexpage]\[a_{t}=argmax_{a}(Q(s,a)+u(s,a))\]
[latexpage]\[u(s,a)=c_{puct}P(s,a)\frac{\sqrt{\sum_{b}N(s,b)}}{1+N(s,a)}\]
[latexpage]\[(P(s,a),v)=f_{\theta}(s)\]
Trong đ&oacute;, u kiểm so&aacute;t việc thăm d&ograve;. N&oacute; phụ thuộc v&agrave;o gi&aacute; trị visit count N, P l&agrave; chiến thuật từ mạng học s&acirc;u f, c l&agrave; một si&ecirc;u tham số kiểm so&aacute;t mức độ thăm d&ograve;. Q kiểm so&aacute;t việc khai th&aacute;c l&agrave; h&agrave;m gi&aacute; trị của h&agrave;nh động được t&iacute;nh to&aacute;n từ phương ph&aacute;p MCTS.
<h2 style="text-align: justify;">Bước mở rộng v&agrave; đ&aacute;nh gi&aacute;</h2>
Với đường đi đ&atilde; chọn được quyết định, một n&uacute;t l&aacute; sẽ được th&ecirc;m v&agrave;o c&acirc;y t&igrave;m kiếm. N&oacute; sử dụng mạng học s&acirc;u f để t&iacute;nh to&aacute;n chiến thuật p v&agrave; V.
&nbsp;
N&uacute;t l&aacute; được mở rộng với c&aacute;c cạnh (s, a). Mỗi cạnh được khởi tạo bằng c&ocirc;ng thức sau: <img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/6c77fcb5-2348-4fb4-b385-89bffef35318" alt="" width="600" height="175" />
[latexpage]\[(p,v)=f_{\theta}\]
[latexpage]\[{N(s_{L},a)=0, W(s_{L},a)=0,Q(s_{L},a)=0,P(s_{L},a)=p_{a}}\]
N&oacute; đặt gi&aacute; trị 0 cho visit count N, gi&aacute; trị của h&agrave;nh động được t&iacute;ch lũy W v&agrave; gi&aacute; trị của h&agrave;nh động Q. P được khởi tạo bởi v, được t&iacute;nh từ mạng học s&acirc;u f.
<h2 style="text-align: justify;">Backup</h2>
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/c2fb67c9-5048-4188-abb7-7da35ce4537e" alt="" width="600" height="206" />
Sau khi p v&agrave; v được t&iacute;nh cho n&uacute;t l&aacute;, ch&uacute;ng ta sẽ lưu trữ v để cập nhật gi&aacute; trị của h&agrave;nh động Q cho mọi cạnh (s, a) trong đường đi đ&atilde; được chọn.
[latexpage]\[(p,v)=f_{\theta}\]
[latexpage]\[N(s,a)=N(s,a)+1\]
[latexpage]\[W(s,a)=W(s,a) + v\]
[latexpage]\[Q(s,a)=\frac{W(s,a)}{N(s,a)}\]
<h2 style="text-align: justify;">Thực hiện</h2>
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/dce01a3d-d414-4d39-bee1-772efe907b61" alt="" width="600" height="162" />
Để quyết định bước đi tiếp theo, AlphaGo Zero sẽ lấy mẫu một bước đi&nbsp;[latexpage]$\alpha$ dựa tr&ecirc;n c&ocirc;ng thức:
[latexpage]\[\pi(a|s)=N(s,a)^{1/ \tau}/ \sum_{b}N(s,b)^{1/ \tau}\]
[latexpage]\[a\sim \pi\]
Bước đi đ&atilde; chọn [latexpage]$\alpha$ sẽ trở th&agrave;nh n&uacute;t gốc của c&acirc;y t&igrave;m kiếm với tất cả c&aacute;c n&uacute;t con của n&oacute; được giữ nguy&ecirc;n trong khi c&aacute;c n&uacute;t kh&aacute;c sẽ bị loại bỏ. Sau đ&oacute;, thực hiện lại phương ph&aacute;p MCTS một lần nữa cho bước đi tiếp theo.
Đến đ&acirc;y l&agrave; kết th&uacute;c của b&agrave;i n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c phần tiếp theo nh&eacute;!
P/s: Mong mọi người lu&ocirc;n ủng hộ <a href="http://tek4.vn">tek4</a> nh&eacute;!
<hr />
Fanpage Facebook:&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a>&nbsp;
Tham gia cộng đồng để chia sẻ, trao đổi v&agrave; thảo luận:&nbsp;<a href="https://www.facebook.com/groups/tek4.vn/">TEK4.VN - Học Lập Tr&igrave;nh Miễn Ph&iacute;</a>

Admin

Phương Pháp Duyệt Cây Monte Carlo – Học Tăng Cường

Cùng tác giả

Admin

Có liên quan