Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
1

MỤC LỤC

LỜI NÓI ĐẦU 2
I. BIỂU DIỄN TRI THỨC BẰNG LUẬT SINH 3
1. Bài toán đong nƣớc 3
2. Khái niệm luật sinh 10
3. Cơ chế suy luận trên các luật sinh 11
4. Tối ƣu luật 13
5. Ƣu điểm và nhƣợc điểm của biểu diễn tri thức bằng luật sinh 15
II. ỨNG DỤNG LUẬT SINH TRONG THIẾT KẾ TRÒ CHƠI CARO 16
1. Giới thiệu trò chơi Caro 16
2. Cài đặt hệ thống 16
3. Thực thi chƣơng trình 17
4. Phân tích, thiết kế 18
5. Giới thiệu một số source code của chƣơng trình 19
TÀI LIỆU THAM KHẢO 24 Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
2

LỜI NÓI ĐẦU

Luật sinh là một trong những phương pháp biểu diễn tri thức trên máy tính. Nó

).
Bài toán này khá tiêu biểu, thường được dùng để minh họa chon nét đẹp của
phương pháp giải quyết vấn đề - bài toán bằng cách chuyển giao tri thức cho
máy tính. Nếu sử dụng thuật toán thông thường chúng ta chỉ giải được một số
trường hợp cụ thể của bài toán này. Thậm chí, nhiều người khi mới tiếp cận với
bài toán này còn không tin là nó có thể hoàn toàn được giải một cách tổng quát
bởi máy tính. Bài toán này sẽ được giải quyết bằng cách sử dụng các luật dẫn
xuất (luật sinh).
Với một trường hợp cụ thể của bài toán như V
x
=5 (bình 5) và V
y
=7 (bình 7)
và z=4. Sau một thời gian tính toán, ta có thể sẽ đưa ra một quy trình đổ nước đại
loại như:
- Múc đầy bình 7
- Trút hết qua bình 5 cho đến khi 5 đầy
- Đổ hết nước trong bình 5
- Đổ hết nước còn lại từ bình 7 sang bình 5
- Múc đầy bình 7
- Trút hết qua bình 5 cho đến khi 5 đầy
- Phần còn lại chính là số nước cần đong
Tuy nhiên, với những số liệu bình V
x
và V
y
khác, thì ta phải “mày mò” lại từ
đầu để tìm ra quy trình đổ nước. Cứ thế, mỗi một trường hợp sẽ có một cách đổ
nước hoàn toàn khác nhau. Như vậy, nếu có một ai đó yêu cầu ta đưa ra một
cách làm tổng quát thì chính ta cũng sẽ lúng túng, ngoại trừ trường hợp đã biết

nước cần đong là một bội số của ước số chung lớn nhất của thể tích 2 bình: z=n x
USCLN(V
x
,V
y
) (với n nguyên dương).
Trên thực tế, lúc đầu để giải trường hợp tổng quát của bài toán này, người ta
đã dùng đến hơn 15 luật (kinh nghiệm) khác nhau. Sau này, người ta đã rút gọn
lại chỉ còn 3 luật được mô tả như sau:
(L1) Nếu bình X đầy thì đổ hết nước trong bình X đi.
(L2) Nếu bình Y rỗng thì đổ đầy nước vào bình Y.
(L3) Nếu bình Y không rỗng và bình X không đầy thì hãy trút nước từ bình
Y sang bình X (cho đến khi bình X đầy hoặc bình Y hết nước).
Quá trình giải được thực hiện bằng cách xét lần lượt các luật sau, luật nào
thỏa mãn thì sẽ được áp dụng. Sau khi áp dụng luât, trạng thái của bài toán sẽ
thay đổi, ta lại tiếp tục xét các luật kế tiếp, nếu hết luật, quay trở lại luật đầu tiên.
Quá trình tiếp diễn cho đến khi đạt được điều kiện kết thúc của bài toán.
Như vậy, các luật chính là các “kinh nghiệm” hay tri thức mà ta đã chuyển
giao cho máy tính.
Ta có thể dễ dàng chuyển đổi cách giải này thành chương trình như sau:
…
x:=0; y:=0;
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
5

WHILE ((x<>z) AND (y<>z)) DO
BEGIN
IF (x=V

x=0, y=1
Luật (L3)

x=1, y=0
Luật (L2)

x=1, y=4
Luật (L3)

x=3, y=2
Ba luật mà chúng ta đã cài đặt trong chương trình trên được gọi là cơ sở tri
thức. Còn cách thức tìm kiếm lời giải bằng cách duyệt tuần tự từng luật và áp
dụng nó được gọi là động cơ suy diễn. Hai thuật ngữ này sẽ được định nghĩa
chính xác ở cuối phần này.
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
6

Cách giải quyết vấn đề theo kiểu này rất khác so với cách giải bằng thuật
toán thông thường là chúng ta không đưa ra một trình tự giải quyết vấn đề cụ thể
mà chỉ đưa ra các quy tắc chung chung (dưới dạng các luật), máy tính sẽ dựa vào
đó (áp dụng các luật) để xây dựng một quy trình giải quyết vấn đề. Điều này
cũng giống như việc chúng ta giải toán bằng cách đưa ra các định lý, quy tắc liên
quan đến bài toán mà không cần chỉ ra cách giải cụ thể.
Vậy thì điểm thú vị nằm ở điểm nào? Có thể cảm thấy rằng ta vẫn đang dùng
tri thức “cứng” (vì các tri thức vẫn là các câu lệnh IF được cài sẵn trong chương
trình). Thực ra thì chương trình của chúng ta đã “mềm” hơn một chút. Để rõ hơn,
ta hãy quan sát phiên bản kế tiếp của chương trình này.
FUNCTION DK(L INTEGER): BOOLEAN;

IF DK(L) THEN ThiHanh(L);
END;
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
7

END.

Đoạn chương trình chính cũng thi hành bằng cách lần lượt xét qua 3 luật IF
như chương trình đầu tiên. Tuy nhiên, ở đây, biểu thức điều kiện được thay thế
bằng hàm DK và các hành động ứng với điều kiện đã được thay thế bằng thủ tục
ThiHanh. Tính chất “mềm” hơn của chương trình này thể hiện ở chỗ, nếu muốn
bổ sung “tri thức”, ta chỉ phải điều chỉnh lại các hàm DK và ThiHanh mà không
cần phải sửa lại chương trình chính.
Bây giờ hãy giả sử rằng ta đã có hàm và thủ tục đặc biệt sau:
FUNCTION GiaTriBool(DK: String): BOOLEAN;
PROCEDURE ThucHien(ThaoTac: String);

Hàm GiaTriBool nhận vào một chuỗi điều kiện, nó sẽ phân tích chuỗi, tính
toán rồi trả ra giá trị BOOLEAN của biểu thức này. Ví dụ:
GiaTriBoolean(„6<7‟) s4 trả ra FALSE.
Thủ tục ThucHien cũng nhận vào một chuỗi, cũng sẽ phân tích chuỗi rồi tiến
hành thực hiện những hành động được miêu tả trong chuỗi này.
Với hàm và thủ tục này, chương trình của chúng ta sẽ như sau:
CONST SO_LUAT=3;
TYPE
Luat RECORD
DK: String;
ThiHanh: String;

BEGIN
FOR i:=1 TO SO_LUAT DO
IF GiaTriBoolean(CacLuat[i].DK)
THEN ThucHien(CacLuat[i].ThaoTac);
END;
END.

Cứ tạm cho rằng, trong quá trình chương trình thi hành, ta có thể dễ dàng
thay đổi số phần tử mảng CacLuat (các ngôn ngữ lập trình sau này như Visual
C++, Delphi đều cho phép điều này). Và như vậy, với chương trình này, khi
muốn sửa đổi “tri thức”, ta chỉ cần thay đổi giá trị mảng CacLuat là xong.
Tuy nhiên, người sử dụng vẫn gặp khó khăn khi muốn bổ sung hoặc hiệu
chỉnh tri thức. Họ cần phải nhập các chuỗi đại loại như „x=0‟ hoặc „k=min(V
x
-
x,y)‟… Các chuỗi này vẫn còn khá xa lạ đối với những người dùng bình thường
(tuy nó có ý nghĩa đối với chương trình). Chúng ta cần phải giảm bớt “khoảng
cách” này lại bằng cách đưa ra những chuỗi điều kiện hoặc thao tác có ý nghĩa
trực tiếp đối với người dùng. Chương trình sẽ có chuyển đổi lại các điều kiện và
thao tác này sang dạng phù hợp với chương trình.
Để làm được điều trên, chúng ta cần phải liệt kê được các trạng thái và thao
tác cơ bản của bài toán này. Sau đây là một số trạng thái và thao tác cơ bản.
- Tr ạng thái cơ bản: Bình X đầy; Bình X rỗng; Bình X không rỗng; Bình X
có n lít nước.
- Thao tác: Đổ hết nước trong bình; Đổ đầy nước trong bình, Đổ nước từ
bình A sang bình B cho tới khi B đầy hoặc A rỗng.

Lưu ý rằng ta không có thao tác “Đổ n lít nước từ A sang B” ví bài toán đã
giả định rằng các bình đều không có vạch chia, hơn nữa nếu ta biết cách đổ n lít
nước từ A sang B thì lời giải bài toán trở thành quá đơn giản.

thể dùng để vận hành nhiều loại xe máy khác nhau và cơ sở tri thức chính là loại
nhiên liệu đặc biệt để vận hành loại động cơ này. Hình ảnh sau tóm tắt cho thấy
cấu trúc chung nhất của một chương trình trí tuệ nhân tạo.
DỮ LIỆU
THUẬT
TOÁN
ĐỘNG CƠ SUY
DIỄN
DỮ
LIỆU
CƠ SỞ TRI
THỨC
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
10
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
11

được dùng để bắt chước hành vi của những chuyên gia. Theo cách này, luật sinh
không chỉ đơn thuần là một kiểu biểu diễn tri thức trong máy tính mà là một kiểu
biểu diễn các hành vi của con người.
Như vậy, luật là cấu trúc tri thức dùng để liên kết thông tin đã biết với các
thông tin khác giúp đưa ra các suy luận, kết luận từ những thông tin đã biết.
trong hệ thống dựa trên các luật, người ta thu thập các tri thức lĩnh vực của các
chuyên gia và lưu trữ trong cơ sở tri thức. Hệ thống dùng các luật này cùng với
các thông tin trong bộ nhớ để giải bài toán. Việc sử dụng các luật trong hệ thống
để xử lý thông tin được quản lý bằng bộ suy diễn.
Một cách tổng quát, luật sinh có dạng như sau:
P
1
^P
2
^…^P
n


Q
Tùy vào các vấn đề đang quan tâm mà luật sinh có những ngữ nghĩa hay cấu
tạo khác nhau:
- Trong logic vị từ: P
1
^P
2

Trong đó, các f
i
, q đều thuộc F.
Ví dụ: Cho một cơ sở tri thức được xác định như sau:
+ Các sự kiện: A,B,C,D,E,F,G,H,K
+ Tập các quy tắc hay luật sinh (rule)
R1: A

E
R2: B

D
R3: H

A
R4: E^G

C
R5: E^K

B
R6: D^E^K

C
R7: G^K^F

A

3. Cơ chế suy luận trên các luật sinh
Suy diễn tiến: là quá trình suy luận xuất phát từ một số sự kiện ban đầu, xác

+ Lỏng cáp màn hình
+ Tình trạng đèn ổ cứng là “tắt” hoặc “sáng”
+ Có âm thanh đọc ổ cứng
+ Tình trạng đèn màn hình “xanh” hoặc “chớp đỏ”
+ Không sử dụng được máy tính
+ Điện vào máy tính “có” hay “không”

Tập các luật:
R1: Nếu ( (ổ cứng “hỏng”) hoặc (cáp màn hình “lỏng”)) thì không sử
dụng được máy tính.
R2: Nếu (điện vào máy là “có”) và ((âm thanh đọc ổ cứng là “không”)
hoặc tình trạng đèn ổ cứng là “tắt”)) thì (ổ cứng “hỏng”)
R3: Nếu (điện vào máy là “có”) và (tình trạng đèn màn hình là “chớp
đỏ”) thì (cáp màn hình “lỏng”)

Để xác định được các nguyên nhân gây ra sự kiện “không sử dụng được máy
tính”, ta phải xây dựng một cấu trúc đồ thị, gọi là đồ thị AND/OR như sau: Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
13


hình “chớp đỏ”
Âm thanh ổ
cứng “không”
Đèn ổ cứng
“tắt”
OR
AND
AND
OR
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
14

Là hoàn toàn tương đương với: A ^ B  C
Quy tắc rút gọn: có thể loại bỏ những sự kiện bên vế phải nếu những sự
kiện đó đã xuất hiện bên vế trái. Nếu sau khi rút gọn mà vế phải trở thành
rỗng thì luật đó là luật hiển nhiên. Ta có thể loại bỏ các luật hiển nhiên ra
khỏi tri thức.

 Rút gọn bên trái
Xét các luật:
L1: A, B  C L2: A  X L3: X  C
Rõ ràng là luật L1 có thể được thay thế bằng luật A  C mà không làm ảnh
hưởng đến các kết luận trong mọi trường hợp. Ta nói rằng sự kiện B trong
luật L1 là dư thừa và có thể được loại bỏ khỏi luật dẫn trên.

 Phân rã và kết hợp luật
Luật: A v B  C
Tương đương với hai luật: A  C và B  C

15

Với mỗi i từ 1 đến n: R:=R+{X
i
–Y}
R:=R-{r}
Bước 3: Loại bỏ luật thừa
Với mỗi luật r thuộc R
Nếu VếPhải(r) thuộc BaoĐóng(VếTrái(r),R-{r}) thì R:=R-{r}
Bước 4: Rút gọn vế trái
Với mỗi luật dẫn r: X={A
1
,A
2
,…,A
n
}  Y thuộc R
Với mỗi sự kiện A
i
thuộc r
Gọi luật r
1
: X-A
i
 Y
S=(R-{r}) U {r
1
}
Nếu BaoĐóng(X-A
i

16

II. ỨNG DỤNG LUẬT SINH TRONG THIẾT KẾ TRÒ CHƠI CARO
1. Giới thiệu trò chơi Caro
- Cờ caro là một loại cờ cổ xưa của người Trung Quốc, một trong những trò
chơi logic lâu đời nhất được biết đến trên thế giới.
- Cờ caro được chơi trên toàn thế giới, ở mỗi nơi nó lại có tên gọi khác nhau: ở
Nhật là Gomoku, ở Nga và các nước Đông Âu gọi là Five in a row, ở Hàn
Quốc là Omok, ở Trung Quốc là Wuziqi, ở Anh là Connect5… và dĩ nhiên ở
Việt Nam là Caro.

2. Cài đặt hệ thống
Môi trƣờng thực thi
- Windows
- Windows XP
- Java Runtime Environment:
- Java 1.4 (J2SE).
- Phần đính kèm: “j2re-1_4_2_13-windows-i586-p.exe”
- Thư viện
- Phần đính kèm: “jbossrules-ide-3.0.4-bin.zip”
- Eclipse SDK
- Phần đính kèm: “eclipse-SDK-3.2.1-win32.zip”
Môi trƣờng cài đặt
- Cài đặt java với file: “j2re-1_4_2_13-windows-i586-p.exe”.
- Giải nén “eclipse-SDK-3.2.1-win32.zip” và copy vào đĩa cứng.
- Giải nén “jbossrules-ide-3.0.4-bin.zip” và copy file “org.drools.ide_3.0.4.jar”
vào thư mục plug-in của Eclipse.
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm


Y
N {T/F}
Người chơi
Kiểm tra
người chiến
thắng
Tìm 1 ô cho máy
Máy chơi
Kết thúc
trò chơi
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
19

 Hệ luật sử dụng để thiết kế:
Luật 1: Sau khi người đi 1 bước đó, người yêu cầu máy đi bước kế tiếp.

20
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
21
 Kiểm tra người chiến thắng

Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
22
Bài thu hoạch: Biểu diễn tri thức và ứng dụng

Phạm Tuấn Khiêm
23

Bài thu hoạch: Biểu diễn tri thức và ứng dụng