Tổng quan
Trong bối cảnh phát triển của xã hội hiện đại, nhu cầu của con người ngày càng tăng cao nhằm nâng cao chất lượng cuộc sống Game đã trở thành một hình thức giải trí phổ biến và đang ngày càng phát triển đa dạng về thể loại.
Board game là thể loại trò chơi dễ tiếp cận và phù hợp với mọi lứa tuổi Chính vì vậy, chúng tôi đã quyết định phát triển một trò chơi Board game mang tên Cờ gánh.
Cờ gánh là một trò chơi dân gian ở Việt Nam, rất được ưa chuộng, khá hay và thú vị.
Trò chơi này đã tồn tại từ lâu với mục tiêu mang đến một trải nghiệm đơn giản và thú vị Nhóm phát triển đã cải biến một số quy tắc từ luật chơi hiện có, hy vọng rằng sự thay đổi này sẽ tạo ra sự hứng thú cho người chơi.
Mục tiêu đề tài nghiên cứu:
Tạo ra AI có thể hiểu luật chơi và thi đấu cờ với người chơi Tìm cách thắng được nhiều điểm nhất có thể Kèm theo đó AI phải:
-Luôn luôn đánh đúng theo luật của trò chơi.
-Tìm cách đi hiệu quả dựa trên các tiêu chí cho trước.
Cơ sở lý thuyết chung
Giới thiệu
Board Game là một trò chơi có bề mặt chơi (board) được chia thành các lĩnh vực với các phần tử di động Các phần này thường liên kết trực tiếp với người chơi, trong khi bề mặt chơi tạo ra một môi trường ngoài tầm kiểm soát của họ Người chơi di chuyển các phần tử trên bề mặt nhằm nắm bắt phần của đối thủ, đạt mục tiêu, giành quyền kiểm soát lãnh thổ hoặc thu thập hàng hóa giá trị Mối quan tâm chính của người chơi là phân tích mối quan hệ hình học giữa các phần trong trò chơi.
Bàn cờ là một bề mặt phẳng với 25 điểm giao nhau của lưới vuông 5x5, trên đó có các đường kẻ thể hiện các đường di chuyển hợp lệ cho quân cờ Các quân cờ của hai người chơi được bố trí ở rìa ngoài bàn cờ, với 16 quân chia thành hai màu: 8 quân màu xanh và 8 quân màu đỏ Mục tiêu của mỗi người chơi là ăn quân cờ của đối phương.
Trận cờ kết thúc khi:
+ Một người chơi không còn con cờ nào trên bàn, thì người kia sẽ chiến thắng
Nếu hai người chơi đạt đến số bước quy định mà chưa phân thắng thua, ví dụ như 200 bước, thì sẽ tiến hành đếm số cờ còn lại trên bàn cờ Người chơi nào còn nhiều cờ hơn sẽ được tuyên bố là người chiến thắng.
Luật chơi
Mỗi quân cờ di chuyển từng bước một theo đường thẳng hay đường kẽ đến giao điểm trống kế tiếp.
Có hai cách để ăn quân cờ của đối phương:
Hình 1 Hình ảnh một bàn cờ gánh
Hình 2 Mô tả cách di chuyển của một quân cờ
Gánh là một chiến thuật trong cờ, khi một quân cờ của phe này di chuyển vào vị trí giữa hai quân cờ của phe đối phương, dẫn đến việc cả hai quân cờ đó sẽ bị ăn Ví dụ, trong hình 3, quân cờ H di chuyển theo mũi tên xanh vào giữa hai quân đỏ N và Q, khiến cho hai quân đỏ này bị loại khỏi ván cờ.
Nhảy qua đầu để ăn : Một quân cờ ở vị trí E, có thể bay qua đầu quân cờ ở vị trí
J, và ăn mất quân cờ ở vị trí J.
Hình 3 Hình ảnh về cách Gánh để ăn hai quân cờ khác
Hình 4 Hình ảnh về cách Nhảy qua đầu quân cờ khác để ăn
Lý thuyết
3.1 Phân tích trò chơi Để biết những gì mong đợi từ một agent 1 , tốt nhất là có một số nghiên cứu toán học về Cờ Gánh được thực hiện trước khi phát triển AI để xác định các thuộc tính như hệ số phân nhánh và kích thước của không gian tìm kiếm, có nghĩa là số lượng trạng thái của trò chơi là duy nhất Các thuộc tính này có thể cho biết liệu có thể giải quyết hoàn toàn trò chơi hay không hoặc có bao nhiêu di chuyển một agent có thể được mong đợi tìm kiếm trước khi di chuyển.
3.2 Không gian trạng thái của trò chơi
Số lượng trạng thái khác nhau trong trò chơi Cờ Gánh rất quan trọng, vì nếu con số này nhỏ, trò chơi có thể được giải quyết bằng cách xác định một chiến lược thắng cho một trong các người chơi Để đạt được điều này, trước tiên chúng ta cần một công thức mô tả số cách mà một phần tử có thể được sắp xếp trên bảng trò chơi.
Game Cờ Gánh bắt đầu với 16 quân cờ trên bàn cờ 5x5, cho phép quân cờ đầu tiên được đặt ở 1 trong 25 vị trí Quân cờ thứ hai có thể được đặt ở 1 trong 24 vị trí còn lại, và quy trình này tiếp tục với các trạng thái bàn cờ còn lại có 15, 14 quân cờ, v.v Từ đó, ta có thể tính toán tổng số cách sắp xếp các quân cờ trên bàn cờ.
Yếu tố phân nhánh đóng vai trò quan trọng trong việc xác định số trạng thái mà một agent cần xem xét để tìm ra phương án di chuyển tối ưu trong trò chơi.
1 agent: một đối tượng chơi cờ một cách thông minh
Mặc dù hệ số phân nhánh không thể thay đổi cho mỗi trò chơi, nhưng thuật toán kiểm tra cây trò chơi có thể được điều chỉnh Việc này cho phép thuật toán loại bỏ một số trạng thái trước khi kiểm tra, dẫn đến việc hệ số phân nhánh giảm so với mức trung bình Bằng cách phân loại các trạng thái không thể dẫn đến bước đi tốt nhất, thuật toán có thể tập trung nhiều thời gian hơn vào những trạng thái khả thi, từ đó tối ưu hóa quá trình tìm kiếm và cải thiện hiệu quả.
3.4 Mạng nơron nhân tạo (Neural Networks)
3.4.1 Mạng nơron nhân tạo (Neural Networks) là gì?
Mạng nơron nhân tạo (Artificial Neural Network - ANN) là một mô hình xử lý thông tin mô phỏng cách thức hoạt động của các hệ nơron sinh học Nó bao gồm nhiều nơron kết nối qua các trọng số liên kết, hoạt động như một thể thống nhất để giải quyết các vấn đề cụ thể Mạng nơron nhân tạo được cấu hình cho các ứng dụng như nhận dạng mẫu và phân loại dữ liệu thông qua quá trình học từ tập mẫu huấn luyện, trong đó học chủ yếu là việc điều chỉnh trọng số liên kết giữa các nơron.
Cấu trúc neural nhân tạo:
Hình 5 Cấu tạo một Neural
Các thành phần cơ bản của một nơron nhân tạo bao gồm:
• Tập các đầu vào: Là các tín hiệu vào (input signals) của nơron, các tín hiệu này thường được đưa vào dưới dạng một vector N chiều.
Mỗi liên kết trong mạng nơ-ron được thể hiện qua trọng số liên kết (Synaptic weight), ký hiệu là wkj, giữa tín hiệu vào thứ j và nơron k Các trọng số này thường được khởi tạo ngẫu nhiên khi mạng bắt đầu và được cập nhật liên tục trong quá trình học.
• Bộ tổng (Summing function): Thường dùng để tính tổng của tích các đầu vào với trọng số liên kết của nó
• Ngưỡng (còn gọi là một độ lệch - bias): Ngưỡng này thường được đưa vào như một thành phần của hàm truyền
Hàm truyền (Transfer function) là công cụ quan trọng trong việc giới hạn phạm vi đầu ra của mỗi nơron, nhận đầu vào từ kết quả của hàm tổng và ngưỡng.
• Đầu ra: Là tín hiệu đầu ra của một nơron, với mỗi nơron sẽ có tối đa là một đầu ra.
Neurone nhân tạo tiếp nhận tín hiệu đầu vào, xử lý chúng bằng cách nhân với trọng số liên kết, tính tổng các tích thu được và gửi kết quả đến hàm truyền, từ đó tạo ra tín hiệu đầu ra, chính là kết quả của hàm truyền.
3.4.2 Một số kiểu Neural Networks
Kiến trúc (topology) của mạng được xác định bởi cách thức kết nối các nơron Các nơron có thể được kết nối đầy đủ (fully connected), nghĩa là mỗi nơron liên kết với tất cả các nơron khác, hoặc kết nối cục bộ (partially connected), chỉ kết nối giữa các nơron ở các tầng khác nhau Có hai loại kiến trúc mạng chính được phân loại dựa trên các kiểu kết nối này.
Tự kết hợp (autoassociative): là mạng có các nơron đầu vào cũng là các nơron đầu ra Mạng Hopfield là một kiểu mạng tự kết hợp
Heteroassociative networks feature distinct input and output neuron sets This category includes models such as Perceptrons, MultiLayer Perceptrons (MLP), and Kohonen networks.
Hình 6 Mạng tự kết hợp
Hình 7 Mạng kết hợp khác kiểu
Mạng nơron được phân loại thành hai loại kiến trúc dựa vào sự hiện diện của các kết nối ngược (feedback connections) từ nơron đầu ra tới nơron đầu vào.
Kiến trúc truyền thẳng (feedforward architecture) là loại mạng nơron không có kết nối ngược từ đầu ra về đầu vào, không lưu trữ giá trị output trước và trạng thái kích hoạt của nơron Trong mạng nơron truyền thẳng, tín hiệu di chuyển theo một chiều duy nhất từ đầu vào tới đầu ra, và đầu ra của một tầng không ảnh hưởng đến tầng đó Mạng Perceptron là một ví dụ điển hình của kiến trúc này.
Kiến trúc phản hồi (Feedback architecture) là một loại kiến trúc mạng đặc trưng bởi các kết nối từ nơron đầu ra đến nơron đầu vào Loại mạng này ghi nhớ các trạng thái trước đó, khiến cho trạng thái tiếp theo không chỉ phụ thuộc vào tín hiệu đầu vào mà còn vào các trạng thái trước đó của mạng Một ví dụ điển hình của kiến trúc phản hồi là mạng Hopfield.
Hình 9 Mạng phản hồiHình 8 Mạng truyền thẳng
3.5 AI trong game Cờ Gánh
Khi chọn một agent để thay thế người chơi, nhiệm vụ của agent là giải quyết vấn đề chiến thắng trong game Cờ Gánh Điều này không hề đơn giản do có đối thủ cạnh tranh Các agent có khả năng quan sát toàn bộ trò chơi và truy cập đầy đủ thông tin trong trạng thái hiện tại Trò chơi diễn ra theo thứ tự và là tĩnh, với các người chơi di chuyển lần lượt và thông tin được lưu trữ trong các trạng thái là nhất quán cho bàn cờ.
Mô hình trí tuệ nhân tạo MiniMax
Cơ sở lý thuyết
Thủ tục Minimax là một phương pháp được thiết kế cho các môi trường agent hoàn toàn quan sát được, tĩnh, tuần tự và đa tác nhân, nhằm giải quyết các vấn đề trong trò chơi hai người Phương pháp này xây dựng một cây trò chơi đầy đủ và đánh giá từ dưới lên Trong đó, các bước di chuyển của agent được xác định là tối đa để tối ưu hóa lợi thế, trong khi đối thủ (người chơi min) cố gắng giảm thiểu lợi thế của agent thông qua các bước di chuyển của mình.
Khi cây trò chơi được đánh giá, các trạng thái ở cấp kế tiếp được gán giá trị thông qua một hàm lượng giá Người chơi ở cấp độ min sẽ chọn trạng thái có giá trị thấp nhất trong số các con của mình, trong khi người chơi ở cấp độ max sẽ chọn trạng thái có giá trị cao nhất Quá trình này tiếp tục cho đến khi đạt đến đỉnh của cây, nơi mà nốt con chứa giá trị tiện ích tốt nhất sẽ được chọn làm bước đi tối ưu.
Trong lý thuyết trò chơi, nếu hàm lượng giá hoàn hảo, thủ tục MiniMax sẽ hoạt động mà không có sai sót Tuy nhiên, thực tế cho thấy hàm lượng giá thường chỉ là ước lượng thô của giá trị thực tế của một trạng thái Do đó, việc có một hàm lượng giá tốt là rất quan trọng cho thủ tục MiniMax; nếu hàm lượng giá kém hoặc sai, thủ tục sẽ hoạt động kém hiệu quả so với những thủ tục khác có hàm lượng giá tốt hơn, ngay cả khi các thủ tục đó có hàm lượng giá xấu nhưng được cho thêm thời gian để phân tích sâu hơn trong trò chơi.
1.1 Hàm lượng giá Định nghĩa của hàm lượng giá là một hàm ước tính chi phí của đường đi nhỏ nhất từ trạng thái hiện tại đến trạng thái mục tiêu Vì việc đoán khoảng cách đến trạng thái mục tiêu phụ thuộc rất nhiều vào cách chơi của đối thủ, nên một hàm lượng giá được sử dụng thay thế trong môi trường đa tác nhân Hàm lượng giá về cơ bản thực hiện điều tương tự, nhưng nó không trả về độ dài dự kiến từ trạng thái hiện tại cho mục tiêu, nhưng trả về giá trị lượng giá trạng thái Nếu hàm lượng giá là chính xác, trạng thái gần với chiến thắng sẽ có một giá trị I lớn hơn, so với trạng thái cách xa chiến thắng Tuy nhiên, không có gì đảm bảo điều này, vì hầu hết các giá trị tiện ích chỉ là ước tính, dựa trên các thuộc tính nhất định của trạng thái hiện tại.
Hàm lượng giá theo nhiều cách là thành phần quan trọng nhất trong tác nhân
MiniMax Nếu đánh giá không chính xác hoặc có giả định sai về trạng thái trò chơi, agent sẽ hoạt động kém hiệu quả so với những agent có đánh giá tốt hơn, dù có nhiều thời gian hơn để phân tích bảng trò chơi.
Có nhiều phương pháp để tối ưu hóa hàm lượng giá, trong đó một cách tiếp cận hiệu quả là sử dụng chức năng đánh giá tuyến tính có trọng số Phương pháp này có những ưu điểm và nhược điểm riêng, sẽ được phân tích chi tiết trong phần tiếp theo.
1.2 Hàm đánh giá tuyến tính có trọng số
Hàm đánh giá tuyến tính có trọng số là một công cụ quan trọng trong việc phân tích trạng thái, với mỗi hàm đại diện cho một thuộc tính cụ thể Đối với một trạng thái s và trọng số wi tương ứng với thuộc tính fi(s), hàm đánh giá này được định nghĩa thông qua công thức, trong đó n là tổng số thuộc tính mà hàm xem xét.
Cách tiếp cận này thường được áp dụng để xây dựng các hàm lượng giá do tính đơn giản và khả thi của nó Tuy nhiên, thách thức lớn nhất là xác định các hàm và trọng số tương ứng, mặc dù đã có nhiều phương pháp hỗ trợ cho quá trình này.
Cờ Gánh là một trò chơi có tổng bằng không, nghĩa là tổng điểm của người chơi luôn bằng không Khi một người thực hiện động tác để tăng cơ hội thắng, đối thủ sẽ giảm cơ hội của mình Điều này dẫn đến việc giá trị lượng giá của người chơi đầu tiên tăng lên, trong khi giá trị của đối thủ giảm Người chơi gần nhất với chiến thắng sẽ có điểm số dương, trong khi đối thủ sẽ có điểm âm với giá trị tương đương Điều này giúp các agent dễ dàng sử dụng hàm lượng giá để phân tích hiệu suất so với đối thủ.
Việc lựa chọn sự kết hợp tối ưu cho các tham số trong hàm lượng giá là một thách thức đối với con người, vì chúng ta chỉ có thể đưa ra những phỏng đoán có điều kiện về tầm quan trọng của từng tham số và có thể bỏ qua những yếu tố quan trọng Để tạo ra các tham số cho hàm lượng giá, cách duy nhất là sử dụng các thuật toán chuyển đổi vấn đề cụ thể trong ngôn ngữ logic thành một tập hợp tham số lượng giá, nhưng phương pháp này có thể không thực tế Một phương pháp thay thế là cho phép con người lựa chọn các tham số và xác định tầm quan trọng của chúng qua các phương tiện khác Tham số quan trọng nhất là những yếu tố tăng lên khi người chơi tiến gần đến chiến thắng và giảm khi họ gần đến thất bại Sau khi phân tích trò chơi, nhóm đã đề xuất một số tham số có thể đưa vào hàm lượng giá.
Giá trị của một quân trên dòng khi đi vào dòng đó.
Giá trị gia tăng khi một quân ở giữa bảng.
Hình phạt cho việc có một quân đứng trước đối thủ trong lượt của đối thủ.
Giá trị gia tăng để có hai quân đứng trong một hàng.
Một giá trị gia tăng cho số lần di chuyển hợp lệ mà người chơi có thể thực hiện.
Giá trị của một điểm ghi.
Giá trị của việc có lượt.
Giá trị của việc người chơi sở hữu hầu hết các quân cờ trên bảng.
Hiện thực MiniMax
Dữ liệu đầu vào cho thuật toán Minimax là trạng thái hiện tại của trò chơi, từ đó thuật toán sẽ phân tích và đưa ra bước đi hợp lý Quy trình này dựa vào các yếu tố quan trọng của trò chơi để tối ưu hóa quyết định.
Nhóm đã mô hình hóa trạng thái của bàn cờ bằng hai mảng hai chiều, tương ứng với vị trí của mỗi quân cờ của hai bên Cụ thể, vị trí quân cờ của người chơi phía trên được biểu diễn bởi mảng upPlayerPos = {{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 0}, {1, 4}, {2, 4}} Trong khi đó, vị trí quân cờ của người chơi phía dưới được lưu trữ trong mảng downPlayerPos = {{4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {3, 0}, {2, 0}, {3, 4}}.
Giải thuật MiniMax thường sử dụng phương pháp duyệt sâu đầu tiên nhằm tối ưu hóa yêu cầu bộ nhớ Để đảm bảo rằng thuật toán có thể trả về một nước đi trong thời gian hợp lý, quá trình tìm kiếm thường bị giới hạn ở một độ sâu nhất định.
Quá trình này được minh họa với độ sâu là 3 như sau
Hình 12 Cây trò chơi ban đầu
Hình 13 Bước duyệt sâu đầu tiên
Trong quá trình thực hiện, thuật toán xác định bước di chuyển tối ưu trong một khoảng thời gian nhất định Để tìm ra bước di chuyển tốt nhất, thuật toán cần hoàn thành một tìm kiếm đến một độ sâu nhất định trong thời gian cho phép.
Chi phí tính toán tăng theo độ sâu tìm kiếm, với hệ số chi phí được xác định qua phương trình, trong đó b là hệ số phân nhánh trung bình và d là độ sâu tìm kiếm.
Hình 15 Kết quả cuối cùngHình 14 Các bước duyệt sâu tiếp theo
Khi độ sâu tăng thêm một đơn vị, chi phí sẽ tăng theo cấp số nhân với hệ số phân nhánh b, dẫn đến một sự gia tăng chi phí đáng kể trong trò chơi.
Thời gian chạy của thuật toán được xác định bởi thời gian tính toán một trạng thái nhân với số lượng trạng thái mà thuật toán tìm kiếm Thời gian tính toán một trạng thái là hằng số, và khi thuật toán thực hiện tìm kiếm ở độ sâu d, nó sẽ xử lý b^(d+1) - 1 trạng thái Do đó, tổng thời gian chạy phụ thuộc vào hệ số phân nhánh b và độ sâu d.
Thử nghiệm ở các độ sâu lần lượt là 1, 2 và 3 nhóm có bảng số liệu sau Độ sâu
Bảng 1 Thời gian chạy của Minimax
Dựa vào các số liệu có được nhóm quyết định sử dụng độ sâu là 1.
Dựa vào các thông số phân tích, nhóm đã xác định hàm lượng giá dựa trên "Số quân còn lại hiện tại trên bàn cờ của 2 bên" Công thức hàm lượng giá được đưa ra là f(x) = a * g(x) – b * h(x), trong đó g(x) là số quân còn lại của AI và h(x) là số quân còn lại của đối thủ Để tối ưu trọng số a và b trong phương trình, nhóm đã thực hiện chạy giải thuật với nhiều trọng số khác nhau và thu thập được dữ liệu tương ứng.
Bảng 2 Kết quả đối kháng của các phiên bản hàm lượng giá khác nhau
Kết quả từ bảng cho thấy cặp trọng số (1:1) và (1:2) có hiệu quả tốt nhất Trong khi đó, cặp (1:1) đã giành chiến thắng trong kết quả đối kháng, do đó nhóm đã quyết định chọn cặp trọng số (1:1).
Mô hình trí tuệ nhân tạo Monte Carlo Tree Search
Bước lựa chọn
Quá trình lựa chọn hoạt động trong MCTS bắt đầu từ nút gốc, áp dụng chiến lược lựa chọn đệ quy cho đến khi đạt được một node chưa thuộc cây Chiến lược này cân bằng giữa khai thác và thăm dò, với mục tiêu chọn bước di chuyển mang lại kết quả tốt nhất (khai thác) trong khi vẫn thử nghiệm các động thái ít hứa hẹn hơn (thăm dò) do sự không chắc chắn trong đánh giá Vấn đề lựa chọn trong MCTS là xác định bước đi tiếp theo để đạt được phần thưởng không thể đoán trước từ một trò chơi ngẫu nhiên MCTS sử dụng đệ quy để thực hiện nhiều lựa chọn tại các độ sâu khác nhau, và đã phát triển nhiều chiến lược như Objective Monte-Carlo và Probability to be Better than Best Move Nhiều chiến lược MCTS được lấy cảm hứng từ các thuật toán Multi-Armed Bandit, nổi bật là Upper Confidence bounds applied to Trees (UCT), được sử dụng phổ biến trong các triển khai MCTS hiện nay.
UCT, được Kocsis và Szepesvári đề xuất vào năm 2006, là một chiến lược dễ thực hiện và được áp dụng rộng rãi trong nhiều chương trình Chiến lược này điều chỉnh phương pháp UCB (Upper Confidence Bound) ban đầu phát triển cho MAB UCT hoạt động bằng cách xác định tập hợp các node có thể truy cập từ nút hiện tại p, và chọn một con k của nút p theo công thức nhất định.
Giá trị của nút i được xác định bởi v i, trong khi n i là số lượt truy cập của nút i và n p là số lượt truy cập của nút p Hệ số C cần được điều chỉnh thông qua thực nghiệm để đảm bảo tính chính xác.
Bước mở rộng
Trong quá trình mở rộng các nút trong cây MCTS, do giới hạn bộ nhớ, chiến lược mở rộng quyết định liệu một nút L cụ thể sẽ được mở rộng bằng cách lưu trữ một hoặc nhiều nút con của nó Có nhiều chiến lược mở rộng khác nhau được áp dụng trong quá trình này.
Mỗi trò chơi mô phỏng sẽ được bổ sung một node, đại diện cho vị trí đầu tiên được phát hiện trong quá trình duyệt cây mà chưa được lưu trữ.
• Có thể khai triển cây đến một độ sâu nhất định (ví dụ: 2 hoặc 3 lớp) trước khi bắt đầu tìm kiếm.
• Thêm tất cả các phần tử con của một nút vào cây ngay khi một số mô phỏng T nhất định đã được thực hiện thông qua nút này.
• Cấm mọi mở rộng nút trước khi một số mô phỏng T nhất định được thực hiện thông qua nút này.
Nhìn chung, ảnh hưởng của các chiến lược này đến sức mạnh chơi là nhỏ.
Bước mô phỏng
Bước mô phỏng, hay còn gọi là playout hoặc rollout, là quá trình mà node được chọn tự chơi cho đến khi kết thúc trò chơi Trong quá trình này, nhiệm vụ có thể bao gồm việc thực hiện các bước di chuyển ngẫu nhiên đơn giản hoặc, tốt hơn, các bước giả ngẫu nhiên được lựa chọn dựa trên một chiến lược mô phỏng.
Một chiến lược mô phỏng cần cân nhắc hai sự đánh đổi quan trọng: giữa việc tìm kiếm và kiến thức Việc bổ sung kiến thức vào chiến lược mô phỏng có thể nâng cao sức mạnh chơi, giúp trò chơi trở nên chính xác hơn và mang lại kết quả đáng tin cậy hơn Tuy nhiên, nếu việc áp dụng kiến thức heuristic quá tốn kém về mặt tính toán, số lượng mô phỏng thực hiện mỗi giây sẽ bị giảm.
Hình 17 Node chưa expand
Khi cây tìm kiếm MCTS bị mở rộng quá mức, hiệu suất chơi sẽ giảm do sự đánh đổi giữa thăm dò và khai thác Nếu chiến lược quá ngẫu nhiên, sẽ xảy ra nhiều thăm dò không hiệu quả, dẫn đến các động tác yếu trong các trò chơi mô phỏng và làm giảm chất lượng của chương trình Monte-Carlo Ngược lại, nếu chiến lược quá xác định, việc khai thác sẽ trở nên quá mức, khiến cho việc khám phá không gian tìm kiếm trở nên hạn chế và làm sai lệch kết quả mô phỏng, từ đó cũng làm giảm hiệu suất của chương trình Monte-Carlo.
Do hai sự đánh đổi này, việc xây dựng một chiến lược mô phỏng hiệu quả là một vấn đề khó khăn.
Bước truyền ngược
Bước truyền ngược là quá trình truyền kết quả từ nút lá L đến các nút trung gian trong trò chơi mô phỏng, như trong Cờ vây, với kết quả thắng là Rk = +1, thua là Rk = -1 và hòa là Rk = 0 Để tính giá trị vL của nút, chiến lược lan truyền ngược sử dụng phương pháp trung bình, trong đó vL được tính bằng cách lấy tổng kết quả Rk chia cho số lượng trò chơi nL, tức là vL = ∑ (Rk) / nL Phương pháp này lần đầu tiên được giới thiệu bởi Kocsis và Szepesvári vào năm 2006 và đã trở thành tiêu chuẩn trong hầu hết các chương trình từ năm 2007.
Biểu đồ quy trình trong hình 19 mô phỏng việc tìm kiếm một phương pháp backpropagation hiệu quả hơn so với trung bình, điều này đặt ra thách thức cho MCTS Ngoài ra, còn có nhiều chiến lược truyền bá khác như Max, Informed Average, Mix và MCTS-Solver.
Lựa chọn bước di chuyển
Sau khi tiến hành mô phỏng, bước di chuyển trong trò chơi được xác định là "node con tốt nhất" của root Có nhiều phương pháp khác nhau để xác định node con tối ưu nhất.
1 Node con tối đa là con có giá trị cao nhất.
2 Node con mạnh mẽ là node con có số lượt truy cập cao nhất.
3 Node con mạnh mẽ tối đa là node con có cả số lượt truy cập cao nhất và giá trị cao nhất Nếu không có node con mạnh mẽ tối đa vào lúc này, nhiều mô phỏng được chơi cho đến khi một đứa trẻ mạnh mẽ tối đa thu được.
4 Node con an toàn là node con tối đa hóa một giá trị cận dưới khoảng tự tin (Lower
Confidence Bound), tức là, tối đa hóa con số v+ A
√ n , trong đó A là một tham số, v là giá trị của nút và n là số lượt truy cập của nút.
Không có sự khác biệt lớn giữa các phương pháp thảo luận khi số mô phỏng đủ lớn cho mỗi nước đi Tuy nhiên, khi thời gian suy nghĩ cho mỗi nước đi bị giới hạn (dưới 1 giây), việc chọn các Node con để tối đa hóa trở nên kém hiệu quả hơn so với các phương pháp khác.
Hiện thực
Cấu trúc cơ bản của MCTS bao gồm các nút đại diện cho trạng thái của trò chơi, trong đó mỗi nút chứa hai thông tin quan trọng: giá trị hiện tại của vị trí, thường là trung bình của kết quả từ các trò chơi mô phỏng đã truy cập, và số lượt truy cập của vị trí đó MCTS thường khởi đầu với một cây chỉ chứa nút gốc.
Dữ liệu đầu vào là state hiện tại của game Đó là node gốc của game tree được xây dựng dựa vào MCTS
Mỗi node có cấu trúc như sau:
2 mảng 2 chiều tương ứng với mỗi quân cờ của mỗi bên
Một giá trị biểu thị cho player turn.
List các node là con của node hiện tại.
Tổng điểm của node sau khi giả lập.
Tổng số lần đã được đuyệt qua.
Ví dụ node khi bàn cờ khi bắt đầu: upPlayerPos = {{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 0}, {1, 4}, {2, 4}}; downPlayerPos = {{4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {3, 0}, {2, 0}, {3, 4}}; nodePlayerTurn = 1; children = null; totValue = 0; nVisits = 0;
Tại bước Selection, nhóm quyết định sử dụng chiến lược UCT đã được nói ở trên. w i n i +e+C √ n N i +e i
wi số lần thắng cho nút được xem xét sau khi di chuyển lần thứ i.
ni số mô phỏng cho nút được xem xét sau khi di chuyển thứ i.
Ni tổng số mô phỏng sau khi di chuyển thứ i được chạy bởi nút cha của nút được xem xét.
C tham số thăm dò theo lý thuyết, bằng √2; trong thực tế thường được chọn theo kinh nghiệm.
e là một hằng số vô cùng bé, bằng 1e-6.
Dựa vào chiến lược trên, các node con chưa được duyệt sẽ được ưu tiên chọn Cây trò chơi sẽ ưu tiên mở rộng theo chiều ngang.
Về phần Simulation thì nhóm quyết định để game giả lập bằng các bước đi ngẫu nhiên.
Bảng 3 Thời gian chạy của MCTS
Dựa vào các số liệu có được nhóm quyết định sử số lần giả lập là 100.
Cây trò chơi được xây dựng sau khi hoàn thành quá trình giả lập Nhóm sẽ quyết định bước đi tiếp theo bằng cách lựa chọn node con tốt nhất từ node gốc, ưu tiên chọn node con có điểm trung bình cao nhất Trong trường hợp có nhiều node con có điểm trung bình giống nhau, nhóm sẽ chọn node con có số lượng con ít nhất.
Thiết kế UI
Giao diện màn hình khởi động của Game
Gồm các button chọn mode cho trò chơi:
Hình 20 Giao diện màn hình khởi động
Button chọn thời gian suy nghĩ cho mỗi nước đi: 5 phút - 10 phút - 15 phút
Giao diện khi vào chơi Game
Phần Mode: thể hiện Mode game đang chơi.
Trong phần Step, số nước cờ đã đi của hai bên được thể hiện rõ ràng Nếu sau 100 nước đi mà vẫn chưa có bên nào giành chiến thắng, thì người chơi nào còn nhiều quân cờ hơn sẽ là người chiến thắng trong ván cờ này.
Button Setting: Menu cài đặt của Game.
Phần Time: thể hiện số phút suy nghĩ người chơi được phép suy nghĩ.
Phần thể hiện: số quân đã ăn được của đối thủ.
Hình 21 Giao diện khi vào chơi Game
Giao diện Setting Game
Bật tắt hiệu ứng tiếng nói game.
Đổi thời gian suy nghĩ cho 1 nước cờ.
Hình 22 Giao diện Setting Game
Kiểm chứng và đánh giá giải thuật
Để đánh giá hiệu quả của các thuật toán AI, nhóm nghiên cứu đã phát triển môi trường trò chơi "Cờ gánh" trên nền tảng game engine Unity, một trong những công cụ hàng đầu thế giới hiện nay.
Trong trò chơi, các quy định về luật chơi sẽ được thiết lập rõ ràng Nhóm phát triển sẽ tạo ra một môi trường mô phỏng, nơi mà trí tuệ nhân tạo (AI) sẽ thi đấu trực tiếp với nhau Kết quả đối đầu giữa các AI sẽ được sử dụng để xếp hạng hiệu suất của chúng.
Bảng 4 Kết quả đối kháng giữa Minimax và MCTS
Thời gian chạy của các giải thuật:
Minimax với các độ sâu khác nhau:
Biểu đồ 1 Thời gian chạy của Minimax
MCTS với số lần giả lập khác nhau:
Dựa vào các số liệu có được, nhóm nhận thấy hiện tại giải thuật Minimax là lựa chọn tốt hơn cho game “Cờ gánh” hiện nay
Giải thuật Minimax gặp hạn chế về độ sâu do giới hạn vật lý, khi tăng độ sâu, thời gian tính toán sẽ tăng đột biến, ảnh hưởng đến hiệu suất của giải thuật.
Mặc dù MCTS chưa có kết quả đối đầu tốt hơn Minimax, nhưng thời gian chạy của nó không tăng đột biến khi số lần giả lập tăng lên, cho thấy tiềm năng phát triển của MCTS rất lớn.
Biểu đồ 2 Thời gian chạy của MCTS
Tổng kết
Đánh giá kết quả
Mục tiêu nghiên cứu đã được hoàn thành, với việc phát triển các agent thông qua hai giải thuật, cho phép chúng chơi cờ và đánh bại người chơi Điều này đã đáp ứng đầy đủ các yêu cầu ban đầu đã đề ra.
Luôn luôn đánh đúng theo luật của trò chơi.
Tìm cách đi hiệu quả dựa trên các tiêu chí cho trước.
Mặc dù các agent đã có khả năng chiến thắng, nhưng cần cải thiện để nâng cao tỉ lệ này Đặc biệt, agent Monte Carlo Tree Search có tiềm năng phát triển cao, trong khi agent Mini Max vẫn còn khả năng cải thiện nhưng bị hạn chế.
Đóng góp của luận văn
Nhóm nghiên cứu về trí tuệ nhân tạo trong trò chơi Cờ Gánh của Việt Nam gặp nhiều khó khăn do là những người tiên phong trong lĩnh vực này Họ thiếu tài liệu tham khảo từ các bài báo khoa học và phải dựa vào các sản phẩm game đã được xuất bản trên các chợ ứng dụng để tìm hiểu thêm.
Ngoài mục tiêu của luận văn, nhóm nghiên cứu cố gắng tìm tòi, giải quyết các vấn đề nêu trên và đạt được những đóng góp như sau:
Kiểm chứng và đánh giá giải thuật trong cả môi trường mô phỏng và thực nghiệm.
Cải biến trong cách chơi, góp phần tạo sự thú vị, dễ tiếp cận cho mọi người.
Hướng phát triển
Game và trí tuệ nhân tạo đang phát triển mạnh mẽ cả hiện tại lẫn tương lai Nhóm mong muốn đóng góp vào sự phát triển của đề tài luận văn theo nhiều hướng khác nhau.
3.1 Các cải tiến có thể được thêm vào MiniMax
Mặc dù MiniMax đã được triển khai với kỹ thuật hiện tại, vẫn còn nhiều khía cạnh của thuật toán cần cải thiện Do đó, các gợi ý cho những cải tiến bổ sung sẽ được thảo luận trong các phần tiếp theo.
Trong một số tình huống khi MiniMax sử dụng hàm lượng giá đơn giản, các bước di chuyển có thể có cùng giá trị lượng giá, dẫn đến việc chọn bước di chuyển đầu tiên có thể gây ra sai lầm Để cải thiện tình hình này, có thể chọn các bước di chuyển ngẫu nhiên từ nhóm có giá trị tiện ích cao nhất Sử dụng hàm xác suất để lựa chọn di chuyển cũng là một phương pháp hiệu quả, cho phép giá trị lượng giá làm chỉ dẫn, với các bước di chuyển có giá trị cao hơn có khả năng được chọn nhiều hơn.
Tối ưu hóa tìm kiếm bằng cách cải thiện thuật toán tìm kiếm trong thủ tục
MiniMax là phương pháp hiệu quả để nâng cao hiệu suất của thủ tục, cho phép lưu trữ cây trò chơi giữa các lần di chuyển Cải tiến này giúp tiết kiệm thời gian tính toán bằng cách tránh việc tính toán lại toàn bộ cây cho mỗi lần di chuyển Hơn nữa, nó có thể kết hợp với duyệt sâu lặp đi lặp lại, giúp giảm chi phí lên tới 30%.
Một thuật toán tìm kiếm như vậy sẽ yêu cầu nhiều bộ nhớ hơn và có thể dẫn đến việc mất một số lỗ hổng để theo dõi các cấu trúc dữ liệu nâng cao cần thiết Nếu được triển khai đúng cách, sự cải thiện này sẽ tiết kiệm thời gian, tuy nhiên, việc giảm thời gian tính toán vẫn có giới hạn.
Để giảm hệ số phân nhánh trong thuật toán MiniMax, cần đảm bảo rằng hai trạng thái giống hệt nhau không bao giờ được duyệt Điều này yêu cầu khi phát hiện hai trạng thái trò chơi giống nhau, trạng thái gần ngọn cây nhất phải được ưu tiên khám phá Trong trường hợp sử dụng tìm kiếm duyệt sâu, điều này không còn cần thiết Hơn nữa, nếu phát hiện hai trạng thái giống nhau ở cùng một cấp độ, chỉ một trong số chúng nên được duyệt để tối ưu hóa quá trình tìm kiếm.
Việc sử dụng bảng băm trong quá trình thực hiện giúp giảm hệ số phân nhánh bằng cách tránh duyệt các trạng thái trùng lặp, tuy nhiên, điều này cũng dẫn đến việc tăng cao mức sử dụng bộ nhớ Trong thuật toán MiniMax, các trạng thái có thể được xóa khỏi bộ nhớ khi đã được duyệt, nhưng với việc áp dụng bảng băm, tất cả các trạng thái cần phải được lưu giữ cho đến khi tìm ra bước đi tối ưu.
Một phương pháp hiệu quả để nâng cao hiệu suất của thuật toán MiniMax là tận dụng sức mạnh xử lý từ nhiều bộ xử lý trên các máy tính hiện đại Việc triển khai MiniMax theo cách an toàn theo luồng có thể làm cho quá trình này trở nên phức tạp, nhưng đây là nhược điểm duy nhất cần lưu ý.
3.2 Các cải tiến có thể được thêm vào MCTS
Mặc dù MCTS có thể hoạt động mà không cần tri thức đặc trưng của trò chơi, nhưng tri thức đóng vai trò quan trọng trong việc cải thiện các phương pháp học tăng cường Học tăng cường là một yếu tố thiết yếu trong MCTS, giúp nâng cao hiệu quả và khả năng ra quyết định trong quá trình chơi.
Công thức UCB thường chỉ tìm kiếm một số nước đi hợp lệ một cách công bằng, trong khi các nước đi hợp lệ khác thường bị bỏ qua Tuy nhiên, chúng ta có thể điều chỉnh giá trị UCB bằng cách thêm giá trị cộng thêm cho các nước đi, dựa trên tri thức đặc trưng từ các ván cờ, giúp xác định các nước đi thực sự tốt hay xấu Nhờ đó, giá trị UCB sẽ bị lệch so với công thức thông thường, dẫn đến việc tìm kiếm chính xác hơn Nhiều công thức đã được đề xuất theo cách này, như đã nêu trong phần lý thuyết.
Trong giai đoạn giả lập, một nước đi được chọn ngẫu nhiên từ tập hợp các nước đi hợp lệ trên trạng thái của ván cờ Để quá trình giả lập ngẫu nhiên đạt hiệu quả nhanh chóng, cần có sự định hướng từ tri thức đặc trưng của các ván cờ Do đó, vai trò của hàm lượng giá hành động trở nên quan trọng, hàm này được xây dựng từ tri thức nhưng tiết kiệm chi phí hơn so với việc xây dựng hàm lượng giá trạng thái.
3.3 Một số hướng mở rộng trong tương lai:
Có thể chơi online , liên kết mạng xã hội để mời bạn bè chơi cùng, bảng xếp hạng top người chơi.
Cải biến cách chơi bằng cách biến quân cờ của đối thủ thành quân cờ của mình, đồng thời áp dụng Machine Learning để nâng cao trí tuệ nhân tạo trong game.
Hình 1 Hình ảnh một bàn cờ gánh 9
Hình 2 Mô tả cách di chuyển của một quân cờ 9
Hình 3 Hình ảnh về cách Gánh để ăn hai quân cờ khác 10
Hình 4 Hình ảnh về cách Nhảy qua đầu quân cờ khác để ăn 10
Hình 5 Cấu tạo một Neural 12
Hình 6 Mạng tự kết hợp 14
Hình 7 Mạng kết hợp khác kiểu 14
Hình 10 Mô hình thiết kế game cờ gánh 16
Hình 11 Đồ thị dòng điều khiển 18
Hình 12 Cây trò chơi ban đầu 22
Hình 13 Bước duyệt sâu đầu tiên 22
Hình 15 Kết quả cuối cùng 23
Hình 14 Các bước duyệt sâu tiếp theo 23
Hình 16 Các bước chính của giải thuật MCTS 1 27
Hình 18 Node sau khi expand 29
Hình 19 Flowchart quá trình mô phỏng 30
Hình 20 Giao diện màn hình khởi động 34
Hình 21 Giao diện khi vào chơi Game 35
Hình 22 Giao diện Setting Game 36
DANH SÁCH BẢNG VÀ BIỂU ĐỒ
Bảng 1 Thời gian chạy của Minimax 24
Bảng 2 Kết quả đối kháng của các phiên bản hàm lượng giá khác nhau 25
Bảng 3 Thời gian chạy của MCTS 33
Bảng 4 Kết quả đối kháng giữa Minimax và MCTS 37
Y Biểu đồ 1 Thời gian chạy của Minimax 37
Biểu đồ 2 Thời gian chạy của MCTS 38