Nhập môn trí tuệ nhân tạo-Bài 4

NHẬP MÔN TRÍ TUỆ NHÂN TẠO
@copyrights by Dr Nguyễn Xuân Hoài
Nội Dung
Tìm kiếm thoả ràng buộc:
Bài toán thoả ràng buộc (CSP)
Tìm kiếm backtracking cho CSP
Tìm kiếm địa phương cho CSP
Tìm kiếm trong game đối kháng:
Ra quyết định tối ưu (minimax)
Tìm kiếm minimax với tỉa α-β
Ra quyết định trong thời gian thực.

Bài toán thoả ràng buộc (CSPs)
Bài toán tìm kiếm ở tiết trước:
Trạng thái: dạng “hộp đen“ – Tất cả các cấu trúc mà trên đó có thể định nghĩa successor function, heuristic function, and goal test
CSP:
Trạng thái được định nghĩa là các biến Xi với giá trị lấy từ các miền xác định Di
goal test là tập các ràng buộc quy định trên tổ hợp các giá trị của tập con của các biến

Có thể đưa ra những thuật toán chung có công hiệu lớn hơn những tìm kiếm Heuristics ở tiết trước.
Ví dụ Tô Mầu Đồ Thị
Biến WA, NT, Q, NSW, V, SA, T
Miền giá trị Di = {red,green,blue}
Ràng buộc: Các miền khác nhau được tô mầu khác nhau
e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}
Ví dụ bài toán: SAT, 3-SAT.
Ví Dụ
Lời giải là các tổ hợp giá trị đủ và nhất quán với ràng buộc VD: WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green
Đồ Thị Ràng Buộc
Bài toán CSP nhị phân: Mỗi ràng buộc chỉ gồm hai biến
Đồ thì ràng buộc: đỉnh là các biến, cung biểu diễn các ràng buộc
Các biến thể của CSPs
Biến rời rạc
Miền giá trị hữu hạn:
n biến, kích thước miền giá trị d  O(dn) tổ hợp giá trị
e.g., Boolean CSPs, như Boolean Satisfiability (NP-complete) –SAT (3SAT).
Miền giá trị vô hạn:
integers, strings, etc.
e.g., lập lịch, biến là ngày bắt đầu ngày kết thúc công việc.
ngôn ngữ biểu diễn ràng buộc StartJob1 + 5 ≤ StartJob3

Biến liên tục
Các bài toán quy hoạch tuyến tính và phi tuyến trong vận trù học.
Các Loại Ràng Buộc
Ràng buộc đơn,
e.g., SA ≠ green
Ràng buộc nhị phân:
e.g., SA ≠ WA
Ràng buộc bậc cao (3 biến trở lên)
e.g., bài toán cryptarithmetic (SEND+ME= MONEY).
Ví dụ: Cryptarithmetic
Biến: F T U W O X1 X2 X3
Miền giá trị: {0,1,2,3,4,5,6,7,8,9}
Ràng buộc: Alldiff (F,T,U,W,R,O)
O + O = R + 10 · X1
X1 + W + W = U + 10 · X2
X2 + T + T = O + 10 · X3
X3 = F, T ≠ 0, F ≠ 0
Các bài toán CSPs trong thực tế
Bài toán gán
e.g., Ai dạy lớp nào?
Bài toán thời khoá biểu
Lớp nào học lúc nào ở đâu.
Bài toán lập lịch xe (giao thông)
Bài toán lập lịch gia công cho dây truyền sản xuất

Tìm kiếm mù

Không gian trạng thái là tập các biến được gán giá trị.
Trạng thái đầu: { }
Successor function: gán giá trị cho một biến mà không gây mâu thuẫn với ràng buộc trên các giá trị đang được gán.
 Thất bại nếu không tìm được giá trị nào như vậy
Goal test: Tập giá trị gán là đầy đủ.

Đối với mỗi bài toán CSPs:
Lời giải tồn tại ở độ sâu tìm kiếm n nếu bài toán có n biến
 dùng DFS
Lời giải là trạng thái (không phải là đường đi)
b = (n - l )d tại độ sâu l, vì vậy có n! · dn lá
Tìm kiếm Backtracking
Chú ý: các cặp gán giá trị có tính giao hoan, i.e.,
[ WA = red sau đó NT = green ] sau đó [ NT = green sau đó WA = red ]

Chỉ cần gán giá trị cho 1 biến tại mỗi node
 b = d có dn lá

DFS cho CSPs gán trị đơn biến – tìm kiếm backtracking

Backtracking là dạng tìm kiếm mù đơn giản cho CSPs

Có thể giải n-queens với n ≈ 25
Backtracking search
Ví Dụ Backtracking
Ví Dụ Backtracking
Ví Dụ Backtracking
Ví Dụ Backtracking
Cải thiện hiệu suất của backtracking
Heuristic chung cần được đưa ra để tra lời các câu hỏi:
Biến nào được gán trị tiếp theo?
Các giá trị để thử theo thứ tự nào?
Liệu có thể biết trước những hướng vô vọng?

Việc trả lời tốt những câu hỏi trên có thể giúp tăng hiệu suất đáng kể Backtracking cho CSP trong thực tế!
Biến nhiều ràng buộc nhất
chọn biến nhiều ràng buộc nhất:
chọn biến với ít giá trị hợp lệ để chọn nhất.



minimum remaining values (MRV) heuristic.
Biến ràng buộc nhiều nhất
Trong trường hợp có nhiều biến như vậy:
Chọn biến có nhiều ràng buộc với các biến khác nhất.
Chọn giá trị ràng buộc tối thiểu
Đối với mỗi biến, chọn giá trị ràng buộc tối thiểu:
giá trị làm hạn chế ít nhất các giá trị cho các biến khác





Kết hợp các heuristics chung nói trên có thể giúp giải bài toán 1000-queens
Kiểm Tra Trước
Ý tưởng:
Lưu trữ và kiểm soát các giá trị có thể gán được cho các biến chưa được gán trị.
Kết thúc nếu có bất cứ biến nào không còn giá trị gán hợp lệ.
Kiểm Tra Trước
Ý tưởng:
Lưu trữ và kiểm soát các giá trị có thể gán được cho các biến chưa được gán trị.
Kết thúc nếu có bất cứ biến nào không còn giá trị gán hợp lệ.
Kiểm Tra Trước
Ý tưởng:
Lưu trữ và kiểm soát các giá trị có thể gán được cho các biến chưa được gán trị.
Kết thúc nếu có bất cứ biến nào không còn giá trị gán hợp lệ.
Kiểm Tra Trước
Ý tưởng:
Lưu trữ và kiểm soát các giá trị có thể gán được cho các biến chưa được gán trị.
Kết thúc nếu có bất cứ biến nào không còn giá trị gán hợp lệ.
Lan Truyền Ràng Buộc
kiểm tra trước lan truyền thông tin từ biến đã được gán sang biến chưa được gán, nhưng không phá hiện sớm được tất cả các trường hợp thất bại






NT vàSA không thể cùng blue!
Lan truyền ràng buộc làm mạnh ràng buộc vào phạm vi địa phương
Nhất quán theo cung
X Y là nhất quán khi và chỉ khi
với mọi giá trị x của X đều có giá trị hợp lệ cho y
Nhất quán theo cung
X Y là nhất quán khi và chỉ khi
với mọi giá trị x của X đều có giá trị hợp lệ cho y
Nhất quán theo cung
X Y là nhất quán khi và chỉ khi
với mọi giá trị x của X đều có giá trị hợp lệ cho y








Nếu X mất một giá trị, thì cần kiểm tra lại lân cận của X.
Nhất quán theo cung
X Y là nhất quán khi và chỉ khi
với mọi giá trị x của X đều có giá trị hợp lệ cho y







Nếu X mất một giá trị, thì cần kiểm tra lại lân cận của X.
Nhất quán theo cung có khả năng phát hiện thất bại sớm hơn kiểm tra trước.
Có thể được thực hiện trước mỗi khi gán trị cho biến.
Thuật toán AC-3
Độ phức tạp thời gian O(n2d3)
Tìm kiếm địa phương cho CSPs
Các phương pháp tìm kiếm địa phương (GHB, SA, GA, ACO,...) có thể áp dụng cho CSP

Để áp dụng vào CSPs:
Cho phép các trạng thái không thoả ràng buộc.
Toán tử để gán lại các giá trị cho biến

Lựa chọn biến: lựa chọn ngẫu nhiên một biến xung đột

Lựa chọn giá trị dựa trên heuristic min-conflict:
Chọn giá trị vi phạm ít ràng buộc nhất
i.e., hill-climb với h(n) = số lượng ràng buộc bị vi phạm
Ví dụ: 4-Queens
Trạng thái: 4 queens trong 4 cột (44 = 256 trạng thái)
Toán tử: chuyển một con hậu trong cột
Goal test: không con hậu nào tấn công nhau
Đánh giá: h(n) = Số lượng cặp hậu tấn công nhau







Trạng thái đầu ngẫu nhiên, tìm kiếm địa phương có thể giúp giải bài toán n-queens với n rất cao (e.g., n = 10,000,000)
Câu hỏi ôn tập
Phát biểu bài toán thoả ràng buộc, tìm ví dụ.
Cài đặt thuật toán Backtracking, Kiểm tra trước, AC3,..
Giải các bài toán n-queen, map coloring, lập lịch,... bằng tìm kiếm địa phương và các thuật toán trên.
Đọc thêm:
+ Giáo trình chương 5.
+ OCW : ch3_csp_games1.
+ Tập hợp các bài toán NP-đầy đủ: Computers and Intractability: A Guide to the Theory of NP-Completeness, M.R.Garey and D.S. Johnson.
+ Programming with constraints: An Introduction, K. Marriott and P.J. Stuckey
Tìm kiếm trong trò chơi đối kháng
Đặc Điểm của Tìm Kiếm trên Games
Không đoán định trước được động thái của đối thủ  Do đó mỗi một nước đi phải tính đến mọi nước đi có thể có của đối thủ sau đó
Giới hạn thời gian  Nói chung không thể tìm được đích tối ưu mà chỉ xấp xỉ.
Game tree (2-player, deterministic, turns)
Minimax
Tối ưu cho trò chơi tĩnh.
Ý tưởng: chọn nước đi có giá trị minimax cao nhất
= Nước đi tốt nhất trong trường hợp đối thủ chọn nước đi khôn ngoan nhất.
E.g., 2-ply game:

Thuật Toán Minimax
Đánh Giá Minimax
đủ có (nếu cây tìm kiếm là hữu hạn)

Tối ưu có (đối với đối thủ luôn ra nước tối ưu)

Độ phức tạp thời gian? O(bm)
Độ phức tạp không gian? O(bm) (DFS)

Ví dụ cờ vua, thông thường b ≈ 35, m ≈100
 Tìm lời giải chính xác và tối ưu là không thể được
Ví dụ về tỉa α-β
Ví dụ về tỉa α-β
Ví dụ về tỉa α-β
Ví dụ về tỉa α-β
Ví dụ về tỉa α-β
Nhận xét về α-β
Tỉa alpha-beta không ảnh hướng đến lời giải

Thứ tự xét nước hợp lý sẽ giúp tỉa cây tìm kiếm hiệu quả

Nếu thứ tự tốt thì thời gian tìm kiếm = O(bm/2)
 gấp đôi DFS-Mininmax.

Tại sao lại gọi là α-β?
α là giá trị của lựa chọn nước tốt nhất hiện tại trong đường tìm kiếm với max
nếu v tồi hơn α, max sẽ loại bỏ không xét nhánh đó.

Tương tự cho β với min.
Thuật toán Minimax với tỉa α-β
Thuật toán Minimax với tỉa α-β
Tìm kiếm thời gian thực
Giới hạn về mặt thời gian.

Cách tiếp cận:
Giới hạn độ sâu (tĩnh và động).
Hàm đánh giá
= đánh giá độ tốt của mỗi nước bằng hiện trạng game sau khi nước đó được thực hiện.
Hàm Đánh Giá
Ví dụ đối với cờ, Hàm tổ hợp tuyến tính các đặc trưng bàn cờ tại mỗi thời điểm sau khi nước đánh được đưa ra

Eval(s) = w1 f1(s) + w2 f2(s) + … + wn fn(s)


Ví dụ???
Tìm kiếm với độ sâu giới hạn
MinimaxCutoff giống như MinimaxValue nhưng
Terminal? thay bằng Cutoff?
Utility thay bằng Eval

Ví dụ trong thực tế (nếu máy tính có thể tính 106 nước/s
bm = 106, b=35  m=4

4-nước tính trước là khó đối với người chơi thường:
4-ply ≈ người mới học chơi
8-ply ≈ PC, chuyên gia cờ
12-ply ≈ Deep Blue, Kasparov.
Câu Hỏi Ôn Tập
Tại sao việc tìm kiếm trên game lại quan trọng với trí tuệ nhân tạo?
Cài đặt thuật toán Minimax, Minimax với alpha-beta cutoff cho các trò chơi cụ thể (cờ tướng, cờ caro, ô ăn quan,...).
Xem thêm:
+ Giáo trình: Chương 6.
+ OCW: ch3_csp_games2.
+ Games Playing with Computers, A.G. Bell.
+ Developing Games That Learn, L. Dorfman and N. Ghosh