Tìm kiếm đồ thị Monte Carlo bắt đầu từ các nguyên lý cơ bản

 (github.com/lightvector)
3 điểm bởi GN⁺ 2024-03-11 | 1 bình luận | Chia sẻ qua WhatsApp
  • Monte-Carlo Graph Search (MCGS) là một cách tiếp cận nhằm áp dụng MCTS lên đồ thị có hướng thay vì cây trong các trò chơi nơi nhiều chuỗi nước đi có thể chuyển tới cùng một trạng thái, để chia sẻ phần tìm kiếm trùng lặp
  • Nếu giữ nguyên số lần thăm N và giá trị trung bình Q của MCTS hiện có rồi chuyển sang DAG, số lần thăm của nút con được chia sẻ có thể lệch khỏi ước lượng chính sách và giá trị của nút cha, khiến thuật toán trở nên không còn vững
  • Nếu xem MCTS như tối ưu hóa chính sách có chuẩn hóa, thì phân phối số lần thăm theo từng hành động do PUCT tạo ra là một chính sách hậu nghiệm, còn Q được diễn giải là lợi ích kỳ vọng của chính sách đó
  • MCGS đúng đắn sẽ theo dõi riêng số lần thăm cạnh N(n,a) bên cạnh số lần thăm nút con, và tính lại Q bằng tổng có trọng số của U(n) và Q của các nút con để giữ nguyên ý nghĩa của chính sách và giá trị ngay cả trên đồ thị
  • Trong triển khai thực tế vẫn còn các lựa chọn như stale Q, cập nhật tăng dần, có tiếp tục playout từ nút con đã chuyển vị hay không, cũng như xử lý va chạm băm và chu trình trong ván đấu; hiện tại KataGo dùng cập nhật idempotent

Trạng thái chuyển vị mà tìm kiếm trên cây bỏ lỡ

  • Trong tìm kiếm trên cây trò chơi, có những trường hợp các chuỗi nước đi khác nhau chuyển vị (transposition) tới cùng một trạng thái
    • Trong cờ vua, 1. d4 d5 2. Nf3 và 1. Nf3 d5 2. d4 đi tới cùng một thế cờ
  • Ở các trò chơi có chuyển vị, khi độ sâu tìm kiếm tăng lên thì số trạng thái trùng lặp có thể tăng theo cấp số nhân, nên việc chia sẻ tính toán cho cùng một trạng thái là điều đáng mong muốn
  • Các triển khai MCTS thông thường coi trò chơi như một cây phân nhánh, nên sẽ lại tiếp tục tìm kiếm nhiều bản sao của cùng một thế cờ
    • Các tối ưu hóa mức thấp như cache đánh giá mạng nơ-ron cho thế lặp có thể giảm chi phí
    • Nhưng vẫn còn vấn đề là nếu phát hiện được một chiến thuật quan trọng ở một bản sao và sửa lại đánh giá, thì điều đó không lan sang các bản sao khác
  • Nếu mô hình hóa không gian trạng thái thành đồ thị có hướng không chu trình (DAG), thì khi nhiều đường đi dẫn tới cùng một trạng thái, ta có thể biểu diễn trạng thái đó bằng một nút duy nhất
  • Bài viết chủ yếu bỏ qua việc xử lý các trò chơi có chu trình thật sự, và tập trung vào việc MCTS nên hoạt động thế nào trên DAG

MCTS tiêu chuẩn: cây tích lũy thống kê theo lần chạy

  • MCTS tiêu chuẩn lưu một phần của trò chơi đã tìm kiếm thành cây nút trong bộ nhớ
  • Mỗi nút thường theo dõi các giá trị sau
    • N: số playout đã đi qua nút này hoặc kết thúc tại nút này
    • Q: trung bình chạy của các giá trị lợi ích mà những playout đó đã lấy mẫu
  • Một playout diễn ra theo thứ tự sau
    • Bắt đầu từ nút gốc, đi xuống bằng cách chọn hành động tiếp theo theo công thức khám phá
    • Khi chạm tới một trạng thái chưa được tìm kiếm, thêm nút mới
    • Lấy giá trị lợi ích U của trạng thái mới. Ví dụ là truy vấn value head của mạng nơ-ron
    • Đi ngược lên cây, tăng N của từng nút và cập nhật trung bình Q
  • Trong MCTS kiểu AlphaZero, việc chọn hành động dùng công thức PUCT
    • N(a): số lần hành động a được thử; trong cây thì bằng N của nút con mà hành động đó trỏ tới
    • Q(a): lợi ích trung bình của hành động a; bằng Q của nút con
    • PlayerToMove: phản ánh người chơi hiện tại đang muốn tối đa hóa hay tối thiểu hóa
    • P(a): xác suất tiên nghiệm như dự đoán chính sách của mạng nơ-ron
    • c_PUCT: hằng số điều chỉnh được
  • “PUCT” xuất phát từ họ Predictor UCT/UCB dùng phân phối tiên nghiệm dự đoán, và biến thể AlphaZero có dạng hàm khác với hình thức ban đầu
  • MCTS hiện đại có thể mang tính xác định khi dùng đánh giá bằng mạng nơ-ron, nhưng chữ “Monte-Carlo” trong tên đến từ cách cũ là chạy rollout ngẫu nhiên tới hết ván để ước lượng lợi ích
  • Sau khi lặp playout cho tới khi hết ngân sách tính toán của lượt đi, tại nút gốc sẽ chọn nút con có số lần thăm N lớn nhất làm hành động cuối cùng thay vì chọn theo Q
    • Nút con có Q cao nhưng N thấp có thể chỉ là một nước đi bị nhiễu làm cho trông tốt hơn trong tìm kiếm nông
  • Phân phối số lần thăm ở nút gốc N(a) / ΣN(b) có thể được dùng làm mục tiêu học chính sách trong vòng lặp huấn luyện AlphaZero

Vấn đề khi áp dụng một cách ngây thơ lên DAG

  • Có thể giữ gần như nguyên mã MCTS trên cây, rồi nếu trạng thái trò chơi mới đã có trong nodes_by_hash thì cho nó trỏ tới nút hiện có
  • Cách này không còn giữ được giả định của cây rằng số lần thăm nút con bằng với số lần thăm hành động mà nút cha đã chọn
  • Tình huống ví dụ
    • Nút A ưu tiên hành động đi tới nút C, và Q của A chủ yếu được quyết định bởi khoảng 30 playout đã khám phá C
    • C còn được thăm khoảng 40 lần từ các đường chuyển vị khác
    • Sau đó C tiếp tục được thăm nhiều hơn từ các đường chuyển vị khác và phát hiện ra chiến thuật sâu hơn, làm ước lượng lợi ích của C tăng từ 0.39 → 0.51
  • Vì các playout cập nhật C không đi qua A, nên Q của A không phản ánh đánh giá mới của C
  • Ngay cả khi A sau đó nhận thêm playout, PUCT vẫn có thể khám phá các hành động khác có số lần thăm thấp thay vì C đã có nhiều lượt thăm
    • Bởi C trông như là “đã được tìm kiếm đủ rồi”
    • Kết quả là Q của A thậm chí có thể giảm xuống
  • Mở rộng đồ thị theo cách ngây thơ sẽ khiến càng nhiều đường chuyển vị thăm một nước đi đang được ưa thích ở phía trên, nút cha lại càng khám phá các nước khác nhiều hơn, tạo ra thiên lệch nhân tạo trong trung bình playout
  • Nó trở thành một thuật toán không vững, đến mức ngay cả trong tìm kiếm vô hạn cũng không rõ có hội tụ về nước tối ưu hay không

Cập nhật mọi nút cha cũng không giải quyết được

  • Khi một nút được cập nhật bởi một playout nào đó, ta cũng có thể nghĩ đến cách phản ánh nó không chỉ lên các nút cha thật sự mà playout đã đi qua, mà còn lên mọi nút cha và tổ tiên
  • Cách này có thể cùng cập nhật lợi ích của A trong ví dụ A-C trước đó
  • Nhưng ở ví dụ khác, nút cha D lại bị nhiễm bởi rất nhiều lượt thăm của nút con chuyển vị F mà bản thân D không ưu tiên
    • Nút con tốt nhất của D là E với Q = 0.56, và Q = 0.55 của D phù hợp với điều đó
    • D chỉ khám phá F một lần, nhưng F đã được thăm 9 lần từ đường khác nên tổng cộng là 10 lần
    • Sau đó nếu F được thăm thêm 100 lần từ các đường khác mà vẫn giữ lợi ích thấp, cách cập nhật mọi nút cha có thể kéo Q của D xuống 0.35
  • Từ góc nhìn của D, nó không hề muốn phân bổ nhiều playout đến thế cho F, nên cập nhật mọi nút cha cũng là cách phá vỡ ý nghĩa của chính sách

Xem MCTS như tối ưu hóa chính sách

Giá trị mà π tối đa hóa:
Σ π(a) Q(a) - λ_N D_KL(P || π)
  • Ý nghĩa của các thành phần
    • Σ π(a) Q(a): lợi ích kỳ vọng được ước lượng khi đi theo chính sách π
    • D_KL(P || π): độ phân kỳ KL ngược đo khác biệt giữa chính sách tiên nghiệm P và chính sách hậu nghiệm π
    • λ_N: hệ số quyết định độ mạnh của hạng KL, giảm dần khi số lần thăm tăng
  • Phân phối số lần thăm có thể được xem là chính sách hậu nghiệm bắt đầu từ chính sách tiên nghiệm P của mạng nơ-ron và dần được cải thiện khi có thêm lượt thăm để tích lũy bằng chứng về lợi ích của từng hành động
  • Vì vậy, MCTS có thể được diễn giải như một thuật toán đồng thời thực hiện học chính sách trực tuyến nhỏ tại mỗi nút trong cây
  • Góc nhìn này giải thích vì sao phân phối số lần thăm trông giống chính sách của một tác tử mạnh, và vì sao nó được dùng làm mục tiêu học chính sách trong AlphaZero
  • Cũng có thể tính nghiệm chính xác của bài toán tối ưu rồi dùng làm chính sách, nhưng trên thực tế cách đó có thể đặt trọng số lớn lên những nước đi ít được thăm mà ngẫu nhiên có vẻ có Q cao
    • Nếu dùng phân phối số lần thăm làm chính sách hậu nghiệm, một nước đi muốn có trọng số cao thì phải thật sự được tìm kiếm nhiều, nên vững hơn

Diễn giải lại Q: từ trung bình playout sang kỳ vọng theo chính sách

  • Theo định nghĩa tiêu chuẩn, Q(n) của nút n là trung bình lợi ích của các playout đã thăm n
Q(n) = (1 / N(n)) Σ U(p)
  • Viết lại theo các nút con thì thành
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
  • Ở đây U(n) là ước lượng lợi ích thô từ mạng nơ-ron của chính nút n, còn N(c) Q(c) là giá trị nút con được gán trọng số theo số lần thăm của từng nút con
  • Vì vậy Q có thể được diễn giải là trung bình có trọng số theo phân phối số lần thăm của các Q nút con
  • Nếu phân phối số lần thăm là chính sách hậu nghiệm mà MCTS đang tối ưu, thì Q(n) là lợi ích kỳ vọng đã chuẩn hóa khi đi theo chính sách hậu nghiệm đó
  • Trong cách diễn giải này, mỗi nút liên tục tối ưu chính sách để tối đa hóa Q mà các nút con báo về, rồi cập nhật Q của chính nó thành ước lượng mới nhất về lợi ích kỳ vọng có thể đạt được dưới chính sách đó
  • Nếu Q của các nút con hội tụ về giá trị tối ưu theo lý thuyết trò chơi, thì chính sách và Q của nút cha cũng sẽ hội tụ đệ quy về giá trị tối ưu

MCGS đúng đắn: tách riêng lượt thăm cạnh và lượt thăm nút con

  • Vấn đề trong đồ thị phát sinh vì ta giả định rằng lượt thăm nút con chỉ có thể đến từ chính nút cha đó
  • Khi có các đường chuyển vị, số lần thăm nút con có thể khác tùy ý so với số lần thăm mà PUCT định phân bổ từ nút cha đó
  • Cách giải là theo dõi riêng số lần tích lũy mà PUCT đã chọn một hành động tại một nút cụ thể
  • Mỗi nút n theo dõi các giá trị sau
    • N(n): tổng số lần nút này được thăm
    • N(n,a): số lần PUCT chọn hành động a tại nút n, tức số lần thăm cạnh
    • Q(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
  • Ở đây Q(n,a) bằng Q(c) của nút con c đạt được khi đi hành động a
  • Trong phép tính PUCT cũng dùng số lần thăm cạnh thay vì số lần thăm nút con
argmax_a PlayerToMove(n) * Q(n,a)
       + c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
  • Thuật toán cơ bản là chọn các hành động trên đường playout, nếu trạng thái chuyển vị đã tồn tại thì nối tới nút cũ, rồi khi quay lui tăng số lần thăm cạnh và tính lại N cùng Q dưới dạng hàm của các giá trị nút con
  • Cách này tương tự ở mức độ cao với Monte-Carlo Graph Search for AlphaZero của Czech, Korus và Kersting, nhưng được suy ra từ góc nhìn tối ưu hóa chính sách thay vì từ góc nhìn thống kê theo lần chạy

Lựa chọn triển khai: stale Q và cách cập nhật

  • Mã giả được nêu chỉ cập nhật các nút trên đúng đường mà playout đã đi qua
  • Vì thế Q của các nút ở đường không đi qua có thể trở thành stale Q
  • Dù vậy về mặt lý thuyết nó vẫn vững
    • Các công thức khám phá tiêu chuẩn như PUCT trong giới hạn sẽ thử mọi hành động vô hạn lần
    • Khi một nút được thăm lại, tại thời điểm đó nó sẽ trực tiếp tính ra Q đúng bằng cách dùng Q của các nút con và số lần thăm cạnh hiện tại
    • Trên DAG, về mặt giới hạn nó có thể hội tụ tới giá trị tối ưu theo lý thuyết trò chơi
  • Stale Q có thể làm giảm hiệu quả tìm kiếm
    • Có thể giữ con trỏ tới nút cha để cập nhật luôn Q của nút cha
    • Có thể cập nhật mọi tổ tiên theo thứ tự topo để loại bỏ trạng thái stale
    • Có thể chỉ cập nhật đường playout trong khi một luồng song song riêng tìm các nút stale để cập nhật
  • Mã giả dùng cập nhật idempotent
    • Bất kể trước đó có cập nhật trung gian nào, chỉ cần thăm nút thêm một lần thì N và Q của nó sẽ lại khớp với các giá trị hiện tại của các nút con
  • Cũng có thể cập nhật tăng dần, nhưng trên đồ thị thì khó làm sao cho tương đương hoặc tương đương trong giới hạn hơn
  • Czech và cộng sự tiếp cận từ góc nhìn thống kê theo lần chạy nên dùng các công thức mang tính tăng dần hơn
    • Họ lưu không chỉ số lần thăm cạnh mà còn cả Q của cạnh
    • Có cơ chế để stale Q dần bắt kịp giá trị mới nhất cùng với siêu tham số cho phép sai số
  • Mã giả được nêu cho thấy có thể làm MCGS hoạt động mà không cần tham số cho phép sai số mới hay lưu Q của cạnh
  • KataGo hiện đang dùng công thức idempotent

Có nên tiếp tục playout từ nút con đã chuyển vị không

  • Trong MCTS trên cây, việc tăng số lần thăm cạnh và tăng số lần thăm nút con là cùng một sự kiện
  • Trên đồ thị, do chuyển vị, nút con có thể đã được thăm nhiều hơn cạnh tương ứng
  • Lúc này có thể coi nút con là đã được thăm đủ, dừng playout lại, chỉ tăng số lần thăm cạnh rồi cập nhật nút cha và tổ tiên
  • Lý do để ưu tiên dừng
    • Nếu số lần thăm cạnh thấp mà số lần thăm nút con cao, thì lượng thông tin biên thu được từ thêm một lượt thăm cho nút con đó có thể nhỏ
  • Lý do để ưu tiên tiếp tục
    • Nút có số lần thăm con lớn hơn số lần thăm cạnh có khả năng là nút được nhiều cha chuyển vị tới, nên nó ảnh hưởng đến nhiều nút cha hơn và vì thế cần đánh giá chính xác hơn
  • Lựa chọn này vẫn là một vùng cần thực nghiệm
    • Cũng có thể dùng cách đặt ngưỡng và chỉ dừng khi số lần thăm nút con lớn hơn số lần thăm cạnh đủ nhiều
  • KataGo mặc định dừng playout, nhưng có tùy chọn cấu hình để tiếp tục hoặc chỉ dừng một phần theo xác suất
  • Mã giả không dừng playout; nếu cần có thể thêm một dòng kiểm tra với điều kiện child.N <= edge_visits

Băm, nút kết thúc và chu trình thật trong trò chơi

  • Trong mã giả, nút kết thúc trò chơi được tính lại với N = 1, U = Q = lợi ích kết quả ván đấu bất kể số lần thăm
    • Số lần thăm của cạnh tương ứng ở nút cha vẫn tăng bình thường nên cách này vẫn khả thi
    • Nếu kết quả ván đấu là ngẫu nhiên và không thể trực tiếp tính lợi ích kỳ vọng, thì việc tăng N ở mỗi lần thăm nút kết thúc và lấy trung bình các kết quả được lấy mẫu có thể trở nên quan trọng
  • Cũng có thể xử lý lợi ích kết thúc ván rộng hơn để truyền các giá trị có thể chứng minh được lên đồ thị nhanh hơn
    • MCTS/MCGS thông thường không có cơ chế nhận biết giá trị lợi ích chắc chắn, nên khi trạng thái kết thúc quan trọng thì chúng không hội tụ tới giá trị tối ưu với chi phí rẻ như tìm kiếm cổ điển kiểu alpha-beta
  • Để phát hiện chuyển vị, bài viết giả định có băm duy nhất của trạng thái trò chơi
    • Việc tạo ra hàm băm thật sự không va chạm cho các trạng thái trò chơi phức tạp có thể khó và tốn kém
    • Một Zobrist hash đủ lớn như 128 bit hoặc 192 bit thường là đủ trong thực tế để gần như loại bỏ va chạm, miễn là trạng thái không được tạo ra theo cách đối kháng
    • Để tránh đệ quy vô hạn khi va chạm băm tạo ra chu trình, có thể thêm cơ chế phát hiện chu trình
  • Bài viết không đi sâu vào việc xử lý các chu trình phát sinh từ luật chơi thực tế như superko trong cờ vây hay lặp lại 3 lần trong cờ vua
  • Phụ lục ngày 2024-03-10 cung cấp liên kết Google Docs chứa thêm một số suy nghĩ còn thô về việc xử lý lặp lại và chu trình, và có thể cần thử nghiệm heuristic theo từng trò chơi
  • Trong cách KataGo xử lý cờ vây, hệ thống tận dụng một định lý chuyên biệt cho cờ vây rằng để quay về vị trí ban đầu sau một số nước nhất định thì cần ít nhất S + E - 1 nước, từ đó giới hạn việc chia sẻ nút trong các tình huống liên quan đến chu trình một cách ổn định

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-03-11
Ý kiến trên Hacker News

  • Tôi nghĩ kiểu tìm kiếm đồ thị này là cần thiết để thúc đẩy suy luận AI. Chỉ dùng LLM đơn thuần thì khả năng thất bại là cao
    Trong liên kết có nhiều tài liệu tham khảo hay, bao gồm Zobrist hashing cho bàn cờ: https://en.wikipedia.org/wiki/Zobrist_hashing
    Cần tìm cách băm tốt phù hợp với mô tả trạng thái dựa trên ngôn ngữ, để lượng tính toán của tìm kiếm đồ thị không bùng nổ
    Về tìm kiếm cây, cũng đáng đọc Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 và Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642, bài so sánh cách tiếp cận MCTS với các chiến lược học tăng cường khác hiện nay

    • Cái này có vẻ quá cấp thấp
      Để tiến thêm một bước, có thể là cách học đồng thời biểu diễn trạng thái và thuật toán tìm kiếm. Tức là thuật toán tìm kiếm sẽ tìm trên biểu diễn trạng thái của mạng nơ-ron, nơi nó có thể nhận được chi phí
      https://sites.google.com/view/genie-2024/
      Genie của DeepMind là một ví dụ tốt về mô hình hóa trạng thái rời rạc. Mạng nơ-ron học một biểu diễn rất phức tạp, bao gồm phát hiện va chạm và hành động. Thay vì giải mã trạng thái đó thành pixel, có lẽ ta có thể tìm kiếm trực tiếp trên trạng thái đó
      Tất nhiên cấu trúc này trên thực tế có thể khá khác
    • Dù đơn giản hóa quá mức, tôi nghĩ một hướng đáng khám phá là thế này
      Với một tập các lập luận logic, tìm cách gán hash cho từng lập luận, rồi biểu diễn các hash lập luận đó dưới dạng cây Merkle lồng nhau theo nguyên lý đầu tiên
      Nếu một lập luận bị phản bác thành công, hash của lập luận đó thay đổi, và hash của các lập luận con cũng trở nên vô hiệu
    • Tôi tự hỏi liệu có cách nào kết hợp hai thứ đó không. Khó mà tin rằng bộ não chỉ dùng một kỹ thuật duy nhất cho mọi việc; nhiều khả năng nó có nhiều công cụ và một bộ chọn ở phía trên để quyết định khi nào dùng công cụ nào

  • Nhìn tác giả trong URL HN là tôi nhận ra ngay đây là thiên tài đã tạo ra KataGo: https://github.com/lightvector/KataGo
    Các bài viết người này đăng trên https://www.reddit.com/r/cbaduk/ cũng luôn rất xuất sắc

    • URL đúng nghĩa là nằm trong repo KataGo

  • Tôi không có quá nhiều kinh nghiệm cờ vua, nhưng khá hoài nghi với nhận định rằng cùng một thế cờ bị lặp lại trong cây tìm kiếm đủ thường xuyên để trở nên quan trọng. Tôi muốn xem số đo thực tế bằng Leela Zero
    Nếu đưa cả lặp lại ba lần và luật 50 nước vào trạng thái, khả năng lặp lại sẽ còn thấp hơn nhiều, và tôi nghĩ ngay cả khi chưa xét phần đó thì vẫn vậy

    • Trong cờ vây, ko rất phổ biến. Không được lặp lại nguyên trạng vị trí trên bàn, nhưng nếu tìm kiếm cây không đánh giá đúng vị trí ko, rất dễ tạo ra tình huống AI đi nước dở

  • Điều kỳ lạ là, trái với cái tên “Monte-Carlo Tree Search”, trong thuật toán trên hoàn toàn không có Monte Carlo và nó hoàn toàn mang tính quyết định. Họ nói MCTS thường được triển khai theo cách quyết định sao? Tôi cứ tưởng tính ngẫu nhiên nằm ở việc lấy mẫu

    • Ban đầu MCTS có tính ngẫu nhiên. Bài viết dường như cũng có nhắc đến: nó thực hiện playout để đánh giá vị trí ở bước cuối
      Trong các dự án tương tự hiện nay, phần này được thay bằng đánh giá mạng nơ-ron chất lượng cao hơn. Cách đi ngẫu nhiên để xem ai thắng không hay lắm, nhưng đó là chiến lược tốt nhất được biết vào thời điểm đó
      Rốt cuộc, phần Monte Carlo ngay cả hiện nay cũng không phải yếu tố cốt lõi của thứ vẫn được gọi là MCTS; nó đúng hơn là một phương án kém hơn. Vì vậy cái tên hơi không may
    • Nói chặt chẽ thì đây là một thuật toán khác nằm dưới cùng cái tên “monte carlo”
      Điểm thú vị là đa số phương pháp Monte Carlo dựa vào bộ sinh số giả ngẫu nhiên chứ không phải bộ sinh số ngẫu nhiên thật, nên với cùng seed và đầu vào, chúng là các phương pháp quyết định luôn cho cùng kết quả
      Thuật toán này truy vấn mạng nơ-ron thay vì dùng bộ sinh số giả ngẫu nhiên thông thường và các heuristic riêng. Mạng nơ-ron là một heuristic trên không gian tìm kiếm khổng lồ, nên tùy theo huấn luyện, nó hoạt động như một bộ sinh số giả ngẫu nhiên rất tệ bị lệch mạnh về một kết quả cụ thể, và rốt cuộc trông giống như một bộ sinh số giả ngẫu nhiên có áp dụng heuristic
      Điểm quan trọng là đây là một chuyên biệt hóa của MCTS, nên về mặt kỹ thuật nó không phù hợp với mọi trường hợp sử dụng
    • Nếu có tính ngẫu nhiên thì tôi tò mò liệu nó có hội tụ không, và cần bao nhiêu tài nguyên-thời gian. Điều này cũng có thể khác nhau tùy theo CPU, RAM, GPU, TPU, QPU

  • Khi tìm hiểu MCTS, bài báo được nhắc trong bài viết hoàn toàn nằm ngoài radar của tôi. Lần tới nếu tự chạy thử cách sửa đổi này chắc sẽ khá thú vị

  • Giá mà có một phần giới thiệu ngắn gọn

    • Khi tạo AI chơi game, nói rộng ra thì hầu như AI nào cũng vậy, một trong những kỹ thuật triển vọng nhất là tìm kiếm cây. Nó xếp hạng nước đi hiện tại dựa trên các nước đi tiếp theo
      Trong các trò chơi mà có thể đạt cùng một trạng thái qua nhiều đường khác nhau, có thể lãng phí nhiều bộ nhớ vì ghi lại cùng một nút trạng thái ở các nhánh khác nhau
      Bài viết này xem xét kỹ cách tiếp cận gọi là tìm kiếm đồ thị. Về bản chất là tính thêm hash của trạng thái trò chơi để kiểm tra xem đó có phải nút đã thăm hay không, đổi lại tiết kiệm bộ nhớ
      Vì không cần ghi lại lần nữa các nút đã thấy, cây không có chu trình sẽ trở thành đồ thị có hướng không chu trình
      Vì vậy, để có kết quả đúng, cần chỉnh sửa đôi chút cách tìm kiếm cây. Đặc biệt, đơn vị tối ưu hóa nên nghiêng nhiều hơn về cạnh, tức hành động hay nước đi, thay vì đỉnh, tức trạng thái
      Đây là một bài tiểu luận kỹ thuật viết tốt theo phong cách lập trình văn chương, do người hiểu rõ chủ đề viết