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.
1
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:
2
– 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).
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.
3
– 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.
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.
4
– 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.
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).
5
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?
– 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à ∞)
6
• Độ phức tạp thời gian và không gian được tính toán dựa trên
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
7
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
8
• Thuật toán:
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
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
• 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
13
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.
14
• Thuật toán:
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
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
• 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
27
Các trạng thái lặp
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)
• Cây tìm kiếm có thể chứa nhiều nút ứng với cùng một trạng
28
• 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ũ!
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
– Không sinh ra các nút mà nó đã được sinh ra, tức là chỉ sinh ra
đó nằm trên đường đi dẫn tới u
• 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.
29
các nút mới
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
• Thuật toán:
30
là các nút ở độ sâu l không có nút kế tiếp
Tìm kiếm sâu lặp
theo độ sâu, ta có thể bị mắc kẹt ở nhánh đó và không tìm ra nghiệm.
• Nếu cây tìm kiếm chứa nhánh vô hạn, khi sử dụng tìm kiếm
31
• Để 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ế
Tìm kiếm sâu lặp
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
• 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 = b0 + 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
• Không gian? O(bd) • Tối ưu? Thuật toán là tối ưu nếu giá = 1 ở mỗi bước
35
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)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
Tổng kết các thuật toán
36
• 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.
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)
37
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.
– 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á
38
• Các bước tiến hành tìm kiếm
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
• h1(S) = ? • h2(S) = ?
39
(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)
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
• h1(S) = ? 8 • h2(S) = ? 3+1+2+2+2+3+3+2 = 18
40
(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)
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
41
• 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.
Tìm kiếm tốt nhất đầu tiên
42
Đồ thị không gian trạng thái
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
43
(slide tiếp theo)
Tìm kiếm tốt nhất đầu tiên
44
Cây tìm kiếm tốt nhất - đầu tiên
Tìm kiếm tốt nhất đầu tiên
• Thuật toán:
45
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
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)
46
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,
Tìm kiếm leo đồi
47
Cây tìm kiếm leo đồi
Tìm kiếm leo đồi
• Thuật toán:
48
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:
49
– Thuật toán A* – Thuật toán tìm kiếm nhánh cận
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
50
thông, h(u) có thể được xác định là độ dài đường chim bay từ u tới đích.
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.
51
Thuật toán A*
52
Đồ thị không gian trạng thái
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
53
Thuật toán A*
54
Cây tìm kiếm theo thuật toán A*
Thuật toán A*
55
• Thuật toán
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
56
– 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
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 ở
•
vì h(G2) = 0
57
vì G2 là tối ưu cục bộ vì h(G) = 0 từ trên đườ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) • g(G2) > g(G) f(G) = g(G) • f(G2) > f(G) •
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 ở
•
từ trên vì h là chấp nhận được > f(G) ≤ h*(n)
58
≤ f(G) f(n)
đườ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) • h(n) • g(n) + h(n) ≤ g(n) + h*(n) • Do vậy f(G2) > f(n), và A* sẽ không bao giờ chọn G2 để mở rộng
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
59
trạng thái con đang chờ được phát triển
Đồ thị không gian trạng thái
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.
18.
• Đi xuống phát triển E, sinh ra các đỉnh con là K và I, f(K) = 17, f(I) =
• Đ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
60
ưu tạm thời với độ dài là 21
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
61
• 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
Thuật toán tìm kiếm nhánh cận
Cây tìm kiếm nhánh cận
62
Thuật toán tìm kiếm nhánh cận
63
• Thuật toán
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
64
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
trong tương lai
• Tuy nhiên, người chơi không biết đối thủ của mình sẽ đi nước nào
65
• 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.
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
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à.
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
• 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
66
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
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
67
– Lá của cây ứng với các trạng thái kết thúc
Cây trò chơi
68
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
có giá trị nhỏ nhất trong các đỉnh con của v
69
– Đến lượt mình MIN cũng chọn nước đi tốt nhất → chọn đỉnh w
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 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
70
– Nếu u là đỉnh trong của cây:
Chiến lược Minimax
• Thủ tục chọn nước đi cho Max tại đỉnh u, trong đó v là đỉnh con
{val ← MinVal(w); v ← w}
đượ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 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
71
của u)
end;
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
end;
của u)
• Thủ tục chọn nước đi như trên gọi là chiến lược Minimax, bởi vì
72
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
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ó
• Để 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
73
khoảng 10120 đỉnh
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 đó
74
Hàm đánh giá
Hàm đánh giá trong trò chơi tic-tac-toe:
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
75
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
• 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
76
=> mới đạt trình độ người mới tập chơi cờ
Phương pháp cắt tỉa alpha - beta
77
Ví dụ về phương pháp cắt tỉa alpha - beta
Phương pháp cắt tỉa alpha - beta
78
Ví dụ về phương pháp cắt tỉa alpha - beta
Phương pháp cắt tỉa alpha - beta
79
Ví dụ về phương pháp cắt tỉa alpha - beta
Phương pháp cắt tỉa alpha - beta
80
Ví dụ về phương pháp cắt tỉa alpha - beta
Phương pháp cắt tỉa alpha - beta
81
Ví dụ về phương pháp cắt tỉa alpha - beta
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
82
tăng gấp đôi độ sâu tìm kiếm
Cắt tỉa S
MAX
=
≥
A
MIN
Z
=
- cut
= z z ≤
83
Cắt tỉa S
=
MIN
≤
A
=
MAX
Z
- cut
= z z ≥
84
Phương pháp cắt tỉa alpha - beta
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
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: --------------------------------------------
86
