Cơ vua chọn nước đi bằng thuật toán minimax năm 2024
|
Các trò chơi có dạng như cờ Vua, cờ Tướng, cờ Vây, cờ Caro,… là những trò chơi đối kháng, diễn ra giữa hai đấu thủ. Nói chung, các trò chơi này đều có thể chuyển về một dạng bài toán tìm kiếm đặc biệt: tìm đường đi đến các điểm cao nhất giữa hai đấu thủ. Đặc điểm của loại trò chơi này như sau: Show
Cây trò chơi: các trạng thái bàn cờ khác nhau trong quá trình chơi có thể biểu diễn thành một cây tìm kiếm và ta sẽ tiến hành tìm kiếm trên cây để tìm được nước đi tốt nhất. Ở cây này, các nút của cây là các tình huống khác nhau của bàn cờ, các nhánh nối sẽ cho ta biết từ một tình huống cờ thế này chuyển sang tình huống cờ như thế khác thông qua một nước đi đơn nào đó. Các nước đi này diễn ra theo cặp do hai đấu thủ lần lượt tiến hành. Độ sâu của cây trò chơi là số tầng của cây Vét cạn: thuật toán vét cạn có thể hiểu đơn giản là sinh ra hết tất cả mọi khả năng có thể xảy ra trong trò chơi. Sau đó tiến hành lựa chọn đánh giá trên từng khá năng, từ đó chọn ra phương án tối ưu nhất. Trong cờ vua, nếu bạn áp dụng thuật toán này để tính toán nước đi, kết quả trả về sẽ rất chính xác. Nếu vậy thì việc cho máy tính chơi cờ vua chẳng có gì gọi là khó khăn. Tuy nhiên, may mắn thay cách làm này không thể thực hiện được do một hiện tượng gọi là bùng nổ tổ hợp. Ví dụ nếu một thế cờ trung bình với khả năng đi được 16 nước khác nhau (ta gọi hệ số nhánh con tại mỗi nút là b = 16). Như vậy, sau một tầng ta sẽ có 16 nút con, mỗi nút có thể có 16 nút con nữa. Tổng số nút con tại độ sâu thứ hai là 16*16 = b^2. Cứ như vậy ở độ sâu d sẽ có b^d nút. Thử làm một phép toán nhỏ, nếu giả sử độ sâu của cây là 100 (hệ số nhánh 16 và độ sâu 100 đều là những con số nhỏ hơn con số thường gặp trong cá trò chơi cờ), áp dụng thuật toán vét cạn, ta phải duyệt 16^100 nhánh hay xấp xải 10^120 nhánh – một con số lớn khủng khiếp. Qua phân tích trên ta thấy không thể áp dụng hoàn toàn thuật toán vét cạn vào trò chơi được. Để tạo ra một thuật toán đánh cờ vua tối ưu cho máy tính, chúng ta phải xác định được chiến lược tìm kiếm trong trò chơi rồi dựa vào đó xây dựng nên những thuật toán tối ưu cho máy tính.
Chiến lược tìm kiếm: Một chiến lược thường được cả người lẫn máy dùng là phân tích thế cờ chỉ sau một số nước đi nào đó của cả hai bên. Sau khi “nhìn xa” xem bàn cớ có những khả năng biến đổi như thế nào sau một số nước, ta sẽ đánh giá độ tốt xấu của các thế cờ nhận được. Tiếp theo, ta sẽ chọn nước đi sẽ dẫn tới một thế cờ tốt nhất trong đó số đó có cân nhắc đến cách đi của cả hai bên (thường chúng ta xem như cả hai người đều đưa ra những lựa chọn tối ưu). Với máy thế cờ này được đánh giá tối hơn thế cờ kia nhờ so sánh điểm của thế đó do bộ lượng giá đáp trả lại. Việc lượng giá quân cờ có thể hiểu đơn giản rằng, gán mỗi quân cờ một số điểm. Thường là như sau: Hậu trị giá 9 điểm, Xe trị giá 5 điểm, Tượng và Mã đều trị giá 3 điểm và Tốt trị giá 1 điểm. Do việc mất Vua tương đương với thua cờ nên giá trị của nó là vô hạn, trong cờ tàn nó khoảng 3,5 điểm. Trong lập trình cờ vua, thường người ta cho Vua một giá trị rất lớn nào đó (chẳng hạn 2000 điểm). Tuy nhiên, giá trị thực sự và tầm quan trọng của một quân cờ không thể chỉ đơn giản như vậy. Nó còn phụ thuộc vào thế cờ. Ví dụ một quân Xe đang nằm ở vị trí xấu không có giá trị bằng một con Mã đang có thế đứng tốt. Nếu một người chơi thực hiện việc thí quân (cho phép đối phương bắt quân có trị giá cao của mình) thì thông thường họ sẽ bỏ qua các giá trị danh định dành cho quân đó để đổi lấy các ưu thế về chiến lược hay ưu thế về vị trí của các quân đang tấn công. Khi chơi cờ, chắc chắn bạn phải xét trước một số hữu hạn các nước đi, đề tự tìm chiến thuật cho riêng mình. Người bình thường xét 2-4 nước đi, trong khi các đại kiện tướng có thể xét từ 8-10 nước đi. Rõ ràng nếu càng xét sâu, nước đi càng chắc chắn và cơ hội chiến thắng càng cao. Như vậy, dựa vào chiến lược tìm kiếm ta hiểu ra rằng thay vì xét hết toàn bộ quá trình chơi, các nước đi từ khi bắt đầu đến khi kết thúc, ta có thể xét trong một số hữu hạn các nước. Điều này đảm bảo về mặt thời gian, nhưng cũng góp phần tăng độ chắc chắn trong các nước đi của chúng ta. Bước 1: Trong bước đầu tiên, thuật toán tạo ra Game Tree và áp dụng hàm tiện ích để nhận các giá trị và các trạng thái kết thúc. Trong sơ đồ cây dưới đây, hãy lấy A là trạng thái bắt đầu của Tree. Giả sử bộ tối đa hóa thực hiện lượt đi đầu tiên có giá trị ban đầu trong trường hợp xấu nhất = – infinite và minimizer sẽ thực hiện lượt tiếp theo có giá trị ban đầu trong trường hợp xấu nhất = + infinity. Bước 2: Bây giờ, đầu tiên chúng ta tìm giá trị tiện ích cho Maximizer, giá trị ban đầu của nó là -∞, vì vậy chúng ta sẽ so sánh từng giá trị ở trạng thái đầu cuối với giá trị ban đầu của Maximizer và xác định các giá trị nút cao hơn. Nó sẽ tìm thấy mức tối đa trong số tất cả. Đối với nút D max (-1, – -∞) => max (-1,4) = 4 Đối với nút E max (2, -∞) => max (2, 6) = 6 Đối với nút F max (-3, -∞) => max (-3, -5) = -3 Đối với nút G max (0, -∞) = max (0, 7) = 7 Bước 3: Trong bước tiếp theo, đến lượt trình thu nhỏ, vì vậy nó sẽ so sánh giá trị tất cả các nút với + ∞ và sẽ tìm giá trị nút lớp thứ 3. Đối với nút B = min (4,6) = 4 Đối với nút C = min (-3, 7) = -3 Bước 4: Bây giờ đến lượt Maximizer, nó sẽ lại chọn giá trị lớn nhất của tất cả các nút và tìm giá trị lớn nhất cho nút gốc. Trong Game Tree này, chỉ có 4 lớp, do đó chúng tôi truy cập ngay đến nút gốc, nhưng trong trò chơi thực, sẽ có nhiều hơn 4 lớp. Đối với nút A max (4, -3) = 4 Đó là toàn bộ quy trình làm việc của trò chơi minimax hai người chơi. Các thuộc tính của thuật toán Mini-Max:Complete– Thuật toán Min-Max đã hoàn thành. Nó chắc chắn sẽ tìm thấy một giải pháp (nếu tồn tại), trong cây tìm kiếm hữu hạn. Optimal– Min-Max là tối ưu nếu cả hai đối thủ đều chơi tối ưu. Time complexity– Vì nó thực hiện DFS cho Game Tree, do đó độ phức tạp thời gian của thuật toán Min-Max là O (bm), trong đó b là hệ số phân nhánh của Game Tree và m là độ sâu tối đa của cây. Space Complexity – Độ phức tạp không gian của thuật toán Mini-max cũng tương tự như DFS là O (bm). Giới hạn của thuật toán minimax:Hạn chế chính của thuật toán minimax là nó thực sự chậm đối với các trò chơi phức tạp như Cờ vua, cờ vây, v.v. Loại trò chơi này có hệ số phân nhánh rất lớn và người chơi có rất nhiều lựa chọn recursive. Hạn chế này của thuật toán minimax có thể được cải thiện từ việc lược bớt alpha-beta mà chúng ta đã thảo luận trong chủ đề tiếp theo. Xem thêm Thuật toán Alpha-Beta Pruning Một số câu hỏi phổ biến về thuật toán minimax
Thuật toán minimax là một thuật toán đánh giá giá trị của các nút trong cây trò chơi, để tìm ra nước đi tối ưu cho một người chơi. Thuật toán này được sử dụng rộng rãi trong trò chơi có hai người, như cờ vua, cờ tướng và tic-tac-toe.
Để sử dụng thuật toán minimax trong trò chơi, cần xây dựng một cây trò chơi, trong đó mỗi nút đại diện cho một trạng thái của trò chơi và mỗi cạnh đại diện cho một nước đi. Các nút ở độ sâu chẵn đại diện cho các nước đi của người chơi đang chơi, trong khi các nút ở độ sâu lẻ đại diện cho các nước đi của đối thủ. Thuật toán minimax duyệt cây trò chơi và đánh giá giá trị của các nút lá. Nếu nút lá đại diện cho một trạng thái kết thúc của trò chơi, giá trị của nó được tính bằng cách xem ai đã thắng hoặc thua trò chơi. Nếu nút lá đại diện cho một trạng thái không kết thúc, giá trị của nó được tính bằng cách sử dụng một hàm đánh giá, đại diện cho khả năng thắng của người chơi đang chơi.
Thuật toán minimax có thể được sử dụng để giải quyết các trò chơi có hai người chơi, có hữu hạn số lượng nước đi và không có yếu tố ngẫu nhiên, ví dụ như cờ vua, cờ tướng, tic-tac-toe và Connect Four.
Để tối ưu hóa thuật toán minimax, có thể sử dụng một số kỹ thuật như cắt tỉa alpha-beta hoặc sử dụng các phương pháp đánh giá khác nhau để tăng độ chính xác của giá trị đánh giá của các nút. Ngoài ra, việc sử dụng các cấu trúc dữ liệu hiệu quả để lưu trữ cây trò chơi cũng có thể giúp tăng tốc
Alpha-beta pruning là một kỹ thuật cắt tỉa được sử dụng để tối ưu hóa thuật toán minimax bằng cách loại bỏ các nút không cần thiết trong cây trò chơi. Kỹ thuật này hoạt động bằng cách sử dụng hai giá trị alpha và beta để giới hạn khoảng giá trị đánh giá của các nút con của một nút cha trong cây trò chơi. Khi giá trị đánh giá của một nút con vượt quá giới hạn này, các nút con còn lại của nút cha đó không cần được kiểm tra nữa.
Thuật toán minimax có thể có nhược điểm là thời gian tính toán và không gian lưu trữ tăng lên nhanh chóng với số lượng nút trong cây trò chơi. Điều này đặc biệt đúng đối với các trò chơi lớn và phức tạp như cờ vua, khi số lượng nút có thể lên đến hàng tỷ. Ngoài ra, thuật toán minimax không thể xử lý các trò chơi có yếu tố ngẫu nhiên, ví dụ như poker hoặc blackjack.
Có nhiều phương pháp thay thế cho thuật toán minimax, trong đó phương pháp Monte Carlo là một trong những phương pháp phổ biến nhất. Phương pháp này sử dụng một số lượng lớn các trận đấu mô phỏng để đánh giá giá trị của một nút, thay vì duyệt toàn bộ cây trò chơi. Phương pháp Monte Carlo có thể được sử dụng để giải quyết các trò chơi có yếu tố ngẫu nhiên, như poker hoặc blackjack, và có thể được tối ưu hóa để tăng độ chính xác của kết quả.
Các trò chơi phức tạp hơn, ví dụ như cờ vua, thường có số lượng nút lớn hơn rất nhiều so với các trò chơi đơn giản hơn như tic-tac-toe. Để áp dụng thuật toán minimax vào các trò chơi phức tạp hơn, ta cần sử dụng các kỹ thuật cải tiến để giảm số lượng nút trong cây trò chơi, và tối ưu hóa thời gian tính toán. Một trong những kỹ thuật cải tiến phổ biến là sử dụng bảng tra cứu đánh giá, trong đó các giá trị đánh giá cho các trường hợp đặc biệt đã được tính toán trước và lưu trữ trong bảng. Khi thực hiện thuật toán minimax, ta có thể sử dụng bảng này để tránh tính toán lại các giá trị đánh giá đã được tính toán trước đó. Ngoài ra, ta cũng có thể sử dụng các kỹ thuật thay thế cho thuật toán minimax, như phương pháp Monte Carlo, để giảm thời gian tính toán và tối ưu hóa thuật toán cho các trò chơi phức tạp hơn.
Mặc dù thuật toán minimax thường được sử dụng để giải quyết các trò chơi, nó cũng có thể được áp dụng cho các bài toán tối ưu hóa và quyết định trong các lĩnh vực khác. Ví dụ, thuật toán minimax có thể được sử dụng để tìm kiếm chiến lược tối ưu trong quản lý tài sản và quản lý rủi ro. Thuật toán minimax cũng có thể được sử dụng trong các bài toán tìm kiếm con đường tối ưu trong đường đi tối ưu hoá, tối ưu hóa mạng và tối ưu hóa vận hành của hệ thống. |
