ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG ----------------- BÀI THU HOẠCH MÔN HỌC BIỂU DIỄN TRI THỨC VÀ ỨNG DỤNG ĐỀ TÀI CÁC PHƯƠNG PHÁP BIỂU DIỄN TRI THỨC VÀ ỨNG DỤNG VÀO TRÒ CHƠI CỜ CARO GVHD: PGS.TS. Đỗ Văn Nhơn Học viên thực hiện: Huy ̀ nh Thi ̣ My ̃ Hô ̀ ng Mã số học viên: CH1101086 TP.HCM, năm 2012 MỤC LỤC Trang MỞ ĐẦU 1 Chương 1: TỔNG QUAN VỀ BIỂU DIỄN TRI THỨC VÀ GIẢI TOÁN DỰA TRÊN TRI THỨC .2 1.1. Khái niệm tri thức .2 1.2. Khám niệm về biểu diễn tri thức 2 1.3. Các dạng tri thức .3 Chương 2: CẤU TRÚC CỦA HỆ GIẢI TOÁN DỰA TRÊN TRI THỨC 4 2.1. Cấu trúc hệ thống 4 2.2. Vấn đề biểu diễn tri thức .5 Chương 3: PHƯƠNG PHÁP BIỂU DIỄN TRI THỨC .6 3.1. Các phương pháp biểu diễn tri thức 6 3.2. Suy diễn tự động .7 Chương 4: TỔNG QUAN VỀ CÁC CHIẾN LƯỢC HEURISTIC .9 4.1. Khái niệm Heuristic .9 4.2. Các chiến lược tìm kiếm Heuristic (tìm kiếm có đối thủ) .10 4.3. Hàm đánh giá và các phương pháp đánh giá kinh nghiệm trong các chiến lược tìm kiếm Heuristic 19 Chương 5: TÌM HIỂU VỀ TRÒ CHƠI CỜ CARO VÀ ỨNG DỤNG CÁC CHIẾN LƯỢC HEURISTIC VÀO TRÒ CHƠI CỜ CARO .21 5.1. Giới thiệu về trò chơi cờ caro 21 5.2. Các kinh nghiệm trong trò chơi cờ caro 22 5.3. Ứng dụng các chiến lược tìm kiếm Heuristic cho trò chơi cờ caro .23 Chương 6: Ý TƯỞNG VÀ CHƯƠNG TRÌNH TRÒ CHƠI CỜ CARO .26 6.1. Ý tưởng cho chương trình trò chơi cờ caro .26 6.2. Giới thiệu về chương trình trò chơi cờ caro 31 TÀI LIỆU THAM KHẢO 34 1 MỞ ĐẦU Trong khoa học trí tuệ nhân tạo, mô hình phương pháp biểu diễn tri thức là một bước ngoặc quan trọng trong việc thiết kế các hệ cơ sở tri thức và các hệ chuyên gia. Ngày nay, có nhiều phương pháp biểu diễn tri thức đã được đề xuất và ứng dụng. Tri thức là một hệ chuyên gia được biểu diễn theo nhiều phương pháp khác nhau. Tùy theo hệ chuyên gia người ta sử dụng một hoặc đồng thời cả nhiều phương pháp. Mục tiêu chính biểu diễn tri thức trong máy tính là phục vụ cho việc thu nhận tri thức vào máy tính, truy xuất tri thức và thực hiện các phép suy luận dựa trên những tri thức đã lưu trữ. Tuy có nhiều phương pháp biểu diễn tri thức tùy theo từng trường hợp, ta nên chọn phương pháp nào cho phù hợp. Biểu diễn tri thức được ứng dụng nhiều trong các bài toán thực tế, nó có đến hàng trăm giải thuật. Trong bài tiểu luận này em xin trình bày sơ lược về các phương pháp biểu diễn tri thức và ứng dụng nó để giải quyết bài toán chơi cờ caro. Qua đây, em xin gửi lời cảm ơn sâu să ́ c đến PGS.TS. Đỗ Văn Nhơn, người đã tận tâm truyền đạt những kiến thức nền tảng cơ bản cho chúng em về môn học “Biểu diễn tri thức và ứng dụng”. Bên cạnh đó cũng không thể không nhắc đến công lao trợ giúp không mệt mỏi của các chuyên gia cố vấn qua mạng thuộc Trung tâm phát triển CNTT – ĐH Quốc gia TP.HCM và toàn thể các bạn bè học viên cùng lớp. 2 Chương 1 TỔNG QUAN VỀ BIỂU DIỄN TRI THỨC VÀ GIẢI TOÁN DỰA TRÊN TRI THỨC 1.1. Khái niệm tri thức Tri thức không có định nghĩa chính xác bởi tri thức là một khái niệm trừu tượng. Tuy nhiên vì phải tập hợp và xử lý được “tri thức” bằng máy tính nên ta cố gắng đưa ra định nghĩa về tri thức càng hình thức càng tốt. - Khái niệm: Tri thức là sự hiểu biết về một lĩnh vực của vấn đề. - Lĩnh vực: Miền chủ đề được chú trọng. - Tri thức: Thường bao gồm các khái niệm, các loại sự kiện, các luật. Ví dụ: + Kiến thức về y học và khả năng chuẩn đoán bệnh là tri thức. + Biết một tam giác có các yếu tố nào cùng với các công thức liên quan giữa các yếu tố là tri thức. + Biết các dạng cấu trúc dữ liệu thường dùng trong lập trình cùng với các thuật toán xử lý cơ bản trên các cấu trúc là tri thức. 1.2. Khám niệm về biểu diễn tri thức Biểu diễn tri thức (Knowledge Representation) là sự diễn đạt và thể hiện của tri thức dưới những dạng thích hợp để có thể tổ chức một hệ cơ sở tri thức của hệ thống. Trong tin học biểu diển tri thức là một phương pháp mã hóa tri thức sao cho máy tính có thể xử lí được chúng. Cũng như dữ liệu có nhiều cách khác nhau để biểu diễn tri thức trong máy tính. Tuy nhiên ta phải chọn một phương pháp nào phù hợp để đưa lên máy tính. Các công cụ cho việc biểu diễn tri thức đơn giản như: + Các cấu trúc dữ liệu cơ bản: Dãy danh sách, tập hợp, mẫu… + Các cấu trúc dữ liệu trừu tượng: ngăn xếp, hàng đợi. + Các mô hình toán học: đồ thị, cây… + Các mô hình đối tượng. + Các ngôn ngữ đặc tả tri thức. Ví dụ: Kiến thức về một hình chữ nhật cần thiết cho việc giải bài toán có thể được biểu diễn gồm: 3 + Một tập hợp các biến thực, mỗi biến đại diện cho một yếu tố của hình chữ nhật như chiều dài, chiều rộng. + Một tập hợp các công thức liên quan đến tính toán trên các yếu tố của hình chữ nhật. 1.3. Các dạng tri thức - Tri thức mô tả: Các khái niệm, các đối tượng cơ bản. - Tri thức cấu trúc: Các khái niện cấu trúc, các quan hệ, các đối tương phức hợp,… - Tri thức thủ tục: Các luật dẫn, các thủ tục xử lý, các chiến lược,… - Tri thức meta: tri thức về các dạng tri thức khác và cách sử dụng chúng. 4 Chương 2 CẤU TRÚC CỦA HỆ GIẢI TOÁN DỰA TRÊN TRI THỨC 2.1. Cấu trúc hệ thống Cấu trúc của hệ giải toán thông minh Các thành phần chính của hệ thống trong việc giải toán tổng quát trong một miền tri thức: - Bộ suy diễn tri thức (Knowledge Base): Đây là trái tim của hệ thống, trong đó chứa các kiến thức cần thiết trong việc giải các bài toán. - Bộ suy diễn hay mô tả suy diễn: Bộ suy diễn áp dụng kiến thức được lưu trữ trong cơ sở tri thức để giải quyết hay tìm lời giải cho bài toán đặt ra. Sự tách biệt của bộ suy diễn và một cơ sở tri thức là sự tách biệt quan trọng: Sự tách biệt: tính độc lập tương đối giữa các cơ sở tri thức và bộ suy diễn. Cần có sự tách biệt này vì: a. Việc biểu diễn tri thức được thực hiện một cách tự nhiên hơn, gần gũi hơn với quan niệm của con người. b. Các nhà thiết kế sẽ tập trung vào việc nắm bắt và tổ chức cơ sở tri thức hơn là phải đi vào những chi tiết cài đặt trên máy tính. c. Giúp tăng cường tính mô-đun hóa của phần cơ sở tri thức, bộ suy diễn và bộ phận cập nhật, hiệu chỉnh kiến thức. Sự bổ sung hay loại bỏ một phần kiến thức sẽ không gây ra các hiệu ứng lề các thành phần cho hệ thống. d. Cho phép cùng một chiến lược điều khiển và giao tiếp có thể được sử dụng cho nhiều hệ thống khác nhau. 5 e. Sự tách biệt của kiến thức giải bài toán và bộ suy diễn còn giúp ta có thể thử nghiệm nhiều chiến lượt điều khiển khác nhau trên cùng một cơ sở tri thức. 2.2. Vấn đề biểu diễn tri thức Biểu diễn tri thức đóng vai trò quan trọng trong thiết kế và xây dựng một hệ giải toán thông minh và các hệ chuyên gia. Phương pháp biểu diễn tri thức thích hợp sẽ tạo nên một hệ thống có trái tim khỏe mạnh. Xây dựng và phát triển các phương pháp biểu diễn tri thức và một hướng nghiên cứu quan trọng trong các nhà nghiên cứu Trí tuệ nhân tạo. Suy diễn tự động để giải quyết các bài toán dựa trên tri thức cũng là một vấn đề rất quan trọng. Các phương pháp suy diễn tự động nhằm vận dụng kiến thức đã biết trong quá trình lập luận giải quyết vấn đề, trong đó quan trọng nhất là các chiến lược điều khiển giúp phát sinh các sự kiện mới từ các sự kiện đã có. Xây dựng và phát triển các phương pháp biểu diễn tri thức là một hướng nghiên cứu quan trọng cho các nhà nghiên cứu về Trí tuệ nhân tạo. 6 Chương 3 PHƯƠNG PHÁP BIỂU DIỄN TRI THỨC 3.1. Các phương pháp biểu diễn tri thức 3.1.1. Biểu diễn dựa trên logic hình thức Sử dụng các biểu thức logic hình thức trong hệ thống logic để diễn đạt các sự kiện và các luật trong cơ sở tri thức. Phép tính logic vị từ cấp 1 được sử dụng phổ biến nhất và cả một ngôn ngữ lập trình hỗ trợ cho phương pháp này. Đó là ngôn ngữ lập trình PROLOG. Trong ngôn ngữ PROLOG chỉ cần khai báo sự kiện và các luật. Hệ thống sẽ thực hiện giải quyết vấn đề được yêu cầu dựa trên tri thức được khai báo. 3.1.2. Hệ luật dẫn Mỗi luật dẫn được phát biểu dưới dạng: If<giả thiết> then <kết luận> Mô hình: Một cách hình thức, hệ luật dẫn gồm: - Tập kí hiệu đại diện cho các sự kiện. - Tập dẫn trong đó <giả thiết> và <kết luận> là các tập sự kiện. Nhận xét: Mô hình hệ luật dẫn trên khó áp dụng trực tiếp vì quan niệm sự kiện khá đơn giản. 3.1.3. Mạng ngữ nghĩa Mạng ngữ nghĩa (semantic network) có dạng đồ thị gồm các nút và các cung, trong đó: - Các nút thể hiện các khái niệm, các đối tượng. - Các cung thễ hiện các quan hệ giữa các đối tượng. Dựa trên mạng ngữ nghĩa ta nhận biết tri thức một cách trực quan giúp thiết kế các xử lý như: thêm/ bớt các khái niệm hay các đối tượng, tìm kiếm thông tin. Nhận xét: Mô hình khá trừu tượng và khái quát, trong áp dụng phải phát triển các mô hình tri thức cụ thể hơn. 3.1.4. Các khung Các khung (frame) thể hiện các khái niệm dưới dạng các cấu trúc mẫu tin các hình thức như một bảng mẫu. Khung cơ bản: Gồm các thành phần cơ bản sau: - Tên đối tượng (loại khung) 7 - Các thuộc tính - Giá trị các thuộc tính Khung lớp: Thể hiện các tính chất tổng quát của một lớp các đối tượng với những quan hệ kế thừa và cấu trúc phân cấp. 3.2. Suy diễn tự động 3.2.1. Khái niệm suy diễn tự động Suy diễn nhằm vận dụng kiến thức đã biết trong quá trình lập luận giải quyết vấn đề, trong đó quan trọng nhất là các chiến lược điều khiển giúp phát sinh những sự kiện mới từ các sự kiện đã có. Suy diễn tự động: Quá trình suy diễn được thuật giải hóa và có thể cài đặt thành chương trình máy tính. Các kỹ thuật suy diễn cơ bản: - Suy diễn tiến. - Suy diễn lùi. 3.2.2. Hợp giải trong tri thức dạng logic Phương pháp: Thực hiện quá trình phát sinh sự kiện mới bằng cách sử dụng các luật suy diễn cơ bản trên các biểu thức logic như: Modus Ponens, Modus Tollens, tam đoạn luận. Trong logic vị từ: Quá trình hợp giải có thể được cài đặt dựa trên kỹ thuật hợp nhất, PROLOG là một ngôn ngữ lập trình được thiết kế với chức năng suy diễn theo phương pháp này. Hợp giải trong tri thức dạng logic: - Phương pháp: Thực hiện quá trình phát sinh sự kiện mới bằng cách sử dụng các luật suy diễn cơ bản trên các biểu thức logic như: Modus Ponens, Modus Tollens, tam đoạn luận. - Trong logic vị từ: Quá trình hợp giải có thể được cài đặt dựa trên kỹ thuật hợp nhất (unification) và quay lui (backtracking). - PROLOG là một ngôn ngữ lập trình được thiết kế với chức năng suy diễn theo phương pháp này. 3.2.3. Suy diễn tiến Phương pháp: Suy dẫn từ giả thiết đi đến kết luận. Chiến lược này được bắt đầu bằng tập sự kiện đã biết, rút ra các sự kiện mới nhờ dùng các luật mà phần giả thiết khớp với sự