- 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. - 5CHƯƠNG 1: TỔNG QUAN VỀ CÁC VẤN ĐỀ TÌM KIẾM. - 51.1 Bài toán tìm kiếm và không gian trạng thái. - 51.1.1 Bài toán tìm kiếm. - 71.1.2 Không gian tìm kiếm. - 101.2 Các kỹ thuật tìm kiếm cơ bản. - 111.2.1 Tìm kiếm không có thông tin. - 141.2.2 Tìm kiếm có thông tin. - 151.2.3 Tìm kiếm đối kháng. - 20CHƯƠNG 2: GIẢI THUẬT TÌM KIẾM MINIMAX. - 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. - 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. - 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. - 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. - 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. - 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. - 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. - 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. - 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. - Việc tìm kiếm được áp dụng rất đa dạng và rộng rãi.. - 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. - X được gọi là khóa tìm kiếm hay đối trị tìm kiếm. - 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). - 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).. - 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. - 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. - 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ị. - 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. - 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. - 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 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). - Ngoài ra bảng băm (hash table) cũng được dùng cho tìm kiếm trên danh sách. - 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.. - 1.2.1.3 Tìm kiếm trên đồ thị. - 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.. - 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. - Các giai đoạn cơ bản để giải quyết vấn đề bằng tìm kiếm heuristic như sau:. - 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á. - 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á. - 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.. - 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ả. - 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ủ. - 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. - 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. - Do đó, các phương pháp tìm kiếm khác đã ra đời và phát triển. - Do đó sẽ không cần phải tìm kiếm gì nữa. - Ta cần có chiến lược tìm kiếm trong trò chơi.. - 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. - 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]. - 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 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. - 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. - 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 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 ở đó. - Chúng ta khó có thể thực hiện tìm kiếm đến độ sâu của các nút lá. - 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. - 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. - 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à trên 2 triệu rưỡi nút). - 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]. - 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].. - 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]. - Có hai giá trị, gọi là alpha và beta được tạo ra trong quá trình tìm kiếm. - Để 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ó. - 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ó. - 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ó. - 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 ở đó. - 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. - 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. - 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. - 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. - Để 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.. - 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. - Đã 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. - Đường tìm kiếm- chuỗi nước đi dẫn đến thế cờ tốt nhất có thể đạt được. - Kết quả tìm kiếm nước đi