MÔ HÌNH HỆ THỐNG ĐÁNH CỜ CARO SỬ DỤNG GIẢI THUẬT TÌM KIẾM LEO ĐỒI
Tổng quan
-
Hệ thống đánh cờ caro dựa vào các giải thuật trí tuệ nhân tạo là một chương trình đánh cờ caro tự động giữa người với máy, với sự thông minh đủ để chiến thắng, hoặc cầm hòa với con người.
-
Hệ thống AI sử dụng giải thuật tìm kiếm leo đồi để giải quyết bài toán tìm nước đi tiếp theo.
-
Sử dụng các thư viện có sẵn trong python, và trực tiếp cài đặt thuật toán.
Nội dung chuyên môn chính
-
Giải thuật của hệ thống là sử dụng phương pháp tìm kiếm leo đồi: là tìm kiếm trạng thái tốt nhất hiện tại (cụ bộ).
-
Chương trình sẽ chạy duyệt qua tất cả các vị trí chưa được đánh trên bàn cờ.
-
Sau đó tính giá trị của vị trí đó khi ta đi nước tiếp theo tại vị trí đó.
-
Tính giá trị tấn công đạt được khi đánh vào vị trí đó.
-
Tính giá trị phòng thủ đại được khi đánh vào vị trí đó.
-
Chọn ra giá trị lớn hơn (giá trị tấn công hoặc giá trị phòng thủ), làm giá trị của nước cờ đó, có ưu tiên cho tấn công hơn phòng thủ. Và có ưu tiên tấn công / phòng thủ theo đường chéo hơn theo chiều dọc và chiều ngang.
-
-
Duyện lại toàn bộ và tìm ra ô cờ có giá trị lớn nhất, nếu các ô cờ có giá trị lớn nhất và bằng nhau. Thì ta tính tổng giá trị tấn công và giá trị phòng thủ của các ô cờ đó và so sánh lấy lại lần nữa để tìm ra ô cờ có giá trị lớn nhất.
-
-
Sản phần của project là một trò chơi caro giữa người và máy, sử dụng ngôn ngữ python và ứng dụng trí tuệ nhân tạo để phân tích, tính toán tìm ra nước đi cho máy tính.
-
Kết quả thực nghiệm, máy tính có khả năng đánh hòa hoặc thắng trong đa số các ván chơi với người, hay các hệ thống AI đánh cờ caro online khác trên mạng.
Ngôn ngữ lập trình và công cụ sử dụng
-
Ngôn ngữ lập trình được sử dụng để tạo nên hệ thống đánh cờ caro của project này là ngôn ngữ Python, bạn cũng có thể sử dụng ngôn ngữ C hoặc một vài ngôn ngữ khác.
-
Phiên bản sử dụng là python 3.10.
MÔ HÌNH HỆ THỐNG
Mô tả bài toán
-
Bài toán của trò chơi cờ caro là một ma trận 5X5 với mỗi ô có thể đánh X hoặc O.
-
Mỗi bên sẽ thay phiên nhau điền vào ma trận.
-
Mục tiêu là có 4 ô X hoặc ô O liên tiếp theo đường chéo hoặc đường dọc hoặc đường ngang sẽ chiến thắng.
Các yêu tố chính
-
Tập hợp các trạng thái của bài toán : là trạng thái của toàn bộ bàn cờ hoặc trạng thái của nước đi tại một ô cờ.
-
Trạng thái bắt đầu : là trạng thái bàn cờ trống rỗng, khi chưa có quần cờ nào được đánh.
-
Mục tiêu đặt ra : là có 4 ô X (máy sẽ đánh X) liên tiếp theo đường chéo hoặc đường dọc hoặc đường ngang sẽ chiến thắng.
-
Cơ chế chuyển trạng thái : là khi máy hoặc người đánh vào một vị trí trống trong các ô cờ.
PHƯƠNG PHÁP
Thuật toán leo đồi
-
Thuật toán được sử dụng trong bài là thuật toán leo đồi : Nó thực hiện tìm một trạng thái tốt hơn trạng thái hiện tại để mở rộng. Để biết trạng thái tiếp theo nào là lớn hơn, nó dùng một hàm H để xác định trạng thái nào là tốt nhất.
Mô hình cây không gian trạng thái của bài toán AI
-
Trạng thái ban đầu ô cờ rỗng.
-
Nếu máy đánh trước thì sẽ sinh ra 25 trạng thái mới, tiếp tục người đánh sẽ sinh ra tiếp 24 trạng thái mới …
-
Phương pháp tìm kiếm được sử dụng là thuật toán leo đồi, đây là phương pháp tìm kiếm dễ dàng cài đặt, chạy nhanh, không chiếm không gian bộ nhớ và cho hiệu quả cao.
Biểu diễn bài toán
Bước 1:
-
Xét trạng thái đầu: Nếu là đích ⇒ dừng.
-
Ngược lại, thiết lập trạng thái bắt đầu = trạng thái hiện tại.
Bước 2:
-
Lựa một luật để áp dụng vào trạng thái hiện tại để sinh ra một trạng thái mới.
Bước 3:
-
Xem xét trạng thái mới này:
-
Nếu là đích ⇒ dừng.
-
Nếu không phải là đích nhưng tốt hơn trạng thái hiện tại thì thiết lập trạng thái hiệu t là trạng thái mới.
-
Nếu không tốt hơn thì đến trạng thái mới tiếp theo.
-
Lặp đến khi: gặp đích hoạt không còn luật nào nữa chưa được áp dụng vào trạng thái hiện tại.
Tổng Kết
-
Hệ thống có khác năng đánh thắng hoặc cầm hoà người chơi. Tuy nhiên vì sử dụng giải thuật leo đồi nên khi gặp một trường hợp máy đánh thua người, thì khi lặp lại các nước cờ cũ thì vẫn cho ra một kết quả thua, không có sự cải tiến hay tự học trong project.