Chương 1 GIỚI THIỆU: giới thiệu chung về đề tài, mục tiêu nghiên cứu, giới hạn đề tài, phương pháp nghiên cứu, đối tượng và phạm vi nghiên cứu. - Chương 2 CƠ SỞ LÝ THUYẾT: giới thiệu về tình hình nghiên cứu, hướng nghiên cứu, các công nghệ đang được sử dụng liên quan đến chơi cờ. - Chương 3 THIẾT KẾ HỆ THỐNG: trình bày mô hình tổng quan của hệ thống, các khối của hệ thống, thiết kế chi tiết từng khối và các thiết bị được sử dụng trong từng khối, các phần mềm sử dụng trong hệ thống. - Chương 4 KẾT QUẢ: trình bày kết quả thực hiện của mô hình hệ thống, bao gồm cả việc chơi cờ và đánh giá hiệu suất của robot.
- Chương 5 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN: rút ra các kết luận từ nghiên cứu, và đề xuất các hướng phát triển tiếp theo. 2 Chương 2 CƠ SỞ LÝ THUYẾT 2.1 GIỚI THIỆU VỀ STOCKFISH 2.1 Khái niệm Stockfish là một chương trình cờ vua mạnh nhất thế giới, được phát triển bởi một nhóm lập trình viên tình nguyện từ khắp nơi trên thế giới. Nó được coi là một trong những hệ thống trí tuệ nhân tạo mạnh nhất hiện nay, luôn đứng đầu các giải đấu cờ vua máy tính. 1 Logo chương trình cờ vua Stockfish [16] Stockfish sử dụng một số thuật toán chính để đạt được sức mạnh cờ vua phi thường của mình: • Thuật toán Alpha-Beta Pruning: Đây là một thuật toán tìm kiếm cây, cho phép Stockfish xem xét một không gian tìm kiếm lớn một cách hiệu quả hơn so với các thuật toán tìm kiếm cổ điển khác.
• Quản lý bộ nhớ và cache: Stockfish sử dụng các kỹ thuật quản lý bộ nhớ tinh vi để tối ưu hóa tốc độ truy xuất dữ liệu, giúp nó có thể phân tích vị thế cờ nhanh chóng. • Đánh giá vị thế (Position Evaluation): Stockfish sử dụng một hàm đánh giá vị thế cực kỳ phức tạp, bao gồm hàng trăm tham số được tinh chỉnh thông qua huấn luyện trên dữ liệu ván cờ. 3 • Quản lý cây tìm kiếm (Minimax Search): Stockfish sử dụng các kỹ thuật như transposition tables, history heuristics và killer moves để quản lý và tối ưu hóa cây tìm kiếm, giúp tăng tốc độ tính toán. Bắt đầu với Stockfish 12 (2020), chức năng đánh giá bảng mạng thần kinh đã được tích hợp.2 Biểu đồ đánh giá quá trình phát triển theo thời gian của Stockfish Chương trình cờ vua Stockfish chiếm lĩnh top 1 trong nhiều năm do sự cải tiến thuật toán và áp dụng mô hình nơ ron mới dành riêng cho đánh cờ vua.
Sự tiến bộ Elo của Stockfish trong hành trình 10 năm đầu được thể hiển qua hình sau: Hình 2. 2 Sơ đồ thể hiện sự tiến bộ điểm Elo của Stockfish theo thời gian trong hơn 10 năm qua [18] 4 2.2 GIỚI THIỆU MẠNG NƠ RON THẦN KINH CÓ THỂ CẬP NHẬT HIỆU QUẢ (EFFICIENTLY UPDATABLE NEURAL NETWORKS - NNUE) 2.1 Khái niệm mạng nơ ron thần kinh có thể cập nhật hiệu quả (NNUE) Mạng nơ ron thần kinh có thể cập nhật hiệu quả (NNUE) là một kiến trúc mạng nơ- ron tận dụng sự thay đổi tối thiểu trong các đầu vào của mạng giữa các lần đánh giá liên tiếp. Nó được phát minh cho Shogi bởi Yu Nasu, được tích hợp vào YaneuraOu do Motohiro Isozaki phát triển vào tháng 5 năm 2018, và sau đó được đưa vào cờ vua cho Stockfish bởi Hisayori Noda vào tháng 6 năm 2019, nhưng có thể áp dụng cho nhiều trò chơi ván bài khác và thậm chí là trong các lĩnh vực khác. NNUE hoạt động dựa trên các nguyên tắc sau: [1][3] ● Mạng nên có số lượng đầu vào không phải 0 tương đối thấp.
● Các đầu vào nên thay đổi càng ít càng tốt giữa các lần đánh giá liên tiếp. ● Mạng nên đơn giản đủ để hỗ trợ suy luận độ chính xác thấp trong miền số nguyên. Tuân theo nguyên tắc 1 có nghĩa là khi mạng được mở rộng quy mô, đầu vào phải trở nên thưa thớt. Các kiến trúc tốt nhất hiện tại có mức độ thưa thớt đầu vào khoảng 0,1%.
Số lượng đầu vào không phải 0 nhỏ đặt ra một giới hạn trên thời gian cần thiết để đánh giá mạng trong trường hợp phải đánh giá toàn bộ. Đây là lý do chính khiến các mạng NNUE có thể lớn nhưng vẫn rất nhanh để đánh giá [1]. Tuân theo nguyên tắc 2 (với giả định rằng nguyên tắc 1 được tuân thủ) tạo ra một cách để hiệu quả cập nhật mạng (hoặc ít nhất là một phần tốn kém của nó) thay vì phải đánh giá lại toàn bộ. Điều này tận dụng việc một nước đi duy nhất chỉ thay đổi trạng thái bàn cờ một chút.
Điều này kém quan trọng hơn nguyên tắc thứ nhất và hoàn toàn không bắt buộc đối với các cài đặt để tận dụng, nhưng tuy nhiên vẫn mang lại một sự cải thiện đáng kể trong các cài đặt quan tâm đến việc sử dụng điều này [1]. Tuân theo nguyên tắc 3 cho phép đạt được hiệu suất tối đa trên phần cứng phổ biến và khiến mô hình đặc biệt phù hợp với suy luận CPU thời gian thực, điều này cần thiết cho các máy chơi cờ truyền thống [1]. Nhìn chung, các nguyên tắc NNUE cũng có thể áp dụng cho các mạng sâu tốn kém, nhưng chúng thể hiện rõ ràng trong các mạng nông nhanh, phù hợp với suy luận CPU thời 5 gian thực mà không cần batching và gia tốc. Hiệu suất mục tiêu là hàng triệu lần đánh giá mỗi giây mỗi luồng.
Đây là một trường hợp sử dụng cực đoan yêu cầu các giải pháp cực đoan, và quan trọng nhất là việc định lượng [1][2].2 Kiến trúc mạng nơ ron thần kinh có thể cập nhật hiệu quả (NNUE) Mạng nơ ron bao gồm bốn lớp. Lớp đầu vào được tham số hóa quá mức, nhận vào biểu diễn bàn cờ cho tất cả các vị trí quân vua của mỗi bên [18].1 Kiến trúc HalfKP Cấu trúc HalfKP bao gồm hai nửa, mỗi nửa tương ứng với một trong hai quân vua, giao thoa với nữa lớp ẩn đầu tiên về di chuyển hoặc không di chuyển. Với mỗi vị trí quân vua đen hoặc trắng, 10 quân không phải vua trên ô tương ứng là các đầu vào boolean {0,1}, cùng với một phần dư từ cờ Shogi (BONA_PIECE_ZERO), tổng cộng 64 x (64 x 10 + 1) = 41.024 đầu vào cho mỗi nửa, được nhân với một véc-tơ trọng số 16 bit để tạo ra 256 đầu ra cho mỗi nửa, tổng cộng 256 x 41. Như Ronald de Man đã nhấn mạnh trong một cuộc thảo luận trên diễn đàn CCC, các trọng số đầu vào được sắp xếp theo cách mà cấu hình quân cờ đảo ngược màu trong cả hai nửa chia sẻ cùng một chỉ số.
Tuy nhiên, và điều này cũng có vẻ là một phần dư từ cờ Shogi với đối xứng quay 180 độ trên bàn cờ 9x9, thay vì lật đứng (xor 56), việc xoay (xor 63) được áp dụng [18]. Hiệu quả của NNUE là do việc cập nhật dần đầu ra của lớp đầu vào trong các bước di chuyển, nơi chỉ một phần nhỏ các neuron cần được xem xét trong trường hợp di chuyển không phải vua. Ba lớp còn lại với 2x256x32, 32x32 và 32x1 trọng số thì tính toán ít tốn kém hơn, các lớp ẩn áp dụng kích hoạt ReLu, được tính toán tốt nhất bằng cách sử dụng các hướng dẫn SIMD phù hợp thực hiện tính toán véc-tơ số nguyên 8 bit/16 bit nhanh chóng, như MMX, SSE2 hoặc AVX2 trên x86/x86-64, hoặc, nếu có sẵn, AVX-512 [18]. 3 Các lớp NNUE trong hoạt động [18] Theo giải thích của Ronald de Man, người đã thực hiện việc port NNUE của Stockfish sang CFish [18]: • Bộ tích lũy (accumulator) có một nửa "vua trắng" và một nửa "vua đen", trong đó mỗi nửa là một vector 256 phần tử của các số nguyên 16-bit, tương đương với tổng của các trọng số của các đặc trưng "hoạt động" (pt, sq, ksq) cộng với một vector 256 phần tử của các độ lệch 16-bit.
• Bước "biến đổi" (transform) của việc đánh giá NNUE tạo ra một vector 512 phần tử của các số nguyên 8-bit, trong đó nửa đầu được tạo ra từ vector 256 phần tử của phía đi và nửa sau được tạo ra từ vector 256 phần tử của phía kia. Trong bước này, các phần tử 16-bit được cắt/giới hạn (clip/clamp) về một giá trị từ 0 đến 127. Đây là đầu ra của lớp đầu vào. • Vector 512 phần tử 8-bit này sau đó được nhân với một ma trận 32x512 các trọng số 8-bit để thu được một vector 32 phần tử các số nguyên 32-bit, và sau đó cộng thêm một vector các độ lệch 32-bit.
Các giá trị tổng này được chia cho 64 và cắt/giới 7 hạn về một vector 32 phần tử các số nguyên 8-bit từ 0 đến 127. Đây là đầu ra của lớp ẩn thứ nhất. • Vector 32 phần tử 8-bit thu được này được nhân với một ma trận 32x32 các trọng số 8-bit để thu được một vector 32 phần tử các số nguyên 32-bit, và sau đó cộng thêm một vector các độ lệch 32-bit khác. Các giá trị nguyên này lại được chia cho 64 và cắt/giới hạn về 32 số nguyên 8-bit từ 0 đến 127.
Đây là đầu ra của lớp ẩn thứ hai. • Vector 32 phần tử 8-bit này sau đó được nhân với một ma trận 1x32 các trọng số 8- bit (tức là thực hiện phép nhân vô hướng của hai vector). Điều này tạo ra một giá trị 32-bit, và một độ lệch 32-bit được cộng vào. Đây là đầu ra của lớp đầu ra.
• Đầu ra của lớp đầu ra được chia cho FV_SCALE = 16 để tạo ra đánh giá NNUE. Đánh giá của Stockfish sau đó thực hiện một số bước tiếp theo như cộng thêm một điểm thưởng Tempo (mặc dù đánh giá NNUE đã bao gồm thông tin về phía đi trong bước "biến đổi") và thu hẹp đánh giá về không khi rule50_count() tiến gần đến 50 nước.2 Kiến trúc HalfKA Trong các phiên bản Stockfish tiếp theo, kiến trúc mạng lưới đã được cải thiện thêm bởi Tomasz Sobczyk và cộng sự. Kiến trúc HalfKA sử dụng 12x64x64 = 45056 đầu vào cho mỗi trong 12 loại quân cờ, nhân với 64 ô vuông cho mỗi trong 64 ô của vua của mình, nhân với 2 vì cả hai phía đi và phía đối thủ, sử dụng lật dọc thay vì xoay HalfKP. HalfKAv2 được áp dụng trong Stockfish 14 tiết kiệm một số không gian khi xem xét sự dư thừa của ô vua bằng cách sử dụng 11x64x64 = 45056 đầu vào mỗi bên, được ánh xạ vào bộ chuyển đổi đặc trưng tuyến tính 2x520, sau đó trực tiếp cấp vào 8x2 đầu ra của bộ chuyển đổi đặc trưng này để học tốt hơn các cấu hình vật liệu không cân bằng.