Do sâu trong đánh giá cờ caro năm 2024
|
BỘ GIAO THÔNG VẬN TẢI TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO BÀI TẬP LỚN HỌC PHẦN :TRÍ TUỆ NHÂN TẠO XÂY DỰNG TRÒ CHƠI CỜ CARO Giảng viên bộ môn:Nguyễn Duy Trường Giang Sinh viên thực hiện: Phan Hà Mai Linh – MSV: 83741 Show
Mục lục Lời mở đầu......................................................................................................
####### I. Giới thiệu đề tài “Game Caro” ...................................................................... Game gồm có 2 người chơi, một người cầm quân X, một người cầm quân O. Hai người chơi sẽ lần lượtđưa đánh quân tương ứng của mình trên một bàn cờ MxN ô (thường thì M = N).Luật chơi:Quân X là quân được đánh trước. Hai người chơi có thể đánh vào bất kỳ ô nào trên bàn cờ miễn là ô đóchưa được đánh. Trò chơi kết thúc khi một trong hai người chơi có 5 quân thằng hàng liên tiếp nhau(ngang, dọc hoặc chéo). Dưới đây là bàn cờ caro kích thước 15xIIât toán MiniMax và thuật toán cắt cụt Alpha-Beta ####### 1. Thuật toán MiniMax.........................................................................
MAX chọn các nước đi tương ứng với giá trị MINIMAX cực đại ( MIN chọn các nước đi ứng với giá trị MINIMAX cực tiểu. Áp dụng vào game Caro: Người chơi cầm quân X đóng vai trò như Max, người chơi cầm quân O đóng vai trò như Min. Để quyết định nước đi tiếp theo, ta xây dựng một thủ tục đệ quy gồm 2 hàm max_value() để tìm nước đi tiếp theo cho quân X, min_value() để tìm nước đi tiếp theo cho quân O. Để giảm thời gian của giải thuật đệ quy, ta giới hạn độ sâu của giải thuật bằng 4. int max_value(state s, int dept){ if(terminal_test() || dept >= 4) return eval(s); v = -∞; for(duyệt tất cả các trạng thái con s’ của s){ v = max(v, min_value(s’, dept + 1)); } return v; } int min_value(state s, int dept){ if(terminal_test() || dept >= 4 ) return eval(s); v = +∞; for(duyệt tất cả các trạng thái con s’ của s){ v = min(v, max_value(s’, dept + 1)); } return v; } Hàm xác định trạng thái kết thúc terminal_test(): Hàm có nhiệm vụ xác định xem trò chơi có kết thúc hay không khi một quân cờ được đánh thêm vào. Hàm hoạt động như sau: Từ vị trí thêm quân cờ, kiểm tra theo các chiều ngang, dọc, chéo(ví dụ kiểm tra theo chiều ngang: giả sử quân cờ đánh vào là X, duyệt theo hướng bên trái cho đến khi gặp quân O hoặc tường thì dừng lại, tiếp tục duyệt theo hướng bên phải tương tự để xác định số quân X liên tiếp nhau). Nếu số quân X (hoặc O) liên tiếp là 5 thì trả lại giá trị true, ngược lại trả về giá trị false. ####### 2. Thuật toán cắt cụt alpha-beta............................................................... Trong chiến lược Minimax với độ sâu hạn chế thì số đỉnh của cây trò chơi phải xét vẫn còn rất lớn với h>=3. Khi đánh giá đỉnh utới độ sâu h, thuật toán Minimax đòi hỏi phải đánh giá tất cả các đỉnh của cây gốc u với độ sâu h. Tuy nhiên, phương pháp cắt cụt alpha-beta cho phép cắt bỏ if(v < alpha) return v; beta= min(beta, v); return v; } ####### 3. Hàm đánh giá................................................................................. Hàm đánh giá là một hàm quan trọng trong việc xây dựng trò chơi cờ caro. Hàm này giúp cho điểm trạng thái của bàn cờ để từ đó xây dựng cây trò chơi. Việc xây dựng hàm lượng giá hợp lý, chính xác sẽ giúp cho hệ thống có đánh giá chính xác về trạng thái bàn cờ để đưa ra nước đi thông minh hơn. Trong game caro, để tính điểm cho trạng thái bàn cờ ta đưa ra các tiêu chí sau: Trong trường hợp chắc chắn thắng, điểm cộng sẽ là +Int32_VALUE đối với X và -Int32_VALUE đối với O. Trong trường hợp có nước 3, điểm cộng sẽ là +300 đối với X và -300 đối với O Trong trường hợp có nước 4, điểm cộng sẽ là +600 đối với X và -600 đối với O III. Cài đặt chương trình Chương trình gồm các lớp như sau: 1ớp Board Là lớp để lưu lại trạng thái của bàn cờ Biến: COLUMN, ROW: số cột và hàng của bàn cờ PieceState: các trạng thái có thể có của một quân cờ(X, O, chưa đánh hoặc không hợp lệ). boardState: là một mảng lưu lại các trạng thái của các quân cờ. byte[] boardState; Hàm: GetPieceAt(): Lấy trạng thái của quân cờ tại một tọa độ xác đinh. IsOccupied(): Xác định xem tại một vị trí xác định đã có quân cờ nào đươc đánh chưa. AddPiece(): Thêm một quân cờ vào bàn cờ. IsWinner(): Kiểm tra trạng thái hiện tại của bàn cờ đã kết thúc chưa. 2ớp CaroAI Biến: MINMAX_DEPTH: độ sâu của giải thuật MiniMax numMoves, numComparisons: số nút con duyệt qua và số lượng phép so sánh cần sử dụng trong giải thuật MiniMax (dùng để đánh giá thuật toán). computerPiece, playerPiece: dùng để xác định kiểu quân cờ của người chơi và máy(X hay O). Hàm: MinimaxHelper(): xác định nếu thêm một quân cờ vào trạng thái hiện tại của bàn cờ có làm trạng thái hiện tại trở thành trạng thái kết thúc hay không, nếu không thì sử dụng giải thuật MiniMax. MiniMax(): cài đặt giải thuật MiniMax. private Result MiniMax(Node node, int depth, int alpha, int beta, bool needMax) { if (depth <= 0 || node()) { var result = new Result(); var score = node(computerPiece); result(score); return result; } var best = new Result(); foreach (var child in node()) { Biến: score: điểm của trạng thái bàn cờ. gameNodes: là một mảng chứa các nút con của nút đang xét Hàm: GetMove(): getScore(): lấy điểm của trạng thái bàn cờ. setScrore(): gán điểm của trạng thái bàn cờ. Add(): IV. Giao diện chương trình
####### V. Kết luận................................................................................................. |
