Đồ án tốt nghiệp: Xây dựng Bot Chơi Cờ Vua sử dụng thuật toán Minimax (Đoàn Đức Long)

Đồ án tốt nghiệp xây dựng bot chơi cờ vua: Khám phá quy trình, thuật toán và kỹ thuật lập trình để tạo ra một bot cờ vua thông minh, cạnh tranh.

• Tác giả: Đoàn Đức Long
• Người hướng dẫn: Ts. Lâm Sinh Công
• Trường học: Đại học Quốc Gia Hà Nội Trường Đại Học Công Nghệ
• Chuyên ngành: Công Nghệ Kỹ Thuật, Điện Tử - Viễn Thông
• Đề tài: Xây Dựng Bot Chơi Cờ
• Loại tài liệu: Khóa Luận Tốt Nghiệp Đại Học
• Năm xuất bản: 2024
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM KẾT
• LỜI CẢM ƠN
• TÓM TẮT
• Mục lục
• Danh mục hình ảnh và bảng biểu
• Danh mục các từ viết tắt và thuật ngữ
• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ CỜ VUA VÀ CÁC THUẬT TOÁN SỬ DỤNG TRONG VIỆC LẬP TRÌNH GAME CỜ VUA
• 1.1. Quy tắc chơi cơ bản
• 1.2. Tổng quan về trí tuệ nhân tạo và áp dụng vào lập trình
• 1.3. Đánh giá về một số phương pháp áp dụng trí tuệ nhân tạo trong lập trình game cờ vua
• 2. CHƯƠNG 2: XÂY DỰNG GIAO DIỆN CHƠI CỜ VUA TRÊN UNITY ENGINE, XỬ LÝ DỮ LIỆU VÀ XÂY DỰNG BOT
• 2.1. Xây dựng giao diện trò chơi với Unity Engine
• 2.2. Cấu trúc trò chơi
• 2.3. Xây dựng các nước đi trong trò chơi
• 2.4. Xây dựng giao diện người dùng
• 2.5. Hoàn thiện trò chơi
• 2.6. Xử lý dữ liệu và xây dựng bot
• 2.7. Phương pháp nghiên cứu
• 2.8. Các quy tắc đặc biệt trong cờ vua
• 2.9. Khai cuộc và Openings Book
• 2.10. Thuật toán Minimax
• 2.11. Cải tiến thuật toán Minimax
• 2.12. Alpha-Beta Pruning
• 2.13. Sắp xếp ưu tiên các nước đi
• 2.14. Cải tiến hàm đánh giá
• 2.15. Thuật toán Minimax trước và sau khi cải tiến
• 3. CHƯƠNG 3: KẾT QUẢ ĐẠT ĐƯỢC
• 3.1. Trò chơi cờ vua tương tác đầy đủ
• 3.2. Các thuật toán sử dụng trong chương trình
• 3.3. Đánh giá hiệu quả của bot
• 3.4. Đối đầu với người chơi
• 3.5. Đối đầu với bot
• 3.6. Tài nguyên sử dụng
• 3.7. Ưu điểm và nhược điểm của bot chơi cờ vua
• TÀI LIỆU THAM KHẢO
• Danh mục hình ảnh và bảng biểu
• Danh mục các từ viết tắt và thuật ngữ

Tóm tắt

I. Tổng Quan Về Đồ Án Xây Dựng Bot Chơi Cờ Vua Chess AI

Cờ vua là một trò chơi trí tuệ phổ biến trên toàn thế giới, với lịch sử lâu đời và vẫn được yêu thích. Nó rèn luyện tư duy chiến lược, khả năng dự đoán và ra quyết định. Việc xây dựng bot chơi cờ vua (Chess AI) không chỉ nâng cao khả năng chơi cờ của con người mà còn mở ra cơ hội khám phá sâu hơn về trò chơi này. Đồ án này tập trung vào việc xây dựng một bot cờ vua có khả năng chơi ở mức độ chuyên nghiệp, sử dụng các thuật toán trí tuệ nhân tạo (AI) và học máy (Machine Learning). Mục tiêu là tạo ra một AI cờ vua có thể học hỏi từ cách chơi của người chơi, cải thiện liên tục và trở thành một đối thủ đáng gờm, đồng thời cung cấp một công cụ hữu ích cho việc học tập và nghiên cứu về cờ vua. Khóa luận tập trung vào việc ứng dụng các thuật toán, cải thiện hiệu suất và đánh giá hiệu quả sau khi cải tiến. Chương 1: Tổng quan về cờ vua và các thuật toán sử dụng trong lập trình game Cờ Vua; Chương 2: Xây dựng giao diện chơi cờ vua trên Unity Engine, xử lý dữ liệu và xây dựng bot; Chương 3: Kết quả đạt được.

1.1. Tại Sao Xây Dựng Bot Cờ Vua Lại Quan Trọng

Xây dựng bot chơi cờ vua đòi hỏi sự kết hợp của nhiều lĩnh vực như trí tuệ nhân tạo, máy học, và xử lý ngôn ngữ tự nhiên. Nghiên cứu và phát triển bot chơi cờ giúp mở rộng kiến thức và hiểu biết về các kỹ thuật và thuật toán trong những lĩnh vực này. Cờ vua là một trò chơi phức tạp với không gian trạng thái rộng lớn, đòi hỏi khả năng đánh giá và quyết định tốt. Bot chơi cờ có thể được áp dụng trong nhiều lĩnh vực khác như lập kế hoạch, tối ưu hóa và quyết định tự động trong quản lý, giao thông, và tài chính. Công nghệ phát triển từ việc xây dựng bot chơi cờ vua có thể được áp dụng trong nhiều lĩnh vực khác. Ví dụ, các thuật toán tìm kiếm và quyết định trong cờ vua có thể được áp dụng trong lập kế hoạch, tối ưu hóa và quyết định tự động trong các lĩnh vực như quản lý, giao thông và tài chính. Việc xây dựng bot chơi cờ vua không chỉ có tầm quan trọng trong việc nâng cao hiệu suất chơi cờ và mở rộng kiến thức về trí tuệ nhân tạo, mà còn đóng góp vào việc thách thức các thuật toán và kỹ thuật trong lĩnh vực này và tạo ra ứng dụng trong các lĩnh vực khác.

1.2. Mục Tiêu Của Đồ Án Phát Triển Chess AI

Mục tiêu chính của đồ án này là xây dựng một bot chơi cờ vua có khả năng chơi ở mức độ chuyên nghiệp. Bot này sẽ có khả năng học hỏi từ cách chơi của người chơi và cải thiện khả năng chơi cờ vua của chính nó. Nghiên cứu tập trung vào việc ứng dụng thuật toán, cải thiện hiệu suất thuật toán và đánh giá hiệu suất sau khi cải thiện thuật toán. Nghiên cứu tập trung vào việc ứng dụng thuật toán, cải thiện hiệu suất thuật toán và đánh giá hiệu suất sau khi cải thiện thuật toán. Chương 1 trình bày tổng quan về cờ vua và các thuật toán được sử dụng. Chương 2 mô tả quy trình xây dựng giao diện trò chơi trên Unity Engine, xử lý dữ liệu và xây dựng bot. Chương 3 trình bày kết quả đạt được.

II. Thuật Toán Minimax Nền Tảng Xây Dựng Bot Chơi Cờ Vua

Thuật toán Minimax là một phương pháp tìm kiếm trong cây trò chơi, được sử dụng để đánh giá các nước đi tiếp theo và tìm ra nước đi tốt nhất cho một trạng thái cụ thể. Thuật toán này đánh giá các nước đi dựa trên giả định rằng đối thủ sẽ chọn nước đi tối ưu nhất để gây thiệt hại lớn nhất cho mình. Minimax sử dụng một cây tìm kiếm để duyệt qua các nước đi tiếp theo và đánh giá chúng. Cây tìm kiếm bao gồm các nút đại diện cho trạng thái của trò chơi và các cạnh đại diện cho nước đi. Bằng cách duyệt cây tìm kiếm, Minimax có thể xác định nước đi tốt nhất. Tuy nhiên, nếu chỉ sử dụng thuật toán Minimax, chương trình có thể trở nên rất tốn thời gian và tài nguyên tính toán bởi số lượng nút lớn và thời gian tính toán lâu. Do đó, cần sử dụng các kỹ thuật cải tiến thuật toán Minimax để làm tăng hiệu suất tìm kiếm và giảm độ phức tạp.

2.1. Cách Hoạt Động Của Thuật Toán Minimax Trong Cờ Vua

Minimax hoạt động bằng cách xây dựng một cây trạng thái trò chơi, trong đó mỗi nút đại diện cho một trạng thái bàn cờ sau một nước đi. Thuật toán gán một giá trị cho mỗi nút, thể hiện độ tốt của trạng thái đó đối với người chơi. Giá trị này thường được tính toán bằng một hàm đánh giá (evaluation function). Sau đó, thuật toán thực hiện đệ quy trên cây, chọn nước đi tối đa hóa giá trị cho người chơi (MAX) và tối thiểu hóa giá trị cho đối thủ (MIN). Quá trình này lặp lại cho đến khi đạt đến độ sâu tìm kiếm định trước hoặc một trạng thái kết thúc (thắng, thua, hòa). Cuối cùng, thuật toán trả về nước đi tốt nhất tại nút gốc của cây.

2.2. Hạn Chế Của Minimax và Giải Pháp Khắc Phục

Mặc dù Minimax là một thuật toán mạnh mẽ, nó có một số hạn chế, đặc biệt là trong các trò chơi phức tạp như cờ vua: Tốn kém về mặt tính toán: Số lượng trạng thái cần xem xét tăng theo cấp số nhân với độ sâu tìm kiếm, dẫn đến thời gian tính toán lớn. Để giải quyết vấn đề này, có thể sử dụng các kỹ thuật cắt tỉa như Alpha-Beta Pruning, giúp loại bỏ các nhánh không cần thiết trong cây tìm kiếm. Giới hạn độ sâu tìm kiếm: Do giới hạn về thời gian tính toán, độ sâu tìm kiếm thường bị giới hạn, có thể bỏ qua các nước đi quan trọng nằm sâu trong cây. Sử dụng Iterative Deepening có thể giúp tìm kiếm sâu hơn mà vẫn đảm bảo thời gian phản hồi. Đánh giá tĩnh: Minimax thường sử dụng một hàm đánh giá tĩnh để đánh giá các trạng thái, nhưng hàm này có thể không chính xác trong mọi tình huống. Sử dụng Quiescence Search có thể giúp mở rộng tìm kiếm trong các trạng thái không ổn định, cải thiện độ chính xác của đánh giá.

2.3. Cải Tiến Thuật Toán Minimax Bằng Alpha Beta Pruning

Alpha-Beta Pruning là một kỹ thuật cải tiến quan trọng của thuật toán Minimax, giúp giảm đáng kể số lượng trạng thái cần xem xét. Kỹ thuật này hoạt động bằng cách theo dõi hai giá trị: alpha (giá trị tốt nhất đã tìm thấy cho người chơi MAX) và beta (giá trị tốt nhất đã tìm thấy cho người chơi MIN). Trong quá trình tìm kiếm, nếu một nút có giá trị nhỏ hơn alpha (đối với người chơi MIN) hoặc lớn hơn beta (đối với người chơi MAX), thì nhánh đó có thể bị cắt tỉa, vì nó không thể ảnh hưởng đến kết quả cuối cùng.

III. Openings Book Tối Ưu Hóa Khai Cuộc Cho Bot Cờ Vua

Trong cờ vua, các nước đi mở đầu và chiến thuật mà người chơi thực hiện ở giai đoạn đầu game khá quan trọng, quyết định vị trí ban đầu của các quân cờ và có thể ảnh hưởng lớn đến diễn biến và kết quả trận đấu. Có hàng trăm kiểu khai cuộc và biến thể khác nhau, mỗi kiểu dẫn đến những lối chơi độc đáo và chiến thuật riêng. Để bot có thể mở đầu trận đấu một cách ổn định và đa dạng, khóa luận này sử dụng Openings Book - thường được sử dụng trong các trận đấu của các máy tính chơi cờ vua.

3.1. Openings Book Là Gì và Tại Sao Cần Thiết

Openings Book (sách khai cuộc) là một tập hợp các nước đi khai cuộc được lưu trữ sẵn, thường được sử dụng trong các chương trình cờ vua máy tính. Thay vì tính toán từ đầu mỗi nước đi, bot có thể tra cứu trong Openings Book để chọn các nước đi phổ biến và đã được nghiên cứu kỹ lưỡng. Điều này giúp bot có một khởi đầu vững chắc, tránh các sai lầm ngớ ngẩn và tiết kiệm thời gian tính toán.

3.2. Xây Dựng và Sử Dụng Openings Book Hiệu Quả

Xây dựng Openings Book đòi hỏi thu thập dữ liệu từ các nguồn uy tín như cơ sở dữ liệu các ván đấu của các kỳ thủ hàng đầu, các sách khai cuộc nổi tiếng, và kết quả phân tích của các chuyên gia. Dữ liệu này được lưu trữ dưới dạng cây khai cuộc, với mỗi nút đại diện cho một trạng thái bàn cờ và các cạnh đại diện cho các nước đi. Khi sử dụng Openings Book, bot sẽ tra cứu trong cây khai cuộc để tìm nước đi phù hợp. Nếu trạng thái hiện tại của bàn cờ không có trong Openings Book, bot sẽ chuyển sang sử dụng các thuật toán tìm kiếm khác (như Minimax) để tính toán.

3.3. Lựa Chọn Nước Đi Từ Openings Book

Đầu tiên, cần tách file thành các mục riêng biệt. Chia các chuỗi nước đi thành các chuỗi con sử dụng “pos” làm ngăn cách, lưu vào Span dưới tên entries. Sử dụng vòng lặp for lặp qua các entries. Các entries được chia thành các dòng sử dụng “ ” làm phân cách, entries đầu tiên được gán cho một biến string đặt tên là positionFen. Các dòng còn lại được lưu trữ trong Span có tên allMoveData. Duyệt allMoveData, chia dữ liệu thành các chuỗi con ngăn cách với nhau bởi khoảng trắng (‘ ‘). Chuyển đổi các chuỗi con từ dạng string sang dạng int và lưu trong mảng bookMoves với chỉ số moveIndex tương ứng. Đoạn code này trích xuất dữ liệu nước đi từ file “Book.txt” và lưu trữ chúng như một từ điển các nước đi.

IV. Cải Thiện Hàm Đánh Giá Để Nâng Cao Chess AI

Trong thuật toán Minimax, hàm đánh giá đóng vai trò quan trọng trong việc xác định độ tốt của một trạng thái bàn cờ. Một hàm đánh giá tốt sẽ giúp bot đưa ra các quyết định chính xác và hiệu quả hơn. Cải thiện hàm đánh giá là một trong những cách quan trọng nhất để nâng cao sức mạnh của Chess AI.

4.1. Các Yếu Tố Cần Cân Nhắc Trong Hàm Đánh Giá

Hàm đánh giá cần cân nhắc nhiều yếu tố, bao gồm: Giá trị quân cờ: Các quân cờ khác nhau có giá trị khác nhau (ví dụ: hậu > xe > tượng/mã > tốt). Vị trí quân cờ: Vị trí của quân cờ trên bàn cờ có thể ảnh hưởng đến sức mạnh của nó (ví dụ: quân cờ ở trung tâm thường mạnh hơn quân cờ ở rìa). Cấu trúc tốt: Cấu trúc của các quân tốt trên bàn cờ có thể ảnh hưởng đến khả năng tấn công và phòng thủ. An toàn vua: Bảo vệ vua là ưu tiên hàng đầu. Khả năng di chuyển: Số lượng nước đi hợp lệ mà một quân cờ có thể thực hiện. Kiểm soát không gian: Kiểm soát không gian trên bàn cờ có thể giúp tạo ra các cơ hội tấn công.

4.2. Áp Dụng Thông Tin Chiến Thuật Vào Hàm Đánh Giá

Ngoài các yếu tố cơ bản, có thể bổ sung thông tin chiến thuật vào hàm đánh giá để cải thiện độ chính xác. Ví dụ: Giá trị của các quân nặng (hậu, xe) có thể tăng lên ở giai đoạn cuối trận đấu. Có thể ưu tiên đưa quân tốt phong hậu để gia tăng sức mạnh. Nên ưu tiên kiểm soát trung tâm, tìm cách đưa quân Tốt phong Hậu để gia tăng sức mạnh của quân mình. Các yếu tố đánh giá: + Số lượng quân cờ trên bàn. + Ước lượng khoảng cách giữa midgame và endgame. + Khả năng di động của quân cờ + Số lượng quân tốt trên từng hàng, từng cột. + Khả năng di chuyển của quân cờ + Kiểm tra số lượng quân tốt trên từng hàng, từng cột + Kiểm tra vị trí Vua. + Kiểm tra số lượng quân tốt trên từng hàng, từng cột.

4.3. Thêm các yếu tố đánh giá trạng thái cờ

Để cải thiện độ chính xác của khả năng đánh giá, cần bổ sung thông tin chiến thuật, theo giai đoạn của trận đấu, giá trị của những quân nặng chủ lực như Hậu và Xe càng có giá trị lớn hơn. Ở giai đoạn sau, có thể hi sinh những quân cờ có giá trị thấp hoặc ít khả năng di chuyển đổi lại ăn được những quân cờ có giá trị cao của đối thủ cũng có thể thay đổi cục diện cả bàn cờ.

V. Quiescence Search Giải Quyết Trạng Thái Bất Định Chess AI

Trong thuật toán Minimax, việc dừng tìm kiếm ở một độ sâu cố định có thể dẫn đến các đánh giá không chính xác, đặc biệt là khi gặp phải các 'trạng thái bất định' (ví dụ: khi có thể ăn quân, chiếu tướng). Quiescence Search là một kỹ thuật giúp giải quyết vấn đề này bằng cách tiếp tục tìm kiếm cho đến khi đạt được một trạng thái 'yên tĩnh' (ví dụ: không có thể ăn quân hoặc chiếu tướng).

5.1. Trạng Thái Bất Định Trong Cờ Vua Là Gì

Một trạng thái bất định là một trạng thái mà giá trị của nó có thể thay đổi đáng kể chỉ sau một vài nước đi. Ví dụ, một trạng thái mà một quân cờ đang bị đe dọa ăn, hoặc một trạng thái mà có thể chiếu tướng. Việc dừng tìm kiếm ở một độ sâu cố định trong một trạng thái bất định có thể dẫn đến đánh giá sai, vì thuật toán không thể thấy được các hậu quả của các nước đi tiếp theo.

5.2. Cơ Chế Hoạt Động Của Quiescence Search

Quiescence Search hoạt động bằng cách mở rộng tìm kiếm trong các trạng thái bất định cho đến khi đạt được một trạng thái yên tĩnh. Trạng thái yên tĩnh là một trạng thái mà không có thể ăn quân hoặc chiếu tướng. Khi đạt được một trạng thái yên tĩnh, thuật toán có thể đánh giá trạng thái đó một cách chính xác hơn.

5.3. Kết hợp Quiescence Search vào bot cờ vua

Khi kết hợp Quiescence Search vào bot cờ vua thì bot tiếp tục tìm kiếm trong các trạng thái yên lặng như khi có các nước đi bắt buộc, các nước đi chiếm quân, hoặc các nước đi có thể gây thay đổi đáng kể đối với giá trị đánh giá. Kết hợp Quiescence Search giúp tránh hiện tượng "trạng thái bất định" và đảm bảo kết quả tìm kiếm chính xác hơn.

VI. Kết Quả Đánh Giá Hiệu Quả Của Chess AI

Chương này trình bày về kết quả xây dựng bot chơi cờ, giao diện chơi cờ vua trực quan được xây dựng bằng Unity Engine với ngôn ngữ C#, các thuật toán sử dụng, đánh giá hiệu suất thuật toán. Bao gồm đánh giá khả năng của Chess AI khi đối đầu với người chơi và các bot khác.

6.1. Giao Diện Trò Chơi Tương Tác Hoàn Chỉnh

Màn hình giao diện trò chơi bao gồm: - Bàn cờ - Thông tin trò chơi - Thông tin về bot - Các nút bấm điều chỉnh bot với 2 chế độ được thiết lập sẵn: + Smart Preset: Độ sâu khởi đầu 6 (tính trước 6 nước đi) + Fast Preset: Độ sâu khởi đầu 4 (tính trước 4 nước đi) - Game Settings với các chức năng Load Game, Copy trạng thái bàn cờ hiện tại. - Màn hình Game Over có các chức năng: chơi lại, xem lại kết thúc game, lưu quá trình trận đấu. Bằng cách sử dụng nút View Game và Undo Move, người chơi có thể xem lại trận đấu và rút kinh nghiệm từ trận đấu đó.

6.2. Thuật Toán Sử Dụng Trong Chương Trình

Thuật toán Minimax là một trong những thuật toán quan trọng và phổ biến trong việc lập trình những bot chơi cờ vua, tuy nhiên nó vẫn còn khá nhiều nhược điểm. Các thuật toán đưa ra tập trung vào việc khắc phục các nhược điểm của thuật toán này: Độ phức tạp thời gian, Giới hạn độ sâu tìm kiếm, Thuật toán Minimax luôn giả định đối thủ đưa ra nước đi tối ưu nhất, Hiệu suất của thuật toán phụ thuộc rất lớn vào cách xây dựng hàm đánh giá.

6.3. Hiệu Năng CPU RAM

Chương trình chơi cờ vua có tổng dung lượng nhỏ hơn 78.2MB được chạy trên máy tính cá nhân sử dụng CPU Intel Core i7-10750H 2.60GHz và 8GB RAM. Qua quá trình sử dụng để chơi cờ, chương trình chỉ sử dụng từ 140MB đến 400MB bộ nhớ RAM tuỳ theo mức độ sử dụng bot. Với mức độ đơn giản nhất, Low Iterative Deepening, bot chỉ sử dụng dưới 20% CPU. Với mức độ cao hơn, Normal Iterative Deepening, bot sử dụng khoảng 25% đến 50% CPU. Với High Iterative Deepning, bot sử dụng trên 50% CPU, tuy nhiên sẽ xảy ra hiện tượng Not Responding. Có thể thấy, nếu sử dụng một CPU cao cấp hơn, chương trình sẽ hoạt động tốt mà không ảnh hưởng đến việc tính toán của bot.

Trích đoạn nội dung tài liệu

mở đầu trận đấu một cách ổn định và đa dạng, khoá luận này sử dụng Openings Book - thường được sử dụng trong các trận đấu của các máy tính chơi cờ vua. Openings Book hay còn gọi là sách khai cuộc, là một tập hợp các nước đi khai cuộc được lưu trữ dưới dạng: pos “vị trí các quân cờ” “lượt đi tiếp theo” “trạng thái nhập thành” “en passant” “nước đi” “tần suất nước đi được sử dụng” Ví dụ: pos rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - e2e4 243109 Những thông tin trên được hiểu như sau: “rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR” - biểu diễn các quân cờ trên bàn cờ. Chữ thường biểu thị quân đen, chữ hoa biểu thị quân trắng. “w” - nước đi tiếp theo là của quân trắng.

“-” không thể thực hiện “en passant” “e2e4 243109” - Tốt trắng di chuyển từ e2 đến e4, 243109 chỉ ra tần suất nước đi này được thực hiện trong các nghiên cứu trước đây.6 Thuật toán đọc dữ liệu từ Openings Book Đầu tiên, cần tách file thành các mục riêng biệt. Chia các chuỗi nước đi thành các chuỗi con sử dụng “pos” làm ngăn cách, lưu vào Span<string> dưới tên entries. Sử dụng vòng lặp for lặp qua các entries. Các entries được chia thành các dòng sử dụng “\n” làm phân cách, entries đầu tiên được gán cho một biến string đặt tên là positionFen.

Các dòng còn lại được lưu trữ trong Span<string> có tên allMoveData. Duyệt allMoveData, chia dữ liệu thành các chuỗi con ngăn cách với nhau bởi khoảng trắng (‘ ‘). Chuyển đổi các chuỗi con từ dạng string sang dạng int và lưu trong mảng bookMoves với chỉ số moveIndex tương ứng. Đoạn code này trích xuất dữ liệu nước đi từ file “Book.txt” và lưu trữ chúng như một từ điển các nước đi.

Với một khởi đầu ổn định, Bot có thể dễ dàng tiến vào giai đoạn sau của trận đấu với vô số khả năng. Tuy nhiên, cần phải tính toán kỹ lưỡng, tận dụng các lợi thế để lập kế hoạch cho việc đưa quân cờ vào các vị trí thuận lợi. Với thuật toán Minimax, có thể tìm kiếm qua tất cả các nước đi tiếp theo có thể xảy ra và đánh giá chúng để đưa ra nước đi tốt nhất. Thuật toán Minimax Minimax [9] sử dụng một cây tìm kiếm để duyệt qua các nước đi tiếp theo và đánh giá chúng.

Cây tìm kiếm bao gồm các nút đại diện cho trạng thái của trò chơi và các cạnh đại diện cho nước đi. Bằng cách duyệt cây tìm kiếm, Minimax có thể xác định nước đi tốt nhất.7 Lưu đồ thuật toán Minimax - Bắt đầu từ trạng thái hiện tại của bàn cờ, tạo cây trò chơi bằng cách tạo tất cả các nước đi có thể, mỗi node đại diện cho một trạng thái của bàn cờ. - Đánh giá trạng thái mỗi nút theo góc nhìn của người chơi dựa trên các tiêu chí: + Giá trị của các quân cờ: Mỗi quân cờ được gán giá trị dựa trên độ mạnh yếu của quân cờ. + Vị trí chiến lược của các quân cờ: Dựa trên giá trị cơ bản của các quân cờ, đánh giá giá trị hiện tại của các quân cờ theo vị trí trên bàn cờ.

Càng gần trung tâm bàn cờ và các vị trí dẫn đến chiến thắng (gần vua đối thủ hoặc ở vị trí có thể gây nguy hiểm cho vua đối thủ) càng tăng cao giá trị của quân cờ. + Cấu trúc bàn cờ: Thể hiện sự cân bằng giữa phòng thủ và tấn công của người chơi. Đánh giá dựa trên sự phát triển của quân cờ (giá trị hiện tại), số lượng quân cờ trên bàn, sự an toàn của vua, sự liên kết giữa các quân cờ. + Tiềm năng tấn công và phòng thủ: Đánh giá dựa trên sự bảo vệ vua của các quân cờ, khả năng tấn công các quân cờ quan trọng và bảo vệ các quân cờ đồng minh.

16 + Tiến độ trò chơi: Đánh giá tiến độ trò chơi (Khai cuộc, trung cuộc, tàn cuộc) dựa trên số quân cờ đã mất, sự thay đổi trong cấu trúc bàn cờ, khả năng tấn công của mỗi người chơi. - Đệ quy Minimax: Bắt đầu từ nút gốc của cây, thực hiện đệ quy Minimax để đánh giá tất cả các nút con + Nếu nút là một trạng thái kết thúc của trận đấu (hoà hoặc chiếu hết), trả về giá trị của trạng thái đó. + Nếu nút là lượt đi của người chơi hiện tại, chọn giá trị tối đa của các node con. + Nếu nút là lượt đi của đối thủ, chọn giá trị tối thiểu của các node con.

Sau khi đệ quy Minimax, chọn nước đi tối ưu từ nút gốc của cây dựa trên giá trị tối đa hoặc tối thiểu đã tính toán từ các nút. Tuy nhiên, nếu chỉ sử dụng thuật toán Minimax, chương trình có thể trở nên rất tốn thời gian và tài nguyên tính toán bởi số lượng nút lớn và thời gian tính toán lâu. Do đó, cần sử dụng các kỹ thuật cải tiến thuật toán Minimax để làm tăng hiệu suất tìm kiếm và giảm độ phúc tạp. Cải tiến thuật toán Minimax 2.

Alpha-Beta Pruning - Alpha-Beta Pruning [10] : sử dụng hai giá trị là alpha và beta để đánh giá các nút trong cây tìm kiếm, giá trị alpha là tốt nhất với người chơi hiện tại, beta là giá trị tốt nhất cho đối thủ. Alpha-Beta Pruning hoạt động theo cách sau: 1. Bắt đầu từ gốc của cây tìm kiếm. Duyệt qua các nút con theo thứ tự từ trái qua phải và thực hiện đệ quy.

Khi đệ quy đến một nút, kiểm tra giá trị alpha và beta hiện tại và các giá trị thu được từ các nút đã duyệt qua. Nếu alpha tại nút hiện tại lớn hơn hoặc bằng beta, đối thủ chắc chắn sẽ không chọn vì nó tốt hơn những nốt trước đó. Do đó, ta có thể cắt tỉa nhánh này và không cần duyệt qua các nút con còn lại. Nếu beta nhỏ hơn hoặc bằng alpha, người chơi chắc chắn sẽ không chọn vì nó tốt hơn những nút trước đó.

Do đó, ta cũng có thể cắt tỉa nhánh này và không cần duyệt qua những nút con còn lại. Cập nhật giá trị alpha và beta tại nút hiện tại. Lặp lại các bước trên cho tất cả nút con còn lại 17 Hình 2.8 Kỹ thuật Alpha-Beta Pruning Áp dụng kỹ thuật Alpha-Beta Pruning mang lại lợi ích đáng kể trong quá trình xây dựng bot, tuy nhiên vẫn còn có thể tối ưu hiệu suất của bot. Transposition Table Theo một bài báo của Ernst A.

Heinz cung cấp cái nhìn về việc quản lý hiệu quả Transposition Table trong các ứng dụng thực tế, ta có thể áp dụng để nâng cao hiệu suất của bot cờ vua. [11] Trong quá trình tìm kiếm, thuật toán Minimax thường phải duyệt qua rất nhiều nút có cùng trạng thái. Điều đó dẫn đến việc phải tính toán lại các giá trị đánh giá cho những trạng thái đó, gây lãng phí thời gian và tài nguyên tính toán. Transposition Table là một cấu trúc dữ liệu được sử dụng trong thuật toán Minimax để lưu trữ và tái sử dụng các giá trị đã tính toán trong quá trình tìm kiếm.

Các giá trị đánh giá cho mỗi trạng thái của bàn cờ được lưu trữ. Khi duyệt một nút mới, nếu trạng thái này đã được lưu trữ trong Transposition Table, có thể sử dụng lại giá trị đã được đánh giá mà không cần tính toán lại. Transposition Table lưu trữ các cặp key-value, trong đó key là trạng thái và value là giá trị được đánh giá của trạng thái đó. Tuy nhiên, sử dụng Transposition Table cần lưu ý về kích thước bộ nhớ và cập nhật các giá trị khi trạng thái thay đổi.

Để khắc phục vấn đề này, chỉ lưu trữ đối với các nước đi gần tốt nhất, không lưu trữ các giá trị mang lại lợi ích lớn cho đối thủ. Do cờ vua là một trò chơi có không gian trạng thái lớn, khi bàn cờ tiến vào trạng thái khác, thay thế giá trị của các trạng thái được lưu trữ bằng giá trị của các trạng thái mới để đảm bảo tính chính xác của thông tin đã lưu trữ.9 Tạo transposition table và làm trống các trạng thái cũ Tham số size đại diện cho kích thước bộ nhớ được cấp cho bảng. Mảng positions được khởi tạo để lưu trữ các vị trí trong bảng với kích thước là positionCount. Phương thức Clear() dụng để xoá toàn bộ dữ liệu trong bảng.

Đảm bảo rằng toàn bộ dữ liệu được xoá và chuẩn bị sẵn sàng lưu trữ dữ liệu mới. Nếu hai hoặc nhiều trạng thái có cùng giá trị có thể dẫn đến xung đột dẫn đến sai sót trong đánh giá. Number of Positions 105 106 107 108 109 1010. Số lượng bit cần thiết để giảm xác suất xung đột trong Transposition Table 2.

Sắp xếp ưu tiên các nước đi Cây tìm kiếm của thuật toán Minimax đem lại rất nhiều nước đi, tuy nhiên, thay vì duyệt qua các nước đi cố định, ta có thể sắp xếp các nước đi dựa trên một số tiêu chí để đưa những nước đi tiềm năng nhất lên đầu danh sách. Sử dụng các tiêu chí đánh giá sau: - Ưu tiên các nước đi kiểm soát trung tâm bàn cờ. Trung tâm bàn cờ là vị trí quan trọng trong cờ vua, chiếm được quyền kiểm soát trung tâm bàn cờ sẽ đem lại lợi thế về không gian và khả năng tấn công. 19 - Sau khi kiểm soát được trung tâm bàn cờ, ưu tiên những nước đi có khả năng ăn quân đối thủ, sắp xếp theo giá trị của các quân bị tấn công.10 Thuật toán sắp xếp thứ tự ưu tiên các nước đi Hàm nhận một đối tượng board đại diện cho trạng thái hiện tại của bàn cờ.

Biến remainingMaterial tính toán giá trị quân cờ còn lại trên bàn cờ. Biến interpFactor được tính toán bằng cách chia tỉ lệ quân cờ còn lại trên bàn cờ cho giá trị quân cờ tối đa. Giá trị này được tạo ra để đánh giá giai đoạn giữa trận và cuối trận. 20 Mảng m được khởi tạo với kích thước bằng số lượng các nước đi có thể trong trạng thái hiện tại của bàn cờ.

Sử dụng vòng lặp để duyệt qua các nước đi có thể. Trong mỗi vòng lặp, điểm đánh giá score của mỗi nước đi được tính toán dựa trên các yếu tố như loại quân cờ, việc bắt quân, phong Hậu, vị trí và các yếu tố khác. Các điểm đánh giá score được lưu trữ cùng với nước đi tương ứng trong mảng m. Mảng m được sắp xếp theo thứ tự giảm dần của điểm đánh giá.

Danh sách các nước đi được sẽ được trả về dưới dạng một danh sách, chọn ra nước đi từ mảng m và bỏ qua điểm đánh giá. Cải tiến hàm đánh giá Dựa trên các yếu tố đánh giá trạng thái của bàn cờ, bổ sung thông tin chiến thuật để cải thiện độ chính xác của khả năng đánh giá.