Bài giảng Trí tuệ nhân tạo - Trần Ngân Bình

 trong phép tính mệnh đề:Mỗi ký hiệu mệnh đề, ký hiệu chân lý là một câu.Phủ định của một câu là một câu.Hội, tuyển, kéo theo, tương đương của hai câu là một câu.	Ký hiệu ( ), [ ] được dùng để nhóm các ký hiệu vào các biểu thức con.Một biểu thức mệnh đề được gọi là một câu (hay công thức dạng chuẩn- WFF)  nó có thể được tạo thành từ những ký hiệu hợp lệ thông qua một dãy các luật trên.Ví dụ: ( (PQ)  R) = P  Q  RC2 – Phép tính vị từTTNT. p.20Ngữ Nghĩa của Phép Tính MĐSự thông dịch (Intepretation):Là sự gán giá trị chân lý (T / F) cho các câu mệnh đề.Là một sự khẳng định chân lý của các câu mệnh đề trong một thế giới khả hữu nào đó.Sự thông dịch của một câu kép thường được xác định bằng bảng chân lý:P	Q	P	PQ	PQ	PQ	P=Q	T	T	F	T	T	T	T	T	F	F	F	T	F	F	F	T	T	F	T	T	F	F	F	T	F	F	T	T	C2 – Phép tính vị từTTNT. p.21Sự Tương Đương của Phép Tính MĐ(P) = P(PQ) = (P  Q)Luật tương phản: (P  Q) = (Q  P)Luật De Morgan:(P  Q) = (P  Q), và	 (P  Q) = (P  Q)Luật giao hoán: (P  Q) = (Q  P), và (PQ) = (QP)Luật kết hợp: 	((P  Q)  R) = (P  (Q  R)), 	((P  Q)  R) = (P  (Q  R))Luật phân phối: P  (Q  R) = (P  Q)  (P  R), 	P  (Q  R) = (P  Q)  (P  R)C2 – Phép tính vị từTTNT. p.22Phép TínhVị Từ (1)Ký hiệu vị từ là tập hợp gồm các chữ cái, chữ số, ký hiệu “_”, và được bắt đầu bằng chữ cái. VD: X3, tom_and_jerryKý hiệu vị từ có thể là:ký hiệu chân lý: true, falseHằng: dùng để chỉ một đối tượng / thuộc tính trong thế giới. Ký hiệu bắt đầu bằng chữ thường: 	 VD: helen, yellow, rainBiến: dùng để chỉ một lớp tổng quát các đối tượng / thuộc tính.Ký hiệu bắt đầu bằng chữ hoa: 	VD: X, People, StudentsHàm: dùng để chỉ một hàm trên các đối tượng.Ký hiệu bắt đầu bằng chữ thường: 	VD: father, plusMỗi ký hiệu hàm có một ngôi n, chỉ số lượng các đối số của hàm.Vị từ: dùng để định nghĩa một mối quan hệ giữa không hoặc nhiều đối tượng.Ký hiệu vị từ bắt đầu bằng chữ thường. 	VD: likes, equals, part_ofC2 – Phép tính vị từTTNT. p.23Phép TínhVị Từ (2)Biểu thức hàm: là một ký hiệu hàm theo sau bởi n đối số. VD: father(david) price(bananas) like(tom, football)Mục (term): là một hằng, một biến hay một biểu thức hàmCâu sơ cấp: là một hằng vị từ với n ngôi theo sau bởi n thành phần (mỗi thành phần là một mục) đặt trong dấu (), cách nhau bởi dấu ‘,’ và kết thúc với dấu ‘.’Trị chân lý true, false là các câu sơ cấp.Câu sơ cấp còn được gọi là: biểu thức sơ cấp (atomic expression), nguyên tử (atom) hay mệnh đề (proposition)VD: friends(helen, marry).	likes(hellen, mary).	 likes(helen, sister(mary)).	likes( X, ice-cream).	Ký hiệu vị từ trong các câu này là friends, likes.C2 – Phép tính vị từTTNT. p.24Phép TínhVị Từ (3)Câu: được tạo ra bằng cách kết hợp các câu sơ cấp sử dụng:Các phép kết nối logic: , , , , =Các lượng tử biến: Lượng tử phổ biến : dùng để chỉ một câu là đúng với mọi giá trị của biến lượng giá	VD:  X likes(X, ice-cream).Lượng tử tồn tại :	dùng để chỉ một câu là đúng với một số giá trị nào đó của biến lượng giá. 	VD: Y friends(Y,tom).VD: likes(helen, chocolat)   likes(bart, chocolat).	  X foo(X,two,plus(two,three))  equal(plus(three,two),five)(foo(two, two,plus(two,three)))  (equal(plus(three,two),five)= true).C2 – Phép tính vị từTTNT. p.25Ngữ Nghĩa của Phép Tính Vị TừSự thông dịch của một tập hợp các câu phép tính vị từ: là một sự gán các thực thể trong miền của vấn đề đang đề cập cho mỗi ký hiệu hằng, biến, vị từ và hàm.Giá trị chân lý của một câu sơ cấp được xác định qua sự thông dịch. Đối với các câu không phải là câu sơ cấp, sử dụng bảng chân lý cho cho các phép nối kết, và:Giá trị của câu  X là true nếu là T cho tất cả các phép gán có thể được cho X.Giá trị của câu  X là true nếu tồn tại một phép gán cho X làm cho có giá trị T.C2 – Phép tính vị từTTNT. p.26Phép Tính Vị Từ Bậc NhấtPhép tính vị từ bậc nhất cho phép các biến lượng giá tham chiếu đến các đối tượng trong miền của vấn đề đang đề cập nhưng KHÔNG được tham chiếu đến các vị từ và hàm. VD không hợp lệ:	(Likes) Likes(helen, ice-cream)VD hợp lệ: Nếu ngày mai trời không mưa, tom sẽ đi biển.weather(rain, tomorrow)  go(tom, sea)Tất cả các cầu thủ bóng rổ đều cao. X ( basketball_player(X)  tall(X) )Có người thích coca-cola X person(X)  likes(X, coca-cola)Không ai thích thuế X likes(X, taxes)C2 – Phép tính vị từTTNT. p.27Ví dụ về phép tính vị từCho trước:	mother(eve,abel)	mother(eve, cain)father(adam, abel)	father(adam,cain)X Y father(X,Y)  mother(X,Y)  parent(X,Y)X Y Z parent(Z,X)  parent(Z,Y)  sibling(X,Y)Có thể suy luận:parent(eve,abel)	parent(eve, cain)parent(adam,abel)	parent(adam,cain)sibling(abel, cain)	sibling(cain, abel)sibling(abel,abel)	sibling(cain,cain) !không có nghĩaC2 – Phép tính vị từTTNT. p.28Các luật suy diễnLuật Modus Ponens (MP):	P  Q 	P 	QLuật Modus Tolens (MT): 	P  Q 	Q	PLuật triển khai phổ biến (Universal Instantiation):	X P(X) 	a thuộc miền xác định của X	P(a) C2 – Phép tính vị từTTNT. p.29Ví Dụ“Tất cả mọi người đều chết và Socrates là người, do đó Socrates sẽ chết”=> 	X man(X)  mortal(X)	 (1) 	man(socrates) 	 (2) Từ (1),(2) bằng luật UI, ta có:	man(socrates)  mortal(socrates) 	(3)Từ (3) và (2) bằng luật MP, ta có:	mortal(bill)	 (4) C2 – Phép tính vị từTTNT. p.30Đối sánh mẫu và phép hợp nhấtĐể áp dụng các luật như MP, một hệ suy diễn phải có khả năng xác định khi nào thì hai biểu thức là một hay còn gọi là đối sánh (match).Phép hợp nhất là một giải thuật dùng để xác định những phép thế (substitution) cần thiết để làm cho hai biểu thức vị từ đối sánh nhau.Một biến có thể thay thế bởi một mục bất kỳ:	C2 – Phép tính vị từBiếnHằngBiểu thức hàm có thể chứa các biến khácBiến khácThay thế bởiBiến đã kết buộc (bound)Biến chưa kết buộc (unbound)TTNT. p.31“Giải thuật” Đối Sánh MẫuHằng / hằng đối sánh : chỉ khi chúng giống hệt nhau	VD:	tom không đối sánh với jerryHằng a / biến X đối sánh:	Biến chưa kết buộc: biến trở thành kết buộc với hằng 	=> Khi đó ta có phép thế 	{a/X}Biến đã kết buộc : xem (1)Biến X/ biến Y đối sánh:Hai biến chưa kết buộc: luôn luôn đối sánh	=> Khi đó ta có phép thế {X/Y}Một biến kết buộc và một biến chưa kết buộc: xem (2)Hai biến kết buộc: xem (1)Biểu thức / biểu thức đối sánh: chỉ khi các tên hàm hoặc vị từ, số ngôi giống nhau thì áp dụng đối sánh từng đối số một.	VD: goo(X) - không đối sánh với foo(X) hay goo(X,Y)	 - đối sánh với goo(foo(Y)) với phép thế {foo(Y) / X}C2 – Phép tính vị từTTNT. p.32Phạm vi của một biếnPhạm vi của một biến là một câu. Một khi biến đã bị kết buộc, các phép hợp nhất theo sau và các suy luận kế tiếp phải giữ sự kết buộc nàyVD: 	man(X) => mortal(X)	Nếu ta thế X bởi socrates thì ta được:	man(socrates) => mortal(socrates)C2 – Phép tính vị từTTNT. p.33Ví dụ: Biểu thức đối sánhHãy xác định xem foo(X,a,goo(Y)) có đối sánh với các biểu thức sau hay không? Nếu có thì cho biết phép thế tương ứng:	foo(X,b,foo(Y))	foo(fred, a, goo(Z))	foo(X,Y)	moo(X,a,goo(Y))	foo(Z,a,goo(moo(Z)))	foo(W,a,goo(jack))	Cho biết kết quả có được khi hợp nhất p(a, X) với :p(Y,Z) => q(Y,Z)	q(W,b) => r(W,b)C2 – Phép tính vị từTTNT. p.34Thủ tục hợp nhất “Unify”Ghi chú:p(a,b) ~ (p a b)p(f(a), g(X, Y) ~ (p (f a) (g x Y) )C2 – Phép tính vị từTTNT. p.35Tích các phép thế hợp nhất (Composition)Nếu S và S’ là hai tập hợp phép thế, thì tích của S và S’ được xác định bằng cách áp dụng S’ cho những phần tử của S và bổ sung kết quả này vào S.VD: {X/Y, W/X}, {V/X}, {a/V, f(b)/W}	=> {a/Y, f(b)/Z}C2 – Phép tính vị từTTNT. p.36Hợp tử tổng quát nhất(Most General Unifier)Yêu cầu của giải thuật hợp nhất là hợp tử (unifier) càng tổng quát càng tốt: đó là hợp tử tổng quát nhất tìm thấy cho hai biểu thức.VD: Khi hợp nhất p(X) và p(Y): không nên chọn {fred/X, fred/Y} vì fred không phải là hợp tử tổng quát nhất nên chọn {Z/Y, Z/Y}C2 – Phép tính vị từTTNT. p.37Ứng Dụng: Hệ tư vấn tài chính (1)Hệ tư vấn tài chính hoạt động theo các nguyên tắc sau:Các cá nhân không đủ tiền tiết kiệm nên tăng tiền tiết kiệm, bất kể thu nhập là bao nhiêu.Các cá nhân có đủ tiền tiết kiệm và đủ thu nhập nên xem xét việc đầu tư vào chứng khoán. Các cá nhân với thu nhập thấp nhưng đủ tiền tiết kiệm có thể chia phần thu nhập thêm vào tiết kiệm và chứng khoán.Với:tiết kiệm đủ là 5000$/ người phụ thuộcThu nhập đủ 15000$ + (4000$ / người phụ thuộc)C2 – Phép tính vị từTTNT. p.38Ứng Dụng: Hệ tư vấn tài chính (2) Xâu dựng hệ thống logic với các câu vị từ như sau:savings_account(inadequate) investment(saving)savings_account(adequate) income(adequate)  investment(stocks)savings_account(adequate) income(inadequate)  	investment(combination)X amount_saved(X) Y(dependents(Y)  greater(X,minsavings(Y))) 	 savings_account(adequate)X amount_saved(X) Y(dependents(Y)  	greater(X,minsavings(Y)))  savings_account(inadequate)X earning(X, steady) Y(dependents(Y)  	greater(X,minincome(Y)))  income(adequate)X earning(X, steady) Y(dependents(Y)  	greater(X,minincome(Y)))  income(inadequate)X earning(X, unsteady)  income(inadequate)With:	minavings(X) = 5000 * X 	minincome(X)=15000+(4000*X)C2 – Phép tính vị từTTNT. p.39Ứng Dụng: Hệ tư vấn tài chính(3)Một nhà đầu tư với tình trạng như sau:amount_saved(22000)earnings(25000,steady)dependents(3)	 investment (?)Dùng phép hợp nhất và luật Modus Ponens, suy ra:income(inadequate)savings_account(adequate) investment (combination)C2 – Phép tính vị từBài Tập Chương 2TTNT. p.41Chương 3 - Cấu trúc và chiến lược cho TK - KGTTKhi biểu diễn một vấn đề như là một đồ thị không gian trạng thái, chúng ta có thể sử dụng lý thuyết đồ thị để phân tích cấu trúc và độ phức tạp của các vấn đề cũng như các thủ tục tìm kiếm.C 3 – Tìm kiếm không gian trạng thái5 6 Riverbank 1 Riverbank 2 Island 1 Island 2 1 2 3 4 7 Hệ thống cầu thành phố Konigsberg và biểu diễn đồ thị tương ứngTTNT. p.42Nội dung chương 3Định nghĩa Không Gian Trạng TháiCác chiến lược tìm kiếm trên không gian trạng thái: TK hướng từ dữ liệu (data – driven) TK hướng từ mục tiêu (goal – driven).Tìm kiếm trên không gian trạng thái: TK rộng (breath – first search)TK sâu (depth – first search)TK sâu bằng cách đào sâu nhiều lần (depth – first search with iterative deepening)Sử dụng không gian trạng thái để biễu diễn suy luận với phép tính vị từ: Đồ thị Và/Hoặc (And/Or Graph)C 3 – Tìm kiếm không gian trạng tháiTTNT. p.43ĐN: KHÔNG GIAN TRẠNG THÁI Một KGTT (state space) là 1 bộ [N, A, S, GD] trong đó:N (node) là các nút hay các trạng thái của đồ thị. A (arc) là tập các cung (hay các liên kết) giữa các nút. S (solution) là một tập chứa các trạng thái đích của bài toán.(S  N  S  )Các trạng thái trong GD (Goal Description) được mô tả theo một trong hai đặc tính:Đặc tính có thể đo lường được các trạng thái gặp trong quá trình tìm kiếm. VD: Tic-tac-toe, 8-puzzle,Đặc tính của đường đi được hình thành trong quá trình tìm kiếm. VD: TSPĐường đi của lời giải (solution path) là một con đường đi qua đồ thị này từ một nút thuộc S đến một nút thuộc GD. C 3 – Tìm kiếm không gian trạng tháiTTNT. p.44Một phần KGTT triển khai trong Tic-tac-toe Đồ thị có hướng không lặp lại (directed acyclic graph - DAG) C 3 – Tìm kiếm không gian trạng tháiTTNT. p.45Trò đố 8 ô hay 15 ô	 Trạng thái ban đầu Trạng thái đíchTrò đố	15 ôTrò đố	8 ôCần biểu diễn KGTT cho bài toán này như thế nào?1234121314511156109871238476511144710651213159128328357621C 3 – Tìm kiếm không gian trạng tháiTTNT. p.46KGTT của 8-puzzle sinh ra bằng phép “di chuyển ô trống”C 3 – Tìm kiếm không gian trạng tháiCó khả năng xảy ra vòng lặp không?TTNT. p.47Một ví dụ của bài toán TSPCần biểu diễn KGTT cho bài toán này như thế nào?C 3 – Tìm kiếm không gian trạng tháiTTNT. p.48KGTT của bài toán TSPMỗi cung được đánh dấu bằng tổng giá của con đường từ nút bắt đầu đến nút hiện tại.C 3 – Tìm kiếm không gian trạng tháiTTNT. p.49Các Chiến Lược cho TK-KGTTTK hướng từ dữ liệu (Data-driven Search)Suy diễn tiến (forward chaining)TK hướng từ mục tiêu (Goal-driven Search)Suy diễn lùi (backward chaining)C 3 – Tìm kiếm không gian trạng tháiTTNT. p.50TK Hướng từ Dữ LiệuViệc tìm kiếm đi từ 	dữ liệu đến mục tiêuThích hợp khi:Tất cả hoặc một phần dữ liệu được cho từ đầu.Có nhiều mục tiêu, nhưng chỉ có một số ít các phép toán có thể áp dụng cho một trạng thái bài toán. Rất khó đưa ra một mục tiêu hoặc giả thuyết ngay lúc đầu.C 3 – Tìm kiếm không gian trạng tháiTTNT. p.51TK Hướng Từ Mục TiêuViệc tìm kiếm đi từ 	mục tiêu trở về 	dữ liệu.Thích hợp khi:Có thể đưa ra mục tiêu hoặc giả thuyết ngay lúc đầu.Có nhiều phép toán có thể áp dụng trên 1 trạng thái của bài toán => sự bùng nổ số lượng các trạng thái. Các dữ liệu của bài toán không được cho trước, nhưng hệ thống phải đạt được trong quá trình tìm kiếm.C 3 – Tìm kiếm không gian trạng tháiTTNT. p.52Các phương pháp tìm kiếm trên đồ thị KGTT:Phát triển từ giải thuật quay lui (back – tracking):Tìm kiếm rộng (breath-first search)Tìm kiếm sâu (depth-first search)TK sâu bằng cách đào sâu nhiều lần (depth-first search with iterative deepening)C 3 – Tìm kiếm không gian trạng tháiTTNT. p.53Tìm Kiếm RộngOpen = [A]; closed = []Open = [B,C,D]; 	closed = [A]Open = [C,D,E,F];	closed = [B,A]Open = [D,E,F,G,H];	closed = [C,B,A]Open = [E,F,G,H,I,J];	closed = [D,C,B,A]Open = [F,G,H,I,J,K,L]; 	closed = [E,D,C,B,A]Open = [G,H,I,J,K,L,M];	(vì L đã có trong open);	closed = [F,E,D,C,B,A]	C 3 – Tìm kiếm không gian trạng tháiTTNT. p.54Tìm kiếm SâuOpen = [A]; closed = []Open = [B,C,D]; closed = [A]Open = [E,F,C,D];closed = [B,A]Open = [K,L,F,C,D];	closed = [E,B,A]Open = [S,L,F,C,D];	closed = [K,E,B,A]Open = [L,F,C,D]; 	closed = [S,K,E,B,A]Open = [T,F,C,D];	closed = [L,S,K,E,B,A]Open = [F,C,D]; 	closed = [T,L,S,K,E,B,A]C 3 – Tìm kiếm không gian trạng tháiTTNT. p.55Tìm Kiếm Sâu hay Rộng? (1)Có cần thiết tìm một đường đi ngắn nhất đến mục tiêu hay không?Sự phân nhánh của không gian trạng tháiTài nguyên về không gian và thời gian sẵn cóKhoảng cách trung bình của đường dẫn đến trạng thái mục tiêu.Yêu cầu đưa ra tất cả các lời giải hay chỉ là lời giải tìm được đầu tiên.C 3 – Tìm kiếm không gian trạng tháiTTNT. p.56Tìm kiếm sâu bằng cách đào sâu nhiều lần(depth-first iterative deepening)Độ sâu giới hạn (depth bound): giải thuật TK sâu sẽ quay lui khi trạng thái đang xét đạt đến độ sâu giới hạn đã định.TK Sâu bằng cách đào sâu nhiều lần: TK sâu với độ sâu giới hạn là 1, nếu thất bại, nó sẽ lặp lại GT TK sâu với độ sâu là 2, GT tiếp tục cho đến khi tìm được mục tiêu, mỗi lần lặp lại tăng độ sâu lên 1.GT này có độ phức tạp về thời gian cùng bậc với TK Rộng và TK Sâu.C 3 – Tìm kiếm không gian trạng tháiTTNT. p.57Trò chơi ô đố 8-puzzleThe 8-puzzle searched by a production system with loop detection and depth bound 5C 3 – Tìm kiếm không gian trạng tháiTTNT. p.58Đồ thị Và/HoặcSử dụng KGTT để biễu diễn suy luận với phép tính vị từLà phương pháp qui bài toán về các bài toán con.Một tập hợp các mệnh đề / câu vị từ tạo thành một đồ thị Và/Hoặc (And/Or graph) hay siêu đồ thị (hypergraph).Trong đồ thị Và/Hoặc:Các nút AND biểu thị sự phân chia bài toán, tất cả các bài toán con phải được chứng minh là đúng.Các nút OR biểu thị các chiến lược giải quyết bài toán khác nhau, chỉ cần chứng minh một chiến lược đúng là đủCó thể áp dụng TK theo kiểu hướng từ dữ liệu hay từ mục tiêu.Trong giải thuật cần ghi nhận diễn tiến của quá trình.C 3 – Tìm kiếm không gian trạng tháiTTNT. p.59Ví dụ Đồ thị Và/HoặcGiả sử một tình huống với các mệnh đề sau:a	b	cabd	acebdf	fgaeh	Hãy trả lời các câu hỏi sau:h có đúng không?h có cón đúng nêu b sai?C 3 – Tìm kiếm không gian trạng tháiTTNT. p.60Ví dụ: Hệ Tư Vấn Tài ChínhĐồ Thị And/Or biểu diễn phần KGTT đã duyệt qua để đi đến lời giảiTTNT. p.61VÍ DỤ ĐỒ THỊ AND/OR:Cho một bài toán được mô tả bằng các câu vị từ:Hãy vẽ đồ thị AND/OR biểu diễn phần KGTK để trả lời câu hỏi: “Fred đang ở đâu?” (Áp dụng suy diễn lùi)Bài Tập Chương 3TTNT. p.63Chương 4 – Tìm kiếm heuristicHeuristics: là các phỏng đoán, ước chừng dựa trên kinh nghiệm, trực giác.Các hệ giải quyết AI sử dụng heuristic trong hai tình huống cơ bản:Bài toán được định nghĩa chính xác nhưng chi phí tìm lời giải bằng TK vét cạn là không thể chấp nhận.	VD: Sự bùng nổ KGTT trong trò chơi cờ vua.Vấn đề với nhiều sự mơ hồ trong lời phát biểu bài toán hay dữ liệu cũng như tri thức sẵn có.	VD: Chẩn đoán trong y học.C 4 – Tìm kiếm HeuristicTTNT. p.64Giải Thuật HeuristicMột giải thuật heuristic có thể được xem gồm 2 phần:Phép đo heuristic: thể hiện qua hàm đánh giá heuristic (evaluation function), dùng để đánh giá các đặc điểm của một trạng thái trong KGTT.Giải thuật tìm kiếm heuristic:Giải thuật leo núi (hill-climbing) TK tốt nhất (best-first search)C 4 – Tìm kiếm HeuristicTTNT. p.65KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng của các trạng thái.C 4 – Tìm kiếm HeuristicTTNT. p.66Phép đo heuristic (2)Heuristic “Số đường thắng nhiều nhất” áp dụng cho các nút con đầu tien trong tic-tac-toe.C 4 – Tìm kiếm HeuristicTTNT. p.67KGTT càng thu nhỏ khi áp dụng heuristicC 4 – Tìm kiếm HeuristicTTNT. p.68Giải thuật Leo NúiGiải thuật:Mở rộng trạng thái hiện tại và đánh giá các trạng thái con của nó bằng hàm đánh giá heuristic.Con “tốt nhất” sẽ được chọn để đi tiếp.Giới hạn: Giải thuật có khuynh hướng bị sa lầy ở những cực đại cục bộ: Lời giải tìm được không tối ưu Không tìm được lời giải mặc dù có tồn tại lời giảiGiải thuật có thể gặp vòng lặp vô hạn do không lưu giữ thông tin về các trạng thái đã duyệt. C 4 – Tìm kiếm HeuristicTTNT. p.69Giải thuật TK Tốt Nhấtopen = [A5]; closed = []Đánh giá A5; open = [B4,C4,D6]; closed = [A5]Đánh giá B4; 	open = [C4,E5,F5,D6]; 	closed = [B4,A5]Đánh giá C4; 	open = [H3,G4,E5,F5,D6]; 	closed = [C4,B4,A5]Đánh giá H3; 	open = [O2,P3,G4,E5,F5,D6]; 	closed = [H3,C4,B4,A5]	Đánh giá O2; 	open = [P3,G4,E5,F5,D6]; 	closed = [O2,H3,C4,B4,A5]Đánh giá P3; tìm được lời giải!C 4 – Tìm kiếm HeuristicTTNT. p.70Cài Đặt Hàm Đánh Giá (Evaluation Function)28316475283164752831476528316475start12384765goalg(n) = 0g(n) = 1646Xét trò chơi 8-puzzle. Cho mỗi trạng thái n một giá trị f(n):	f(n) = g(n) + h(n)g(n) = khoảng cách thực sự từ n đến trạng thái bắt đầuh(n) = hàm heuristic đánh giá khoảng cách từ trạng thái n đến mục tiêu. f(n) = C 4 – Tìm kiếm Heuristich(n): số lượng các vị trí còn saiTTNT. p.71Khó khăn trong thiết kế hàm heuristicBa heuristic áp dụng vào 3 trạng thái của trò chơi ô đố 8 sốC 4 – Tìm kiếm HeuristicTTNT. p.72Heuristic trong trò chơi đối khángGiải thuật minimax:Hai đấu thủ trong trò chơi được gọi là MIN và MAX.Mỗi nút lá có giá trị: 1 nếu là MAX thắng, 0 nếu là MIN thắng.Minimax sẽ truyền các giá trị này lên cao dần trên đồ thị, qua các nút cha mẹ kế tiếp theo các luật sau:Nếu trạng thái cha mẹ là MAX, gán cho nó giá trị lớn nhất có trong các trạng thái con.Nếu trạng thái bố, mẹ là MIN, gán cho nó giá trị nhỏ nhất có trong các trạng thái con.C 4 – Tìm kiếm HeuristicTTNT. p.73Hãy áp dụng GT Minimax vào Trò Chơi NIMC 4 – Tìm kiếm HeuristicTTNT. p.74Minimax với độ sâu lớp cố địnhMinimax đối với một KGTT giả định.Các nút lá được gán các giá trị heuristicCòn giá trị tại các nút trong là các giá trị nhận được dựa trên giải thuật MinimaxC 4 – Tìm kiếm HeuristicTTNT. p.75Heuristic trong trò chơi tic-tac-toeHàm Heuristic: 	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 nC 4 – Tìm kiếm HeuristicTTNT. p.76Minimax 2 lớp được áp dụng vào nước đi mở đầu trong tic-tac-toeTrích từ Nilsson (1971).C 4 – Tìm kiếm HeuristicTTNT. p.77Giải thuật cắt tỉa -Tìm kiếm theo kiểu depth-first.Nút MAX có 1 giá trị  (luôn tăng)Nút MIN có 1 giá trị  (luôn giảm)TK có thể kết thúc dưới bất kỳ:Nút MIN nào có    của bất kỳ nút cha MAX nào.Nút MAX nào có    của bất kỳ nút cha MIN nào.Giải thuật cắt tỉa - thể hiện mối quan hệ giữa các nút ở lớp n và n+2, mà tại đó toàn bộ cây có gốc tại lớp n+1 có thể cắt bỏ.C 4 – Tìm kiếm HeuristicTTNT. p.78Cắt tỉa  SAZMAXMIN= z≥ = z ≤  - cut= C 4 – Tìm kiếm HeuristicTTNT. p.79Cắt tỉa  SAZMINMAX= z ≤ = z ≥  - cut= C 4 – Tìm kiếm HeuristicTTNT. p.80GT Cắt Tỉa - áp dụng cho KGTT giả địnhC 4 – Tìm kiếm HeuristicCác nút không có giá trị là các nút không được duyệt quaBài Tập Chương 4