Tic-tac-toe MDP trăn
Q-learning là một phương pháp học tăng cường tuyệt vời và cơ bản đã cho thấy rất nhiều thành công gần đây nhờ cuộc cách mạng học sâu. Mặc dù hướng dẫn này sẽ không giải thích cái được gọi là deep Q-learning, nhưng chúng ta sẽ đi qua thuật toán Q-learning ban đầu để dạy một tác nhân cách chơi trò tic-tac-toe. Mặc dù đơn giản, nhưng chúng ta sẽ thấy rằng nó có thể mang lại kết quả tuyệt vời Show
Đầu tiên, chúng ta sẽ lướt qua một số kiến thức cơ bản cần thiết để có cái nhìn tổng quan về học tăng cường, sau đó chúng ta sẽ trình bày thuật toán Q-learning và cuối cùng là cách triển khai nó để dạy một tác nhân chơi tic-tac-toe Để hiểu hướng dẫn này, không cần thiết phải có bất kỳ kiến thức nào trước đó về học tăng cường nhưng sẽ giúp bạn có hiểu biết cơ bản về giải tích và đại số tuyến tính. Cuối cùng, tôi đang chia sẻ kho lưu trữ Github của riêng mình, nơi tôi có những thứ mà tôi giải thích mà bạn có thể xem miễn phí, hãy nhấp vào đây nếu bạn quan tâm Tổng quan về học tăng cườngMục tiêu của học tăng cường là tối ưu hóa hành vi của một tác tử theo một số chức năng phần thưởng khi nó hoạt động trong một môi trường có các trạng thái khác nhau. Đối với hướng dẫn này, môi trường là trò chơi tic-tac-toe có các hành động được xác định rõ ràng và nhân viên phải quyết định chọn hành động nào để giành chiến thắng trong trò chơi. Hơn nữa, đại lý sẽ nhận được phần thưởng khi chiến thắng trò chơi, điều này khuyến khích đại lý học các chiến lược tốt trong trò chơi Một khuôn khổ phổ biến cho việc học tăng cường là Quy trình quyết định Markov (hữu hạn) (MDP). Nó giúp chúng tôi xác định một tập hợp các hành động và trạng thái làm cơ sở cho việc ra quyết định của tác nhân Một MDP bao gồm
Hàm chuyển tiếp đưa ra xác suất chuyển từ trạng thái s sang s' khi thực hiện hành động a. Điều này là cần thiết khi chúng ta ở trong một môi trường không chắc chắn liệu một hành động có luôn tạo ra kết quả mong muốn hay không. Tuy nhiên, trong trường hợp tic-tac-toe, chúng tôi biết chính xác mỗi hành động sẽ làm gì nên chúng tôi sẽ không sử dụng hành động này Khung MDP giúp chúng tôi chính thức hóa vấn đề để xác định hành động nào, tùy thuộc vào trạng thái hiện tại, sẽ tối đa hóa tổng phần thưởng của tác nhân trong trò chơi. Hàm phần thưởng R(s,a) sẽ rất đơn giản
Trong học tăng cường, chúng tôi tìm cách tìm ra một chính sách tối ưu mà tác nhân sử dụng để quyết định chọn hành động nào. Vì chúng tôi đang sử dụng Q-learning, chúng tôi sẽ chỉ biểu thị chính sách của mình là hành động a làm cực đại hàm Q(s,a) khi tác tử ở trạng thái s. Đây là cốt lõi của Q-learning, vậy chúng ta hãy tính toán hàm này như thế nào Đối với mọi trạng thái trong trò chơi, mỗi hành động được liên kết với một giá trị Q. Chiến lược tốt nhất là chọn hành động có giá trị cao nhất. Trong ví dụ này với trạng thái s, lượt tiếp theo thuộc về người chơi X và rõ ràng hành động nào có phần thưởng được mong đợi cao nhất vì X sắp thắngCập nhật với phương trình BellmanGiải thích Q(s,a) là Q là phần thưởng dự kiến được đưa ra khi kết thúc trò chơi nếu tác nhân chọn hành động a ở trạng thái s. Vì đại lý muốn tối đa hóa phần thưởng của mình, nên họ muốn chọn hành động tối đa hóa Q Ví dụ về tình huống trong đó chúng tôi hiển thị các giá trị Q cho người chơi X hiện tại ở trạng thái này của trò chơi. Bằng cách đặt điểm đánh dấu tiếp theo ở vị trí có giá trị lớn nhất, người chơi sẽ thắng trò chơi và nhận phần thưởng. (Hình của tác giả)Để tính Q(s,a), tác nhân phải khám phá tất cả các cặp trạng thái và hành động có thể có trong khi nhận phản hồi từ hàm phần thưởng R(s,a). Trong trường hợp tic-tac-toe, chúng tôi cập nhật Q(s,a) lặp đi lặp lại bằng cách cho phép người đại diện chơi nhiều trò chơi với đối thủ. Với thuật toán Q-learning, phương trình được sử dụng để cập nhật Q như sau
Phương trình này dựa trên phương trình nổi tiếng trong học tăng cường được gọi là phương trình Bellman. Hãy xem cách sử dụng phương trình này để dạy cho đại lý của chúng tôi Triển khai thuật toán Q-learningĐể có được một đại lý được đào tạo, chúng ta cần tìm hiểu các giá trị của Q(s,a). Điều này sẽ được thực hiện bằng cách để hai tác nhân chơi với nhau. Chúng tôi sẽ đưa ra xác suất ε là mỗi tác nhân chọn một hành động ngẫu nhiên, nếu không, nó sẽ chọn hành động tốt nhất theo Q(s,a). Bằng cách này, chúng tôi đảm bảo cân bằng việc học sao cho các tác nhân đôi khi khám phá các hành động mới và những lần khác khai thác thông tin mà tác nhân đã học được Giai đoạn đào tạo này có thể được mô tả bằng mã giả sau của thuật toán Q-learning Initialise: Q(s,a) = 0, starting state s, Chú ý số lần lặp N phải tương đối lớn, mình đang dùng khoảng 500.000. Ngoài ra, Q(s,a) có thể được triển khai dưới dạng lệnh Python hoặc dưới dạng mảng hai chiều nếu chúng ta biểu diễn (s,a) dưới dạng số nguyên. Cuối cùng, có thể thay đổi xác suất ε theo thời gian để nhấn mạnh việc khám phá ngẫu nhiên hơn trong các lần lặp lại trước đó, điều này có thể tăng tốc độ học tập Sau khi bạn đã đào tạo đại lý của mình bằng thuật toán, bạn có thể lưu các giá trị của Q(s,a) và tải nó khi bạn muốn chơi với đại lý. Sau đó, tác nhân chỉ cần tuân theo chính sách tối ưu bằng cách chọn các hành động tối đa hóa Q(s,a). Mặc dù tác nhân không trở nên thông minh lắm vì trò chơi tic-tac-toe đơn giản như thế nào, nhưng vẫn rất thú vị khi thử trò này nếu bạn muốn tìm hiểu cách triển khai Q-learning và thấy rằng nó hoạt động Tóm lượcTóm lại, hướng dẫn này lần đầu tiên giải thích khung Quá trình quyết định Markov (MDP) và cách nó được sử dụng trong học tăng cường. Chúng tôi đã lập mô hình trò chơi tic-tac-toe bằng cách sử dụng các trạng thái, hành động và chức năng phần thưởng. Ngoài ra, chúng tôi đã xác định hàm Q(s,a) định lượng phần thưởng mong đợi bằng cách chọn hành động a ở trạng thái s và đưa ra công thức tính Q(s,a) bằng cách chơi trò chơi nhiều lần Tôi hy vọng rằng bạn thích hướng dẫn này, nếu bạn có bất kỳ câu hỏi nào thì bạn có thể liên hệ với tôi tại đây hoặc qua Twitter. Và cuối cùng, nếu bạn muốn xem nó hoạt động như thế nào trong thực tế thì hãy xem triển khai của tôi trong kho lưu trữ Github của tôi được liên kết bên dưới Làm thế nào để tạo một ngón chân tic tac trong Python?Xây dựng trò chơi Tic-Tac-Toe bằng Python và Tkinter . Xác định các lớp cho người chơi và di chuyển của họ Tạo một lớp để thể hiện logic trò chơi Thiết lập bảng trò chơi trừu tượng Tìm ra các kết hợp chiến thắng Thuật toán nào được sử dụng cho Tic Tac Toe trong Python?Thuật toán Minimax là một quy tắc quyết định được xây dựng cho các trò chơi có tổng bằng 0 của 2 người chơi (Tic-Tac-Toe, Cờ vua, Cờ vây, v.v. ). Thuật toán này đi trước một vài bước và đặt mình vào vị trí của đối thủ.
Làm thế nào để tạo ra một trò chơi tic tac toe?Thứ tự chung của các bước triển khai. . Tạo một bảng Tic Tac Toe và tô nó bằng dấu gạch ngang Tạo một chức năng vẽ bảng như một hình vuông Theo dõi lượt của người chơi và biểu tượng họ đang sử dụng Tiếp tục yêu cầu người dùng nhập hàng và cột cho đến khi chúng hợp lệ Làm thế nào để giải quyết vấn đề Tic Tac Toe trong AI?3 cách khác nhau để giải Bài toán Tic-Tac-Toe khi áp dụng AI là gì? . độ phức tạp của chúng Sử dụng khái quát hóa Sự rõ ràng về kiến thức của họ Khả năng mở rộng của phương pháp của họ |