Bài giảng Trí tuệ nhân tạo: Chương 4 - TS. Nguyễn Văn Hiệu

Chương này giới thiệu về các thuật toán tìm kiếm trong trò chơi đối kháng, một lĩnh vực quan trọng của trí tuệ nhân tạo. Chúng ta sẽ khám phá cách máy tính có thể đưa ra quyết định tối ưu trong môi trường cạnh tranh, nơi có nhiều người chơi với mục tiêu khác nhau.

Sinh viên và nhà nghiên cứu trong lĩnh vực trí tuệ nhân tạo, đặc biệt là những người quan tâm đến lý thuyết trò chơi và các thuật toán tìm kiếm.

Chương này đi sâu vào các khái niệm và thuật toán cơ bản để giải quyết các bài toán tìm kiếm trong môi trường trò chơi đối kháng. Đầu tiên, chúng ta sẽ tìm hiểu về cách biểu diễn trò chơi dưới dạng 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à các cạnh đại diện cho các nước đi có thể. Tiếp theo, chúng ta sẽ khám phá thuật toán Minimax, một phương pháp tìm kiếm đệ quy để xác định nước đi tốt nhất cho người chơi, giả định rằng đối thủ cũng sẽ chơi tối ưu. Thuật toán này dựa trên việc đánh giá các trạng thái cuối cùng của trò chơi và lan truyền các giá trị này ngược lên cây để chọn nước đi mang lại lợi ích cao nhất. Để cải thiện hiệu suất của thuật toán Minimax, chúng ta sẽ nghiên cứu kỹ thuật cắt tỉa Alpha-Beta, một phương pháp loại bỏ các nhánh không cần thiết của cây trò chơi mà không ảnh hưởng đến kết quả cuối cùng. Kỹ thuật này giúp giảm đáng kể không gian tìm kiếm và cho phép máy tính đưa ra quyết định nhanh hơn. Cuối cùng, chúng ta sẽ xem xét một số ví dụ cụ thể về các trò chơi đối kháng và cách áp dụng các thuật toán tìm kiếm này để giải quyết chúng.