Giáo trình Trí tuệ nhân tạo - Chương 2, Phần b: Giải quyết vấn đề bằng tìm kiếm - Lý Anh Tuấn

1 Các chiến lược tìm kiếm I. Các chiến lược tìm kiếm II. Các chiến lược tìm kiếm mù - Tìm kiếm theo bề rộng, tìm kiếm theo độ sâu, tìm kiếm theo độ sâu hạn chế, tìm kiếm sâu lặp. III. Các chiến lược tìm kiếm kinh nghiệm - Hàm đánh giá, tìm kiếm tốt nhất đầu tiên, tìm kiếm leo đồi, tìm kiếm A*, tìm kiếm nhánh cận. IV. Tìm kiếm có đối thủ - Cây trò chơi, chiến lược tìm kiếm minimax, phương pháp cắt tỉa alpha-beta. 2 I. Các chiến lược tìm kiếm • Khi ta biểu diễn một vấn đề cần giải quyết thông qua các trạng thái và các toán tử thì việc tìm lời giải của vấn đề được quy về việc tìm đường đi từ trạng thái ban đầu tới một trạng thái kết thúc • Có thể phân các chiến lược tìm kiếm thành hai loại: – Các chiến lược tìm kiếm mù – Các chiến lược tìm kiếm kinh nghiệm (tìm kiếm heuristic). 3 Các chiến lược tìm kiếm • Các chiến lược tìm kiếm mù – Trong các chiến lược tìm kiếm này, không có một sự hướng dẫn nào cho việc tìm kiếm, mà ta chỉ phát triển các trạng thái ban đầu cho tới khi gặp một trạng thái đích nào đó. – Có hai kỹ thuật tìm kiếm mù đó là tìm kiếm theo bề rộng và tìm kiếm theo độ sâu. – Khi sử dụng các chiến lược tìm kiếm mù thì số lượng các trạng thái được phát triển trước khi ta gặp trạng thái đích thường cực kỳ lớn. Do đó các thuật toán tìm kiếm mù kém hiệu quả, đòi hỏi rất nhiều không gian và thời gian. 4 Các chiến lược tìm kiếm • Các chiến lược tìm kiếm kinh nghiệm – Trong rất nhiều vấn đề chúng ta có thể dựa vào sự hiểu biết của chúng ta về vấn đề, dựa vào kinh nghiệm, trực giác, để đánh giá các trạng thái. – Sử dụng sự đánh giá các trạng thái để hướng dẫn sự tìm kiếm: trong quá trình phát triển các trạng thái, ta sẽ chọn trong số các trạng thái chờ phát triển, trạng thái được đánh giá tốt nhất để phát triển. Do đó tốc độ tìm kiếm sẽ nhanh hơn. – Các phương pháp tìm kiếm dựa vào sự đánh giá các trạng thái để hướng dẫn sự tìm kiếm gọi chung là các phương pháp tìm kiếm kinh nghiệm. 5 Cây tìm kiếm • Quá trình tìm kiếm là quá trình xây dựng cây tìm kiếm. Cây tìm kiếm là cây mà các đỉnh được gắn bởi các trạng thái của không gian trạng thái. Gốc của cây tìm kiếm tương ứng với trạng thái ban đầu. • Có thể chuyển vấn đề tìm kiếm đồ thị thành vấn đề tìm kiếm trên cây (hình dưới). 6 Các chiến lược tìm kiếm • Một chiến lược tìm kiếm được xác định bằng việc lựa chọn thứ tự phát triển các nút • Các chiến lược tìm kiếm được đánh giá dựa trên các tiêu chí sau đây: – tính hoàn thành: nó có luôn tìm ra nghiệm nếu thực sự có nghiệm? – độ phức tạp thời gian: số lượng các nút được tạo ra – độ phức tạp không gian: số lượng lớn nhất các nút trong bộ nhớ – tính tối ưu: nó có luôn tìm thấy nghiệm có giá thấp nhất? • Độ phức tạp thời gian và không gian được tính toán dựa trên – b: nhân tố nhánh lớn nhất của cây tìm kiếm – d: độ sâu của nghiệm có giá thấp nhất – m: độ sâu lớn nhất của không gian trạng thái (có thể là ∞) 7 II. Các chiến lược tìm kiếm mù • Các chiến lược tìm kiếm mù: chỉ sử dụng thông tin được cung cấp trong định nghĩa vấn đề • Tìm kiếm theo bề rộng (Breadth-first search) • Tìm kiếm theo độ sâu (Depth-first search) • Tìm kiếm độ sâu hạn chế (Depth-limited search) • Tìm kiếm sâu lặp (Iterative deepening search 8 Tìm kiếm theo bề rộng • Tư tưởng của tìm kiếm theo bề rộng là các trạng thái được phát triển theo thứ tự mà chúng được sinh ra, tức là trạng thái nào được sinh ra trước sẽ được phát triển trước • Thuật toán: 9 Tìm kiếm theo bề rộng • Phát triển nút nông nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào cuối danh sách chờ phát triển 10 Tìm kiếm theo bề rộng • Phát triển nút nông nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào cuối danh sách chờ phát triển 11 Tìm kiếm theo bề rộng • Phát triển nút nông nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào cuối danh sách chờ phát triển 12 Tìm kiếm theo bề rộng • Phát triển nút nông nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào cuối danh sách chờ phát triển 13 Tìm kiếm theo bề rộng • Hoàn thành? Chắc chắn sẽ tìm ra nghiệm nếu bài toán có nghiệm (nếu b là hữu hạn) • Thời gian? 1+b+b2+b3+ +bd + b(bd-1) = O(bd+1) • Không gian? O(bd+1) (luôn giữ tất cả các nút trong bộ nhớ) • Tối ưu? Thuật toán là tối ưu nếu giá = 1 ở mỗi bước • Không gian là vấn đề quan trọng hơn thời gian 14 Tìm kiếm theo độ sâu • Tư tưởng của tìm kiếm theo bề sâu là, tại mỗi bước trạng thái được chọn để phát triển là trạng thái được sinh ra sau cùng trong số các trạng thái chờ phát triển. • Thuật toán: 15 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 16 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 17 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 18 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 19 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 20 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 21 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 22 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 23 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 24 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 25 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 26 Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 27 Tìm kiếm theo độ sâu • Hoàn thành? Không tìm ra nghiệm trong không gian có độ sâu vô hạn, không gian lặp Sửa đổi thuật toán để tránh các đường đi đến các trạng thái gây ra việc lặp lại-> tìm ra nghiệm trong không gian hữu hạn • Thời gian? O(bm): rất lớn nếu m lớn hơn nhiều so với b nhưng nếu bài toán có nhiều nghiệm, có thể thực hiện nhanh hơn tìm kiếm theo bề rộng • Không gian? O(bm) tức là không gian tuyến tính ! (chỉ cần lưu các nút chưa được phát triển là nút con của các nút trên đường đi từ gốc đến nút u) • Tối ưu? Thuật toán không tối ưu 28 Các trạng thái lặp • Cây tìm kiếm có thể chứa nhiều nút ứng với cùng một trạng thái, các trạng thái này được gọi là các trạng thái lặp (xem hình) • Việc không phát hiện ra các trạng thái lặp có thể biến một vấn đề có độ phức tạp tuyến tính thành một vấn đề có độ phức tạp hàm mũ! 29 Các trạng thái lặp • Một số giải pháp để tránh phát triển lại các trạng thái mà ta đã gặp và đã phát triển: – Khi phát triển nút u, không sinh ra các nút trùng với cha của u – Khi phát triển nút u, không sinh ra các nút trùng với một nút nào đó nằm trên đường đi dẫn tới u – Không sinh ra các nút mà nó đã được sinh ra, tức là chỉ sinh ra các nút mới • Hai giải pháp đầu dễ cài đặt và không tốn nhiều không gian nhớ, tuy nhiên không tránh được hết các trạng thái lặp. 30 Tìm kiếm độ sâu hạn chế • Bằng tìm kiếm theo độ sâu với mức giới hạn về độ sâu là l, tức là các nút ở độ sâu l không có nút kế tiếp • Thuật toán: 31 Tìm kiếm sâu lặp • Nếu cây tìm kiếm chứa nhánh vô hạn, khi sử dụng tìm kiếm theo độ sâu, ta có thể bị mắc kẹt ở nhánh đó và không tìm ra nghiệm. • Để khắc phục tình trạng đó, ta tìm kiếm theo độ sâu chỉ tới mức l nào đó; nếu không tìm ra nghiệm, ta tăng độ sâu lên l +1 và lại tìm kiếm theo độ sâu tới mức l +1. Quá trình trên được lặp lại với l lần lượt là 1, 2, , đến một độ sâu max nào đó. • Thuật toán: Sử dụng thủ tục tìm kiếm độ sâu hạn chế 32 Tìm kiếm sâu lặp 33 Tìm kiếm sâu lặp 34 Tìm kiếm sâu lặp 35 Tìm kiếm sâu lặp • Hoàn thành? Chắc chắn sẽ tìm ra nghiệm nếu bài toán có nghiệm (miễn là ta chọn độ sâu max đủ lớn) • Thời gian? Số lượng các nút được tạo ra trong tìm kiếm độ sâu hạn chế tới độ sâu d với nhân tố nhánh b là: NDLS = b 0 + b1 + b2 + + bd-2 + bd-1 + bd Nếu nghiệm ở độ sâu d, trong tìm kiếm sâu lặp ta phải gọi thủ tục tìm kiếm độ sâu hạn chế với độ sâu lần lượt là 0, 1, 2, , d. Do đó các nút ở mức 1 phải phát triển lặp lại d lần, các nút ở mức 2 lặp lại d-1 lần, , các nút ở mức d lặp 1 lần. Do vậy số lượng các nút được tạo ra trong tìm kiếm sâu lặp là: NIDS = (d+1)b 0 + d b1 + (d-1)b2 + + bd = O(bd) • Không gian? O(bd) • Tối ưu? Thuật toán là tối ưu nếu giá = 1 ở mỗi bước 36 Tổng kết các thuật toán • Nhận xét: Tìm kiếm sâu lặp chỉ sử dụng không gian tuyến tính và thời gian tìm kiếm không tốn nhiều hơn đáng kể so với các thuật toán tìm kiếm mù khác. 37 III. Các chiến lược tìm kiếm kinh nghiệm • Hàm đánh giá • Tìm kiếm tốt nhất đầu tiên (Best_first search) • Tìm kiếm leo đồi (Hill_climbing search) • Thuật toán A* • Thuật toán tìm kiếm nhánh cận (Branch_and_bound search) 38 Hàm đánh giá • U – không gian trạng thái, với trạng thái u U  h(u) là hàm đánh giá mức độ gần đích của trạng thái u h: U  R • h(u) nhỏ nhất  u là trạng thái có nhiều hứa hẹn gần đích nhất • Sử dụng hàm đánh giá để định hướng cho việc tìm kiếm. Các chiến lược tìm kiếm dựa vào hàm đánh giá được gọi là tìm kiếm kinh nghiệm. • Các bước tiến hành tìm kiếm – Biểu diễn trạng thái và toán tử (Xây dựng KGTT) – Xây dựng hàm đánh giá h(u) – Xác định chiến lược chọn trạng thái để phát triển ở mỗi bước dựa vào hàm đánh giá 39 Hàm đánh giá Ví dụ, với bài toán 8 số: • h1(u) = số lượng các quân ở sai vị trí • h2(u) = tổng khoảng cách Manhattan (tức là tổng số các ô vuông từ vị trí hiện tại đến vị mong muốn của mỗi quân) • h1(S) = ? • h2(S) = ? 40 Hàm đánh giá Ví dụ, với bài toán 8 số: • h1(u) = số lượng các quân ở sai vị trí • h2(u) = tổng khoảng cách Manhattan (tức là tổng số các ô vuông từ vị trí hiện tại đến vị trí mong muốn của mỗi quân) • h1(S) = ? 8 • h2(S) = ? 3+1+2+2+2+3+3+2 = 18 41 Tìm kiếm tốt nhất đầu tiên • Tìm kiếm tốt nhất đầu tiên = Tìm kiếm theo bề rộng + hàm đánh giá • Phát triển trạng thái tốt nhất theo hàm đánh giá trong số các trạng thái đang chờ được phát triển • Ví dụ: Xét không gian trạng thái được biểu diễn bởi đồ thị trong hình (slide tiếp theo), trong đó trạng thái ban đầu là A, trạng thái kết thúc là B. Giá trị của hàm đánh giá là các số ghi cạnh mỗi đỉnh. 42 Tìm kiếm tốt nhất đầu tiên A D C F G E I B H K 20 15 7 10 6 12 0 8 5 3 Đồ thị không gian trạng thái 43 Tìm kiếm tốt nhất đầu tiên • Quá trình tìm kiếm tốt nhất đầu tiên diễn ra như sau: – Đầu tiên phát triển đỉnh A sinh ra các đỉnh kề là C, D và E. – Trong ba đỉnh này, đỉnh D có giá trị hàm đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra F, I. – Trong số các đỉnh chưa được phát triển C, E, F, I thì đỉnh E có giá trị hàm đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra các đỉnh G, K. – Trong số các đỉnh chưa được phát triển thì G tốt nhất, phát triển G sinh ra B, H. Đến đây ta đã đạt tới trạng thái kết thúc. – Cây tìm kiếm tốt nhất đầu tiên được biểu diễn như trong hình (slide tiếp theo) 44 Tìm kiếm tốt nhất đầu tiên A D C F G E I B H K 20 15 7 10 6 12 0 8 5 3 Cây tìm kiếm tốt nhất - đầu tiên 45 Tìm kiếm tốt nhất đầu tiên • Thuật toán: 46 Tìm kiếm leo đồi • Tìm kiếm leo đồi = Tìm kiếm theo độ sâu + hàm đánh giá • Phát triển trạng thái tốt nhất theo hàm đánh giá trong số các trạng thái con đang chờ được phát triển • Ví dụ: Xét đồ thị không gian trạng thái ở hình phía trước. Quá trình tìm kiếm leo đồi được tiến hành như sau. – Đầu tiên phát triển đỉnh A sinh ra các đỉnh con C, D, E. – Trong các đỉnh này chọn D để phát triển, và nó sinh ra các đỉnh con F, I. – Trong các đỉnh này chọn I để phát triển, và nó sinh ra các đỉnh con B, G. Quá trình tìm kiếm kết thúc. – Cây tìm kiếm leo đồi được biểu diễn như trong hình (slide tiếp theo) 47 Tìm kiếm leo đồi A D C F G E I B 20 15 7 10 6 0 8 5 Cây tìm kiếm leo đồi 48 Tìm kiếm leo đồi • Thuật toán: 49 Tìm đường đi ngắn nhất • Biết rằng: – Độ dài cung (a,b), k(a,b)≥0 là chi phí để đưa trạng thái a tới trạng thái b (VD: Độ dài đường đi giữa 2 thành phố a và b) – Độ dài đường đi là tổng độ dài của các cung trên đường đi • Vấn đề: Tìm đường đi ngắn nhất từ trạng thái ban đầu tới trạng thái đích • Các thuật toán tìm đường đi ngắn nhất: – Thuật toán A* – Thuật toán tìm kiếm nhánh cận 50 Tìm đường đi ngắn nhất • Hàm đánh giá của các thuật toán tìm đường đi ngắn nhất – Hàm đánh giá f(u) = g(u) + h(u) – g(u) = chi phí thực sự để đi đến u – h(u) = đánh giá chi phí từ u tới đích – f(u) = đánh giá tổng chi phí của đường đi tới đích qua u • Hàm h(u) được gọi là chấp nhận được (hoặc đánh giá thấp) nếu với mọi nút u, h(u) ≤ h*(u), trong đó h*(u) là chi phí thực sự để đạt tới trạng thái đích từ u. – Ví dụ: Trong bài toán tìm đường ngắn nhất trên bản đồ giao thông, h(u) có thể được xác định là độ dài đường chim bay từ u tới đích. 51 Thuật toán A* • Là thuật toán sử dụng kỹ thuật tìm kiếm tốt nhất đầu tiên với hàm đánh giá f(u) • Phát triển trạng thái tốt nhất theo hàm đánh giá f(u) trong số các trạng thái đang chờ được phát triển • Để thấy được thuật toán A* làm việc như thế nào, ta xét đồ thị không gian trạng thái trong hình (slide tiếp theo). Trong đó, trạng thái ban đầu là trạng thái A, trạng thái đích là trạng thái B, các số ghi cạnh các cung là độ dài đường đi, các số ghi cạnh các đỉnh là giá trị của hàm h. 52 Thuật toán A* A D C F G E I B H K 20 15 7 10 6 12 0 8 4 3 5 9 6 4 2 5 6 4 8 7 9 6 13 14 4 Đồ thị không gian trạng thái 53 Thuật toán A* • Đầu tiên phát triển đỉnh A sinh ra các đỉnh con C, D, E và F. Tính giá trị của hàm f tại các đỉnh này ta có: • Như vậy đỉnh tốt nhất là D (vì f(D) = 13 là nhỏ nhất). Phát triển D, ta nhận được các đỉnh con H và E. Ta đánh giá H và E (mới): • Trong số các đỉnh chờ phát triển, thì đỉnh E với đánh giá f(E) = 19 là đỉnh tốt nhất. Phát triển đỉnh này, ta nhận được các đỉnh con của nó là K và I. • Tiếp tục quá trình trên cho tới khi đỉnh được chọn để phát triển là đỉnh kết thúc B, độ dài đường đi ngắn nhất tới B là g(B) = 19 54 Thuật toán A* A D C F E I B H K 24 27 13 18 21 25 19 19 25 21 14 E K B 17 Cây tìm kiếm theo thuật toán A* 55 Thuật toán A* • Thuật toán 56 Thuật toán A* • Một số nhận xét về thuật toán A*: – Người ta chứng minh được rằng, nếu hàm đánh giá h(u) là đánh giá thấp (trường hợp đặc biệt, h(u) = 0 với mọi trạng thái u) thì thuật toán A* là thuật toán tối ưu, tức là nghiệm mà nó tìm là nghiệm tối ưu – Ngoài ra, nếu độ dài của các cung không nhỏ hơn một số dương  nào đó thì thuật toán A* là thuật toán hoàn thành tức là, nó luôn dừng lại và tìm ra nghiệm – Thuật toán A* đã được chứng tỏ là thuật toán hiệu quả nhất trong số các thuật toán hoàn thành và tối ưu cho vấn đề tìm kiếm đường đi ngắn nhất 57 Chứng minh tính tối ưu của A* • Giả sử đích tối ưu cục bộ G2 nào đó đã được tạo ra và nằm ở đường viền. Giả sử n là một nút chưa được mở rộng ở đường viền sao cho n nằm trên đường đi ngắn nhất tới đích tối ưu G • • f(G2) = g(G2) vì h(G2) = 0 • g(G2) > g(G) vì G2 là tối ưu cục bộ • f(G) = g(G) vì h(G) = 0 • f(G2) > f(G) từ trên 58 Chứng minh tính tối ưu của A* • Giả sử đích tối ưu cục bộ G2 nào đó đã được tạo ra và nằm ở đường viền. Giả sử n là một nút chưa được mở rộng ở đường viền sao cho n nằm trên đường đi ngắn nhất tới đích tối ưu G • • f(G2) > f(G) từ trên • h(n) ≤ h*(n) vì h là chấp nhận được • g(n) + h(n) ≤ g(n) + h*(n) • f(n) ≤ f(G) Do vậy f(G2) > f(n), và A * sẽ không bao giờ chọn G2 để mở rộng 59 Thuật toán tìm kiếm nhánh cận • Là thuật toán sử dụng kỹ thuật tìm kiếm leo đồi với hàm đánh giá f(u) • Phát triển trạng thái tốt nhất theo hàm đánh giá f(u) trong số các trạng thái con đang chờ được phát triển A D C F G E I B H K 20 15 7 10 6 12 0 8 4 3 5 9 6 4 2 5 6 4 8 7 9 6 13 14 4 Đồ thị không gian trạng thái 60 Thuật toán tìm kiếm nhánh cận • Ví dụ: Chúng ta lại xét không gian trạng thái ở hình trước. Phát triển đỉnh A, ta nhận được các đỉnh con C, D, E và F, f(C) = 24, f(D) = 13, f(E) = 21, f(F) = 27. • Trong số này D là tốt nhất, phát triển D, sinh ra các đỉnh con là H và E, f(H) = 25, f(E) = 19. • Đi xuống phát triển E, sinh ra các đỉnh con là K và I, f(K) = 17, f(I) = 18. • Đi xuống phát triển K, sinh ra đỉnh B, f(B) = 21 • Đi xuống phát triển B, vì B là đỉnh đích, vậy ta tìm được đường đi tối ưu tạm thời với độ dài là 21 61 Thuật toán tìm kiếm nhánh cận • Từ B quay lên K, rồi từ K quay lên cha của nó là E, từ E đi xuống I, f(I) = 18 nhỏ hơn độ dài đường đi tạm thời. Phát triển I sinh ra các con K và B, f(K) = 25, f(B) = g(B) = 19 • Đi xuống phát triển B, vì B là đỉnh đích, ta tìm được đường đi đầy đủ mới với độ dài là 19 nhỏ hơn độ dài đường đi tối ưu tạm thời cũ. Vậy độ dài đường đi tối ưu tạm thời bây giờ là 19 • Từ B ta lại quay lên các đỉnh còn lại chưa được phát triển, tuy nhiên các đỉnh này đều có giá trị hàm đánh giá lớn hơn 19, do đó không có đỉnh nào được phát triển nữa. Như vậy ta tìm được đường đi tối ưu với độ dài 19 62 Thuật toán tìm kiếm nhánh cận A D C F E I K E K 24 27 13 18 21 25 19 25 19 21 14 H B B 17 Cây tìm kiếm nhánh cận 63 Thuật toán tìm kiếm nhánh cận • Thuật toán 64 IV. Tìm kiếm có đối thủ • Cây trò chơi • Chiến lược Minimax • Phương pháp cắt tỉa alpha - beta 65 Cây trò chơi • Trong các trò chơi hai người, chẳng hạn các loại cờ, hai người chơi luân phiên nhau đưa ra các nước đi • Các luật của trò chơi là như nhau với hai người chơi • Hai người chơi đều biết thông tin đầy đủ về các tình thế trong trò chơi • Tuy nhiên, người chơi không biết đối thủ của mình sẽ đi nước nào trong tương lai • Mục tiêu: Mỗi lần đến lượt mình, người chơi phải tìm trong số rất nhiều nước đi hợp lệ, một nước đi tốt nhất sao cho qua một dãy nước đi, anh ta giành phần thắng. 66 Cây trò chơi • Quy vấn đề chơi cờ về việc tìm kiếm trong không gian trạng thái. • Mỗi trạng thái là một tình thế (sự bố trí các quân của hai bên trên bàn cờ) – Trạng thái ban đầu là sự sắp xếp các quân cờ của hai bên lúc bắt đầu cuộc chơi – Các toán tử là các nước đi hợp lệ – Các trạng thái kết thúc là các tình thế mà cuộc chơi dừng, thường được xác định bởi một số điều kiện dừng nào đó. – Một hàm kết cuộc ứng mỗi trạng thái kết thúc với một giá trị nào đó. Chẳng hạn như cờ vua, mỗi trạng thái kết thúc chỉ có thể là thắng hoặc thua hoặc hoà. • Người chơi cần tìm ra một dãy các nước đi xen kẽ với các nước của đối thủ từ trạng thái ban đầu tới trạng thái kết thúc nhằm giành phần thắng 67 Cây trò chơi • Hai đấu thủ trong trò chơi được gọi là MIN và MAX • Cây trò chơi được xây dựng như sau: – Gốc của cây ứng với trạng thái ban đầu. – Đỉnh MAX ứng với trạng thái MAX đưa ra nước đi, đỉnh MIN ứng với trạng thái MIN đưa ra nước đi – Nếu một đỉnh là MAX thì các đỉnh con của nó đều là MIN do vậy trên cùng một mức của cây các đỉnh đều là MAX hoặc đều là MIN – Lá của cây ứng với các trạng thái kết thúc 68 Cây trò chơi 69 Chiến lược Minimax • Trên cây trò chơi: – Giả sử đỉnh có giá trị càng lớn càng có lợi cho MAX, đỉnh có giá trị càng nhỏ càng có lợi cho MIN – MAX tìm nước đi tại đỉnh u, MAX sẽ chọn nước đi tốt nhất → chọn đỉnh v có giá trị lớn nhất trong các đỉnh con của u – Đến lượt mình MIN cũng chọn nước đi tốt nhất → chọn đỉnh w có giá trị nhỏ nhất trong các đỉnh con của v 70 Chiến lược Minimax • Đánh giá các đỉnh trên cây trò chơi – Nếu u là đỉnh kết thúc thì giá trị tại u là giá trị của hàm kết cuộc val(u) = f(u) – Nếu u là đỉnh trong của cây: • Nếu u là đỉnh MAX thì val(u) = max của các giá trị các đỉnh con. • Nếu u là đỉnh MIN thì val(u) = min của các giá trị các đỉnh con. – Gán giá trị cho các đỉnh của cây trò chơi từ lá đến gốc 71 Chiến lược Minimax • Thủ tục chọn nước đi cho Max tại đỉnh u, trong đó v là đỉnh con được chọn của u: procedure Minimax(u, v); begin val ← -∞; for mỗi w là đỉnh con của u do if val ≤ MinVal(w) then {val ← MinVal(w); v ← w} end; ------------------------------------- function MinVal(u); {hàm xác định giá trị cho các đỉnh Min} begin if u là đỉnh kết thúc then MinVal(u) ← f(u) else MinVal(u) ← min(MaxVal(v) | v là đỉnh con của u) end; 72 Chiến lược Minimax ------------------------------------- function MaxVal(u); {hàm xác định giá trị cho các đỉnh Max} begin if u là đỉnh kết thúc then MaxVal(u) ← f(u) else MaxVal(u) ← max(MinVal(v) | v là đỉnh con của u) end; • Thủ tục chọn nước đi như trên gọi là chiến lược Minimax, bởi vì MAX đã chọn được nước đi dẫn tới đỉnh con có giá trị là max của các giá trị các đỉnh con, và MIN đáp lại bằng nước đi tới đỉnh có giá trị là min của các giá trị các đỉnh con 73 Chiến lược Minimax • Về mặt lý thuyết chiến lược Minimax cho phép ta tìm được nước đi tối ưu • Tuy nhiên trên thực tế, chúng ta sẽ không đủ thời gian để tính được nước đi tối ưu vì phải xem xét toàn bộ các đỉnh trong cây trò chơi • Trong các trò chơi hay, cây trò chơi là cực kỳ lớn – Ví dụ: Với cờ vua, chỉ tính đến độ sâu 40 cây trò chơi đã có khoảng 10120 đỉnh • Để tìm ra nhanh nước đi tốt (không tối ưu) không sử dụng hàm kết cuộc và xem xét toàn bộ các đỉnh trong cây, mà: – Sử dụng hàm đánh giá – Xem xét một bộ phận của cây trò chơi 74 Hàm đánh giá Hàm đánh giá trong cờ vua: • Mỗi loại quân được gán với một giá trị số tương ứng với “sức mạnh” của nó. Ví dụ: – Tốt có giá trị 1 đối với quân trắng, -1 đối với quân đen – Mã, Tượng có giá trị 3 đối với quân trắng, -3 đối với quân đen – Xe có giá trị 5 đối với quân trắng, -5 đối với quân đen – Hậu có giá trị 9 đối với quân trắng, -9 đối với quân đen • Hàm đánh giá tuyến tính có trọng số sẽ là: Eval(s) = w1s1 + w2s2 + + wnsn Trong đó: wi là giá trị mỗi loại quân si là số quân loại đó 75 Hàm đánh giá Hàm đánh giá: E(n) = M(n) – O(n) Trong đó: M(n) là tổng số đường thắng có thể của tôi O(n) là tổng số đường thắng có thể của đối thủ E(n) là trị số đánh giá tổng cộng cho trạng thái n Hàm đánh giá trong trò chơi tic-tac-toe: 76 Phương pháp cắt tỉa alpha - beta • Dù đã han chế không gian tìm kiếm nhưng số đỉnh của cây trò chơi vẫn còn rất lớn. • Ví dụ, trong cờ vua: – Nhân tố nhánh trong cây trò chơi trung bình khoảng 35 – Thời gian đòi hỏi phải đưa ra nước đi là 150 giây – Trên máy tính thông thường chương trình chỉ xem xét được các đỉnh trong độ sâu 3, hoặc 4 => mới đạt trình độ người mới tập chơi cờ • Phương pháp cắt tỉa alpha – beta cho phép ta cắt bỏ các nhánh không cần thiết cho việc đánh giá giá trị heuristic tại một đỉnh 77 Phương pháp cắt tỉa alpha - beta Ví dụ về phương pháp cắt tỉa alpha - beta 78 Phương pháp cắt tỉa alpha - beta Ví dụ về phương pháp cắt tỉa alpha - beta 79 Phương pháp cắt tỉa alpha - beta Ví dụ về phương pháp cắt tỉa alpha - beta 80 Phương pháp cắt tỉa alpha - beta Ví dụ về phương pháp cắt tỉa alpha - beta 81 Phương pháp cắt tỉa alpha - beta Ví dụ về phương pháp cắt tỉa alpha - beta 82 Phương pháp cắt tỉa alpha - beta • Tính chất của phương pháp α-β: – Việc cắt tỉa không ảnh hưởng đến kết quả cuối cùng – Việc sắp thứ tự các nước đi tốt sẽ cải thiện đáng kể việc cắt tỉa – Với “thứ tự lý tưởng”, độ phức tạp thời gian giảm đi một nửa  tăng gấp đôi độ sâu tìm kiếm 83 Cắt tỉa  A S Z MAX MIN = z ≥  =  z ≤   - cut =  84 Cắt tỉa  S A Z MIN MAX = z ≤  =  z ≥   - cut =  Phương pháp cắt tỉa alpha - beta Thủ tục chọn nước đi cho Max tại đỉnh u, trong đó v là đỉnh con được chọn của u: Procedure Alpha_beta(u, v); begin α←-∝; β←-∝; for mỗi w là đỉnh con của u do if α <= MinVal(w, α, β) then {α ← MinVal(w, α, β); v ← w} end; -------------------------------------------- 85 Function MinVal(u, α, β); {hàm xác định giá trị cho các đỉnh Min} begin if u là đỉnh kết thúc or u là lá của cây hạn chế then MinVal(u, α, β) ← eval(u) else for mỗi đỉnh v là con của u do {β ← min{β, MaxVal(v, α, β)} ; If α >= β then exit}; /*cắt bỏ các cây con từ các đỉnh v còn lại */ MinVal(u, α, β) ← β; end; Function MaxVal(u, α, β); { hàm xác định giá trị cho các đỉnh Max} begin if u là đỉnh kết thúc or là lá của cây hạn chế then MaxVal(u, α, β) ← eval(u) else for mỗi đỉnh v là con của u do α ← max{α, MinVal(v, α, β)} ; If α >= β then exit}; /*cắt bỏ các cây con từ các đỉnh v còn lại */ MaxVal(u, α, β) ← α end; 86