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 MÔN TRÍ TUỆ NHÂN TẠO
Ứng dụng Alpha-beta cắt tỉa xây dựng game cờ tướng
GVHD: Thầy Phạm Văn Hải
Nhóm thực hiện: 6
Lê Văn Thành 20102156
Lê Minh Quân 20102034
Tạ Văn Trường 20102404
Nguyễn Đức Thọ 20102258
Nguyễn Văn Thông 20102261
Nguyễn Trọng Hiển 20101533
Mục lục
Phần 1: Tổng quan về các vấn đề liên quan
1. Giới thiệu về trò chơi cờ tướng
Trò chơi cờ tướng là một trong những trò chơi thể thao trí tuệ hấp dẫn,
được đưa vào thi đấu quốc tế. Cờ tướng có xuất xứ từ Trung Quốc và nhanh
chóng được nhiều người chơi trên toàn thế giới. Cờ tướng cũng giống như các
môn cờ khác là trò chơi đối kháng 2 người, người chơi sử dụng kĩ năng, tư duy
chiến thuật để giành chiến thắng. Cờ tướng cũng là một loại cờ có nhiều chiến
thuật, áp dụng nhiều tư duy nhất. Cờ tướng nhìn qua có vẻ giống cờ vua nhưng
luật di chuyển và khống chế phạm vi của quân cờ được áp đặt lên, làm cho
người chơi có thêm nhiều chiến thuật trong cách phòng ngự và tấn công.
Bàn cờ tướng có kích thướng 9x10, ở thời điểm xuất phát 2 bên được phân
cách bởi sông (còn gọi là “hà”), người chiếm được “hà” sẽ có nhiều lợi thế
trong tấn công. Cờ tướng gồm 7 quân cờ chính: Tướng, Sĩ, Tượng, Xe, Pháo,
Mã, Tốt.
2. Windows Phone và framework XNA 4.0
Hiện nay, điện thoại di động ngày càng phổ biến và tiện lợi, việc sở hữu 1
chiếc smartphone là rất dễ dàng. Các ứng dụng trên điện thoại có rất nhiều với

Xây dựng thuật toán chạy AI -> lớp computer
3
Nhóm 63
Figure 2: biểu đồ lớp tổng quan
Figure 3: biểu đồ lớp kết tập
4
Phần 2: Xây dựng thuật giải Alpha-Beta PruningPhần 2: Xây dựng thuật giải
Alpha-Beta PruningPhần 2: Xây dựng thuật giải Alpha-Beta Pruning
4
3. Thiết kế chi tiết cho các lớp
Figure 4: Biểu đồ lớp chi tiết
Xác định nước đi kế tiếp cho các quân cờ
Tại mỗi bàn cờ nhất định, chúng ta cần duyệt qua tất cả các cách đi của các
quân cờ để tìm ra nước đi tối ưu tiếp theo. Muốn làm được điều đó ta cần biết
đặc điểm và cách đi của từng quân cờ.
Luật chơi cờ tướng cơ bản :
5
Nhóm 65
Luật di chuyển các quân cờ như sau:
1. 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.
2. Sĩ: Đi chéo, mỗi nước một ô. Sĩ luôn ở trong "Cung" giống như Tướng.
3. Tượng: Đi chéo 2 ô mỗi nước, đi ngang hoặc dọc. Tượng không được phép
qua sông sang bàn cờ của đối phương.Nước đi của Tượng không hợp lệ khi có
quân cờ chặn giữa đường.
4. Xe: Đi ngang hoặc dọc khắp bàn cờ miễn không có quân khác cản trên
đường đi.
5. Mã: Đi ngang 2 ô và đi dọc 1 ô ( hoặc đi dọc 2 ô và đi ngang 1 ô) cho mỗi
nước đi.Nếu có quân khác nằm cạnh mã và cản đường ngang 2 hoặc cản
đường dọc 2, thì mã không được đi đường đó.

If then ( quân tượng đi được tới ô a[i-2,j-2]
If then ( quân tượng đi được tới ô a[i-2,j+2]
If then ( quân tượng đi được tới ô a[i+2,j-2]
7
Nhóm 67
If then ( quân tượng đi được tới ô a[i+2,j+2]
4. Xe :
+ For (k=i+1 , k<11 , k++)
If ( a[k,j]==0 ) then (cập nhật nước đi của quân xe)
else break;
+ For (k=i-1 , k>0 , k )
If ( a[k,j]==0 ) then (cập nhật nước đi của quân xe)
else break;
+ For (k=j+1 , k<10 , k++)
If ( a[i,k]==0 ) then (cập nhật nước đi của quân xe)
else break;
+ For (k=j-1 , k>0 , k )
If ( a[i,k]==0 ) then (cập nhật nước đi của quân xe)
else break;
5. Mã :
If then ( quân mã đi được tới ô a[i-2,j-1] )
If then ( quân mã đi được tới ô a[i-2,j+1] )
If then ( quân mã đi được tới ô a[i+1,j+2] )
If then ( quân mã đi được tới ô a[i-1,j+2] )
If then ( quân mã đi được tới ô a[i-2,j+1] )
If then ( quân mã đi được tới ô a[i-2,j-1] )
If then ( quân mã đi được tới ô a[i-1,j-2] )
If then ( quân mã đi được tới ô a[i+1,j-2] )
6. Pháo :
+ For (k=i+1 , k<11 , k++)

• Mimimax là giải thuật áp dụng vào các trò chơi mang tính đối kháng, 1
người chơi là Max, 1 người chơi là Min. Minimax sử dụng tri thức là 1 hàm
lượng giá, khi khởi tạo hàm lượng giá này có giá trị là 0, ứng với khả năng
giành chiến thắng của Max và Min là như nhau.
• Nước đi của Max ảnh hướng đến nước đi của Min và ngược lại, Max tìm
cách cực đại hóa hàm lượng giá, Min tìm cách cực tiểu giá trị này.
• Cây trò chơi Minmax được hình thành từ trạng thái bắt đầu và các nước
đi hợp lệ của Max (Min).
• Giải thuật Minimax tìm kiếm nước đi có lợi nhất dựa và hàm đánh giá, ở
các cây con của Max, Max chọn các trạng thái tốt nhất với nó là những
trạng thái hàm đánh giá cực đại và ngược lại với Min, nó chọn các trạng
thái sao cho hàm đánh giá là nhỏ nhất.
• Độ phức tạp của Minimax tăng theo hàm mũ và phụ thuộc vào độ sâu tìm
kiếm. Trên thực tế không có máy tính nào cho phép tính đến trạng thái
đích từ trạng thái bắt đầu, vì cây trò chơi là quá lớn vì thế chỉ có thể cài
đặt ở một độ sâu nhất định, đảm bảo về mặt thời gian.
Với sự bùng nổ của cây trò chơi Minimax và giải thuật Minimax cổ điển không
có sự tối ưu nào để giảm bớt sự phức tạp tìm kiếm, bỏ bớt những nút không
tối ưu. Chính vì thế người ta đã áp dụng cắt tỉa Alpha-beta vào việc tối ưu tìm
kiếm.
10
Phần 2: Xây dựng thuật giải Alpha-Beta PruningPhần 2: Xây dựng thuật giải
Alpha-Beta PruningPhần 2: Xây dựng thuật giải Alpha-Beta Pruning
10
2. Thuật giải Alpha-beta cắt tỉa
Tư tưởng của cắt tải alpha-beta: “Nếu một nhánh tìm kiếm nào đó không
thể cải thiện đối với giá trị (hàm tiện ích) mà chúng ta đã có, thì không cần
xét đến nhánh tìm kiếm đó nữa!”
Cắt tỉa Alpha-beta được áp dụng vào nhằm cắt tỉa bớt những nhánh tồi tiết
kiệm chi phí thời gian, bộ nhớ cho cây tìm kiếm.

β: = min (β, alphabeta (trẻ em, độ sâu - 1, α, β, không
(maximizingPlayer)))
nếu β ≤ α
phá vỡ (* Alpha cắt *)
trở β
(* Ban đầu gọi *)
alphabeta (nguồn gốc, độ sâu, vô tận, vô cực, TRUE)
Cải thiện hơn nữa có thể đạt được mà không bị mất độ chính xác, bằng cách sử
dụng heuristic để tìm kiếm các bộ phận của cây có khả năng buộc cuto•s alpha-
beta đầu. Ví dụ, trong cờ vua, di chuyển mà phải mất mảnh có thể được kiểm
tra trước khi di chuyển mà không làm, hoặc di chuyển mà đã ghi được đánh giá
cao trong đường chuyền trước đó thông qua phân tích trò chơi cây có thể
được đánh giá trước những người khác. Khác thường, và rất rẻ, heuristic là
các phỏng đoán kẻ giết người , mà di chuyển cuối cùng gây ra một phiên bản
beta-cắt cùng cấp trong việc tìm kiếm cây luôn luôn kiểm tra đầu tiên. Ý tưởng
này có thể được khái quát thành một tập hợp các bảng bác bỏ .
Tìm kiếm alpha-beta có thể được thực hiện nhanh hơn bằng cách xem xét chỉ
có một cửa sổ tìm kiếm hẹp (thường được xác định bởi các dự đoán dựa trên
kinh nghiệm). Này được gọi là tìm kiếm khát vọng. Trong trường hợp cực đoan,
việc tìm kiếm được thực hiện với alpha và beta bằng, một kỹ thuật được gọi
là không-cửa sổ tìm kiếm, null-cửa sổ tìm kiếm, hoặc tìm kiếm trinh sát. Điều
này đặc biệt hữu ích cho thắng / thua tìm kiếm ở gần cuối của một trò chơi, nơi
độ sâu thêm thu được từ cửa sổ hẹp và thắng / thua chức năng đánh giá đơn
giản có thể dẫn đến một kết quả thuyết phục. Nếu một khát vọng tìm kiếm thất
bại, nó là đơn giản để phát hiện xem nó không thành công cao (cạnh cao của
cửa sổ quá thấp) hoặc thấp (cạnh dưới của cửa sổ là quá cao). Điều này cung
cấp thông tin về những gì giá trị cửa sổ có thể có ích trong một lại tìm kiếm vị
trí này.
Một số biểu diễn minh họa
12

2
3. Áp dụng vào bài toán chơi cờ tướng
a) Hàm lượng giá
Tri thức áp dụng vào bài toán sao cho đánh giá đúng được thế cờ, giá trị bàn cờ
để có được lợi thế trong trò chơi cờ tướng.
Máy tính muốn tìm được lời giải bài toán buộc phải qui bài toán về các con số
có thể tính toán được, do đó căn cứ vào thế cờ (bàn cờ) máy sẽ gán cho nó
một điểm số (lượng giá tĩnh) để đánh giá độ tốt xấu. Nhờ điểm này máy mới có
thể so sánh các thế cờ với nhau và biết chọn nước đi tốt nhất. Đâylà một nhiệm
vụ rất khó khan và phức tạp do không tồn tại một thuật toán tổng quát và
14
min
min
max
max
min
max
Min
max
Phần 2: Xây dựng thuật giải Alpha-Beta PruningPhần 2: Xây dựng thuật giải
Alpha-Beta PruningPhần 2: Xây dựng thuật giải Alpha-Beta Pruning
14
thống nhất nào để tính điểm cả. Điểm của một thế cờ dựa trên rấtnhiều yếu tố
mà khó có thể số hoá hết được như phụ thuộcvào số lượng và giá trị các quân
cờ hiện tại, phụ thuộc vào tính hãm, tính biến, thếcông, thế thủ của từng quân
cờ cũng như cả cục diệntrận đấu. Ví dụ, một cặp Mã giao chân, có thể sát
Cánh tiến quân và tựa lưng phòng thủ thường có giá hơn hai Mã đứng rời.
Nhưng cũng có lúc hai Mã đứng rời lại tốthơn hai Mã giao chân khi Mã này lại
cản Mã kia trong một thế trận nào đó. Ta cũng biết rằng, "lạc nước hai Xe đành
bỏ phí, gặp thời một Tốt cũng Thành công", thế nhưng số hoá điều này qua

Nhóm 615
{
Computer com = new Computer();
if (depth == 0 || board.CheckWinNegativeTeam() ||
board.CheckWinPositiveTeam())
{
com.Value = board.Value;
com.Board = board.Clone();
return com;
}
if (player == 1)
{
foreach (var b in GenerateBoardPositiveTeam(board))
{
int temp = AlphaBetaPruning(b, alpha, beta, depth - 1, -1).Value;
i++;
if (temp > alpha)
{
alpha = temp;
com.Value = alpha;
com.Board = b.Clone();
}

if (beta <= alpha) return com;
}
return com;
}
else
{
foreach (var b in GenerateBoardNegativeTeam(board))

trình sẽ nhanh hơn và tối ưu hơn.
17
Nhóm 617
4. Phương án tối ưu cho bài toán
a) Tối ưu hàm lượng giá
• Đánh giá giá trị các quân cờ 1 cách chính xác và tỉ mỉ hơn: Phân tích tình
huống cờ theo giai đoạn: Khai cuộc – Trung cuộc - Tàn cuộc, ở mỗi giai
đoạn có các định giá khác nhau.
• Với mỗi quân cờ cũng có nhiều thay đổi về giá trị (ví dụ: mã ở thế kẹt,
pháo mất nòng, …).
b) Tối ưu thời gian tìm kiếm
Thời gian chạy giải thuật Alpha-beta phụ thuộc nhiều vào độ sâu và sự phân
nhánh. Độ sâu ở một mức là cố định như vậy ta cố gắng tìm kiếm tối ưu sư
phân nhánh.
Nếu lời giải càng nằm về phía bên trái, nhánh được tìm thấy trước sẽ càng cắt
tải được nhiều. Do đó nhóm đề xuất cách sắp xếp các quân cờ để khi sinh các
bàn cờ, mình có những bàn cờ tối ưu đặt trước, xét trước như vậy sẽ cắt tỉa
được nhiều
Nhóm đã áp dụng sắp xếp các quân Xe, Pháo, Mã lên trước, vì các bàn cờ
do các con này sinh có giá trị hơn các bàn cờ do quân Tốt, Sĩ, Tượng,
Tướng gây ra. Do đó cắt tỉa được nhiều.
Cách sắp xếp còn tỏ ra hiệu quả khi các bàn cờ có giá trị bằng nhau thì chọn bàn
cờ nào trước, cách sắp xếp như vậy tuy chưa hoàn toàn hiệu quả, nhưng đem
lại nhiều lợi ích và nhiều nước đánh giá được cho là tốt
5. Thống kê cài đặt thuật toán thành công
Việc triển khai ứng dụng chạy trên thiết bị di động Nokia Lumia 520 hệ điều
hành Windows Phone 8 vô cùng khó khawn khi thuật toán chạy ì ạch ở mức độ
sâu thấp
Vì thế nhóm đã triển khai một phiên bản tương tự chạy trên desktop có thể
test được ở độ sâu 4 thời gian chờ ~3s

viết báo cáo, làm slide, test chương
trình
Nguyễn Đức Thọ Cài đặt giải thuật, xây dựng cây trò
chơi, đề xuất các phương án tối ưu,
lượng giá cho quân cờ
Tạ Văn Trường Nghiên cứu giải thuật để đi đến cài
đặt, lượng giá cho quân cờ
Lê Minh Quân Code chi tiết các lớp quân cờ, bàn cờ,
test chương trình
Nguyễn Văn Thông Xây dựng phương thức sinh các nước
đi kế tiếp cho các quân cờ
Nguyễn Trọng Hiển Thiết kế giao diện
Tài liệu tham khảo
Slide môn Trí tuệ nhân tạo – Nguyễn Nhật Quang
Thuật giải Minimax dịch trên mạng – Phạm Hồng Nguyên
Discovering Chinese Chess Strategies through Coevolutionary
Approaches - C. S. Ong, H. Y. Quek, K. C. Tan and A. Tay
20
Phần 2: Xây dựng thuật giải Alpha-Beta PruningPhần 2: Xây dựng thuật giải
Alpha-Beta PruningPhần 2: Xây dựng thuật giải Alpha-Beta Pruning
20