Giải thuật tìm kiếm Minimax và ứng dụng trong các trò chơi có tổng bằng không

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------(--(--(------ NGUYỄN THỊ LỆ GIẢI THUẬT TÌM KIẾM MINIMAX VÀ ỨNG DỤNG TRONG CÁC TRÒ CHƠI CÓ TỔNG BẰNG KHÔNG Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số: 60.46.35 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN THỊ HỒNG MINH Hà Nội - 2009 Mục lục LỜI NÓI ĐẦU 3 CHƯƠNG 1: TỔNG QUAN VỀ CÁC VẤN ĐỀ TÌM KIẾM 5 1.1 Bài toán tìm kiếm và không gian trạng thái 5 1.1.1 Bài toán tìm kiếm 5 1.1.2 Không gian tìm kiếm 7 1.2 Các kỹ thuật tìm kiếm cơ bản 10 1.2.1 Tìm kiếm không có thông tin 11 1.2.2 Tìm kiếm có thông tin 14 1.2.3 Tìm kiếm đối kháng 15 CHƯƠNG 2: GIẢI THUẬT TÌM KIẾM MINIMAX 20 2.1 Giới thiệu 20 2.1.1 Trò chơi có tổng bằng không (Zero-sum-game) 21 2.1.2 Định lý Minimax 26 2.2 Giải thuật Minimax 27 2.2.1 Ý tưởng 27 2.2.2 Áp dụng giải thuật Minimax đến độ sâu lớp cố định 31 2.2.3 Thủ tục Minimax 33 2.2.4 Đánh giá 38 2.3 Giải thuật cải tiến Alpha-beta 38 2.3.1 Ý tưởng 40 2.3.2 Giải thuật 42 2.3.3 Đánh giá 44 2.4 So sánh giải thuật Minimax và giải thuật Alpha-beta. 47 CHƯƠNG 3: ỨNG DỤNG 50 3.1 Phân tích bài toán 50 3.1.1 Trò chơi 50 3.1.2 Cơ sở lý thuyết 52 3.2 Cài đặt chương trình 52 3.2.1 Cấu trúc chương trình và mối quan hệ giữa các lớp chính 52 3.2.2 Lớp Form1 54 3.2.3 Lớp CBoard 54 3.2.4 Lớp gameAI 55 3.3 Một số giao diện và kết quả chạy chương trình 66 KẾT LUẬN 70 Tài liệu tham khảo 71 LỜI NÓI ĐẦU Lý thuyết trò chơi (game theory) thường được coi là một nhánh của toán học ứng dụng và kinh tế học ứng dụng nhằm nghiên cứu về các tình huống trong đó các bên tham gia trò chơi áp dụng những chiến lược ra quyết định nhằm tối ưu hóa kết quả mình nhận được. Ban đầu Lý thuyết trò chơi được phát triển như một công cụ để nghiên cứu hành vi kinh tế học, ngày nay Lý thuyết này được sử dụng trong nhiều ngành khoa học như Sinh học, Triết học, Chính trị học… Đặc biệt Lý thuyết trò chơi đã thu hút được sự chú ý của các nhà Khoa học máy tính do ứng dụng của nó trong Trí tuệ nhân tạo và Điều khiển học. Trí tuệ nhân tạo đã vận dụng Lý thuyết trò chơi để nghiên cứu về các trò chơi đối kháng và thiết kế chương trình chơi cờ giữa Người và Máy tính. Do bùng nổ tổ hợp quá lớn của cây trò chơi mà cả người và máy không thể (và không bao giờ) có thể tìm kiếm vét cạn (hết mọi khả năng). Do đó phương pháp tìm kiếm duy nhất là chỉ tìm kiếm đến một độ sâu giới hạn nào đó và chọn nước đi dẫn đến một thế cờ có lợi nhất cho mình. Do phải tính cả khả năng chống trả của đối phương nên ta không dùng được các thuật toán tìm kiếm thông thường mà phải dùng một thuật toán tìm kiếm riêng cho cây trò chơi, đó là thuật toán theo chiến lược Minimax. Đây cũng là chiến lược hiệu quả áp dụng trong các trò chơi có tổng bằng không. Chúng ta đều biết, nhiều tình huống trong thực tế đặc biệt là trong lĩnh vực Kinh tế, Chính trị có thể nhìn nhận như một trò chơi có tổng bằng không. Do đó việc nghiên cứu chiến lược tìm kiếm nước đi cho dạng trò chơi này có thể mang lại những ý nghĩa thực tiễn nhất định. Nội dung của luận văn tìm hiểu và nghiên cứu về thuật toán tìm kiếm đối kháng Minimax, các cải tiến của nó và ứng dụng trong trò chơi có tổng bằng không. Nội dung bản luận văn được chia làm 3 chương: Chương 1 trình bày một cách tổng quan về các vấn đề tìm kiếm : bài toán tìm kiếm, biểu diễn vấn đề bằng không gian trạng thái và các kỹ thuật tìm kiếm cơ bản. Chương 2 trình bày giải thuật tìm kiếm Minimax và giải thuật cải tiến Alpha-beta áp dụng cho các trò chơi với tổng bằng không. Mỗi giải thuật được trình bày gồm các nội dung: ý tưởng, thủ tục thực hiện giải thuật và đánh giá. Chương 3 trình bày một ứng dụng của thuật toán tìm kiếm Minimax áp dụng cho trò chơi xếp các quân hậu lên bàn cờ có chướng ngại vật. Trong thời gian học tập và nghiên cứu để hoàn thành luận văn này, tác giả đã nhận được sự quan tâm, hướng dẫn, đóng góp của các thầy cô, các bạn bè và người thân. Trước hết, tác giả xin được dành lời cảm ơn chân thành và lòng biết ơn sâu sắc nhất tới giáo viên hướng dẫn của mình là Tiến sĩ Nguyễn Thị Hồng Minh, người đã định hướng, gợi mở những ý tưởng sâu sắc và hiệu quả, đã tận tình chỉ bảo giúp đỡ tác giả về mọi mặt để có thể hoàn thành nhiệm vụ nghiên cứu. Luận văn được thực hiện bằng những kiến thức mà tác giả được trang bị trong suốt 2 năm học tại Khoa Toán - Cơ - Tin, Trường Đại Học Khoa học tự nhiên với sự giảng dạy nhiệt tình của các giảng viên và sự hăng say học tập của các học viên. Lời cảm ơn chân thành xin được gửi tới các thầy, cô trong khoa Toán-Cơ-Tin học, đặc biệt các thầy cô trong bộ môn Tin học, các anh, chị và bạn bè trong cùng lớp cao học chuyên ngành Bảo đảm toán học cho máy tính và hệ thống tính toán khóa 2007-2009. Lời cảm ơn cuối cùng xin được dành cho gia đình và những bạn bè thân thiết, những người đã dành sự quan tâm và động viên hết mực để tác giả hoàn thành tốt bản luận văn này. Hà nội, tháng 10 năm 2009 CHƯƠNG 1: TỔNG QUAN VỀ CÁC VẤN ĐỀ TÌM KIẾM 1.1 Bài toán tìm kiếm và không gian trạng thái 1.1.1 Bài toán tìm kiếm Tìm kiếm luôn là thao tác nền móng cho rất nhiều tác vụ tính toán. Các bài toán tìm kiếm bao gồm việc tìm cách tốt nhất để thu được thông tin cần cho một quyết định. Mỗi bài toán bất kỳ đều chứa trong đó một bài toán con tìm kiếm theo một chiều hướng nào đó, các tình huống tồn tại ở đó việc tìm kiếm cần phải xử lý là: kiểm tra các tài khoản, thanh tra và điều khiển chất lượng… Một cách tổng quát, tìm kiếm có thể hiểu là tìm một hoặc một số đối tượng thỏa mãn những đòi hỏi nào đó trong tập hợp rộng lớn các đối tượng. Chúng ta có thể kể ra rất nhiều vấn đề mà việc giải quyết nó được quy về vấn đề tìm kiếm. Trong các trò chơi, chẳng hạn cờ vua, cờ caro vấn đề tìm kiếm được thể hiện ở chỗ trong số rất nhiều nước đi được phép thực hiện, ta phải tìm ra các nước đi dẫn tới tình thế có ưu thế thắng. Chứng minh định lý cũng có thể xem như vấn đề tìm kiếm. Có nhiều phát biểu bài toán tìm kiếm khác nhau. Trong phần này chúng ta xem xét một số phát biểu của bài toán tìm kiếm như sau: Trong lý thuyết tính toán, một bài toán tìm kiếm là một loại bài toán tính toán được biểu diễn bởi một quan hệ nhị phân. Nếu R là một quan hệ nhị phân sao cho field(R)
Γ+ và T là một máy Turing, thì T tính f nếu: Nếu mỗi x có một số giá trị y mà R(x,y) thì T truy nhập vào với đầu ra z mà R(x,z) ( có thể có nhiều y, và T chỉ cần một trong số chúng) Nếu với giá trị x mà không có giá trị y thỏa mãn R(x,y) thì T loại bỏ x. Chú ý rằng đồ thị của hàm bộ phận là một quan hệ nhị phân, và nếu T tính một hàm bộ phận thì hầu hết mọi giá trị có thể cho đầu ra. Một quan hệ R có thể được biểu diễn như một bài toán tìm kiếm, và một máy Turing tính R còn được gọi để giải quyết nó. Mọi bài toán tìm kiếm đều tương ứng với bài toán quyết định, cụ thể là: L(R) = { x |
yR(x,y)}. Tìm kiếm nghĩa là tìm một hay nhiều mẩu thông tin đã được lưu trữ. Thông thường, thông tin được chia thành các mẩu tin (record), mỗi mẩu tin đều có một KHÓA (key) dùng cho việc tìm kiếm. Ta sẽ luôn có một khoá cho trước giống như khoá của các mẩu tin mà ta cần tìm. Mỗi mẩu tin được tìm thấy sẽ chứa toàn bộ thông tin để cung cấp cho một quá trình xử lý nào đó. Việc tìm kiếm được áp dụng rất đa dạng và rộng rãi. Ví dụ: Một Ngân hàng nắm giữ tất cả thông tin của rất nhiều tài khoản khách hàng và cần tìm kiếm để kiểm tra các biến động. Một hãng Bảo hiểm hay một hệ thống trợ giúp bán vé xe, vé máy bay….Việc tìm kiếm thông tin để đáp ứng việc sắp đặt ghế và các yêu cầu tương tự như vậy là thực sự cần thiết. Một phát biểu Bài toán tìm kiếm thường được sử dụng nhất là: “Cho một bảng gồm n bản ghi R1, R2, …., Rn. Mỗi bản ghi Ri (1
i
n) tương ứng với 1 khóa ki. Hãy tìm bản ghi có giá trị khóa tương ứng bằng X cho trước. X được gọi là khóa tìm kiếm hay đối trị tìm kiếm. Công việc tìm kiếm sẽ hoàn thành khi có một trong hai tình huống sau đây xảy ra. Tìm được bản ghi có giá trị khóa tương ứng bằng X, lúc đó ta nói: phép tìm kiếm được thỏa (Successful). Không tìm được bản ghi nào có khóa bằng X cả: phép tìm kiếm không thỏa. (unsuccessful). Thuật ngữ thường được dùng trong việc mô tả cấu trúc dữ liệu của việc tìm kiếm là TỪ ĐIỂN và BẢNG KÝ HIỆU. Một ví dụ điển hình như ta muốn xây dựng hệ thống tra từ điển Tiếng Anh chẳng hạn. Ở đây, “khoá” là từ và “mẩu tin” là diễn giải cho từ đó, mỗi mẩu tin chứa định nghĩa, cách phát âm và các thông tin khác. BẢNG KÝ HIỆU chính là từ điển cho chương trình và các mẩu tin chứa thông tin mô tả đối tượng được đặt tên. Một cách tổng quát, bài toán tìm kiếm có thể được phát biểu dựa vào không gian trạng thái với bộ 4 (S, To, Op, TG) hoặc bộ 5: (S, T0, Op, TG,, Pcost). Trong đó: S là tập các trạng thái, T0 là trạng thái ban đầu, Op là tập các toán tử hay tập các phép chuyển trạng thái mà có thể chuyển một trạng thái này sang trạng thái khác, TG là trạng thái đích. Pcost là chi phí đường đi. Mục đích của bài toán là tìm ra cách chuyển từ trạng thái ban đầu sang trạng thái đích, nếu theo bộ 5 có thêm Pcost thì bài toán cần tìm nghiệm tốt nhất nghĩa là tìm cách chuyển từ trạng thái ban đầu đến trạng thái đích với chi phí nhỏ nhất (hoặc lớn nhất). Phát biểu chi tiết hơn của cách biểu diễn này chúng ta sẽ xét trong mục không gian tìm kiếm dưới đây. 1.1.2 Không gian tìm kiếm 1.1.2.1 Không gian tìm kiếm Khi muốn giải quyết một vấn đề nào đó bằng tìm kiếm, trước hết ta phải xác định không gian tìm kiếm. Không gian tìm kiếm bao gồm tất cả các đối tượng mà ta cần quan tâm để tìm ra trong đó đối tượng yêu cầu. Đó có thể là không gian liên tục, chẳng hạn không gian các véctơ thực n chiều; hoặc cũng có thể là không gian các đối tượng rời rạc như tập các nút của đồ thị hay tập các lời giải của bài toán [7].   Một cách chung nhất, nhiều bài toán phức tạp đều có dạng "tìm đường đi trong đồ thị" hay nói một cách hình thức hơn là "xuất phát từ một đỉnh của một đồ thị, tìm đường đi hiệu quả nhất đến một đỉnh nào đó". Một phát biểu khác thường gặp của dạng bài toán này là : Cho trước hai trạng thái T0 và TG hãy xây dựng chuỗi trạng thái T0, T1, T2, ..., Tn-1, Tn = TG sao cho :
thỏa mãn một điều kiện cho trước (thường là nhỏ nhất). Trong đó, Ti thuộc tập hợp S (gọi là không gian trạng thái – state space) bao gồm tất cả các trạng thái có thể có của bài toán và Pcost(Ti-1,Ti) là chi phí để biến đổi từ trạng thái Ti-1 sang trạng thái Ti. Tuy nhiên, từ một trạng thái Ti-1 ta có nhiều cách để biến đổi sang trạng thái Ti. Khi nói đến một biến đổi cụ thể từ Ti-1 sang Ti ta sẽ dùng thuật ngữ hướng đi (với ngụ ý nói về sự lựa chọn).
Hình 1.1: Mô hình chung của các vấn đề-bài toán phải giải quyết bằng phương pháp tìm kiếm lời giải. Không gian tìm kiếm là một tập hợp trạng thái - tập các nút của đồ thị. Chi phí cần thiết để chuyển từ trạng thái này sang trạng thái khác được biểu diễn dưới dạng các con số nằm trên cung nối giữa hai nút tượng trưng cho hai trạng thái. 1.1.2.2 Biểu diễn vấn đề trong không gian trạng thái Ta sẽ xét việc biểu diễn một vấn đề trong không gian trạng thái sao cho việc giải quyết vấn đề được quy về việc tìm kiếm trong không gian trạng thái. Một phạm vi rộng lớn các vấn đề, đặc biệt các câu đố, các trò chơi, có thể mô tả bằng cách sử dụng khái niệm trạng thái và phép chuyển trạng thái hay là phép chuyển (phép biến đổi trạng thái). Ví dụ: Trong trò chơi cờ vua, mỗi cách bố trí các quân trên bàn cờ là một trạng thái. Trạng thái ban đầu là sự sắp xếp các quân lúc đầu cuộc chơi. Mỗi nước đi hợp lệ là một phép chuyển trạng thái, nó biến đổi một trạng thái trên bàn cờ thành một trạng thái khác. Như vậy muốn biểu diễn một vấn đề trong không gian trạng thái, ta cần xác định các yếu tố sau: - Trạng thái ban đầu - Tập hợp các phép chuyển trạng thái. Trong đó mỗi toán tử hay phép chuyển mô tả một hành động hoặc một phép biến đổi có thể đưa một trạng thái tới một trạng thái khác. Tập hợp tất cả các trạng thái có thể đạt tới từ trạng thái ban đầu bằng cách áp dụng một dãy phép chuyển trạng thái, lập thành không gian trạng thái của bài toán. Ta sẽ ký hiệu không gian trạng thái là S, trạng thái ban đầu là T0 (T0
S). Mỗi phép chuyển R có thể xem như một ánh xạ R: S
S. Nói chung R là một ánh xạ không xác định khắp nơi trên S. - Một tập hợp TG các trạng thái kết thúc (trạng thái đích). TG là tập con của không gian S. Trong nhiều vấn đề (chẳng hạn các loại cờ) có thể có nhiều trạng thái đích và ta không thể xác định trước được các trạng thái đích. Nói chung trong phần lớn các vấn đề hay, ta chỉ có thể mô tả các trạng thái thỏa mãn một số điều kiện nào đó. Khi biểu diễn một vấn đề thông qua các trạng thái và các phép chuyển, thì việc tìm nghiệm của bài toán được quy về việc tìm đường đi từ trạng thái ban đầu tới trạng thái đích. (Một đường đi trong không gian trạng thái là một dãy phép chuyển dẫn một trạng thái tới một trạng thái khác). Chúng ta có thể biểu diễn không gian trạng thái bằng đồ thị định hướng, trong đó mỗi đỉnh đồ thị tương ứng với một trạng thái. Nếu có phép chuyển R biến đổi trạng thái u thành trạng thái v, thì có cung gán nhãn R đi từ đỉnh u tới đỉnh v. Khi đó một đường đi trong không gian trạng thái sẽ là một đường đi trong đồ thị. Sau đây chúng ta sẽ xem xét một ví dụ về không gian trạng thái được xây dựng cho bài toán 8 số. Ví dụ : Bài toán 8 số. Cho bảng 3x3 ô và tám quân mang số hiệu từ 1 đến 8, còn lại một ô trống. Mỗi quân ở cạnh ô trống có thể được chuyển dịch tới ô trống đó. Yêu cầu của bài toán là tìm ra một dãy các chuyển dịch để biến đổi trạng thái ban đầu của bảng (hình bên trái) thành một trạng thái xác định nào đó, chẳng hạn trạng thái trong hình bên phải. Xem hình minh họa dưới đây: Hình 1.2: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số. Trong bài toán này, trạng thái ban đầu là trạng thái ở bên trái hình, còn trạng thái kết thúc ở bên phải hình. Tương ứng với các quy tắc chuyển dịch các quân, ta có bốn phép chuyển: up (đẩy quân lên
), down (đẩy quân xuống
), left (đẩy quân sang trái
), right (đẩy quân sang phải
). Rõ ràng là, các phép chuyển này chỉ là các phép chuyển bộ phận; chẳng hạn, từ trạng thái ban đầu (hình bên trái), ta chỉ có thể áp dụng các phép chuyển down, left, right. Trong ví dụ trên việc tìm ra một biểu diễn thích hợp để mô tả các trạng thái của vấn đề là khá dễ dàng và tự nhiên. Song trong nhiều vấn đề việc tìm hiểu được biểu diễn thích hợp trong các trạng thái của vấn đề là hoàn toàn không đơn giản. Việc tìm ra dạng biểu diễn tốt cho các trạng thái đóng vai trò hết sức quan trọng trong quá trình giải quyết một vấn đề. Có thể nói rằng, nếu ta tìm được dạng biểu diễn tốt cho các trạng thái của vấn đề, thì vấn đề hầu như đã được giải quyết. 1.2 Các kỹ thuật tìm kiếm cơ bản Có nhiều kỹ thuật tìm kiếm khác nhau để giải quyết các bài toán tìm kiếm. Tuy nhiên với mỗi bài toán tùy theo đặc điểm, cách tổ chức dữ liệu mà ta có thể lựa chọn và áp dụng kỹ thuật phù hợp và hiệu quả. Chúng ta sẽ tìm hiểu về một số kỹ thuật tìm kiếm cơ bản trong các mục tiếp theo, bao gồm: Tìm kiếm không có thông tin, tìm kiếm có thông tin và tìm kiếm đối kháng. Trong đó, tập trung vào kỹ thuật tìm kiếm đối kháng để làm cơ sở cho phát triển chương 2 của luận văn này. 1.2.1 Tìm kiếm không có thông tin Một giải thuật tìm kiếm không có thông tin là giải thuật không tính đến bản chất cụ thể của bài toán. Khi đó, các giải thuật dạng này có thể được cài đặt tổng quát, và cùng một cài đặt có thể được sử dụng trong một diện rộng các bài toán (do sử dụng trừu tượng hóa). Nhược điểm của các giải thuật này là phần lớn các không gian tìm kiếm có kích thước cực kì lớn, và một quá trình tìm kiếm (đặc biệt tìm kiếm theo cây) sẽ cần một khoảng thời gian đáng kể cho các ví dụ nhỏ. Sau đây ta sẽ giới thiệu một số dạng tìm kiếm không có thông tin tiêu biểu ứng với các cách tổ chức dữ liệu. 1.2.1.1 Tìm kiếm trên danh sách Các giải thuật tìm kiếm trên danh sách là loại giải thuật tìm kiếm cơ bản nhất. Mục đích là tìm trong một tập hợp một phần tử chứa một khóa nào đó. Các giải thuật tìm kiếm tiêu biểu nhất trên danh sách là: Tìm kiếm tuần tự (hay tìm kiếm tuyến tính), tìm kiếm nhị phân. Tìm kiếm tuần tự kiểm tra từng phần tử trong danh sách theo thứ tự của danh sách đó. Nó có thời gian chạy khá lớn: O(n), trong đó n là số phần tử trong danh sách, nhưng có thể sử dụng cho một danh sách bất kỳ mà không cần tiền xử lý. Tìm kiếm nhị phân là một thuật toán cao cấp hơn so với thuật toán tìm kiếm tuần tự với thời gian chạy là O(log n). Đối với các danh sách lớn, thuật toán này tốt hơn hẳn tìm kiếm tuyến tính nhưng nó đòi hỏi danh sách phải được sắp xếp từ trước và đòi hỏi khả năng truy cập ngẫu nhiên. Thuật toán tìm kiếm nội suy tốt hơn so với thuật toán tìm kiếm nhị phân đối với danh sách rất lớn và với phân bố gần đều. Ngoài ra bảng băm (hash table) cũng được dùng cho tìm kiếm trên danh sách. Nó đòi hỏi thời gian hằng số trong trường hợp trung bình, nhưng lại cần nhiều chi phí về không gian bộ nhớ và thời gian chạy O(n) cho trường hợp xấu nhất. Một phương pháp tìm kiếm khác dựa trên các cấu trúc dữ liệu chuyên biệt sử dụng cây tìm kiếm nhị phân cân bằng (self-balancing binary search tree) và đòi hỏi thời gian chạy O(log n). Các giải thuật loại này có thể coi là mở rộng của tư tưởng chính về tìm kiếm nhị phân để cho phép chèn và xóa nhanh. 1.2.1.2 Tìm kiếm trên cây Tìm kiếm trên cây là trung tâm của các kỹ thuật tìm kiếm. Các thuật toán này tìm kiếm trên các cây gồm các nút, cây này có thể là cây tường minh hoặc được xây dựng dần trong quá trình tìm kiếm. Nguyên lý cơ bản là: một nút được lấy ra từ một cấu trúc dữ liệu, các nút con của nó được xem xét và bổ sung vào cấu trúc dữ liệu đó. Bằng cách thao tác trên cấu trúc dữ liệu này, cây tìm kiếm được duyệt theo các thứ tự khác nhau, chẳng hạn theo từng mức ( tìm kiếm theo chiều rộng) hoặc đi tới một nút lá trước rồi quay lui (tìm kiếm theo chiều sâu). Tìm kiếm theo chiều rộng Tìm kiếm chiều rộng mang hình ảnh của vết dầu loang. Từ trạng thái ban đầu, ta xây dựng tập hợp S bao gồm các trạng thái kế tiếp (mà từ trạng thái ban đầu có thể biến đổi thành). Sau đó, ứng với mỗi trạng thái Tk trong tập S, ta xây dựng tập Sk bao gồm các trạng thái kế tiếp của Tk rồi lần lượt bổ sung các Sk vào S. Quá trình này cứ lặp lại cho đến lúc S có chứa trạng thái kết thúc hoặc S không thay đổi sau khi đã bổ sung tất cả Sk.  Tìm kiếm theo chiều sâu Trong tìm kiếm theo chiều sâu, tại trạng thái (đỉnh) hiện hành, ta chọn một trạng thái kế tiếp (trong tập các trạng thái có thể biến đổi thành từ trạng thái hiện hành) làm trạng thái hiện hành cho đến lúc trạng thái hiện hành là trạng thái đích. Trong trường hợp tại trạng thái hiện hành, ta không thể biến đổi thành trạng thái kế tiếp thì ta sẽ quay lui (back-tracking) lại trạng thái trước trạng thái hiện hành (trạng thái biến đổi thành trạng thái hiện hành) để chọn đường khác. Nếu ở trạng thái trước này mà cũng không thể biến đổi được nữa thì ta quay lui lại trạng thái trước nữa và cứ thế. Nếu đã quay lui đến trạng thái khởi đầu mà vẫn thất bại thì kết luận là không có lời giải. Tìm kiếm chiều sâu và tìm kiếm chiều rộng đều là các phương pháp tìm kiếm có hệ thống và chắc chắn tìm ra lời giải. Tuy nhiên, do bản chất là vét cạn nên với những bài toán có không gian lớn thì ta không thể dùng hai chiến lược này được. Hơn nữa, hai chiến lược này đều có tính chất "mù quáng" vì chúng không chú ý đến những thông tin (tri thức) ở trạng thái hiện thời và thông tin về đích cần đạt tới cùng mối quan hệ giữa chúng. Các tri thức này vô cùng quan trọng và rất có ý nghĩa để thiết kế các giải thuật hiệu quả hơn. Do đó hai chiến lược trên được cải tiến thành một số thuật toán tìm kiếm mới trên cây bao gồm: tìm kiếm lặp sâu dần, tìm kiếm chiều sâu giới hạn, tìm kiếm hai chiều và tìm kiếm chi phí đều [7]. 1.2.1.3 Tìm kiếm trên đồ thị Nhiều dạng bài toán tìm kiếm cụ thể trên đồ thị như: Tìm đường đi ngắn nhất, tìm cây bao trùm nhỏ nhất, tìm bao đóng bắc cầu,…Tuy nhiên ứng