Chương 1: Giới thiệu và tổng quan đề tài. • Chương 2: Trình bày về cơ sở lý thuyết. • Chương 3: Phân tích và thiết kế hệ thống. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 12/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính • Chương 4: Hiện thực và kết quả • Chương 5: Tổng kết những kết quả đạt được, những hạn chế và rút kinh nghiệm.
Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 13/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính 2 Cơ sở lý thuyết 2.1 Giới thiệu cờ tướng 2.1 Lịch sử cờ tướng Hiện nay, cờ tướng phổ biến nhất tại một số nước như: Trung Quốc, Việt Nam, ĐàiLoan, Singapore và nằm cùng thể loại với cờ vua, shogi, janggi. Trò chơi mô phỏng cuộc chiến giữa hai quốc gia, với mục tiêu là bắt được Tướng đối phương hoặc bao vây quân Tướng. Đầu tiên, chúng ta sẽ nói lịch sử hình thành nên cờ tướng. Cờ Ấn Độ du nhập vào Trung Quốc và trở thành tiền thân cờ tướng cũng như cờ Shogi của xứ Nhật Bản và khi cờ Trung Quốc du nhập vào Triều Tiên thì trở thành cờ Janggi.
Trong khi đó, cờ Ấn Độ du nhập sang Tây phương trở thành cờ vua. Và cuối cùng, người Trung Quốc chuyển thành cờ tướng vào thời kỳ nhà Tống. Nhà sử học người Đức Peter Banaschak đã chỉ ra rằng cờ tướng Baoying, không có "Pháo" trong "Xuanguailu" do đó chưa có Pháo của Niu Sengru, ngài tể tướng của nhà Đường, là nguồn gốc thực sự của cờ tướng hiện đại tức là thời Đường đã manh nha trò chơi cờ tướng hiện đại hoàn toàn xuất hiện bởi người Trung Hoa vào thời kỳ nhà Đường. Tiếp theo, chúng ta đề cập đến bàn cờ.
Về bàn cờ, có dạng là hình chữ nhật do 9 đường dọc và 10 đường ngang cắt nhau vuông góc tại điểm 90 tạo thành. Ở giữa bàn cờ có một khoảng trống được gọi là sông,chia bàn cờ thành hai phần đối xứng bằng nhau. Mỗi bên có một cung Tướng hình vuông do 4 ô hợp thành tại các đường dọc 4, 5, 6 kể từ đường ngang cuối của mỗi bên, trong 4 ô này có vẽ hai đường chéo. Mỗi ván cờ lúc bắt đầu phải có 32 quân cờ chia đều cho mỗi bên gồm 16 quân trắng và 16 quân đen, gồm 7 loại quân.Tuy tên quân cờ của mỗi bên có thể viết khác nhau (ký hiệu theo chữ Hán) nhưng giá trị và cách đi quân của chúng giống nhau hoàn toàn.2 Quân cờ và luật di chuyển của các quân cờ Trong bàn cờ, mỗi quân cờ có một cách di chuyển khác nhau, chúng được di chuyển theo luật như sau: • Tướng: Đi từng ô một, đi ngang hoặc đi dọc.
Tướng luôn trong phạm vi "cung" và không được ra ngoài. "Cung" tức là hình vuông 3x3 được đánh dấu bởi lằng chéo hình chữ X. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 14/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính • Sĩ: Đi chéo 1 ô mỗi nước và phải luôn trong cung. Như vậy quân Sĩ có 5 vị trí hợp lệ và có chức năng bảo vệ tướng.
• Tượng: Đi chéo 2 ô mỗi nước và không được vượt qua sông. Như vậy, trên bàn cờ, quân Tượng có 7 vị trí có thể đi được. • Xe: Đi ngang hoặc dọc trên bàn cờ miễn là đừng bị quân khác cản đường từ điểm đi đến điểm đến. • Pháo: Đi ngang hoặc dọc giống như quân Xe.
Điểm khác biệt muốn ăn quân phải nhảy qua đúng 1 quân nào đó. Khi không ăn, tất cả những điểm từ điểm đi đến điểm đến không có quân nào cản. • Mã: Đi ngang 2 ô và dọc 1 ô (hay dọc 2 ô và ngang 1 ô). Nếu có quân cờ nào đó nằm ngay bên cạnh thì Mã bị cản, không được đi đường đó.
• Tốt: Đi 1 ô mỗi nước. Nếu chưa qua sông, nó chỉ được tiến. Nếu qua sông thì được đi ngang hay tiến, không được lùi. Quân cờ Ký hiệu Số lượng Tướng 1 Sĩ 2 Tượng 2 Xe 2 Pháo 2 Mã 2 Tốt 5 Bảng 2.1: Ký hiệu và số lượng quân cờ mỗi bên Ngoài ra còn tồn tại những luật chơi khác trong trò chơi cờ tướng: • Lộ mặt tướng: Hai quân Tướng không được đối mặt nhau trên cùng một cột.
Luôn luôn phải có một quân nào đó nằm giữa để che mặt. Nước đi để hai tướng đối mặt nhau là không hợp lệ. • An toàn của Tướng: Sau một nước đi, Tướng của bên đi không được để đối phương ăn ngay trong nước kế tiếp. Những nước để Tướng không an toàn là không hợp lệ.
Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 15/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Ván đấu sẽ được kết thúc nếu xảy ra 1 trong những trường hợp sau đây: • Chiếu bí: Nếu một bên chiếu tướng, và đối thủ không có khả năng đỡ, bên chiếu tướng thắng. • Hết nước đi: Nếu bên tới phiên không có nước hợp để đi, bên đó thua. • Sau 120 nước đi của cả 2 bên, mà không có quân cờ nào bị ăn thì hòa nhau. • Cấm chiếu tướng liên tục 10 lần.
• Ăn quân: Khi quân di chuyển đến 1 vị trí được giữ bởi quân đối phương, quân đối phương bị ăn và bị lấy ra khỏi bàn cờ. • Chống tướng: Hai quân Tướng trên bàn cờ không được nằm cùng nhau trên một cột dọc mà không có quân cản nào ở giữa. Nước đi để 2 quân Tướng trong vị trí chống tướng là không hợp lệ.2 Cây tìm kiếm Trong lĩnh vực khoa học máy tính, cây tìm kiếm là cây cấu trúc dữ liệu dạng cây được sử dụng để định vị các khóa cụ thể từ bên trong một tập hợp. Để cây hoạt động như cây tìm kiếm, khóa cho mỗi nút phải lớn hơn bất kỳ khóa nào trong cây con bên trái và nhỏ hơn bất kỳ khóa nào trong cây con bên phải.
Ưu điểm của cây tìm kiếm là hiệu quả về thời gian tìm kiếm của chúng do cây được cân bằng hợp lý, nghĩa là lá ở hai đầu có độ sâu tương đương. Các cấu trúc cây tìm kiếm khác nhau tồn tại, một số trong đó chép chèn và xóa các phần tử hiệu quả, mà các hoạt động đó duy trì sự cân bằng của cây. Cây tìm kiếm được sử dụng trong trò chơi cờ tướng cho việc lưu trữ trạng thái bàn cờ. Mỗi một nút trong cây là một trạng thái bàn cờ và các cạnh của nó tương ứng với nước đi.
Số lượng các trạng thái có thể sinh ra từ một trạng thái là số con của nút đó trong cây. Khi bắt đầu vào là trạng thái bàn cờ, trò chơi sẽ tính toán các nước đi hợp lệ. Kết hợp với với trạng thái bàn cờ và nước đi hợp lệ sẽ tạo ra được trạng thái tiếp theo cho bàn cờ. Thực hiện tương tự như vậy ta có thể xây dựng được cây tìm kiếm từ đầu vào là trạng thái bàn cờ.
Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 16/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Hình 2.3 Giải thuật tìm kiếm Minimax Minimax là một quy tắc quyết định được sử dụng trong AI (Artificial Intelli- gence), lý thuyết quyết định (decision theory), lý thuyết trò chơi (game theory), thống kê,. cho việc giảm thiểu tổn thất có thể xảy ra đối với trường hợp xấu nhất. Khi xử lý, nó được gọi là ’maximin’, để tối đa hóa mức tối thiểu. Ban đầu được xây dựng cho lý thuyết trò chơi tổng bằng 0 của n người chơi, bao gồm cả trường hợp người chơi thực hiện các nước đi thay thế và những trường hợp họ thực hiện các bước đi đồng thời.
Nó cũng được mở rộng sang các trò chơi phức tạp hơn và ra quyết định chung khi không chắc chắn. Một giải thuật Minimax là một thuật toán đệ quy cho việc lựa chọn các bước đi kế tiếp trong trò chơi. Mỗi trạng thái hay vị trí của trò chơi đều được gán giá trị. Dựa vào hàm tính giá trị vị trí ta sẽ tính toán được giá trị này và biết được độ hiệu quả nếu đạt được vị trí này.
Người chơi sau đó có thể thực hiện các nước đi để tối đa giá trị tối thiểu của vị trí kết quả từ các nước đi có thể của đối thủ. 1 function minimax(node, depth, maximizingPlayer) is Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 17/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính 2 if depth = 0 or node is a terminal node then 3 return the heuristic value of node 4 if maximizingPlayer then 5 value := -infty 6 for each child of node do 7 value := max(value, minimax(child, depth - 1, FALSE)) 8 return value 9 else (* minimizing player *) 10 value := +infty 11 for each child of node do 12 value := min(value, minimax(child, minimax(child, depth - 1, TRUE)) 13 return value 2.4 Giải thuật cắt tỉa Alpha-Beta Cắt tỉa Alpha-Beta là một giải thuật tìm kiếm nhầm giảm số lượng các nút được đánh giá bởi giải thuật Minimax trong cây tìm kiếm của nó. Nó là một giải thuật tìm kiếm đối nghịch được sử dụng phổ cho các máy trò chơi của hai người chơi (Tic-tac-toe, cờ vây, cờ vua. Nó ngừng đánh giá một nước đi khi ít nhất một khả năng được tìm thấy chứng tỏ nước đi đó tệ hơn một nước đi đã được kiểm tra trước đó.
Những nước đi như vậy không cần phải đánh giá thêm. Khi áp dụng cho một cây Minimax tiêu chuẩn, nó sẽ tra lại cùng một nước đi như Minimax sẽ làm nhưng cắt bỏ những nhánh không ảnh hưởng đến quyết định cuối cùng. 1 function alphabeta(node, depth, alpha, beta, maximizingPlayer) is 2 if depth = 0 or node is a terminal node then 3 return the heuristic value of node 4 if maximizingPlayer then 5 value := -infty 6 for each child of node do 7 value := max(value, alphabeta(child, depth - 1, alpha, beta, FALSE)) 8 alpha := max(alpha, value) 9 if alpha >= beta then 10 break (* beta cutoff *) 11 return value 12 else 13 value := +infty 14 for each child of node do 15 value := min(value, alphabeta(child, depth - 1, alpha, beta, Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 18/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính TRUE)) 16 beta := min(beta, value) 17 if beta <= alpha then 18 break (* a cutoff *) 19 return value 2.