TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Báo cáo
Trò chơi cờ úp trên nền android sử dụng
thuật toán Alpha-Beta cắt tỉa
Sinh viên thực hiện: Phạm Xuân Cường 20090438
Đinh Minh Quốc 20092156
Nguyễn Quốc Vinh 20093277
Lê Thanh Tùng 20093106
Ngô Việt Linh 20091599
Trần Thanh Sơn 20092281
Hà Nội 07/2013
Mục lục
Sinh viên thực hiện: Phạm Xuân Cường 20090438 1
Mục lục 2
I. Đặt vấn đề bài toán
1. Giới thiệu trò chơi cờ úp:
Cờ úp là một biến thể của trò chơi cờ Tướng, sử dụng bàn
cờ và các quân giống trong cờ Tướng. Trong trò chơi này, tại
thời điểm bắt đầu, các quân cờ mỗi bên trên bàn sẽ được úp
xuống một cách ngẫu nhiên. Nước đi đầu tiên của cờ úp phải
tuân theo luật đi của cờ tướng tại vị trí nó đang chiếm giữ. Sau
nước đầu, các quân cờ được lật lại và từ nước này, quân cờ sẽ đi
theo luật của cờ Tướng thông thường
Luật đi các quân cờ
• Tướng: Mỗi nước đi một ô, đi ngang hoặc dọc. Tướng luôn ở
trong phạm vi cung."Cung" gồm 4 hình vuông nhỏ được gạch
đường chéo.
• Sĩ: Đi chéo, mỗi nước một ô. Sĩ luôn ở trong "Cung" giống
như Tướng.
• Tượng: Đi chéo 2 ô mỗi nước, đi ngang hoặc dọc. Tượng

Xây dựng ứng dụng mô phỏng trò chơi cờ úp giữa người
với máy, người với người trên nền tảng điện thoại android
3. Mô tả không gian trạng thái của bài toán
• Trạng thái đầu: Là trạng thái của bàn cờ tại thời điểm bắt đầu
cuộc chơi. Trạng thái được thể hiện ở hình dưới. Với trò chơi
này, mỗi trạng thái ban đầu được sinh ngẫu nhiên từ 2.17! khả
năng
• Trạng thái đích: Là trạng thái mà một trong hai quân tướng
của hai bên bị ăn mất hoặc quân tướng không còn nước đi
hợp lệ. Khi đó, bên còn lại là người thắng cuộc
• Trạng thái trung gian: Là trạng thái hợp lệ của bàn cờ tại một
thời điểm bất kỳ trong một ván đấu
• Các cạnh nối: Trạng thái bàn cờ tại mức i và mức (i+1) có
cạnh nối với nhau nếu trạng thái mức (i+1) được sinh ra từ
trạng thái mức I bằng cách di chuyển một quân cờ trên bàn
theo một bước đi hợp lệ của nó
II. Phương pháp giải quyết
1. Giới thiệu thuật toán
1.1. Thuật toán MINIMAX :
Đây là thuật toán thường được sử dụng trong các trò
chơi đối kháng hai bên. Giả sử mỗi trạng thái của bàn cở
được gắn một giá trị cụ thể. Người chơi Max sẽ chọn nước
đi dẫn đến điểm của mình lớn hơn, trong khi Min sẽ tìm
các nước đi để điểm của mình nhỏ đi. Các giá trị điểm của
trạng thái bàn cờ được xác định thông qua hàm lượng giá
của trò chơi
Ví dụ về thuật toán MINIMAX:
Xét một cây như hình vẽ, tại thời điểm ban đầu,
Max chọn nút có giá trị 3. Đến lượt đi của Min, Min sẽ
chọn nút hoặc có giá trị bằng 2. Đến lượt đi của

xuống hết độ sâu lớp theo kiểu tìm kiếm sâu, đồng thời áp
dụng đánh giá heuristic cho một trạng thái và tất cả các
trạng thái anh em của nó. Giả thuyết tất cả đều là nút MIN.
Giá trị tối đa của các nút MIN này sẽ được truyền ngược
lên cho nút cha mẹ (là một nút MAX). Sau đó giá trị này
được gán cho ông bà của các nút MIN như là một giá trị
beta kết thúc tốt nhất. Tiếp theo thuật toán này sẽ đi xuống
các nút cháu khác và kết thúc việc tìm kiếm đối với nút
cha mẹ của chúng nếu gặp bất kỳ một giá trị nào lớn hơn
hoặc bằng giá trị beta này. Quá trình này gọi là cắt tỉa
beta (β cut). Cách làm tương tự cũng được thực hiện cho
việc cắt tỉa alpha (α cut) đối với các nút cháu của một nút
MAX.
Hai luật cắt tỉa dựa trên các giá trị alpha và beta là:
o Quá trình tìm kiếm có thể kết thúc bên dưới một nút
MIN nào có giá trị beta nhỏ hơn hoặc bằng giá trị alpha
của một nút cha MAX bất kỳ của nó.
o Quá trình tìm kiếm có thể kết thúc bên dưới một nút
MAX nào có giá trị alpha lớn hơn hoặc bằng giá trị
beta của một nút cha MIN bất kỳ của nó.
Việc cắt tỉa alpha – beta như vậy thể hiện quan hệ giữa
các nút ở lớp n và các nút ở lớp n+2 và do quan hệ đó toàn
bộ các cây con bắt nguồn ở lớp n+1 đều có thể loại khỏi
việc xem xét. Chú ý rằng giá trị truyền ngược thu được
hoàn toàn giống như kết quả Minimax, đồng thời tiết kiệm
được các bước tìm kiếm một cách đáng kể.
Thuật toán được mô tả qua mã giả sau
2. Hàm chi phí
Hàm chi phí của trò chơi tại mỗi trạng thái được đánh giá dựa
trên ba yếu tố

III. Cài đặt chương trình
Chương trình được cài đặt trên các máy chạy hệ điều hành
android thông qua file .apk
Giao diện của chương trình
Bắt đầu ván chơi
Kết thúc ván chơi
IV. Đánh giá chương trình
• Chương trình mô phỏng thành công trò chơi cờ úp trên nền
android
• Trong tương lai, sẽ cải tiến thêm các mức độ khó vào trong
trò chơi