Adversarial Search là gì? Trí tuệ thông minh sẽ chiến thắng con người?

Giới thiệu về Adversarial Search

Adversarial Search có nhiều hơn một thực thể và mỗi thực thể có những mục tiêu và chúng mâu thuẫn với nhau. Các thực thể này đọ sức với nhau trong một tình huống tương tự trò chơi với chiến lược hoặc cách tiếp cận khác nhau tùy theo nước đi của đối thủ.

Người chơi trong Adversarial Search có thể đóng vai trò tối đa hóa (maximizer) hoặc vai trò thu nhỏ (minimizer) tùy thuộc vào tình huống của trò chơi và ý định của đối thủ. Maximizer sẽ luôn cố gắng tối đa hóa lợi nhuận, và Minimizer sẽ cố gắng kiểm soát thiệt hại và giảm thiểu tổn thất.

Trong khi, hoạt động tìm kiếm, thông thường, sẽ thu hút một thực thể duy nhất trong không gian tìm kiếm và tuân theo một tập hợp các quy tắc, cụ thể là thuật toán hoặc kinh nghiệm dựa trên mức độ ưu tiên / phỏng đoán trong quá khứ.

Kết quả cho ra là một tập hợp các hành động được quy định theo trình tự và nó chính xác hơn trong trường hợp thuật toán chứ không phải trong phương pháp heuristics (các kỹ thuật dựa trên kinh nghiệm để giải quyết vấn đề).

Định nghĩa ngắn gọn về Adversarial Search là gì?

Adversarial Search là một phương pháp được áp dụng cho một tình huống mà bạn lên kế hoạch trong khi một tác nhân khác chuẩn bị chống lại bạn. Do đó, kế hoạch của bạn có thể bị ảnh hưởng bởi hành động của đối thủ. Thuật ngữ "search - tìm kiếm" trong Adversarial Search đề cập đến các trò chơi, ít nhất là trong lĩnh vực trí tuệ nhân tạo (AI).

Tầm quan trọng của Adversarial Search

Thuật toán này là một trong những thuật toán được yêu thích nhất trong đấu trường trí tuệ nhân tạo và nó cung cấp các giải pháp trong môi trường nhiều người chơi với các tình huống phức tạp như:

• Mỗi người chơi sẽ phải xem xét chuyển động của những người chơi khác, xây dựng chiến lược một cách linh hoạt để đạt được mục tiêu cuối cùng.
• Người chơi đưa ra các lượt không thể lường trước để làm đối phương khó chịu và giành chiến thắng trong trò chơi.
• Một số trò chơi có tính chất hợp tác, nhưng hầu hết chúng đều mang tính cạnh tranh.
• Mỗi người chơi đều có những mục tiêu đối ngược nhau, và đối thủ là người không thể đoán trước.
• Cần phải có phản ứng nhanh để lập chiến lược và giành chiến thắng trong trò chơi.
• Xử lý tất cả các loại trò chơi có kết quả có thể dự đoán, không thể đoán và tuân theo các quy tắc và điều lệ.

Các tìm kiếm này khá rộng rãi trên tất cả các lĩnh vực ngay từ chính trị, kinh doanh, kinh tế nơi mà sự cạnh tranh rất cao và các kỹ thuật này tối ưu hóa thời gian, công sức và chi phí.

Các kịch bản trò chơi khác nhau sử dụng Adversarial Search

1. Trò chơi với thông tin đầy đủ

Đây là những trò chơi công khai và minh bạch, nơi mỗi người chơi có tất cả thông tin đầy đủ về trạng thái của trò chơi, đối thủ có động thái khá rõ ràng. Cờ vua, cờ caro, Ethello và cờ vây… là một số trò chơi như vậy.

2. Trò chơi có thông tin không hoàn hảo

Trong những trò chơi này, người chơi sẽ không có bất kỳ thông tin nào về trạng thái của trò chơi, và nó sẽ có những bước di chuyển không lường trước bởi những người chơi giả định và dự đoán kết quả. Tic-Tac-Toe, Battleship, Blind và Bridge… là một số ví dụ về loại trò chơi này.

3. Trò chơi xác định

Các trò chơi này tuân theo các quy tắc và khuôn mẫu được xác định trước, và nó được chơi một cách minh bạch. Mỗi người chơi có thể nhìn thấy rõ các bước di chuyển của các đối thủ. Cờ vua, Cờ caro, Tic-tac-toe, Cờ vây là một số trò chơi được chơi theo cách này.

4. Trò chơi không xác định

May mắn, Cơ hội, Xác suất đóng một vai trò quan trọng trong các loại trò chơi này. Kết quả của những trò chơi này rất khó đoán và người chơi sẽ chơi ngẫu nhiên dựa vào may mắn. Poker, Monopoly, Backgammon là một số ít trò chơi được chơi theo phương pháp này.

5. Trò chơi Zero-Sum

Các trò chơi này hoàn toàn mang tính chất cạnh tranh và lợi ích của một người chơi được là thua lỗ của người chơi khác. Giá trị ròng của lãi và lỗ bằng 0 và mỗi người chơi sẽ có các chiến lược khác nhau trong các trò chơi này. Tùy thuộc vào môi trường trò chơi và tình huống trò chơi, mỗi người chơi sẽ cố gắng tối đa hóa lợi ích hoặc giảm thiểu tổn thất.

Nước đi hoặc chiến lược không chỉ phụ thuộc vào tình huống và môi trường trò chơi mà còn phụ thuộc vào chiến lược và kế hoạch trò chơi có thể xảy ra của đối thủ. Đây được gọi là tư duy giải quyết vấn đề trong AI, người chơi có thể lùi lại và thay đổi chiến lược của mình tùy thuộc vào tiến trình của trò chơi. Cờ vua, Tic-tac-toe là một số trò chơi được chơi theo quy tắc này.

Cách Adversarial Search hoạt động

Mỗi trò chơi đều có thể được coi là một loại tìm kiếm trong AI và có các yếu tố sau:

• Bắt đầu: liên quan đến trạng thái ban đầu và thiết lập của.
• Người chơi: những người tham gia vào không gian trò chơi.
• Hành động: biểu thị các bước di chuyển của người chơi trong không gian.
• Kết quả: kết quả của nước đi của người chơi.
• Kiểm tra đầu cuối: nó cho biết liệu trò chơi đã kết thúc hay chưa.
• Tiện ích: thể hiện kết quả cuối cùng của trò chơi dưới dạng thua hay thắng hoặc các giá trị.

Adversarial Search và quy trình Minimax

Trong các cuộc tìm kiếm đối thủ, một người chơi sẽ cố gắng tìm kiếm các bước đi có thể ảnh hưởng đến các nước đi của đối thủ để tác động đến cấu hình tổng thể của trò chơi. Để có thể làm như vậy, người chơi đó phải sử dụng chiến lược tư duy nhìn xa trông rộng. Tức là, trước khi thực hiện một bước đi, họ nhìn vài cấp độ trên cây trò chơi để xem nước đi của mình tác động đến điều gì.

Các đối thủ trong trò chơi được gọi là MIN và MAX, được hiểu đơn giản: MAX đại diện cho người chơi đang cố gắng giành chiến thắng hoặc tối đa hóa lợi thế của mình; MIN là đối thủ cố gắng thu nhỏ MAX.

Giả định, MIN sử dụng cùng một thông tin và luôn cố gắng chuyển MAX sang trạng thái xấu nhất. Bộ tối đa hóa phải lưu ý rằng bộ thu nhỏ có những lựa chọn nào trong bước tiếp theo. Bộ thu nhỏ phải lưu ý rằng bộ tối đa có những lựa chọn nào trong bước tiếp theo. Ví dụ:

Đứng ở nút A, MAX muốn quyết định nút nào sẽ truy cập tiếp theo, tức là chọn giữa B hoặc C. MAX muốn tối đa điểm nên rõ ràng 7 là lựa chọn, vậy nên MAX phải đi đến C để sau đó đến G. Nhưng khi bộ tối đa đạt đến C thì lượt chọn nút tiếp theo thuộc về bộ thu nhỏ, điều này sẽ buộc MAX đến nút F với số điểm là 2.

Do đó, MAX sẽ chỉ có điểm 2 nếu anh ta đi đến C từ A. Mặt khác, nếu MAX đi đến B từ A, thay vì C thì MIN có thể làm anh ta buộc đến nút 3 điểm. Bây giờ, vì sự lựa chọn là giữa điểm 3 hoặc 2, bộ tối đa hóa sẽ đi đến nút B từ A.

Adversarial Search hoạt động trong quy trình minimax như sau:

• Nó có mục đích là tìm ra chiến lược tối ưu cho MAX để chiến thắng trong trò chơi.
• Nó tuân theo cách tiếp cận: Tìm kiếm theo độ sâu trước tiên.
• Trong cây trò chơi, nút lá tối ưu có thể xuất hiện ở bất cứ độ sâu nào.
• Truyền các giá trị minimax tới cây trò chơi cho đến khi phát hiện ra nút đầu cuối.

Công dụng của Adversarial Search

Adversarial Search được sử dụng trong nhiều lĩnh vực để tìm giải pháp tối ưu trong môi trường cạnh tranh với một số ứng dụng là:

• Trong hệ thống pháp luật, khi hai người tranh luận cho lập trường về các vụ việc của họ,  Thẩm phán hoặc Hội đồng xét xử lấy tín hiệu từ các kỹ thuật giải thích ở trên, phân tích và đưa ra phán quyết.
• Những kỹ thuật này được sử dụng trong môi trường kinh doanh để tìm nguồn cung ứng cho các nhà cung cấp và người mua sản phẩm, dịch vụ theo cách thức cạnh tranh.
• Bất cứ nơi nào cần có những cuộc đàm phán khó, những khái niệm này sẽ giúp tối đa hóa lợi ích của những người đàm phán thông minh và thận trọng.
• Khái niệm này là cơ sở để phát triển thêm các công nghệ mới như cắt tỉa Alpha-Beta.

Adversarial Search và Trò chơi

Adversarial Search hoặc các trò chơi sử dụng nó có các liên kết phức tạp đến AI. Thật vậy, AI đang tạo ra sự khác biệt trong hầu hết mọi lĩnh vực, bao gồm cả cách chơi và ngược lại, trò chơi cũng đóng một vai trò quan trọng trong việc nghiên cứu AI.

Các nhà nghiên cứu AI của Pioneer đã sử dụng cờ vua để kiểm tra trí thông minh của các sáng tạo của họ. Tiền đề là khi một cỗ máy có trí thông minh giống con người đã đánh bại con người trong một trò chơi như cờ vua.

Cờ vua

Năm 1997, siêu máy tính có tên "Deep Blue" của IBM đã làm được điều đó. Và nó không đánh bại không ai khác mà là nhà vô địch cờ vua thế giới - Garry Kasparov. Trong một bài luận, Kasparov đã viết về trận đấu đầu tiên của mình với Deep Blue vào năm 1996, rằng anh ấy đã chơi nhiều lần với máy tính, nhưng trận đấu với Deep Blue hoàn toàn khác.

Anh ấy cảm nhận được một “loại trí thông minh mới trên bàn”. Trong một trận tái đấu năm 1997, cao thủ cờ vua đã thua siêu máy tính. Trong trường hợp này, chúng ta có thể suy ra rằng Deep Blue làm tốt hơn trong việc tìm kiếm đối thủ.

Thật vậy, Deep Blue có sức mạnh tính toán khổng lồ. Nó có thể xem xét 100-200 tỷ vị trí mỗi giây và có khoảng 4.000 vị trí trong mở đầu.

Năm 2006, một nhà vô địch thế giới khác, Vladimir Kramnik, bị đánh bại bởi một cỗ máy. Lần này là của Deep Fritz, một chương trình máy tính chơi cờ vua của Đức.

Cờ caro

Cờ caro là một trò chơi hai người chơi khác có thể sử dụng tính năng tìm kiếm đối thủ. Một chương trình máy tính có tên “Chinook” đã được phát triển đặc biệt, để chơi trong Giải vô địch cờ vua thế giới. Vào năm 1990, nó đã đạt được mục tiêu. 

Tuy nhiên, trái ngược với Deep Blue và Deep Fritz, kiến ​​thức về trò chơi của Chinook không được học thông qua AI, vì các nhà phát triển của nó đã lập trình mọi thứ. Tuy nhiên, không thể chống lại thực tế rằng nó là một ứng dụng mạnh mẽ. Nó có không gian tìm kiếm là 5 × 1020 hoặc 500.000.000.000.000.000.000.000 bộ di chuyển.

Cờ vây

AlphaGo là một chương trình máy tính được thiết kế để học và làm chủ board game đã 3.000 năm tuổi - Cờ vây. Nó sử dụng máy học (ML), mạng thần kinh sâu và đã làm chủ cuộc chơi, đánh bại các nhà vô địch cờ vây như Lee Se-dol và Fan Hui.

Se-dol nghỉ hưu vào năm 2019, tuyên bố rằng: "Ngay cả khi tôi trở thành số một, vẫn có một thực thể không thể bị đánh bại". Anh ấy đang đề cập đến các đối thủ cờ vây được hỗ trợ bởi AI, chẳng hạn như AlphaGo.

Các trò chơi hai người chơi như cờ vua, cờ caro và cờ vây đã đi được một chặng đường dài với sự trợ giúp của các phương pháp Adversarial Search và các công nghệ khác. Mặc dù, các quy tắc trò chơi tương tự vẫn được sử dụng, nhưng thật đáng kinh ngạc khi biết rằng những cỗ máy thông minh cũng có thể chống lại con người. Chúng ta cũng có thể trau dồi kỹ năng chơi các loại trò chơi này bằng cách chơi với máy.