Adversarial Search là một cuộc tìm kiếm, nơi chúng tôi xem xét vấn đề nảy sinh khi chúng tôi cố gắng lên kế hoạch trước và các tác nhân khác đang lên kế hoạch chống lại người chơi.
Trong các chủ đề trước, chúng ta đã nghiên cứu các chiến lược tìm kiếm chỉ được kết hợp với một tác nhân duy nhất nhằm mục đích tìm ra giải pháp thường được thể hiện dưới dạng một chuỗi các hành động.
Tuy nhiên, có thể có một số tình huống trong đó nhiều hơn một tác nhân đang tìm kiếm giải pháp trong cùng một không gian tìm kiếm và tình huống này thường xảy ra khi chơi trò chơi.
Môi trường có nhiều hơn một tác nhân được gọi là môi trường đa tác nhân, trong đó mỗi tác nhân là đối thủ của tác nhân khác và chơi với nhau. Mỗi tác nhân cần xem xét hành động của tác nhân khác và ảnh hưởng của hành động đó đối với hoạt động của họ.
Các bài viết liên quan:
Vì vậy, các Tìm kiếm trong đó hai hoặc nhiều người chơi có mục tiêu mâu thuẫn nhau đang cố gắng khám phá cùng một không gian tìm kiếm cho giải pháp, được gọi là tìm kiếm đối nghịch, thường được gọi là Trò chơi.
Trò chơi được mô hình hóa như một bài toán Tìm kiếm và chức năng đánh giá theo kinh nghiệm, và đây là hai yếu tố chính giúp tạo mô hình và giải quyết trò chơi trong AI.
Các loại trò chơi trong AI:
- Perfect information Cờ vua, Cờ caro, cờ vây, Backgammon, monopoly
- Imperfect information Battleships, blind, tic-tac-toe, Bridge, poker, scrabble, nuclear war
Perfect information: Một trò chơi có Perfect information là trong đó các nhân viên có thể nhìn vào bảng hoàn chỉnh. Các nhân viên có tất cả thông tin về trò chơi, và họ cũng có thể nhìn thấy các bước di chuyển của nhau. Ví dụ như Cờ vua, Cờ caro, Cờ vây, v.v.
Imperfect information: Nếu nhân viên trò chơi không có tất cả thông tin về trò chơi và không biết chuyện gì đang xảy ra, thì loại trò chơi đó được gọi là trò chơi có Imperfect information, chẳng hạn như tic-tac-toe, Battleship, Blind, Bridge,….
Deterministic games: Trò chơi xác định là những trò chơi tuân theo một khuôn mẫu và bộ quy tắc chặt chẽ cho trò chơi và không có sự ngẫu nhiên nào liên quan đến chúng. Ví dụ như cờ vua, cờ caro, cờ vây, tic-tac-toe, v.v.
Non-deterministic games: Không xác định là những trò chơi có nhiều sự kiện không thể đoán trước và có yếu tố may rủi. Yếu tố may rủi hoặc may rủi này được đưa vào bởi xúc xắc hoặc thẻ bài. Đây là ngẫu nhiên và mỗi phản hồi hành động không cố định. Những trò chơi như vậy còn được gọi là trò chơi ngẫu nhiên.
Ví dụ: Backgammon, Monopoly, Poker, v.v.
Lưu ý: Trong chủ đề này, chúng ta sẽ thảo luận về các trò chơi xác định, môi trường có thể quan sát được đầy đủ, tổng bằng 0 và nơi mỗi tác nhân hành động theo cách khác.
Xem thêm Hàm max trong c++
Zero-Sum Game
- Zero-sum game không là Adversarial Search liên quan đến cạnh tranh thuần túy.
- Trong trò chơi Zero-sum, lợi ích hoặc mất mát của mỗi tác nhân được cân bằng chính xác với tổn thất hoặc thu được về tiện ích của một tác nhân khác.
- Một người chơi của trò chơi cố gắng tối đa hóa một giá trị duy nhất, trong khi người chơi khác cố gắng giảm thiểu nó.
- Mỗi nước đi của một người chơi trong trò chơi được gọi là lớp.
- Cờ vua và tic-tac-toe là những ví dụ về Zero-sum game.
Zero-sum game: Tư duy
Zero-sum game liên quan đến suy nghĩ được nhúng trong đó một đặc vụ hoặc người chơi đang cố gắng tìm ra:
- Làm gì.
- Làm thế nào để quyết định việc di chuyển
- Cũng cần nghĩ về đối thủ của mình
- Đối phương cũng nghĩ làm gì
Mỗi người chơi đang cố gắng tìm ra phản ứng của đối thủ đối với hành động của họ. Điều này đòi hỏi tư duy nhúng hoặc suy luận ngược để giải quyết các vấn đề của trò chơi trong AI.
Tổng quát hóa vấn đề:
Trò chơi có thể được định nghĩa là một loại tìm kiếm trong AI có thể được chính thức hóa bằng các yếu tố sau:
- Trạng thái ban đầu: Nó chỉ định cách trò chơi được thiết lập khi bắt đầu.
- (Các) người chơi: Nó chỉ định người chơi nào đã di chuyển trong không gian trạng thái.
- (Các) Hành động: Nó trả về tập hợp các bước di chuyển hợp pháp trong không gian trạng thái.
- Result (s, a): Là mô hình chuyển tiếp, chỉ rõ kết quả của các chuyển động trong không gian trạng thái.
- (Các) kiểm tra đầu cuối: Kiểm tra đầu cuối là đúng nếu trò chơi kết thúc, nếu không, sai trong bất kỳ trường hợp nào. Trạng thái mà trò chơi kết thúc được gọi là trạng thái cuối.
- Utility (s, p): Một hàm tiện ích cung cấp giá trị số cuối cùng cho một trò chơi kết thúc ở trạng thái đầu cuối s đối với người chơi p. Nó còn được gọi là hàm trả thưởng. Đối với Cờ vua, kết quả là thắng, thua hoặc hòa và giá trị kết quả của nó là +1, 0, ½. Và đối với tic-tac-toe, các giá trị tiện ích là +1, -1 và 0.
Game tree:
Game tree là cây trong đó các nút của cây là trạng thái trò chơi và Các cạnh của cây là các bước di chuyển của người chơi. Game tree liên quan đến trạng thái ban đầu, chức năng hành động và chức năng kết quả.
Ví dụ: Game tree Tic-Tac-Toe:
Hình dưới đây là một phần của Game tree cho trò chơi tic-tac-toe. Sau đây là một số điểm chính của trò chơi:
- Có hai người chơi MAX và MIN.
- Người chơi có một lượt thay thế và bắt đầu với MAX.
- MAX tối đa hóa kết quả của Game tree
- MIN thu nhỏ kết quả.
Giải thích Ví dụ:
- Từ trạng thái ban đầu, MAX có thể có 9 bước di chuyển khi anh ta xuất phát đầu tiên. TỐI ĐA vị trí x và TỐI ĐA vị trí o, và cả hai người chơi sẽ chơi xen kẽ cho đến khi chúng ta đến một nút lá nơi một người chơi có ba người liên tiếp hoặc tất cả ô vuông được lấp đầy.
- Cả hai người chơi sẽ tính toán từng nút, minimax, giá trị minimax là tiện ích có thể đạt được tốt nhất để chống lại kẻ thù tối ưu.
- Giả sử cả hai cầu thủ đều nhận thức rõ về tic-tac-toe và chơi lối chơi tốt nhất. Mỗi người chơi đang cố gắng hết sức để ngăn người khác giành chiến thắng. MIN đang chống lại Max trong trò chơi.
- Vì vậy, trong Game tree, chúng ta có một lớp Max, một lớp MIN và mỗi lớp được gọi là Ply. Đặt tối đa x, sau đó MIN đặt o để ngăn Max thắng và trò chơi này tiếp tục cho đến khi kết thúc.
- Trong trận đấu này, MIN thắng, MAX thắng hoặc hòa. Game tree này là toàn bộ không gian tìm kiếm các khả năng mà MIN và MAX đang chơi tic-tac-toe và thay phiên nhau.
Do đó, Adversarial Search cho quy trình minimax hoạt động như sau:
- Nó nhằm mục đích tìm ra chiến lược tối ưu cho MAX để giành chiến thắng trong trò chơi.
- Nó tuân theo cách tiếp cận của Tìm kiếm theo độ sâu trước tiên.
- Trong Game tree, nút lá tối ưu có thể xuất hiện ở bất kỳ độ sâu nào của cây.
- Truyền các giá trị minimax tới cây cho đến khi phát hiện ra nút đầu cuối.
Trong một Game tree nhất định, chiến lược tối ưu có thể được xác định từ giá trị minimax của mỗi nút, có thể được viết dưới dạng MINIMAX (n). MAX thích chuyển sang trạng thái có giá trị lớn nhất và MIN thích chuyển sang trạng thái có giá trị nhỏ nhất thì:
