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 7