Thạc Sĩ Giải thuật tìm kiếm minimax và ứng dụng trong các trò chơi có tổng bằng không

LỜI NÓI ĐẦU

Lý thuyết trò chơi (game theory) thường được coi là một nhánh của toán học ứng dụng và kinh tế học ứng dụng nhằm nghiên cứu về các tình huống trong đó các bên tham gia trò chơi áp dụng những chiến lược ra quyết định nhằm tối ưu hóa kết quả mình nhận được. Ban đầu Lý thuyết trò chơi được phát triển như một công cụ để nghiên cứu hành vi kinh tế học, ngày nay Lý thuyết này được sử dụng trong nhiều ngành khoa học như Sinh học, Triết học, Chính trị học Đặc biệt Lý thuyết trò chơi đã thu hút được sự chú ý của các nhà Khoa học máy tính do ứng dụng của nó trong Trí tuệ nhân tạo và Điều khiển học.
Trí tuệ nhân tạo đã vận dụng Lý thuyết trò chơi để nghiên cứu về các trò chơi đối kháng và thiết kế chương trình chơi cờ giữa Người và Máy tính. Do bùng nổ tổ hợp quá lớn của cây trò chơi mà cả người và máy không thể (và không bao giờ) có thể tìm kiếm vét cạn (hết mọi khả năng). Do đó phương pháp tìm kiếm duy nhất là chỉ tìm kiếm đến một độ sâu giới hạn nào đó và chọn nước đi dẫn đến một thế cờ có lợi nhất cho mình. Do phải tính cả khả năng chống trả của đối phương nên ta không dùng được các thuật toán tìm kiếm thông thường mà phải dùng một thuật toán tìm kiếm riêng cho cây trò chơi, đó là thuật toán theo chiến lược Minimax. Đây cũng là chiến lược hiệu quả áp dụng trong các trò chơi có tổng bằng không. Chúng ta đều biết, nhiều tình huống trong thực tế đặc biệt là trong lĩnh vực Kinh tế, Chính trị có thể nhìn nhận như một trò chơi có tổng bằng không. Do đó việc nghiên cứu chiến lược tìm kiếm nước đi cho dạng trò chơi này có thể mang lại những ý nghĩa thực tiễn nhất định.
Nội dung của luận văn tìm hiểu và nghiên cứu về thuật toán tìm kiếm đối kháng Minimax, các cải tiến của nó và ứng dụng trong trò chơi có tổng bằng không. Nội dung bản luận văn được chia làm 3 chương:
Chương 1 trình bày một cách tổng quan về các vấn đề tìm kiếm : bài toán tìm kiếm, biểu diễn vấn đề bằng không gian trạng thái và các kỹ thuật tìm kiếm cơ bản.
Chương 2 trình bày giải thuật tìm kiếm Minimax và giải thuật cải tiến Alpha-beta áp dụng cho các trò chơi với tổng bằng không. Mỗi giải thuật được trình bày gồm các nội dung: ý tưởng, thủ tục thực hiện giải thuật và đánh giá.
Chương 3 trình bày một ứng dụng của thuật toán tìm kiếm Minimax áp dụng cho trò chơi xếp các quân hậu lên bàn cờ có chướng ngại vật.
Trong thời gian học tập và nghiên cứu để hoàn thành luận văn này, tác giả đã nhận được sự quan tâm, hướng dẫn, đóng góp của các thầy cô, các bạn bè và người thân.
Trước hết, tác giả xin được dành lời cảm ơn chân thành và lòng biết ơn sâu sắc nhất tới giáo viên hướng dẫn của mình là Tiến sĩ Nguyễn Thị Hồng Minh, người đã định hướng, gợi mở những ý tưởng sâu sắc và hiệu quả, đã tận tình chỉ bảo giúp đỡ tác giả về mọi mặt để có thể hoàn thành nhiệm vụ nghiên cứu.
Luận văn được thực hiện bằng những kiến thức mà tác giả được trang bị trong suốt 2 năm học tại Khoa Toán - Cơ - Tin, Trường Đại Học Khoa học tự nhiên với sự giảng dạy nhiệt tình của các giảng viên và sự hăng say học tập của các học viên. Lời cảm ơn chân thành xin được gửi tới các thầy, cô trong khoa Toán-Cơ-Tin học, đặc biệt các thầy cô trong bộ môn Tin học, các anh, chị và bạn bè trong cùng lớp cao học chuyên ngành Bảo đảm toán học cho máy tính và hệ thống tính toán khóa 2007-2009.
Lời cảm ơn cuối cùng xin được dành cho gia đình và những bạn bè thân thiết, những người đã dành sự quan tâm và động viên hết mực để tác giả hoàn thành tốt bản luận văn này.


Mục lục
LỜI NÓI ĐẦU 3
CHƯƠNG 1: TỔNG QUAN VỀ CÁC VẤN ĐỀ TÌM KIẾM 5
1.1 Bài toán tìm kiếm và không gian trạng thái 5
1.1.1 Bài toán tìm kiếm 5
1.1.2 Không gian tìm kiếm 7
1.2 Các kỹ thuật tìm kiếm cơ bản 10
1.2.1 Tìm kiếm không có thông tin 11
1.2.2 Tìm kiếm có thông tin 14
1.2.3 Tìm kiếm đối kháng 15
CHƯƠNG 2: GIẢI THUẬT TÌM KIẾM MINIMAX 20
2.1 Giới thiệu 20
2.1.1 Trò chơi có tổng bằng không (Zero-sum-game) 21
2.1.2 Định lý Minimax 26
2.2 Giải thuật Minimax 27
2.2.1 Ý tưởng 27
2.2.2 Áp dụng giải thuật Minimax đến độ sâu lớp cố định 31
2.2.3 Thủ tục Minimax 33
2.2.4 Đánh giá 38
2.3 Giải thuật cải tiến Alpha-beta 38
2.3.1 Ý tưởng 40
2.3.2 Giải thuật 42
2.3.3 Đánh giá 44
2.4 So sánh giải thuật Minimax và giải thuật Alpha-beta. 47
CHƯƠNG 3: ỨNG DỤNG 50
3.1 Phân tích bài toán 50
3.1.1 Trò chơi 50
3.1.2 Cơ sở lý thuyết 52
3.2 Cài đặt chương trình 52
3.2.1 Cấu trúc chương trình và mối quan hệ giữa các lớp chính 52
3.2.2 Lớp Form1 54
3.2.3 Lớp CBoard 54
3.2.4 Lớp gameAI 55
3.3 Một số giao diện và kết quả chạy chương trình 66
KẾT LUẬN 70
Tài liệu tham khảo 71