Luận văn 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 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 (1in) 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). TG T0 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 (T0S). Mỗi phép chuyển R có thể xem như một ánh xạ R: SS. 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: 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 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 với mỗi dạng bài toán có một số giải thuật tìm kiếm thích hợp để giải quyết. Chẳng hạn thuật toán Dijkstra, thuật toán Kruskal, giải thuật láng giềng gần nhất và giải thuật Prim [3]. Các thuật toán này có thể được coi là các mở rộng của các thuật toán tìm kiếm trên cây: tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng. Thuật toán Dijkstra là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm. Thuật toán này có thể tính toán tất cả các đường đi ngắn nhất từ một đỉnh xuất phát cho trước s tới mọi đỉnh khác mà không làm tăng thời gian chạy. Thuật toán Kruskal là thuật toán xây dựng cây bao trùm ngắn nhất bằng cách chọn thêm dần các cung vào cây. Thuật toán Prim: là thuật toán nhằm xây dựng cây bao trùm ngắn nhất. Tư tưởng của thuật giải Prim là chọn đưa dần vào cây T các đỉnh kề “tốt nhất” trong số các đỉnh còn lại. Thời gian thực hiện giải thuật Prim là O(n2). 1.2.2 Tìm kiếm có thông tin Các kỹ thuật tìm kiếm không có thông tin trong một số trường hợp rất kém hiệu quả và thậm chí không áp dụng được. Để tăng tốc độ của các quá trình tìm kiếm ta có thể dùng các giải thuật tìm kiếm có thông tin. Trong mục này chúng ta sẽ hệ thống một số chiến lược tìm kiếm có thông tin hay còn gọi là chiến lược tìm kiếm heuristic (tìm kiếm kinh nghiệm), đó là các phương pháp sử dụng hàm đánh giá để hướng dẫn sự tìm kiếm. Trong nhiều vấn đề, ta có thể sử dụng kinh nghiệm, tri thức của chúng ta về vấn đề để đánh giá các trạng thái của vấn đề. Với mỗi trạng thái u ta xác định một giá trị số h(u), số này đánh giá “sự gần đích” của trạng thái u. Hàm h(u) được gọi là hàm đánh giá. Trong tìm kiếm có thông tin người ta sử dụng hàm đánh giá này như một đánh giá heuristic đặc thù cho bài toán cần giải quyết với vai trò hướng dẫn cho quá trình tìm kiếm. Một cách đánh giá heuristic tốt sẽ làm cho quá trình tìm kiếm có thông tin hoạt động hiệu quả hơn hẳn một phương pháp tìm kiếm không có thông tin bất kỳ. Trong quá trình tìm kiếm, tại mỗi bước ta sẽ chọn trạng thái để phát triển là trạng thái có giá trị hàm đánh giá là nhỏ nhất, trạng thái này được xem là trạng thái có nhiều hứa hẹn nhất hướng tới đích. Các kỹ thuật tìm kiếm sử dụng hàm đánh giá để hướng dẫn sự tìm kiếm được gọi chung là các kỹ thuật tìm kiếm có thông tin hay tìm kiếm kinh nghiệm (tìm kiếm heuristic). Các giai đoạn cơ bản để giải quyết vấn đề bằng tìm kiếm heuristic như sau: Tìm biểu diễn thích hợp mô tả các trạng thái và các toán tử hay phép chuyển của vấn đề Xây dựng hàm đánh giá Thiết kế chiến lược chọn trạng thái để phát triển ở mỗi bước. Hai chiến lược tìm kiếm có thông tin quan trọng là tìm kiếm tốt nhất - đầu tiên (best-first-search) và tìm kiếm leo đồi (hill-climbing search). Tìm kiếm tốt nhất đầu tiên: là tìm kiếm theo chiều rộng được hướng dẫn bởi hàm đánh giá. Nhưng nó khác tìm kiếm theo chiều rộng ở chỗ, trong tìm kiếm theo chiều rộng ta lần lượt phát triển tất cả các đỉnh ở mức hiện tại để sinh các đỉnh ở mức tiếp theo, còn trong tìm kiếm tốt nhất - đầu tiên ta chọn đỉnh để phát triển là đỉnh tốt nhất được xác định bởi hàm đánh giá (tức là đỉnh có giá trị hàm đánh giá là nhỏ nhất), đỉnh này có thể ở mức hiện tại hoặc ở các mức trên. Thuật toán tìm kiếm leo đồi: thực chất là thuật toán tìm kiếm theo chiều sâu được hướng dẫn bởi hàm đánh giá. Song khác với tìm kiếm theo chiều sâu, khi ta phát triển một đỉnh u thì bước tiếp theo, ta chọn trong số các đỉnh con của u đỉnh có nhiều hứa hẹn nhất để phát triển, đỉnh này cũng được xác định bởi hàm đánh giá. 1.2.3 Tìm kiếm đối kháng Tìm kiếm đối kháng còn gọi là tìm kiếm có đối thủ là chiến lược tìm kiếm được áp dụng để tìm ra nước đi cho người chơi trong các trò chơi đối kháng. Chơi cờ có thể xem như vấn đề tìm kiếm trong không gian trạng thái. Sau đây chúng ta sẽ xem thế nào trò chơi đối kháng và chiến lược tìm kiếm nào sẽ được áp dụng. 1.2.3.1 Trò chơi đối kháng Trong các trò chơi đấu trí như các trò chơi cờ Vua, cờ Tướng, cờ vây, cờ caro (go-moku), có một cây trò chơi bao gồm tất cả các nước đi có thể của cả hai đấu thủ và các cấu hình bàn cờ là kết quả của các nước đi đó. Ta có thể tìm kiếm trên cây này để có được một chiến lược chơi hiệu quả. Các trò chơi này còn gọi là các trò chơi đối kháng, diễn ra giữa hai đấu thủ. Nói chung, các trò chơi đó đều có thể chuyển về một dạng bài toán tìm kiếm đặc biệt: tìm đường đi đến các điểm cao nhất giữa hai đấu thủ. Trong trò chơi này phải tính đến mọi nước đi mà đối thủ của ta có thể sử dụng. Đặc điểm của các trò chơi trên như sau: Có hai đấu thủ, mỗi người chỉ đi một nước khi tới lượt. Các đấu thủ đều biết mọi thông tin về tình trạng trận đấu. Trận đấu không kéo dài vô tận, phải diễn ra hòa, hoặc một bên thắng và bên kia thua. Thông thường các trò chơi này hay được gọi là các loại cờ, đôi khi còn được gọi là các trò chơi Minimax (dựa trên tên của thuật toán tìm kiếm cơ bản áp dụng cho chúng). Thuật toán áp dụng cho dạng bài toán này là thuật toán tìm kiếm Minimax ta sẽ trình bày chi tiết trong chương 2. 1.2.3.2 Cây trò chơi Các trạng thái bàn cờ khác nhau (hay còn gọi là một thế cờ, tình huống cờ) trong quá trình chơi có thể biểu diễn thành một cây tìm kiếm (được gọi là cây trò chơi - hình 1.3) và ta sẽ tiến hành tìm kiếm trên cây để tìm được nước đi tốt nhất. Cây trò chơi có các nút là các tình huống khác nhau của bàn cờ, các nhánh nối giữa các nút sẽ cho biết từ một tình huống bàn cờ chuyển sang tình huống khác thông qua chỉ một nước đi đơn nào đó. Tuy nhiên, các nước đi này diễn ra theo cặp do hai đấu thủ lần lượt tiến hành. Độ sâu của cây trò chơi là số tầng của cây. Thuật ngữ “nước đi” được thống nhất là một lần đi của một đấu thủ hoặc một lần đi phản ứng lại của đối thủ bên kia. Chú ý điều này khác với thói quen dùng trong thực tế một nước đi bao gồm lần đi của ta và một lần đi của đối thủ. Nói cách khác, nước đi ở đây thực chất chỉ là "nửa nước" theo cách hiểu của làng cờ. Hình 1.3: Cây trò chơi Trạng thái bàn cờ gốc (ply=0) Lượt “ta” đi Trạng thái bàn cờ mới (ply=1) Lượt đối phương đi Trạng thái bàn cờ mới (ply=2) Tóm lại: Cây trò chơi dùng các nút để thể hiện trạng thái của trò chơi. Cây này là một dạng của cây ngữ nghĩa, có các nhánh ứng với việc chuyển cấu hình sau một nước đi. Có thể xem hai nhánh xuất phát từ một nút là hai quyết định của hai đấu thủ [5]. Gọi p là số mức của cây thì độ sâu của cây là d= p-1. Mỗi lựa chọn hay bước chuyển là một nước đi. 1.2.3.3. Vét cạn Dùng một thuật toán vét cạn để tìm kiếm trên cây trò chơi dường như là một ý tưởng đơn giản. Ta chỉ cần chọn nhánh cây sẽ dẫn tới nước thắng để đi quân là đảm bảo thắng lợi. Nếu đúng vậy, các loại cờ sẽ trở thành các trò chơi buồn tẻ, và không còn đâu những bí quyết huyền ảo thần kì và bàn cờ sẽ chẳng khác gì bàn tính. Rất tiếc rằng, cách làm này lại không thể thực hiện được do có hiện tượng bùng nổ tổ hợp. Ví dụ, nếu từ một thế cờ, trung bình có khả năng đi được 16 nước đi khác nhau (ta gọi đó là hệ số nhánh con tại mỗi nút là b = 16). Như vậy, sau một tầng ta sẽ có 16 nút con, mỗi nút này lại có thể có 16 con nữa. Tổng số nút con ở độ sâu thứ hai là 16x16 = b2. Cứ như vậy ở độ sâu d sẽ có bd nút. Nếu giả sử độ sâu của cây là 100 (hệ số nhánh 16 và độ sâu 100 đều là những con số còn nhỏ hơn con số thường gặp trong trò chơi cờ), thì số nhánh phải duyệt lên đến 16100 hay xấp xỉ 10120 - một con số quá lớn. Vì số các khả năng tăng quá nhanh, chỉ có một số ít những vấn đề đơn giản là thích hợp với kiểu tìm kiếm vét hết mọi khả năng này (kiểu tìm kiếm vét cạn đòi hỏi phải kiểm tra tất cả các đỉnh). Do đó, các phương pháp tìm kiếm khác đã ra đời và phát triển. Ngược lại, nếu có một phương pháp luôn luôn chính xác nhằm đánh giá một thế cờ này là tốt hay kém so với thế kia, thì trò chơi trở thành đơn giản bằng cách chọn nước đi dẫn tới thế cờ tốt nhất. Do đó sẽ không cần phải tìm kiếm gì nữa. Rất tiếc, các thủ tục như vậy không hề có. Ta cần có chiến lược tìm kiếm trong trò chơi. b b*b=b2 d 1 bd Thời gian Số đỉnh Hàm mũ Hình 1.4: Cây tìm kiếm và sự bùng nổ tổ hợp 1.2.3.4 Chiến lược tìm kiếm trong trò chơi Trong Lý thuyết trò chơi đã nghiên cứu các tình huống chiến thuật trong đó các đối thủ lựa chọn các hành động khác nhau để cố gắng làm tối đa kết quả nhận được. Nói cách khác, Lý thuyết trò chơi nghiên cứu cách lựa chọn hành vi tối ưu khi chi phí và lợi ích của mỗi lựa chọn là không cố định mà phụ thuộc vào lựa chọn của các cá nhân khác. Một chiến lược thường được cả người lẫn máy dùng là phân tích thế cờ chỉ sau một số nước đi nào đó của cả hai bên. Sau khi "nhìn xa" xem bàn cờ có những khả năng biến đổi như thế nào sau một số nước, ta sẽ đánh giá độ xấu tốt của các thế cờ nhận được. Tiếp theo, ta sẽ chọn nước đi sẽ dẫn tới một thế cờ tốt nhất trong số đó có cân nhắc đến cách đi của cả hai bên. Với máy, thế cờ này được đánh giá là tốt hơn thế cờ kia nhờ so sánh điểm của thế cờ đó do bộ lượng giá trả lại. Chúng ta chỉ có khả năng xét trước một số hữu hạn các nước (ví dụ đại kiện tướng chơi cờ vua có thể xét trước 8-10 nước đi, người thường chỉ 2-4 nước đi). Rõ ràng là nếu xét càng sâu thì chơi càng giỏi. Nhưng không thể thực hiện điều này với độ sâu quá lớn được, do số nút ở độ sâu đó có thể trở nên rất lớn và không đủ thời gian để phân tích. Nếu dừng ở một độ sâu hợp lý thì bộ phân tích có thể hoàn thành việc tính toán trong một thời gian hạn định. Để nghiên cứu chiến lược cụ thể được áp dụng trong các trò chơi đối kháng chúng ta sẽ tìm hiểu trong chương 2. CHƯƠNG 2: GIẢI THUẬT TÌM KIẾM MINIMAX 2.1 Giới thiệu Thuật toán Minimax là thuật toán tìm kiếm chuyên dùng để trả về chuỗi nước đi tối ưu cho một người chơi trong trò chơi có tổng bằng không [8]. Minimax (còn gọi là minmax) là một phương pháp trong lý thuyết quyết định có mục đích là tối thiểu hóa (minimize) tổn thất vốn được dự tính có thể là tối đa (maximize). Có thể hiểu ngược lại là, nó nhằm tối đa hóa lợi ích vốn được dự tính là tối thiểu (maximin). Thuật toán này cũng được mở rộng cho nhiều trò chơi phức tạp hơn và giúp đưa ra các quyết định chung khi có sự hiện diện của sự không chắc chắn. Một phiên bản của giải thuật áp dụng cho các trò chơi như tic-tac-toe, khi mà mỗi người chơi có thể thắng, thua, hoặc hòa. Nếu người chơi A có thể thắng trong một nước đi, thì "nước đi tốt nhất" chính là nước đi để dẫn đến kết quả thắng đó. Nếu người B biết rằng có một nước đi mà dẫn đến tình huống người A có thể thắng ngay ở nước đi tiếp theo, trong khi nước đi khác thì sẽ dẫn đến tình huống mà người chơi A chỉ có thể tốt nhất là hòa thì nước đi tốt nhất của người B chính là nước đi sau. Ta sẽ nắm rõ, thế nào là một nước đi "tốt nhất". Giải thuật Minimax giúp tìm ra nước đi tốt nhất, bằng cách đi ngược từ cuối trò chơi trở về đầu. Tại mỗi bước, nó sẽ ước định rằng người A đang cố gắng tối đa hóa cơ hội thắng của A khi đến phiên anh ta, còn ở nước đi kế tiếp thì người chơi B cố gắng để tổi thiểu hóa cơ hội thắng của người A (nghĩa là tối đa hóa cơ hội thắng của B). Lý thuyết trò chơi coi trò chơi là sự kết hợp hoặc trao đổi giữa hai hay nhiều đối thủ ở đó mỗi đối thủ cố gắng lựa chọn tối ưu hành động (hay nước đi) của mình nhằm đạt được lợi ích tối đa. Trong lý thuyết trò chơi có một cách phân loại các trò chơi thành hai loại: trò chơi có tổng bằng không và trò chơi có tổng khác không. Trong những trò chơi có tổng khác không, lợi ích thu được của người chơi này không nhất thiết dẫn tới sự mất mát của người chơi kia. Các tình huống này tồn tại với điều kiện tổng kết quả (mà người thắng được hưởng) không bị giới hạn hay cố định. Về bản chất đây là trường hợp kiến tạo kết quả thay vì chia sẻ kết quả giữa các đối thủ. Chẳng hạn như khi nghe hoà nhạc, người ta không phải thích một bản hoà tấu vì người khác không thích nghe. Việc ai đó không thích nghe chẳng có ảnh hưởng gì tới sở thích của bạn trong điều kiện bạn không phải nghe lời bình luận của người đó . Trong luận văn này trò chơi có tổng bằng không, cụ thể là trò chơi có tổng bằng không với hai người chơi sẽ được quan tâm nghiên cứu kỹ hơn. 2.1.1 Trò chơi có tổng bằng không (Zero-sum-game) Trò chơi có tổng bằng không là trò chơi có tổng giá trị kết quả (mà người thắng được hưởng) là cố định. Bất cứ bên nào thắng (+1) cũng làm cho bên kia thua cuộc (-1), tương ứng với tình huống ganh đua thuần tuý, cuối cùng dẫn tới tổng (+1- 1) = 0. Cờ vua là một trò chơi có tổng bằng không bởi không thể có trường hợp cả hai bên đều thắng hoặc đều thua. Nếu một bên thắng thì bên kia nhất định là thua và ngược lại [8]. Thể thao là những ví dụ điển hình nhất của trò chơi có tổng bằng không. Nhà vô địch chỉ có thể đạt được vinh quang khi toàn bộ các đối thủ khác đều thua cuộc. Trong một giải bóng đá tổng số trận thắng luôn bằng tổng số trận thua cũng là bởi cái tính chất tổng bằng không ấy [11]. Việc đầu tư kinh doanh chứng khoán cũng chính là một trò chơi có tổng bằng không, bởi vì ở đó, số tiền thua lỗ của nhà đầu tư này sẽ là tiền lãi của nhà đầu tư khác. Nhà đầu tư có thể mất trắng hoặc thắng lớn, lợi nhuận mà anh ta thu được có thể đổi bằng cả gia tài, đôi khi mạng sống của những nhà đầu tư tài chính khác. Mô hình toán học của trò chơi có tổng bằng không với hai người chơi [11][10]. Có hai người chơi, P1 và P2. P1 có một tập m chiến lược thuần túy A={a1, a2,…, am}, P2 có một tập n chiến lược thuần túy B={b1, b2, …, bn}. Mỗi người chơi sẽ được lợi với mỗi cặp (ai, bj) của chiến lược. Lợi nhuận của P1 ký hiệu là U1(ai , bj) và lợi nhuận của P2 ký hiệu là U2(ai, bj). Vì đây là trò chơi có tổng bằng không nên U1(ai, bj)= -U2(ai, bj) với mọi i và j. Để đơn giản ta ký hiệu lợi nhuận của trò chơi là M(ai, bj)= abs(U1(ai, bj)). Lợi nhuận thu được khi dùng chiến lược hỗn hợp Mỗi người chơi có thể dùng chiến thuật hỗn hợp bằng việc tạo ra một hàm mật độ và việc chơi mỗi chiến lược thuần túy với một xác suất cố định. Ký hiệu pi là xác suất mà người chơi 1 sẽ chơi ai vàlà xác suất mà người chơi 2 chọn bj. Vì p và q là xác suất nên chúng phải thỏa mãn: (a) i 0, j 0. (b) Một chiến thuật hỗn hợp dùng một hàm mật độ cụ thể được ký hiệu là p=ở đó pi= Pr(ai) là xác suất mà được chơi, tương tự, với người chơi 2 hàm mật độ q= ở đó = Pr(bj) là xác suất mà bj được chơi. Với mỗi cặp chiến thuật ngẫu nhiênlợi nhuận (kết cục) được định nghĩa là: Ta ký hiệu lợi nhuận do người chơi 1 dùng chiến lược thuần túy ai và người chơi 2 dùng chiến lược hỗn hợp q là: Tương tự ta cũng có công thức của M(p, bj) M(p, bj)= Ở đây chiến lược thuần túy và chiến lược hỗn hợp được hiểu như sau: - Chiến lược thuần tuý (Pure Strategy): Là chiến lược dựa trên phán đoán các chiến lược của đối thủ. - Chiến lược hỗn hợp (Mixed Strategy): Là chiến lược khi không dự đoán được chiến lược của đối thủ. Sự đảm bảo cực đại (Maximum Security) Ta dùng P và Q để ký hiệu lần lượt là tập tất cả các chiến lược hỗn hợp sẵn có của người chơi 1 và người chơi 2. Mục đích của người chơi 1 là để chọn một chiến lược ngẫu nhiên p từ P sao cho cực đại M(p,q). Cùng thời điểm đó, mục đích của người chơi 2 là chọn một chiến lược ngẫu nhiên q từ Q sao cho cực đại lợi ích của nó, nghĩa là làm cực tiểu M(p, q). Các luật chơi yêu cầu mỗi người chơi chọn chiến lược của mình một cách hoàn hảo bỏ qua sự lựa chọn của đối thủ. Mỗi chiến lược hỗn hợp p thuộc P, mức độ đảm bảo của người chơi 1 được định nghĩa là: v1(p)= . Bởi vì là tổng trọng số của n lợi ích M(p,bj), giá trị M( p,q) này đạt cực tiểu khi tất cả các giá trị M(p,bj) được gán bằng giá trị nhỏ nhất của chúng, ta ký hiệu giá trị nhỏ nhất này là v1(p) và được xác định như sau: v1(p)= min[M(p, b1), M(p, b2),…, M(p,bn)]. Có thể coi v1(p) là lợi nhuận của người chơi 1 sẽ nhận được nếu người chơi 2 biết người chơi 1 sẽ chọn chiến lược p. (Bởi vì nếu người chơi 2 biết điều này thì sẽ chọn chiến lược tốt hơn để đáp lại). Ta có thể định nghĩa v2(q) cho người chơi 2 một cách tương tự. (Nhưng dùng cực đại thay vì cực tiểu). v2(p)= max[M(a1, q), M(a2, q),…, M(am , q)]. - Theo giả thiết, người chơi 1 muốn cực đại mức độ đảm bảo của nó, vì vậy người chơi 1 phải chọn một chiến lược p* sao cho: v1(p*)v1(p) pP. Ký hiệu v1 là mức độ đảm bảo cực đại thì v1(p*)= v1= (1) Với tất cả các chiến lược hỗn hợp, ta biết rằng: v1= (2) Bất đẳng thức (1) có nghĩa là chiến lược mà cho lợi nhuận v1 là chiến lược mạnh hơn tất cả các chiến lược khác. Bất đẳng thức (2) nghĩa là v1 là giá trị thấp nhất (lợi nhuận cực tiểu) mà người chơi 1 có thể nhận được khi chơi chiến lược p*, nếu người chơi 2 không chọn chiến lược khôn ngoan thì người chơi 1 sẽ nhận được lợi lớn hơn v1. Nếu người chơi 1 không chơi chiến lược p* thì người chơi 1 có thể nhận được lợi nhuận thấp hơn v1. Chiến lược p* được gọi là chiến lược Maximin. Sự tổn thất cực tiểu Bởi vì trò chơi có tổng bằng không, nên khi người chơi 2 cực đại mức độ đảm bảo của nó thì lợi nhuận của người chơi 1 sẽ đạt cực tiểu. Nếu người chơi 2 dùng chiến lược q thì người chơi 1 không thể nhận được một giá trị lớn hơn. v2(q)= Giá trị v2 đôi lúc được gọi là tổn thất. Người chơi 1 cố gắng để cực đại mức đảm bảo, người chơi 2 cố gắng cực tiểu tổn thất. Vì vậy người chơi 2 muốn cực tiểu tổn thất của nó, thì người chơi 2 phải chọn một chiến lược q* sao cho: v2= v2(q*)v2(q) qQ. (3) Lặp lại phân tích mà ta đã làm với người chơi 1 nhưng với người chơi 2 ta có: v2 M(p,q*) pP. (4) Chiến lược q* được gọi là chiến lược Minimax. Mối quan hệ giữa giá trị cực đại và giá trị cực tiểu - Nếu người chơi 1 dùng chiến lược Maximin, nó đảm bảo lợi ích tối thiểu là v1 . v1(p) v1 M(p*,q) qQ Tương tự, nếu người chơi 2 dùng chiến lược Minimax, nó đảm bảo tổn thất không lớn hơn v2, nghĩa là tương đương với việc đảm bảo người chơi 1 có thể nhận được lợi nhuận không lớn hơn v2. M(p, q*) v2 v2(p*) p P Vì vậy: M(p, q*) v2 p P M(p*,q*) v2 v1 M(p*,q) qQ v1 M(p*,q*) v1 v2 (5) Giá trị cân bằng (Equilibrium Value) Trước hết chúng ta cần xem lại một số khái niệm cơ bản về cân bằng trong Lý thuyết trò chơi: - Cân bằng (Equilibrium): Là một kết quả (outcome) mà trong đó các bên tham gia cuộc chơi không muốn thay đổi. - Cân bằng Nash: là một khái niệm trong Lý thuyết trò chơi, được John Nash đưa ra với mô hình trò chơi với n đối thủ. Cân bằng Nash xác định một chiến lược tối ưu cho các trò chơi khi chưa có điều kiện tối ưu nào được xác định trước đó. Nội dung cơ bản của khái niệm cân bằng Nash là: Nếu tồn tại một tập hợp các chiến lược cho một trò chơi với đặc tính là không một đối thủ nào có thể hưởng lợi bằng cách thay đổi chiến lược hiện tại của mình khi các đối thủ khác không thay đổi, tập hợp các chiến lược đó và phần thu nhận tương ứng tạo nên cân bằng Nash. Nói cách khác, cân bằng Nash đạt được nếu như thay đổi một cách đơn phương của bất cứ ai trong số các đối thủ cũng sẽ làm cho chính người đó thu lợi ít hơn mức có được với chiến lược hiện tại. Khái niệm này áp dụng cho những trò chơi gồm từ hai đối thủ trở lên và Nash đã chỉ ra rằng tất cả các khái niệm khác nhau về giải pháp trong các trò chơi được đưa ra trước đó đều có cân bằng Nash. Vì mối quan hệ giữa giá trị cực đại và giá trị cực tiểu đã được thiết lập, chúng ta có thể định nghĩa một giá trị cân bằng của trò chơi. Một cặp chiến lược (p’,q’) được gọi là cân bằng nếu p’ tương xứng tốt với q’ và ngược lại q’ tương xứng tốt với p’ , nghĩa là: M( p,q’) M( p’,q’) M( p’,q). Định lý Minimax Định lý: Với trò chơi có tổng bằng không và có hai người chơi, một trong 3 điều kiện sau đây sẽ dẫn đến 2 điều kiện còn lại. Tồn tại một cặp cân bằng. Tồn tại một số thực v, một chiến lược hỗn hợp p* và một chiến lược hỗn hợp q* sao cho: (a) với j= 1, 2,…, n (b) với i= 1, 2,…, m Điều kiện (3a) nói rằng tổn thất trung bình cho người chơi 2 dùng chiến lược thuần túy bất kỳ nào không nhỏ hơn v. Tương tự điều kiện (3b) nói tổn thất trung bình của người chơi 1 dùng chiến thuật thuần túy bất kỳ thì không lớn hơn v. Trong định lý Minimax, von Neumann (1928) chứng minh sự tồn tại tổng quát của các nghiệm Minimax trong các chiến lược ngẫu nhiên hóa cho các trò chơi hữu hạn bước, hai người chơi và tổng bằng không. Với các trò chơi này, định lý Minimax tương đương về mặt lô-gíc với sự tồn tại của cân bằng Nash. Định lý Minimax còn được phát biểu như sau: Với mọi trò chơi có tổng bằng không với hai người chơi thì luôn tồn tại một chiến lược cân bằng. Phần chứng minh định lý này có thể xem trong tài liệu tham khảo số [10]. Từ đặc điểm của trò chơi có tổng bằng không với hai người chơi (Zero-sum-game) và từ định lý Minimax nên thuật toán Minimax thích hợp với loại trò chơi này. Và đảm bảo khi thuật toán ứng dụng cho các trò chơi này sẽ chắc chắn có lời giải. 2.2 Giải thuật Minimax Xét một trò chơi đối kháng trong đó hai người thay phiên nhau đi nước của mình như cờ vua, cờ tướng, cờ carô,... Trò chơi có một trạng thái bắt đầu và mỗi nước đi sẽ biến đổi trạng thái hiện hành thành một trạng thái mới. Trò chơi sẽ kết thúc theo một quy định nào đó, theo đó thì cuộc chơi sẽ dẫn đến một trạng thái phản ánh có một người thắng cuộc hoặc một trạng thái mà cả hai đấu thủ không thể phát triển được nước đi của mình, ta gọi nó là trạng thái hòa cờ. Ta tìm cách phân tích xem từ một trạng thái nào đó sẽ dẫn đến đấu thủ nào sẽ thắng với điều kiện cả hai đấu thủ đều có trình độ như nhau. 2.2.1 Ý tưởng Hai đối thủ trong một trò chơi được gọi là MIN và MAX. MAX đại diện cho đối thủ quyết giành thắng lợi hay cố gắng tối đa hóa ưu thế của mình. Ngược lại MIN là đối thủ cố gắng tối thiểu hóa điểm số của MAX. Ta giả thiết MIN cũng dùng cùng những thông tin như MAX. Một trò chơi như vậy có thể được biểu diễn bởi một cây trò chơi. Mỗi một nút của cây biểu diễn cho một trạng thái. Nút gốc biểu diễn cho trạng thái bắt đầu của cuộc chơi. Mỗi nút lá biểu diễn cho một trạng thái kết thúc của trò chơi (trạng thái thắng, thua hoặc hòa). Nếu trạng thái x được biểu diễn bởi nút n thì các con của n biểu diễn cho tất cả các trạng thái kết quả của các nước đi có thể xuất phát từ trạng thái x. Do hai đấu thủ luân phiên nhau đi nước của mình nên các mức (lớp) trên cây trò chơi cũng luân phiên nhau là MAX và MIN. Cây trò chơi vì thế còn có tên là cây MIN-MAX. Trên cây trò chơi các nút ứng với trạng thái mà từ đó người chơi MAX chọn nước đi sẽ thuộc lớp MAX, các nút ứng với trạng thái mà từ đó người chơi MIN chọn nước đi sẽ thuộc lớp MIN. Chiến lược minimax thể hiện qua quy tắc định trị cho các nút trên cây trò chơi như sau: - Nếu nút là nút lá gán cho nút đó một giá trị để phản ánh trạng thái thắng thua hay hòa của các đấu thủ. - Sử dụng giá trị của các nút lá để xác định giá trị của các nút ở các mức trên trong cây trò chơi theo quy tắc: + Nút thuộc lớp MAX thì gán cho nó giá trị lớn nhất của các nút con của nút đó. + Nút thuộc lớp MIN thì gán cho nó giá trị nhỏ nhất của các nút con của nút đó. Giá trị được gán cho từng trạng thái theo quy tắc trên chỉ rõ giá trị của trạng thái tốt nhất mà mỗi đối thủ có thể hy vọng đạt được. Người chơi sẽ sử dụng các giá trị này để lựa chọn các nước đi cho mình. Đối với người chơi MAX khi đến lượt đi, người chơi này sẽ chọn nước đi ứng với trạng thái có giá trị cao nhất trong các trạng thái con, còn với người chơi MIN khi đến lượt sẽ chọn nước đi ứng với trạng thái có giá trị nhỏ nhất trong các trạng thái con. Ví dụ 1: Xét trò chơi carô có 9 ô (Tic tac toe). Hai người MAX và MIN thay phiên nhau đi X hoặc O (MAX đi X, MIN đi O). Người nào đi được 3 ô thẳng hàng (ngang, dọc, xiên) thì thắng cuộc. Nếu đã hết ô đi mà chưa phân thắng bại thì hai đấu thủ hòa nhau. Một phần của trò chơi này được biểu diễn bởi cây sau: MAX đi X 1 X X X O O O MAX đi X X X X O O X O X X X X O O O X X X X O O O 1 -1 0 MIN đi O 0 X X X X O O O O X X O X O O X O X O X X O O X O X O X X X O O O 1 0 -1 MAX đi X 0 0 1 MIN đi O X O X X X O O X O X O X X X O O X O X X X O X O O X O Hình 2.1. Một phần cây trò chơi trong trò chơi tic-tac-toe. 1 nếu tại đó người đi X đã thắng -1 nếu tại đó người đi X đã thua 0 nếu hai đấu thủ đã hòa nhau Trong cây trò chơi trên, các nút lá được tô nền và viền khung đôi để dễ phân biệt với các nút khác. Ta có thể gán cho mỗi nút lá một giá trị để phản ánh trạng thái thắng thua hay hòa của các đấu thủ. Chẳng hạn ta gán cho nút lá các giá trị như sau: Như vậy từ một trạng thái bất kỳ, đến lượt mình, người đi X sẽ chọn cho mình một nước đi sao cho dẫn đến trạng thái có giá trị lớn nhất (trong trường hợp này là 1). Ta nói X chọn nước đi MAX, nút mà từ đó X chọn nước đi của mình được gọi là nút MAX. Người đi O đến lượt mình sẽ chọn một nước đi sao cho dẫn đến trạng thái có giá trị nhỏ nhất (trong trường hợp này là -1, khi đó X sẽ thua và do đó O sẽ thắng). Ta nói O chọn nước đi MIN, nút mà từ đó O chọn nước đi của mình được gọi là nút MIN. Áp dụng chiến lược Minimax cho một nhánh trong cây trò chơi của trò chơi Tic-tac-toe ta có giá trị (phía trên mỗi nút) của các nút được thể hiện trong hình 2.1. 7 1 6-1 1 5-2 1 4-3 1 5-1-1 0 4-2-1 1 3-2-2 0 3-3-1 1 4-1-1-1 0 3-2-1-1 1 2-2-2-1 0 3-1-1-1-1 0 2-2-1-1-1 1 2-1-1-1-1-1 0 MAX MIN MAX MAX MIN MIN Ví dụ 2: Xét trò chơi Nim. Để chơi Nim, một số token (vật biểu hiện như đồng xu, lá bài, mảnh gỗ…) được đặt trên bàn giữa hai đối thủ. Ở mỗi nước đi, người chơi phải chia đống token thành hai đống nhỏ có số lượng khác nhau. Người chơi nào đến lượt mà không chia được là thua cuộc. Ứng với một token vừa phải, không gian trạng thái này có thể triển khai đến cùng. Hình sau biểu diễn không gian trạng thái của trò chơi có 7 token: Hình 2.2: Không gian trạng thái của trò chơi Nim. Khi chơi các trò chơi khó có thể triển khai hết không gian trạng thái, khó khăn chủ yếu là phải tính toán phản ứng của đối thủ. Một cách xử lý đơn giản nhất là giả sử đối thủ của chúng ta cũng sử dụng kiến thức về không gian trạng thái giống như chúng ta và áp dụng kiến thức đó kiên định để thắng cuộc. Mặc dù giả thiết này có những hạn chế của nó nhưng nó cũng cho chúng ta một cơ sở hợp lý để dự đoán hành vi của đối thủ. Giải thuật Minimax sẽ tìm kiếm không gian của trò chơi này theo giả thiết đó. Áp dụng chiến lược Minimax, chúng ta đánh dấu luân phiên từng mức trong không gian tìm kiếm phù hợp với đối thủ có nước đi ở mức đó. Trong ví dụ trên, MIN được quyền đi trước, từng nút lá được gán giá trị 1 hay 0 tùy theo kết quả đó là thắng cuộc đối với MAX hay MIN. Kết quả của việc áp dụng Minimax vào đồ thị không gian trạng thái đối với trò chơi Nim được thể hiện như hình trên. Vì tất cả các nước đi đầu tiên có thể xảy ra cho MIN sẽ dẫn đến các nút có giá trị 1 nên đối thủ MAX luôn có thể bắt trò chơi giành thắng lợi cho mình bất kể nước đi đầu tiên của MIN là như thế nào (đường đi thắng lợi của MAX được cho theo mũi tên đậm). 2.2.2 Áp dụng giải thuật Minimax đến độ sâu lớp cố định Khi áp dụng Minimax cho các trò chơi phức tạp, hiếm khi có khả năng mở rộng đồ thị không gian trạng thái đến các nút lá. Thay vào đó không gian trạng thái này chỉ có thể được triển khai đến một số mức xác định phụ thuộc tiềm năng về thời gian và bộ nhớ chẳng hạn. Chiến lược này được gọi là tính trước n nước đi (n –move lookahead). Vì giá trị các nút trong đồ thị con này không phải là trạng thái kết thúc của trò chơi nên chúng không phản ánh giá trị thắng cuộc hay thua cuộc. Chúng chỉ có thể được gán một giá trị phù hợp với một hàm đánh giá heuristic nào đó. Giá trị được truyền ngược về nút gốc không cung cấp thông tin thắng cuộc hay thua cuộc mà chỉ là giá trị heuristic của trạng thái tốt nhất có thể tiếp cận sau n nước đi kể từ nút xuất phát. Việc tính trước này sẽ làm tăng hiệu quả của heuristic vì nó được áp dụng vào một phạm vi lớn hơn trong không gian trạng thái. Minimax sẽ hợp nhất tất cả các giá trị của các nút con cháu của một trạng thái thành một giá trị duy nhất cho trạng thái đó. Trong các cây trò chơi được tìm kiếm bằng mức hay lớp (ply), MAX và MIN luân phiên nhau chọn các nước đi. Mỗi nước đi của một đối thủ sẽ xác định một lớp mới trên cây. Các chương trình trò chơi nói chung đều dự tính trước một độ sâu lớp cố định (thường được xác định bằng các giới hạn về không gian hoặc thời gian của máy tính). Các trạng thái trên mức đó được đánh giá theo các heuristic và các giá trị này sẽ được truyền ngược lên bằng thủ tục Minimax, sau đó thuật toán tìm kiếm sẽ dùng các giá trị vừa nhận được để chọn lựa một nước trong số các nước đi kế tiếp. Bằng cách tối đa hóa cho các cha mẹ MAX và tối thiểu hóa cho các cha mẹ MIN, những giá trị này đi lùi theo đồ thị đến con của trạng thái hiện hành. Sau đó trạng thái hiện hành dùng chúng để tiến hành lựa chọn trong các con của nó [8]. MIN MAX 2 3 3 3 9 0 0 7 2 2 6 3 9 5 7 0 4 2 1 5 6 MAX MIN Hình 2.3: Minimax đối với không gian trạng thái giả 6-5=1 6 - 4= 2 X O 6-6= 0 6-6= 0 4-6= -2 5-6= -1 5-6= -1 X O X X O X 1 1 5 - 4= 1 X O X O X O X O X O X O X O X X O X O 5-5=0 6-5= 1 5-5=0 4-5= -1 -2 -1 Nút MAX Nước đi của MAX Hình 2.4: Minimax hai lớp được áp dụng vào nước đi mở đầu trò chơi Tic-tac-toe. Ở đây sử dụng một heuristic phức tạp hơn, nó cố đo mức độ tranh chấp trong trò chơi. Heuristic chọn một trạng thái cần đo, tính tất cả các đường thắng mở ra cho MAX, rồi trừ đi tổng số các đường thắng mở ra cho MIN. Giải thuật tìm kiếm sẽ cố gắng tối đa hóa sự chênh lệch (hiệu số) đó. Nếu có một trạng thái bắt buộc thắng cuộc cho MAX, nó sẽ được đánh giá là + ∞, còn với trạng thái bắt buộc thắng cuộc cho MIN thì được đánh giá là - ∞. 2.2.3 Thủ tục Minimax Giả sử chúng ta có một bộ phân tích thế cờ có thể áp dụng tất cả các luật, các phương pháp đánh cờ khác nhau vào từng thế cờ và chuyển đổi chúng thành một con số đại diện (cho điểm thế cờ). Mặt khác, ta giả sử con số đó là dương khi áp dụng cho thế cờ của một đấu thủ (được gọi là người chơi cực đại – người chơi MAX), và là âm khi áp dụng cho đấu thủ bên kia (được gọi là người chơi cực tiểu – người chơi MIN). Quá trình tính toán cho điểm thế cờ được gọi là lượng giá tĩnh (static evaluation). Hàm thực hiện việc tính toán được gọi là một bộ lượng giá tĩnh và giá trị nhận được gọi là điểm lượng giá tĩnh. Cả hai đấu thủ đều cố gắng đi như thế nào đó để đạt được điểm tuyệt đối lớn nhất. Người chơi cực đại (MAX) sẽ tìm những nước đi dẫn đến điểm của mình trở nên lớn hơn (hay cao nhất có thể được) hay điểm của đối thủ bớt âm hơn (nhỏ hơn về giá trị tuyệt đối). Còn đấu thủ của anh ta, người chơi cực tiểu (MIN), lại ra sức phản kháng lại, để dẫn tới điểm âm của anh ta âm hơn hay điểm dương của đối thủ nhỏ đi (Hình 2.3). Độ sâu xem xét Đường tìm kiếm- chuỗi nước đi dẫn đến thế cờ tốt nhất có thể đạt được … Các bàn cờ trung gian, phải biến đổi qua chúng trong quá trình đạt đến các bàn cờ đích, không cần so sánh chúng. Nước chọn đi Các bàn cờ đích, ta phải so sánh chúng với nhau để cân nhắc hơn thiệt do nước đi mang lại. Hình 2.5:Minh họa chiến lược chơi cờ của người lẫn máy. Các nút trắng là các thế cờ trung gian phải trải qua để đến được các thế cờ đích. Không cần phải xét đến độ tốt xấu của các thế cờ trung gian. Các nút đen là các thế cờ đích và phải xem xét độ tốt xấu để so sánh chúng với nhau. Từ đó sẽ tìm ra đường đi để đến thế cờ tốt nhất có thể được (chú ý không là thế cờ tốt nhất trong số đó do phải xem xét cả cách đi chống trả của đối phương). Từ ý tưởng ta có thể suy ra các bước của thuật toán Minimax như sau: - Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm tức nút lá), tính giá trị tĩnh của thế cờ hiện tại ứng với người chơi ở đó. Ghi nhớ kết quả - Nếu như mức đang xét là của người chơi cực tiểu (nút MIN), áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả nhỏ nhất. - Nếu như mức đang xét là của người chơi cực đại (nút MAX), áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả lớn nhất. Từ ý tưởng phân tích trên ta có thể xây dựng thủ tục Minimax như sau: Hàm Minimax nhận vào một thế cờ pos và trả về giá trị của thế cờ đó. Nếu thế cờ pos tương ứng với nút lá trong cây trò chơi thì trả về giá trị đã được gán cho nút lá. Ngược lại ta cho pos một giá trị tạm value là -∞ hoặc ∞ tùy thuộc pos là nút MAX hay MIN và xét các thế cờ con của pos. Sau khi một con của pos có giá trị V thì đặt lại value= max(value, V) nếu n là nút MAX và value= min(value,V) nếu n là nút MIN. Khi tất cả các con của n đã được xét thì giá trị tạm value của pos trở thành giá trị của nó. (INFINITY thể hiện cho giá trị vô cùng) [15]. Ta có giả mã cho giải thuật Minimax như sau: function Minimax(pos): integer; value, best : integer; begin if pos là nút lá then return eval(pos) else begin {Khởi tạo giá trị tạm cho best } if pos là nút MAX then best:= -INFINITY else best := INFINITY; {hàm genPos sinh ra mọi nước đi từ thế cờ pos} genPos(pos); {Xét tất cả các con của pos, mỗi lần xác định được giá trị của một nút con, ta phải đặt lại giá trị tạm value. Khi đã xét hết tất cả các con thì value là giá trị của n} while (còn lấy được một nước đi m) do begin pos := Tính thế cờ mới nhờ đi m; value = Minimax(pos); if pos là nút MAX then if (value > best) then best := value; if pos là nút MIN then if (value < best) then best := value; end; Minimax := best; end; end; Xem xét đoạn chương trình trên ta thấy: - Có hai hàm mới là hàm eval(pos) và hàm genPos(pos). Hàm eval(pos) thực hiện việc tính giá trị (lượng giá) của thế cờ pos. Hàm genPos(pos) sinh ra tất cả các nước đi có thể từ thế cờ pos hiện tại. Việc xây dựng hai hàm này sẽ phụ thuộc vào từng trò chơi cụ thể. Hàm đánh giá Eval ứng với mỗi trạng thái (thế cờ) pos của trò chơi với một giá trị số Eval(pos). Giá trị này là sự đánh giá độ lợi thế của trạng thái pos. Trạng thái pos càng thuận lợi cho MAX thì Eval(pos) là số dương càng lớn, pos càng thuật lợi cho MIN thì eval(pos) là số âm càng nhỏ, Eval(pos) 0 đối với trạng thái không lợi thế cho ai cả. Chất lượng của chương trình chơi cờ phụ thuộc rất nhiều vào hàm đánh giá. Nếu hàm đánh giá cho ta sự đánh giá không chính xác về các trạng thái, nó có thể hướng ta đi tới trạng thái được xem là tốt, nhưng thực tế lại rất lợi cho ta. Thiết kế một hàm đánh tốt là một việc khó. Đòi hỏi ta phải quan tâm đến nhiều nhân tố. Ở đây có sự mâu thuẫn giữa độ chính xác của hàm đánh giá và thời gian tính của nó. Hàm đánh giá chính xác sẽ đòi hỏi rất nhiều thời gian tính toán, mà người chơi lại bị giới hạn bởi thời gian phải đưa ra nước đi. Trong chương 3 ta sẽ xem xét chi tiết hàm Eval và hàm GenPos. Như chúng ta đã biết, không phải lúc nào cũng đến được tận các nút lá. Đặc biệt trong các trò chơi cờ, bị giới hạn thời gian suy nghĩ của mỗi đối thủ đồng thời số nút và độ sâu của cây trò chơi là rất lớn. Chúng ta khó có thể thực hiện tìm kiếm đến độ sâu của các nút lá. Vì vậy, chúng ta chỉ thực hiện tìm đến một độ sâu depth cố định nào đó. Độ sâu depth càng lớn, hàm tìm kiếm càng gần giá trị tối ưu, cũng có nghĩa là “trình độ suy nghĩ” của máy càng cao! Như vậy, hàm Minimax bây giờ sẽ có lời gọi: Minimax(pos, depth) trong đó depth là độ sâu tìm kiếm. Thông thường, để cho tiện (và cũng rất gần thực tế) ta coi cả hai người chơi có cùng cách đánh giá về một thế cờ. Có điều thế cờ này là tốt với một người thì phải được đánh giá là tồi với người kia và ngược lại. Trong máy tính cách thể hiện tốt nhất là ta cho điểm một thế cờ có thêm dấu âm dương: dấu dương dành cho người chơi cực đại và dấu âm cho người chơi cực tiểu. Với người chơi cực đại sẽ mong muốn điểm này càng dương càng tốt, còn người chơi cực tiểu lại mong muốn điểm này càng âm càng tốt. Do đó để dễ xử lí ta sẽ tuỳ theo mức người chơi mà đổi dấu giá trị đánh giá thế cờ pos. Chú ý rằng, thay đổi độ sâu là chuyển sang đối phương nên phải đổi dấu. Chương trình thực hiện đổi dấu như sau: value:= -Minimax (pos, depth-1); {Tính điểm của pos} Do dùng cùng hàm lượng giá nên khi đến lượt, người chơi cực đại và cực tiểu có cùng cái nhìn như nhau về một thế cờ. Điều này dẫn đến có thể dùng cùng cách chọn nước đi tốt nhất cho họ. Vậy ta phát triển hàm Minimax thành dạng sau [15]: function Minimax (pos, depth): integer; begin if (depth = 0) or (pos là nút lá) then Minimax := Eval (pos) { Tính giá trị thế cờ pos } else begin best := -INFINITY; genPos(pos); { Sinh ra mọi nước đi từ thế cờ pos } while còn lấy được một nước đi m do begin pos := Tính thế cờ mới nhờ đi m; value := -Minimax (pos, depth - 1); if value > best then best := value; end; Minimax := best; end; end; - Trong cài đặt, bàn cờ được biểu diễn bằng các biến toàn cục. Do đó thay cho truyền tham số là một bàn cờ mới pos vào thủ thục Minimax thì người ta biến đổi luôn biến toàn cục này nhờ thực hiện nước đi "thử" (nước đi dẫn đến bàn cờ mới pos). Sau khi Minimax thực hiện việc tính toán dựa vào bàn cờ lưu ở biến toàn cục thì thuật toán sẽ dùng một số thủ tục để loại bỏ nước đi này. Như vậy Minimax bỏ các tham số pos như sau: function Minimax(depth): integer; begin if (depth = 0) or (pos là nút lá) then Minimax := Eval { Tính giá trị thế cờ pos } else begin best := -INFINITY;  genPos; { Sinh ra mọi nước đi từ thế cờ pos } while còn lấy được một nước đi m do begin thực hiện nước đi m; value := -Minimax (depth - 1); bỏ thực hiện nước đi m; if value > best then best := value; end;  Minimax := best; end; end; 2.2.4 Đánh giá Thuật toán Minimax thăm toàn bộ cây trò chơi bằng việc dùng chiến lược tìm kiếm theo chiều sâu. Nên độ phức tạp của thuật toán này tương ứng trực tiếp với kích thước không gian tìm kiếm bd, trong đó b là hệ số phân nhánh của cây hay chính là nước đi hợp pháp tại mỗi điểm, d là độ sâu tối đa của cây. Thuật toán sẽ thăm tất cả các nút không chỉ là các nút lá vì vậy số lượng các nút được thăm sẽ là b(bd-1)/(b-1). Nhưng hàm lượng giá sẽ là phương thức chi phối hầu hết thời gian và chỉ làm việc trên các nút lá, vì vậy việc thăm các nút không phải các nút lá có thể bỏ qua [8]. Do đó độ phức tạp thời gian là O(bd). Bản chất của thuật toán là tìm kiếm theo chiều sâu, vì vậy việc đòi hỏi không gian bộ nhớ của nó chỉ tuyến tính với d và b. Vì thế độ phức tạp không gian là O(bd) [8][13]. Nếu hệ số nhánh trung bình của cây là b = 40, và tìm kiếm đến độ sâu d = 4 (các con số thường gặp trong trò chơi cờ) thì số nút phải lượng giá là 404 = 2560000 (trên 2 triệu rưỡi nút). Còn với b = 40, d = 5 thì số nút phải lượng giá sẽ tăng 40 lần nữa thành 405 = 102400000 (trên 102 triệu nút), đây là con số tương đối lớn. Có thể tiết kiệm được nhiều thời gian bằng việc dùng các thuật toán tìm kiếm thông minh hơn như thuật toán Alpha-beta, thuật toán này không thăm tất cả các nút lá mà vẫn cho kết quả đúng với thuật toán Minimax [9]. Trong phần tiếp theo ta sẽ xét thuật toán cải tiến này. 2.3 Giải thuật cải tiến Alpha-beta Thuật toán Minimax yêu cầu phải có sự phân tích qua hai bước đối với không gian tìm kiếm: bước đầu truyền xuống đến độ sâu của lớp áp dụng heuristic và bước sau để truyền ngược các giá trị trên cây. Minimax lần theo tất cả các nhánh trong không gian bao gồm cả những nhánh mà một thuật toán thông minh hơn có thể bỏ qua hay tỉa bớt. Các nhà nghiên cứu trong lĩnh vực chơi game đã xây dựng một kỹ thuật tìm kiếm gọi là cắt tỉa Alpha-beta nhằm nâng cao hiệu quả tìm kiếm trong các bài toán trò chơi hai đối thủ [9]. Bộ đánh giá tĩnh trong thủ tục Minimax cần được thực hiện đối với tất cả các nút tại mức cuối của cây trò chơi (nút lá). Ta có thể giảm bớt số tính toán tốn kém này bằng cách giảm số nhánh cây cần tạo ra và số các đánh giá tĩnh cần tính ra. Do vậy một giải pháp như đã dùng trong thủ tục nhánh và biên là không tiếp tục đi theo các đường không tốt. Mức cực đại Mức cực tiểu Mức cực đại 2 7 Mức cực đại Mức cực tiểu Mức cực đại 2 7 =2 =2 2 1 1 Mức cực đại Mức cực tiểu Mức cực đại 2 7 =2 2 Thuật toán Alpha-beta là một cải tiến của thuật toán Minimax nhằm tỉa bớt nhánh của cây trò chơi, làm giảm số lượng nút phải sinh và lượng giá, do đó có thể tăng độ sâu của cây tìm kiếm [9]. Giả sử hình sau là một thế cờ mà hai nút đầu tiên đã được lượng giá. Nếu thực hiện thủ tục Minimax đối với các nút đó sẽ cho thấy người chơi cực đại đã được đảm bảo nếu đi nước bên trái sẽ được ít nhất là 2 điểm dù là các lượng giá của các nút khác cho kết quả như thế nào đi nữa. Hình 2.6: Thuật toán Alpha-beta cắt tỉa nhánh Bây giờ, ta lại giả sử nút tiếp theo được lượng giá và cho kết quả là 1. Nếu đi vào nhánh này thì đối phương sẽ đảm bảo làm điểm của người chơi cực đại không thể vượt quá được giá trị 1 dù là các lượng giá của các nút khác cho kết quả như thế nào đi nữa. Do đó đến đây, nước đi tốt nhất là chọn nước đi bên trái với đảm bảo là ít nhất đạt được 2 điểm. Và do đó, hoàn toàn không cần thiết phải lượng giá nút còn lại. 2.3.1 Ý tưởng Ý tưởng của tìm kiếm Alpha-beta rất đơn giản: Thay vì nếu như tìm kiếm toàn bộ không gian đến một độ sâu lớp cố định, tìm kiếm Alpha-beta thực hiện theo kiểu tìm kiếm sâu. Có hai giá trị, gọi là alpha và beta được tạo ra trong quá trình tìm kiếm: - Giá trị alpha liên quan với các nút MAX và có khuynh hướng không bao giờ giảm. - Ngược lại giá trị beta liên quan đến các nút MIN và có khuynh hướng không bao giờ tăng. Giả sử có giá trị alpha của một nút MAX là 6, MAX không cần phải xem xét giá trị truyền ngược nào nhỏ hơn hoặc bằng 6 có liên quan với một nút MIN nào đó bên dưới. Giá trị alpha là giá trị thấp nhất mà MAX có thể nhận được sau khi cho rằng MIN cũng sẽ nhận giá trị tốt nhất của nó. Tương tự nếu MIN có giá trị beta là 6 nó cũng không cần xem xét các nút nằm dưới nó có giá trị lớn hơn hoặc bằng 6. Để bắt đầu thuật toán tìm kiếm Alpha-beta, ta đi xuống hết độ sâu lớp theo kiểu tìm kiếm sâu, đồng thời áp dụng đánh giá heuristic cho một trạng thái và tất cả các trạng thái anh em của nó. Giả thuyết tất cả đều là nút MIN. Giá trị tối đa của các nút MIN này sẽ được truyền ngược lên cho nút cha mẹ (là một nút MAX). Sau đó giá trị này được gán cho ông bà của các nút MIN như là một giá trị beta kết thúc tốt nhất. Tiếp theo thuật toán này sẽ đi xuống các nút cháu khác và kết thúc việc tìm kiếm đối với nút cha mẹ của chúng nếu gặp bất kỳ một giá trị nào lớn hơn hoặc bằng giá trị beta này. Quá trình này gọi là cắt tỉa Beta (β cut). Cách làm tương tự cũng được thực hiện cho việc cắt tỉa Alpha (α cut) đối với các nút cháu của một nút MAX. Hai luật cắt tỉa dựa trên các giá trị alpha và beta là: Quá trình tìm kiếm có thể kết thúc bên dưới một nút MIN nào có giá trị beta nhỏ hơn hoặc bằng giá trị alpha của một nút cha MAX bất kỳ của nó. 2. Quá trình tìm kiếm có thể kết thúc bên dưới một nút MAX nào có giá trị alpha lớn hơn hoặc bằng giá trị beta của một nút cha MIN bất kỳ của nó. Việc cắt tỉa Alpha-beta như vậy thể hiện quan hệ giữa các nút ở lớp n và các nút ở lớp n+2 và do quan hệ đó toàn bộ các cây con bắt nguồn ở lớp n+1 đều có thể loại khỏi việc xem xét. Chú ý rằng giá trị truyền ngược thu được hoàn toàn giống như kết quả Minimax, đồng thời tiết kiệm được các bước tìm kiếm một cách đáng kể. Nguyên tắc Alpha-beta: Nếu biết điều đó thật sự tồi thì đừng mất thời gian tìm hiểu nó sẽ tồi tệ đến đâu. Ý tưởng này được gọi là nguyên tắc Alpha-beta do nó dùng trong thủ tục Alpha-beta (ta sẽ xét dưới đây). Hai tham số của thủ tục này được gọi là alpha và beta được dùng để theo dõi các triển vọng - chúng cho biết các giá trị nằm ngoài khoảng [alpha, beta] là các điểm "thật sự tồi" và không cần phải xem xét nữa. Khoảng [alpha, beta] còn được gọi là cửa sổ alpha, beta. Trong ngữ cảnh của các trò chơi, nguyên tắc Alpha-beta nói rằng, mỗi khi xem xét một nút bất kì, nên kiểm tra các thông tin đã biết về các nút cha, ông của nó. Có thể do có đủ thông tin từ cha, ông nên không cần phải làm bất cứ việc gì nữa cho nút này. Do đó, nguyên tắc này cũng giúp chỉnh sửa hoặc xác định chính xác giá trị tại nút cha, ông nó [5]. Như trên nói, một cách để tiện theo dõi quá trình tính toán là dùng các tham số alpha và beta để ghi lại các thông tin theo dõi cần thiết. Thủ tục Alpha-beta được bắt đầu tại nút gốc với giá trị của alpha là - và beta là +. Thủ tục sẽ tự gọi đệ quy chính nó với khoảng cách giữa các giá trị alpha và beta ngày càng hẹp hơn. 2.3.2 Giải thuật Thuật toán Alpha -Beta Nếu mức đang xét là đỉnh (gốc cây), đặt giá trị của alpha là - và beta là +. Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm, nút lá), tính giá trị tĩnh của thế cờ hiện tại ứng với người chơi ở đó. Ghi lại kết quả. Nếu như mức đang xét là của người chơi cực tiểu (MIN), thực hiện các công việc sau cho đến khi tất cả các con của nó đã được xét với thủ tục Alpha-beta hoặc cho đến khi alpha là bằng hoặc lớn hơn beta. Áp dụng thủ tục Alpha-beta với giá trị alpha và beta hiện tại cho một con. Ghi nhớ lại kết quả. So sánh giá trị ghi nhớ với giá trị beta, nếu giá trị đó nhỏ hơn thì đặt beta bằng giá trị mới này. Ghi nhớ lại beta (thu hẹp khoảng [alpha, beta] bằng cách giảm giá trị beta). Nếu như mức đang xét là của người chơi cực đại (MAX), thực hiện các công việc sau cho đến khi tất cả các con của nó đã được xét với thủ tục Alpha-beta hoặc cho đến khi alpha là bằng hoặc lớn hơn beta. Áp dụng thủ tục Alpha-beta với giá trị alpha và beta hiện tại cho một con. Ghi nhớ lại kết quả. So sánh giá trị ghi nhớ với giá trị alpha, nếu giá trị đó lớn hơn thì đặt Alpha bằng giá trị mới này. Ghi nhớ lại alpha (thu hẹp khoảng [alpha, beta] bằng cách tăng giá trị alpha). MIN MAX 2 3 3 3 0 0 2 2 3 5 0 2 1 MAX MIN A D E B C Hình 2.7 Minh họa giải thuật Alpha-beta A có=3 ( Giá trị nút A sẽ không lớn hơn 3). B bị cắt tỉa , vì 5>3. C có =3 ( Giá trị nút C sẽ không nhỏ hơn 3). D bị cắt tỉa , vì 0<3. E bị cắt tỉa , vì 2<3. Giá trị nút C là 3. Từ ý tưởng trên ta sẽ xây dựng hàm AlphaBeta bằng ngôn ngữ tựa Pascal. Hàm này sẽ có dạng khai báo như dưới đây, trong đó depth là độ sâu tìm kiếm, INFINITY là giá trị vô cùng, thuật toán tính toán dựa trên thế cờ hiện tại pos là các biến toàn cục [15][16]. function AlphaBeta(alpha, beta, depth): integer; begin if (depth = 0) or (pos là nút lá) then AlphaBeta := Eval { Tính giá trị thế cờ pos } else begin best := -INFINITY;  Gen; { Sinh ra mọi nước đi từ vị trí pos } while (còn lấy được một nước đi m) and (best Alpha then Alpha := best;  Thực hiện nước đi m; value := -AlphaBeta(-beta, -Alpha, depth-1); Bỏ thực hiện nước đi m; if value > best then best := value; end;  AlphaBeta := best; end; end; Ví dụ lời gọi thủ tục AlphaBeta đầu tiên với độ sâu tìm kiếm 4 và thế cờ hiện tại pos có dạng như sau: AlphaBeta(-INFINITY, +INFINITY, 4); alphaa beta Miền xem xét miền “tồi tệ” (cẳt bỏ) miền “tồi tệ” (cẳt bỏ) So với thuật toán Minimax thì trong thuật toán AlphaBeta đã đưa thêm hai biến alpha, beta làm hai mức ngưỡng. Ta thấy cứ mỗi khi best >= beta thì thuật toán không thực hiện tiếp vòng lặp, có nghĩa là nó không chịu mở rộng tiếp những nhánh còn lại nữa. Các nhánh đó đã bị cắt bỏ và do đó ta sẽ tiết kiệm được thời gian. Việc cắt bỏ này hoàn toàn an toàn với những lí do ta đã xét ở trên. Ta thấy rằng mỗi lần hàm này được gọi thì chỉ có tham số beta được dùng để so sánh cắt bỏ, còn tham số alpha không được dùng. Tuy nhiên khi áp dụng cùng thuật toán cho cây con thì ta đã hoán vị hai giá trị alpha, beta cho nhau (và đảo cả dấu), do đó alpha sẽ có tác dụng trong độ sâu sau, rồi độ sâu sau nữa lại đến lượt beta... Nói cách khác, một giá trị chỉ luôn ảnh hưởng đến người chơi cực đại, còn giá trị kia lại luôn ảnh hưởng đến người chơi cực tiểu. Chúng là các ngưỡng giữa các nước đi được chấp nhận và không chấp nhận. Những nước đi cần quan tâm phải nằm lọt giữa hai giá trị này. Dần dần khoảng cách giữa hai giá trị alpha và beta càng ngày càng thu hẹp và dẫn đến các nhánh cây có giá trị nằm ngoài khoảng này nhanh chóng bị cắt bỏ: Hình 2.8: alpha, beta giống như hai lưỡi dao dùng để cắt bỏ lớp vỏ dầy. Hai lưỡi dao này sẽ được thu hẹp dần dần. Lượng cắt bỏ phụ thuộc vào tốc độ thu hẹp, thu hẹp càng nhanh cắt bỏ càng nhiều. 2.3.3 Đánh giá Hiệu quả của việc cắt nhánh Alpha-beta phụ thuộc nhiều vào thứ tự các nước đi kế tiếp được thực hiện. Nếu các nước đi kế tiếp được thực hiện có thứ tự ngẫu nhiên thì tổng số nút được thực hiện sẽ khoảng O(b3d/4) [8]. Trong đó b là độ rộng của cây (hệ số phân nhánh trung bình của các con), d là độ sâu của cây. 2-1 với d chẵn +-1 với d lẻ Trong điều kiện lí tưởng, thuật toán Alpha-beta chỉ phải xét số nút theo công thức:  Như vậy, trong trường hợp tốt nhất thuật toán Alpha-beta chỉ cần thực hiện khoảng O(bd/2) nút để chọn ra nước đi tốt nhất, thay vì O(bd). Hệ số phân nhánh hiệu quả trở thành thay vì b như trong thuật toán Minimax [8][14]. Thuật toán Alpha-beta nói chung giúp chúng ta tiết kiệm nhiều thời gian so với Minimax mà vẫn đảm bảo kết quả tìm kiếm chính xác. Tuy nhiên lượng tiết kiệm này không ổn định - phụ thuộc vào số nút mà nó cắt bỏ. Trong trường hợp xấu nhất thuật toán không cắt được một nhánh nào và phải xét số nút đúng bằng thuật toán Minimax. Ta cần đẩy mạnh việc cắt bỏ nhờ đẩy nhanh sự thu hẹp của cửa sổ tìm kiếm Alpha-beta. Cửa sổ này được thu hẹp một bước khi gặp một giá trị mới tốt hơn giá trị cũ. Khi gặp giá trị tốt nhất thì cửa sổ này thu hẹp nhất. Do đó nếu càng sớm gặp giá trị tốt nhất thì cửa sổ càng chóng thu hẹp. Như vậy phải làm sao cho các nút ở lá được sắp xếp theo trật tự từ cao xuống thấp. Trật tự này càng tốt bao nhiêu thì thuật toán chạy càng nhanh bấy nhiêu (các công thức về số nút phải lượng giá trong điều kiện lí tưởng ở trên tính được với trật tự là tốt nhất). Ví dụ: Ta sẽ xét xem thuật toán Alpha-beta hoạt động như thế nào đối với cây trò chơi sau: 1 3 4 9 11 7 13 17 19 21 24 26 28 34 32 36 5 2 =8 8 9 38 29 14 12 10 30 23 25 27 22 20 18 37 35 33 15 6 39 31 16 2 4 = 4 1 3 = 5 1 2 =3 3 9 6 5 = 5 3 8 = 4 4 5 = 5 Kết quả tìm kiếm nước đi 8 7 2 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2 1 2 3 9 7 2 16 6 4 Hình 2.9: Một cây trò chơi có độ sâu 3 và hệ số nhánh 3. Số trong các hình chữ nhật cho biết thứ tự đưa ra các kết luận. Chú ý rằng chỉ có tất cả là 16 đánh giá tĩnh được thực hiện (các nút đen) chứ không phải là 27 như khi không dùng thuật toán Alpha-beta. Nhánh đi tốt nhất cho người chơi cựa đại là nhánh giữa. Các thứ tự kết luận (các con số bên trái) được đưa ra như sau: [1-2] Tìm kiếm đi xuống dưới theo nhánh trái cho đến lá. Ở đây giá trị tĩnh thu được là 8. Giá trị đầu tiên này do người chơi cực đại được phép chọn trong ba giá trị ở nhánh này đã đảm bảo rằng là kết quả thu được sẽ ít nhất là bằng 8. Điều lưu ý này được bước 2 ghi lại. [3-5] Để chắc chắn không còn có điểm nào cao hơn 8, người chơi cực đại phải xét cả hai thế cờ còn lại và thu được các giá trị 7 và 2. Do đó đến đây đã kết luận chính xác điểm cao nhất có thể đạt được ở cây con là đúng bằng 8. [6] Leo lên một tầng cây. Đây là các nước đi của người chơi cực tiểu. Ta không hi vọng anh ta cho người chơi cực đại được nhiều điểm nên có thể tạm kết luận ở mức này là sẽ đạt được nhiều nhất là 8 điểm. [7-8]. Để xem người chơi cực tiểu còn lựa chọn nào tốt hơn (và tồi tệ hơn cho người chơi cực đại) ta phải xem xét cả hai nước đi còn lại. Nước đi còn lại đầu tiên dẫn đến giá trị lượng giá tĩnh là 9> 8. Như vậy nhánh giữa là tồi tệ hơn cho người chơi cực tiểu. Đến đây việc cắt bỏ được thực hiện do đó người chơi cực đại không thể với tới được điểm đó khi đã có sẵn lựa chọn thấp hơn cho anh ta (là 8). Điều này cũng dẫn đến không cần thiết phải xét hai nút còn lại - đằng nào nhánh giữa cũng đủ tồi tệ rồi và người chơi cực tiểu sẽ không chọn nó để đi. [9-14] Người chơi cực tiểu cần phải khảo sát tiếp lựa chọn cuối cùng. Cách làm tương tự như phần trên. Ở đây phải lượng giá cả ba nút cây và kết luận cuối cùng được đưa ra là người chơi cực đại đi giỏi lắm thì chỉ đạt được 4 điểm. [15] Như vậy nhờ việc khảo sát nhánh cây bên phải người chơi cực tiểu thấy rằng nếu chọn đi theo nhánh này thì người chơi cực đại chỉ được có 4 điểm thay cho 8. [16] Bây giờ ta có thể kết luận ở mức trên cùng. Mức này là của người chơi cực đại. Anh ta thấy rằng nếu chọn đi theo nhánh trái thì được 4 điểm. Như vậy anh ta đã chắc chắn điểm của mình sẽ ít nhất là 4 rồi. Để xem liệu có thể đạt được điểm cao hơn nữa hay không cần phải xem xét hai nhánh còn lại. [17-30] Tương tự như phần trên, ta kết luận nhánh giữa sẽ mang lại cho người chơi cực đại 5 điểm. [31] Cũng tương tự như kết luận 16, ở đây ta kết luận khả quan hơn là người chơi cực đại đã cầm chắc 5 điểm và có thể còn cao hơn. [32-38] Ta kết luận được rất nhanh là cây con bên phải chỉ cho "thu hoạch" nhiều nhất là 3 điểm - một điểm số quá kém do đó thuật toán không xem xét các trường hợp còn lại nữa. Do đó đã tiết kiệm được 6 nút không cần phải lượng giá và cũng không phải sinh nước đi cho hai trường hợp. [39] Kết luận cuối cùng là điểm cao nhất mà người chơi cực đại có thể thu được là 5 điểm nhờ chọn đi theo nhánh giữa. 2.4 So sánh giải thuật Minimax và giải thuật Alpha-beta. Dưới đây là bảng so sánh số nút phải xét giữa hai giải thuật Minimax và Alpha-beta. Độ sâu Minimax AlphaBeta Tỉ lệ số nút Minimax/Alpha-beta Số nút Số lần tăng Số nút Số lần tăng 1 40 40 1 2 1600 40 79 1.9 20 3 64000 40 1852 23.2 34 4 2560000 40 3199 1.7 800 5 102400000 40 74118 23.2 1381 6 4096000000 40 127999 1.7 32000 7 163840000000 40 2964770 23.2 55262 8 6553600000000 40 5120000 1.7 1280000 Với b = 40 và d = 4 ta có số nút phải xét là 2x402 - 1 = 3199. Như vậy trong điều kiện lí tưởng thì số nút phải xét nhờ Alpha-beta (chỉ khoảng 3 nghìn nút) ít hơn thuật toán Minimax (hơn 2,5 triệu nút) là 2560000/ 3199 khoảng 800 lần. Còn với b = 40 và d = 5 ta có số nút phải xét là 403 + 40(5/2) - 1 = 64000+10119-1 = 74118. Số nút phải xét nhờ Alpha-beta ít hơn thuật toán Minimax (hơn 102 triệu nút) là 102400000/74118 = 1382 lần. Ta có thể nhận xét như sau: - Số lần tăng số nút khi tăng độ sâu của Minimax luôn là hệ số phân nhánh b, trong trường hợp này là 40. Số lần tăng của Alpha-beta ít hơn nhiều: chỉ cỡ 1.7 lần khi tăng từ d lẻ sang d chẵn và 23.2 lần khi từ d chẵn sang lẻ, trung bình chỉ tăng khoảng hơn 6 lần khi tăng d. - Số nút của Alpha-beta tăng chậm hơn rất nhiều lần so với Minimax. Tỉ số nút phải xét giữa hai giải thuật này càng cao khi d càng lớn. Công thức tính số nút cho thấy số nút phải xét khi dùng Alpha-beta ít hơn nhiều so với Minimax nhưng vẫn là hàm số mũ và vẫn dẫn tới bùng nổ tổ hợp. Thuật toán Alpha-beta hoàn toàn không chống được bùng nổ tổ hợp mà chỉ làm giảm tốc độ bùng nổ tổ hợp. Tuy trong thực tế số nút phải xét (lượng giá) thường nhiều hơn trong điều kiện lí tưởng nhưng nó vẫn đủ để tiết kiệm khá nhiều thời gian. Trong cùng một khoảng thời gian, thuật toán Alpha-beta có thể tìm đến độ sâu gấp hai lần độ sâu tìm kiếm bằng Minimax. Hình sau đây là đồ thị so sánh giữa hai thuật toán này [5]. Hình 2.10 : Khảo sát sự bùng nổ tổ hợp, Thuật toán Alpha-beta chỉ làm giảm sự bùng nổ tổ hợp chứ không chống được nó. Hệ số phân nhánh trong các đồ thị trên là 40. Tóm lại : Do bùng nổ tổ hợp quá lớn của cây trò chơi mà cả hai người chơi 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. 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 Minimax và cải tiến của nó là thuật toán Alpha-beta. Tuy cả hai thuật toán đều không tránh được bùng nổ tổ hợp nhưng thuật toán Alpha-beta làm chậm bùng nổ tổ hợp hơn nên được dùng nhiều trong các trò chơi cờ. CHƯƠNG 3: ỨNG DỤNG 3.1 Phân tích bài toán 3.1.1 Trò chơi Trò chơi N quân hậu bắt nguồn từ bài toán rất nổi tiếng là Bài toán 8 con hậu: đặt lần lượt 8 con hậu lên bàn cờ quốc tế (kích thước 8x8) sao cho không có 2 con hậu nào khống chế lẫn nhau. Do vậy, người ta có khá nhiều cách định nghĩa về trò chơi N quân hậu, điển hình là 3 cách sau: Cho bàn cờ quốc tế có kích thước N x N, 2 người chơi lần lượt đặt từng quân hậu lên bàn cờ sao cho không có 2 quân hậu nào khống chế nhau. Người chơi nào không đặt được quân hậu lên bàn cờ nữa là người thua cuộc. Cho bàn cờ quốc tế có kích thước N x N, 2 người chơi lần lượt đặt từng quân hậu lên bàn cờ sao cho không có 2 quân hậu nào khống chế nhau cho đến khi không đặt được nữa. Mỗi quân hậu đặt lên bàn cờ sẽ khống chế các ô nằm trong 8 hướng đi của nó nếu ô đó còn chưa bị khống chế. Ai khống chế được nhiều ô hơn là người thắng cuộc. Cho bàn cờ quốc tế kích thước N x N. Người đi đầu tiên sẽ đặt a quân hậu lên bàn cờ. Người chơi thứ 2 tiếp tục đặt b con hậu lên bàn cờ (a > b và a + b ≤ N) sao cho không có 2 quân hậu nào khống chế lẫn nhau. Sau đó người chơi thứ nhất sẽ di chuyển các con hậu của mình để ăn các con hậu của đối phương, người chơi thứ 2 có nhiệm vụ phòng thủ, di chuyển các con hậu của mình để đối phương không bắt được. Sau k nước đi nếu người chơi thứ nhất ăn được hết b con hậu của đối phương thì người chơi thứ nhất thắng, ngược lại người chơi thứ 2 thắng. Sau khi cân nhắc, cách phát biểu trò chơi thứ 2 được chọn để tiến hành viết ứng dụng cho luận văn. Tuy nhiên, để cho trò chơi hấp dẫn hơn và công bằng hơn chúng ta bổ sung thêm một số luật chơi. Phát biểu trò chơi (bài toán) như sau: Cho bàn cờ có kích thước N x N (3 ≤ N ≤ 15), trên đó có sẵn m ô đá ( hay có thể hiểu là chướng ngại vật) (0 ≤ m ≤ (N - 2)2) nằm ở các vị trí ngẫu nhiên, các ô còn lại là ô trống. Hai người chơi lần lượt đặt từng con hậu lên bàn cờ sao cho không có 2 con hậu nào khống chế lẫn nhau. Hai con hậu khống chế nhau nếu chúng nằm trên đường đi của nhau và không có ô đá nào nằm trên đường đi ấy. Mỗi con hậu đặt lên bàn cờ sẽ khống chế các ô nằm trên 8 đường đi của nó nếu ô đó còn trống, chưa bị khống chế bởi con hậu nào khác. Trò chơi kết thúc khi không đối thủ nào đặt được quân hậu lên bàn cờ nữa. Người nào khống chế được nhiều ô hơn là người thắng cuộc. Hình 3.1 dưới đây minh họa hai trường hợp: Hai con hậu không khống chế nhau và hai con hậu khống chế nhau: Hình 3.1 (a) Hai con Hậu không khống chế nhau (b) Hai con Hậu khống chế nhau Trong hình (a) Con Hậu xanh ở vị trí (2,3) đặt trước do đó nó khống chế được 5 ô, con Hậu màu vàng đặt sau nên chỉ khống chế được 3 ô. 3.1.2 Cơ sở lý thuyết Theo như phát biểu trò chơi ở trên, ta có thể thấy trò chơi N quân hậu thuộc lớp các trò chơi đối kháng giữa hai người chơi. Cụ thể trò chơi này thuộc dạng trò chơi có tổng bằng không với hai người chơi (Two players, Zero-sum-game). Vì thế ta có thể áp dụng thuật toán tìm kiếm Minimax và thuật toán Alpha-beta trong trò chơi này. Mặt khác nếu viết chương trình để người chơi với người thì chỉ cần xây dựng các tập luật chơi để người chơi không phạm quy và kết thúc khi có người thắng. Tuy nhiên như vậy lại không ứng dụng và kiểm tra được thuật toán trong luận văn này. Vì vậy chúng ta sẽ viết chương trình cho Người chơi với Máy, trong trường hợp này ta phải tính toán như thế nào để khả năng máy tính thắng cao hơn người. Máy tính có lợi thế là khả năng tính toán nhanh, khả năng nhớ tốt gấp nhiều lần so với con người, vậy để máy tính thắng thì thật dễ, vấn đề là làm sao để máy có thể nghĩ được như người? Và có thể tính trước được ít nhất là 4 đến 5 nước.Vậy phải có thuật toán để máy có thể quét qua các phương án đi, và chọn phương án cuối cùng là tốt nhất sao cho máy tính có thể thắng. Trong ứng dụng này ta chọn thuật toán Minimax và thuật toán cải tiến Alpha-beta (chương 2) để cài đặt cho máy tính chơi. 3.2 Cài đặt chương trình Chương trình được cài đặt bằng ngôn ngữ C# (.NET Framework 2.0). Ngoài ra còn sử dụng thêm một số phầm mềm như: PowerCHM, Photoshop và phần mềm tạo file icon. 3.2.1 Cấu trúc chương trình và mối quan hệ giữa các lớp chính Chương trình được thiết kế theo mô hình Hướng đối tượng(Object-Oriented) để tiện cho việc cải tiến về sau. Do chương trình mới được phát triển nên cấu trúc còn đơn giản, chỉ có 3 lớp chính là các lớp Form1 (tên lớp mặc định do C# đặt cho form), lớp CBoard và lớp gameAI. Trong đó lớp gameAI là lớp được áp dụng thuật toán trong chương 2 của chúng ta. Mối quan hệ giữa 3 lớp thể hiện qua sơ đồ các lớp trong hình 3.2 như sau: 1 2 3 4 Hình 3.2: Sơ đồ thể hiện mối liên quan giữa 3 lớp chính. Trong đó: - Lớp Form1 có thuộc tính mb thuộc lớp CBoard. - Lớp CBoard có thuộc tính form thuộc lớp Form1. - Lớp CBoard có thuộc tính machine thuộc lớp GameAI. - Lớp GameAI có thuộc tính ownBoard thuộc lớp CBoard. Các lớp tương tác với nhau thông qua các bước sau: 1. Lớp Form1 truyền thông tin nhận được từ người chơi cho lớp CBoard, lớp CBoard lấy được thông tin thông qua thuộc tính form. 2. Lớp Cboard xử lý dữ liệu thu được từ lớp Form1 và truyền cho lớp GameAI, lớp GameAI thu được thông qua thuộc tính ownBoard . 3. Lớp GameAI sau khi nhận được thông tin sẽ xử lý và truyền lại cho lớp Cboard, lớp Cboard nhận được thông qua thuộc tính machine. 4. Lớp Cboard nhận được thông tin từ lớp GameAI, xử lý và truyền lại cho lớp Form1 thông qua thuộc tính mb. Lớp form1 xử lý lại thông tin và điều chỉnh giao diện của form. Sau đây chúng ta sẽ xem xét cấu trúc và nhiệm vụ của 3 lớp trên. 3.2.2 Lớp Form1 Lớp này thể hiện giao diện của trò chơi, làm nhiệm vụ giao tiếp với người chơi. Các thao tác chính của lớp này là: Nhận thông tin khởi tạo một ván chơi từ người sử dụng như: kích thước bàn cờ, trình độ của máy, số ô đá (hay vật cản) sử dụng, ai là người đi trước để cung cấp thông tin cho lớp CBoard khởi tạo một ván chơi mới. Ghi nhận thông tin về nước đi của người chơi mỗi khi người chơi nhấp chuột lên một ô trống rồi truyền cho lớp CBoard xử lý. Cập nhật nước đi của người và máy lên màn hình. Hiển thị các thông tin về trận đấu như điểm của các đối thủ, các nước đã đi, ai là người đang đi… Thể hiện 1 số hiệu ứng khi người dùng di chuyển chuột trên bàn cờ để tiện cho người chơi suy nghĩ, đánh giá. Ngoài ra còn thực hiện xuất các kết quả của các ván chơi ra một file Excel để tiện theo dõi lại sau nhiều ván chơi. Trong mục 3.3 chúng ta sẽ thấy được các thành phần cụ thể của lớp Form1. 3.2.3 Lớp CBoard Lớp CBoard đóng vai trò như một bàn cờ trong thực tế. Lớp này chứa các thông tin về bàn cờ: Một mảng 2 chiều lưu trữ trạng thái từng ô của bàn cờ. Kích thước bàn cờ, người đi trước, số ô đá trên bàn cờ, thời gian và trình độ suy nghĩ của máy, điểm của 2 đối thủ. Lưu trữ thông tin về nước đi hiện tại: ai đang đi, là nước đi thứ mấy… Các phương thức chính của lớp Cboard như sau: Khởi tạo một ván chơi mới. Kiểm tra một nước đi có hợp lệ hay không? Ghi nhận một nước đi. Thực hiện nước đi của người chơi. Yêu cầu máy thực hiện nước đi. 3.2.4 Lớp gameAI Có thể nói lớp gameAI là lớp trung tâm của các chương trình trò chơi đối kháng. Lớp này chứa các phương thức phục vụ cho việc quyết định đi một nước của máy. Sau đây chúng ta sẽ xem xét chi tiết các thuộc tính và phương thức của lớp này. Hình 3.3: Cấu trúc lớp gameAI Trong lớp gameAI có các thuộc tính đáng chú ý là: Mảng 2 chiều board[,] chứa trạng thái của bàn cờ hiện tại. board[i, j] = -100 nếu ô đó là ô đá. board[i, j] = -x tức là ô (i, j) chứa con hậu được đặt ở nước thứ x. board[i, j] = x nếu ô (i, j) bị khống chế bởi con hậu đặt ở nước thứ x. Mảng listCell[] chứa danh sách các ô sẽ bị khống chế nếu ta đặt con hậu ở một ô nào đó 2 mảng dx, dy thể hiện 8 hướng đi có thể của quân hậu. ownBoard là một thể hiện( đối tượng) của lớp cBoard, chứa bàn cờ chúng ta đang chơi và các thông tin về nó như kích cỡ, trình độ máy v.v….. ownedCell: ghi nhận số ô đã bị khống chế trên bàn cờ totalCell: tổng số ô trống trên bàn cờ lúc đầu = tổng số ô – số ô đá. startTime: ghi nhận thời gian bắt đầu suy nghĩ của máy. resX, resY: ghi lại nước đi máy sẽ đi. bestValue ghi nhận giá trị tốt nhất nếu thực hiện nước đi (resX, resY). Các phương thức của lớp gameAI Lớp chỉ có một phương thức có thuộc tính public là phương thức requestMove(). Phương thức này có đầu vào là một trạng thái của bàn cờ, trả lại giá trị (resX, resY) là ô mà máy sẽ đặt quân hậu. Để tìm kiếm được nước đi tốt nhất, phương thức requestMove sử dụng các phương thức hỗ trợ là: AlphaBeta: thực hiện tìm kiếm theo thuật toán Alpha-beta. Minimax: thực hiện tìm kiếm theo thuật toán Minimax. Hàm eval: lượng giá thế cờ hiện tại. Phương thức heuristicGenerateMove: sinh heuristic các nước đi có thể. Phương thức doMove: thử thực hiện một nước đi được sinh bởi phương thức heuristicGenerateMove. - Phương thức remove: bỏ thực hiện nước đi đã thử (như đã nói trong thuật toán ở chương 2). Sau đây chúng ta sẽ xem xét các phương thức của lớp gameAI một cách chi tiết. Phương thức Minimax Function Minimax(depth): integer; Begin If (đã quá thời gian suy nghĩ) then return –INFINITY; {dừng không duyệt nữa} if (depth=0) or (không thể đi được nước nào nữa) then return eval(depth); {lượng giá ngay thế cờ hiện tại và kết thúc} best = -INFINITY; pMove = heuristicGenerateMove; {sinh các nước đi có thể} while (còn lấy được nước đi m trong pMove)do begin Thực hiện nước đi m; value = -Minimax(depth - 1); Bỏ thực hiện nước đi m; if (value > best) then begin best := value; if (đây là nước đi đầu tiên của máy) then cập nhật nước đi resX, resY; end; end; return best; End; Phương thức Alphabeta Function AlphaBeta(Alpha, beta, depth): integer; Begin If (đã quá thời gian suy nghĩ) then return –INFINITY; {dừng không duyệt nữa} if (depth=0) or (không thể đi được nước nào nữa) then return eval(depth); {lượng giá ngay thế cờ hiện tại và kết thúc} best = -INFINITY; pMove = heuristicGenerateMove; {sinh các nước đi có thể} while (còn lấy được nước đi m trong pMove) and (best < beta) do begin if (best > Alpha) then Alpha := best; Thực hiện nước đi m; value = -AlphaBeta(-beta, -Alpha, depth - 1); Bỏ thực hiện nước đi m; if (value > best) then begin best := value; if (đây là nước đi đầu tiên của máy) then cập nhật nước đi resX, resY; end; end; return best; End; Phương thức sinh nước đi heuristicGenerateMove Trong chương 2 khi đánh giá thuật toán Alpha-beta ta đã nhận xét: thuật toán hoạt động càng hiệu quả khi sự thu hẹp cửa sổ Alpha và Beta càng nhanh. Cửa sổ này được thu hẹp một bước khi gặp một giá trị mới tốt hơn giá trị cũ. Khi gặp giá trị tốt nhất thì cửa sổ này thu hẹp nhất. Do đó nếu càng sớm gặp giá trị tốt nhất thì cửa sổ càng chóng thu hẹp. Như vậy phải làm sao cho các nút ở lá được sắp xếp theo trật tự từ cao xuống thấp. Trật tự này càng tốt bao nhiêu thì thuật toán chạy càng nhanh bấy nhiêu. Tuy vậy, do giới hạn về thời gian tính toán và sự bùng nổ tổ hợp, ta không thể liệt kê hết các nút lá để sắp xếp được. Do đó, ta chỉ áp dụng cách sinh các nước đi theo một tiêu chuẩn mà ta cho là tốt, phù hợp với đặc điểm trò chơi đang xét như sau: Ta thấy, nếu không có ô đá thì nước đi đầu tiên vào ô trung tâm bao giờ cũng chiếm được nhiều ô trống nhất. Do đó, ta sẽ ưu tiên xét các ô theo thứ tự từ ô trung tâm tỏa ra các ô xung quanh (tất nhiên là trừ ô đá!) Một cách cảm tính, ta có thể nhận thấy đi vào các ô có số ô trống trong 8 ô xung quanh nó lớn thì có vẻ có lợi hơn. Như vậy ta có thể sinh các nước đi sắp tới theo hướng heuristic như sau: tìm tất cả các ô còn trống. với mỗi ô, đếm số ô trống xung quanh nó, cho tất cả vào một danh sách. Tiến hành sắp xếp danh sách theo thứ tự giảm dần của số ô trống xung quanh. Nếu hai ô có cùng số ô trống xung quanh thì ưu tiên ô gần trung tâm hơn. Giải thuật được cài đặt như sau: Procedure generateHeuristicMove(var pMove); begin for i := 1 to boardSize do for j := 1 to boardSize do if board[i, j] = 0 then {nếu ô (i, j) còn là ô trống} begin k := số ô trống xung quanh ô (i, j); đặt bộ 3(i, j, k) vào mảng pMove; end; sắp xếp mảng pMove theo tiêu chí ở trên; End; Hàm đếm số ô trống xung quanh ô (i, j) được thực hiện đơn giản, chỉ cần kiểm tra 8 ô xung quanh nó. Lưu ý trường hợp ô (i, j) ở biên của bàn cờ, ta phải sử dụng kỹ thuật lính canh: đặt bên ngoài biên của bàn cờ là các ô đá để tránh trường hợp tràn mảng. Phương thức lượng giá eval Do đặc điểm của trò chơi, hàm lượng giá được thực hiện như sau: Ta chỉ việc tính hiệu số giữa số ô người chơi chiếm giữ và số ô máy chiếm giữ. Tham số depth được đưa vào để biết được đối thủ nào gọi hàm lượng giá này. Function eval(depth): integer; begin for i := 1 to boardSize do for j := 1 to boardSize do if ô (i,j) bị người chơi chiếm then tăng số ô người chiếm lên 1 else if ô (i,j) bị máy chiếm then tăng số ô máy chiếm lên 1; if (depth mod 2 = 0) {nếu người chơi gọi hàm lượng giá} return (số ô máy chiếm – số ô người chiếm) else return (số ô người chiếm – số ô máy chiếm); End; Phương thức doMove Phương thức doMove nhận tham số đầu vào là (i, j): chỉ số ô sẽ đi và x là số thứ tự của nước đi. Phương thức thực hiện như sau: đánh dấu ô sẽ đi là –x. Từ ô (i, j) ta đi lần lượt theo 8 hướng có thể đến khi nào ra biên hoặc gặp ô đá. Với mỗi ô trên đường đi, nếu còn là ô trống thì đánh dấu ô đó mang giá trị x. Trong quá trình đó, cập nhật lại giá trị số ô đã bị chiếm. Phương thức remove Phương thức remove có tham số đầu vào là x: số thứ tự của nước đi. Phương thức thực hiện bỏ nước đi được tạo bởi hàm doMOVE. Phương thức đơn giản chỉ quét các ô trên bàn cờ, nếu giá trị tuyệt đối của ô đó bằng x thì ta gán lại giá trị bằng 0, đồng thời giảm giá trị số ô bị chiếm đi 1. Mã nguồn lớp gameAI: using System; using System.Collections.Generic; using System.Text; using System.Drawing; using System.Collections; namespace n_queens { // xay dung lop diem moi dua vao lop point da co class myPoint { public Point pt; int val; public myPoint(int x, int y, int startVal) { pt = new Point(x, y); val = startVal; } //Tính khoang cách giữa điểm a và điểm trung tâm static double distance(myPoint a, double mid) { return Math.Sqrt(Math.Pow(a.pt.X - mid, 2)+Math.Pow(a.pt.Y - mid, 2)); } // Phương thức tĩnh so sánh khoang cach giua hai diem voi o trung tam public static int compare(myPoint a, myPoint b, float mid) { if (a.val > b.val) return -1; else if (a.val < b.val) return 1; else { double d1 = distance(a, mid); double d2 = distance(b, mid); if (d1 < d2) return -1; else if (d1 > d2) return 1; else return 0; } } } class CompareInv : IComparer// lop Icomparer co 1 phuong thuc compare de so sanh 2 doi tuong { int middlePoint; public CompareInv(int middle) //ham tao { middlePoint = middle; } public int Compare(object obj1, object obj2)//so sanh 2 đoi tuong { myPoint a, b; a = (myPoint)obj1; b = (myPoint)obj2; return myPoint.compare(a, b, middlePoint); } } class gameAI {// khai bao đoi tuong thuoc lop CBoard CBoard ownBoard; /// /// mang chưa trạng thái của ban co /// int[,] board = new int[17, 17]; //dinh nghia 8 huong /// /// thể hiện 8 hướng đi của quân hậu /// int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 }; /// /// int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 }; /// /// Thời gian bắt đầu /// long startTime; /// /// Giá trị thuật toán trả về /// int resX, resY, bestValue; /// /// Số ô đã chiếm /// int ownedCell, totalCell;// so o bi chiem va so o trong ban dau CompareInv compInv; //doi tuong thuoc lop CompareInv /// /// danh sách các ô có thể bị chiếm /// Point[] listCell = new Point[17 * 17]; /// /// hàm tạo của lớp /// public gameAI(CBoard mb) // ham tao { ownBoard = mb; totalCell = mb.boardSize * mb.boardSize - mb.nStone; } /// /// Phuong thuc Sinh nước đi /// void heuristicGenerateMove(ArrayList pMove) { int i, j, k, c; ArrayList al = new ArrayList(); for (i = 1; i <= ownBoard.boardSize; i++) for (j = 1; j <= ownBoard.boardSize; j++) if (board[i, j] == 0) { //Dem o trong gan ke voi o [i,j] c = 0; for (k = 0; k < 8; k++) if (board[i + dx[k], j + dy[k]] == 0) c++; al.Add(new myPoint(i, j, c)); } al.Sort(compInv);// sap xep cac doi tuong trong danh sách al foreach (myPoint p in al) { pMove.Add(p.pt); } } /// /// Thuc hien di chuyen ban co /// /// /// void doMove(Point start, int ord) { int u = start.X, v = start.Y; int i, j; board[u, v] = -ord;// danh dau o [u,v] da di ownedCell++;// so o bi chiem // danh dau cac o bi chiem ngang, doc, cheo i = u - 1; j = v; while ((i >= 1) && (board[i, j] > -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } i--; } i = u + 1; j = v; while ((i -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } i++; } i = u; j = v - 1; while ((j >= 1) && (board[i, j] > -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j--; } i = u; j = v + 1; while ((j -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j++; } i = u - 1; j = v - 1; while ((i >= 1) && (j >= 1) && (board[i, j] > -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j--; i--; } i = u + 1; j = v + 1; while ((i -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j++; i++; } i = u - 1; j = v + 1; while ((i >= 1) && (j -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j++; i--; } i = u + 1; j = v - 1; while ((i = 1) && (board[i, j] > -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j--; i++; } } /// /// Tro lai buoc di chuyen /// /// /// void remove(Point pt, int ord) { for (int i = 1; i <= ownBoard.boardSize; i++) for (int j = 1; j <= ownBoard.boardSize; j++) if (Math.Abs(board[i, j]) == ord) { board[i, j] = 0; ownedCell--; } } /// /// Phuong thuc Uoc luong gia tri cua nuoc di /// /// /// int eval(int ord) { int countOdd = 0, countEven = 0; for (int i = 1; i <= ownBoard.boardSize; i++) for (int j = 1; j <= ownBoard.boardSize; j++) if ((board[i, j] != 0) && (board[i, j] > -100) && (board[i, j] % 2 == 0)) countEven++;//chan else if (board[i, j] % 2 != 0) countOdd++; // le if (ownBoard.playerMove % 2 == 0) { if (ord % 2 == 0) return countEven - countOdd; else return countOdd - countEven; } else { if (ord % 2 == 0) return countOdd - countEven; else return countEven - countOdd; } } /// /// thu tuc Alpha-beta /// /// /// /// /// int AlphaBeta(int Alpha, int beta, int depth) { // het thoi gian suy nghi if (DateTime.Now.Ticks - startTime >= ownBoard.limitTime * 10000000) return -10000; if ((depth == 0) || (totalCell == ownedCell)) return eval(depth); else { ArrayList pMove = new ArrayList(); Point pt; int best, value; best = -10000; //best = -Infinitive heuristicGenerateMove(pMove); IEnumerator myEnumerator = pMove.GetEnumerator(); while (myEnumerator.MoveNext() && (best < beta)) { if (best > Alpha) Alpha = best; pt = (Point)myEnumerator.Current; doMove(pt, ownBoard.nMove + ownBoard.machineLevel - depth + 1); value = -AlphaBeta(-beta, -Alpha, depth - 1); remove(pt, ownBoard.nMove + ownBoard.machineLevel - depth + 1); if ((Math.Abs(value) != 10000) && (value > best)) { best = value; if (depth == ownBoard.machineLevel) { resX = pt.X; resY = pt.Y; } } } return best; } } /// /// Thu tuc Minimax /// int Minimax(int depth) { if (DateTime.Now.Ticks - startTime >= ownBoard.limitTime * 10000000) return -10000; if ((depth == 0) || (totalCell == ownedCell)) return eval(depth); else { ArrayList pMove = new ArrayList(); Point pt; int best, value; best = -10000; //best = -Infinitive heuristicGenerateMove(pMove); IEnumerator myEnumerator = pMove.GetEnumerator(); while (myEnumerator.MoveNext()) //&& (best < beta)) { pt = (Point)myEnumerator.Current; doMove(pt, ownBoard.nMove + ownBoard.machineLevel - depth + 1); value = -Minimax(depth - 1); remove(pt, ownBoard.nMove + ownBoard.machineLevel - depth + 1); if ((Math.Abs(value) != 10000) && (value > best)) { best = value; if (depth == ownBoard.machineLevel) { resX = pt.X; resY = pt.Y; } } } return best; } } /// /// Yêu cầu nước đi /// public Point requestMove(int[,] mb) { board = mb; compInv = new CompareInv((ownBoard.boardSize + 1) / 2); ownedCell = ownBoard.playerScore + ownBoard.machineScore; startTime = DateTime.Now.Ticks; bestValue = Minimax(ownBoard.machineLevel);//AlphaBeta(-10000, 10000, ownBoard.machineLevel); return new Point(resX, resY); } } } 3.3 Một số giao diện và kết quả chạy chương trình Màn hình ban đầu như sau: Hình 3.4: Màn hình ban đầu của trò chơi Trong đó có các tùy chọn để tạo một ván chơi mới Hình 3.5 Các tùy chọn của một ván chơi Sau khi chọn xong các thông số người chơi ấn vào nút “Bắt đầu chơi” để chơi. Màn hình trò chơi bắt đầu: Hình 3.6: Màn hình sau bắt đầu chơi Bàn cờ sau 2 nước đi: Hình 3.7: Bàn cờ sau 2 nước đi. Ô màu xanh là ô mà máy chiếm được sau 1 nước đi của nó, Ô mày vàng là ô mà người chiếm được sau 1 nước đi của người. Còn các ô còn lại là chưa bị chiếm. Sau 2 nước đi kết quả được thể hiện trong hộp trạng thái như sau: Hình 3.8: Kết quả sau 2 nước đi Trong đó thể hiện số điểm của hai đối thủ, đến lượt ai đang chơi và danh sách các nước đi cụ thể của 2 đối thủ. KẾT LUẬN Với mục tiêu đề ra của luận văn là 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, các kết luận chính đã đạt được của luận văn có thể tóm tắt như sau: Đã nhắc lại một cách tổng quan về vấn đề tìm kiếm trong đó có phát biểu bài toán tìm kiếm và giới thiệu các kỹ thuật tìm kiếm cơ bản như 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. Tìm hiểu về đặc điểm của trò chơi có tổng bằng không trong lĩnh vực Lý thuyết trò chơi. Đồng thời đưa ra mô hình toán học của trò chơi có tổng bằng không và phát biểu định lý minimax áp dụng cho các trò chơi có tổng bằng không. Đã nghiên cứu giải thuật tìm kiếm Minimax và giải thuật cải tiến của nó là giải thuật Alpha-beta cho các trò chơi có tổng bằng không. Cài đặt được giải thuật cho trò chơi có tổng bằng không với hai người chơi trong bài toán xếp các quân Hậu lên bàn cờ. Kết quả của việc cài đặt là chương trình trò chơi xếp các quân Hậu giữa người và máy tính. Trong đó thuật toán được cài đặt cho việc suy nghĩ của Máy tính. Mặc dù có nhiều cố gắng nhưng chắc chắn rằng các kết quả đã cài đặt được không tránh khỏi những thiếu sót và hạn chế, hy vọng rằng trong tương lai vấn đề này sẽ được nghiên cứu sâu hơn và phát triển với thuật toán được cải tiến tốt hơn, chẳng hạn chúng ta có thể đi vào nghiên cứu vấn đề song song hóa thuật toán trên. Trên cơ sở các kết quả đã đạt được, chúng ta có thể phát triển những nghiên cứu tiếp về thuật toán Alpha- Beta song song [16]. Hơn nữa, chúng ta có thể nghĩ đến việc triển khai những nghiên cứu về ứng dụng của những kết quả này trong các lĩnh vực khác của xã hội, đặc biệt là kinh tế. Tài liệu tham khảo Tiếng Việt Nguyễn Đình Hóa (2004), Cấu trúc dữ liệu và Thuật giải, NXB ĐHQGHN. Đỗ Xuân Lôi (1998), Cấu trúc dữ liệu và giải thuật, NXB Khoa học kỹ thuật, Hà Nội. Nguyễn Đức Nghĩa - Nguyễn Tô Thành (1997), Toán rời rạc, NXB Giáo dục. Nguyễn Thanh Thủy (2007), Trí tuệ nhân tạo: Các phương pháp giải quyết vấn đề và kỹ thuật xử lý tri thức, NXB Khoa học kỹ thuật. Đỗ Trung Tuấn (1997), Trí tuệ nhân tạo, NXB Giáo dục. Đinh Mạnh Tường (2001), Cấu trúc dữ liệu & Thuật toán, NXB Khoa học kĩ thuật, Hà nội. Đinh Mạnh Tường (2002), Trí tuệ nhân tạo, NXB Khoa học kỹ thuật, Hà nội. Tiếng Anh Jessica Billings (2008), The Minimax Algorithm, CS 330. Jeroen W.T.Carolus (2006), Alpha-beta with Sibling Prediction Pruning in Chess, Faculteitder Natuurwetenschappen, Wiskundeen Informatica Universty of Amsterdam Netherlands. Michael A. Goodrich (2007), Proof of the Minimax Theorem. Heylighen (1993), Zero sum games – Principia Cybernetica Web. R. D. Luce and H. Raiffa (1957), Games and Decisions, John Wiley, New York. George Luger (2002), Artificial Intelligence: Structures and Strategies for Complex Problem Solving, Addison-Wesley Publisher. Stuart J.Russell and Peter Norvig (2003). Artificial Intelligence: A Modern Approach, Prentice Hall, Second edition, p55-p122. Ken Thompson (2008), Play chess with God, Bell Labs, Arun Pratik. Vladan V. Vuˇckovi´c (2007), The method of the chess search algorithms Parallelization using two-Processor distributed system, p175-p188.