Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức
Sinh viên thực hiện:
Nguyễn Anh Dũng MSSV: 20090572
Đinh Văn Đông MSSV: 20090755
Phan Văn Thìn MSSV: 20093692
Lê Minh Đức MSSV: 20090787
Lâm Viết Tùng MSSV: 20093097
Đinh Tiến Sĩ MSSV: 20092222
Nhóm thực hiện: Nhóm 10
Giảng viên hướng dẫn : TS Phạm Văn Hải
Chương Trình Chơi Cờ Tướng Tự Động
Sử Dụng Giải Thuật Alpha-Beta Pruning
TRÍ TUỆ NHÂN TẠO
Bài Tập Lớn
Hà Nội, 07-2013
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
__________*__________
1
Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

MỤC LỤC
THÔNG TIN CHUNG
1. Sinh viên thực hiện
Nguyễn Anh Dũng MSSV: 20090572
Đinh Văn Đông MSSV: 20090755
Phan Văn Thìn MSSV: 20093692
Lê Minh Đức MSSV: 20090787
Lâm Viết Tùng MSSV: 20093097

dành cho hai người, là loại cờ được phổ biến nhất thế giới cùng với cờ vua.
Tại Trung Quốc, cờ tướng được biết đến từ thế kỷ thứ 4 TCN.
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức
3
Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

Mỗi ván cờ được tiến hành giữa hai người, một người cầm quân trắng (hay đỏ), một người
cầm quân Đen (hay xanh lá cây). Mục đích của mỗi người là tìm cách đi quân trên bàn cờ theo
đúng luật để chiếu bí hay bắt tướng của đối phương và giành thắng lợi.
Việc xây dựng chương trình mà máy tính có thể chơi cờ tướng với người chơi thông thường
có thể chuyển về một dạng bài toán tìm kiếm đặc biệt: tìm kiếm đường đi đến các điểm cao
nhất giữa hai đấu thủ hay là tìm kiếm Minimax. Đây cũng là một chiến lược tìm kiếm trong trí
tuệ nhân tạo ứng dụng để máy tính có thể thực hiện các trò chơi thông minh như con người.
Các trạng thái bàn cờ khác nhau trong quá trình chơi có thể biểu diễn thành một cây tìm kiếm
và ta sẽ tiến hành tìm kiếm trên cây để tìm được nước đi tốt nhất.
Việc mô phỏng làm cho máy tính có thể chơi cờ tướng như con người không chỉ giúp ta
hình dung rõ ràng hơn về môn học trí tuệ nhân tạo cụ thể hơn là mảng tìm kiếm mà còn có giúp
chúng ta hiểu hơn về việc áp dụng lập trình hướng đối tượng vào các game đối kháng. Đây cũng
là mong muốn của chúng em khi học môn trí tuệ nhân tạo.
Để hoàn thành bài tập lớn này, chúng em xin được gửi lời cảm ơn chân thành tới :
Thầy giáo hướng dẫn T.S Phạm Văn Hải, giảng viên khoa hệ thống thông tin đã giúp đỡ,
hướng dẫn, chỉ dạy để chúng em hoàn thành được bài tập lớn này.
Hà Nội, ngày 01 – 08 – 2013.
PHẦN 1: KHẢO SÁT VÀ ĐẶC TẢ YÊU CẦU BÀI TOÁN
1.1 MỤC ĐÍCH
Bài toán đặt ra là cần xây dựng chương trình mà máy tính có thể tự động chơi cờ tướng
như con người, thi đấu với đấu thủ là người chơi.
Có hai đấu thủ (máy tính và người chơi), mỗi người chỉ được đi một nước khi tới lượt theo
tập luật của cờ tướng.
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức

• Đánh giá một thế cờ.
• Xử lý một nước đi thử.
• Tìm kiếm alpha-beta.
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức
5
Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

• Xử lý điều khiển của người chơi.
• Cập nhật một nước đi mới của người chơi.
Sau đó để tiện cho người chơi theo dõi một số thông tin như : thời gian suy nghĩ của 2 đấu
thủ, ghi lại số quân mỗi bên đã bắt được …. Ta thực hiện tiếp công việc : hiện một số thông tin
cần thiết cho trò chơi và chạy thử chương trình.
Hình : Các bước thực hiện bài toán
PHẦN 2: PHÂN TÍCH VÀ THIẾT KẾ BÀI TOÁN
2.1 GIẢI QUYẾT CÁC MỤC TIÊU ĐẶT RA VỚI NGƯỜI CHƠI
XÂY DỰNG BÀN CỜ
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức
6
Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

Hình : Khung bàn cờ
Bàn cờ là một JPanel, khung bàn cờ sẽ được vẽ trên JPanel này.
Việc vẽ khung bàn cờ là vẽ các đường ngang và dọc (gồm có 10 đường ngang, 9 đường
dọc), việc này sẽ được đảm nhiệm bởi hàm DrawLine(x1, y1, x2, y2) trong lớp Graphics của Java
(trong đó x1, y1 là tọa độ ta bắt đầu vẽ, x2, y2 là tọa độ ta kết thúc vẽ)
Bắt đầu ta vẽ 5 đường ngang, sau đó vẽ 9 đường dọc giao với 9 đường ngang đó, các vị trí
nước đi trong cung của tướng được đánh dấu bởi dấu X, sẽ được xây dựng là 2 đường thẳng
giao nhau (đường đầu tiên là từ vị trí thứ 4 tới vị trí thứ 24 trên bàn cờ, đường thứ 2 là từ vị trí
thứ 6 tới vị trí thứ 22 của bàn cờ) như vậy ta hoàn thành việc vẽ ½ bàn cờ
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức

mình. Sẽ được thực hiện thông qua phương thức nhận sự kiện click trên chuột của mỗi JLabel
đại diện cho từng quân cờ ở trên, sau khi sự kiện xảy ra các biến toàn cục (vị trí các quân cờ,
lượt đi của mỗi bên, …) sẽ được cập nhật để đến lượt đối phương thực hiện nước đi của mình.
2.2 GIẢI QUYẾT CÁC MỤC TIÊU ĐẶT RA VỚI MÁY
XÂY DỰNG LUẬT ĐI HỢP LỆ CHO CÁC QUÂN CỜ
Việc duyệt hết các nước đi trên bàn cờ trước hết đòi hỏi ta phải nắm rõ luật đi hợp lệ của
các quân cờ trên bàn cờ tướng.
Ta có thể nhắc lại luật đi của từng quân trên bàn cờ như sau :
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức
9
tướng : chỉ được đi trong cung,
trái phải trên dưới 1 nước
tốt : tiến
bên mình : lên trên
đối phương : thêm trái
phải
sĩ : tiến lùi một ví trí trong
dấu X
tượng : chỉ ở bên mình, đi
đường chéo của 4 ô, có
cản
xe : ngang, dọc tung
hoành
pháo ngang dọc tung
hoành, nổ khi bị chặn
mã : tung hoành, đi
đường chéo 2 ô, có cản
Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

Hình : Luật đi hợp lệ của các quân cờ

sẽ được đi đến)
}
}
Đó là ý tưởng chính của việc thực hiện sinh mọi nước đi hợp lệ từ một thế cờ, tuy nhiên ta
còn một số lưu ý khi triển khai là :
Việc kiểm tra trong một hướng đi, khi nào quân đó vượt khỏi bàn cờ (kiểm tra giới hạn bàn
cờ), ta có thể xác định bằng việc mở rộng mảng 90 ô bàn cờ thành mảng 13 * 14 (182 ô bàn cờ
do thêm vào chiều dọc và chiều ngang mỗi bên 4 đường ngoài cùng đánh dấu các vị trí vượt giới
hạn bàn cờ - lý do phải thêm mỗi chiều bốn đường là do quân tượng và quân mã có khả năng
vượt ra khỏi bàn cờ 2 đường), việc có mảng giới hạn bàn cờ này, nên ta có thể dễ dàng kiểm tra
quân cờ mà vượt giới hạn bằng cách kiểm tra xem khi mà vị trí chúng đi đến tiếp theo mà nằm
trong 4 hai bên ngoài cùng của bàn cờ mở rộng thì việc thực hiện đi nước trong hướng đó là kết
thúc.
Việc tiếp theo mà ta cần quan tâm là, một số quân (tượng, sĩ, tướng và tốt) sẽ bị giới hạn vị
trí trong bàn cờ, ta sẽ thiết lập mảng giới hạn chúng, khi mà chúng rơi vào mảng này thì không
thiết lập nước đi.
Do đó khi rơi vào hai trường hợp trên thì hướng đi của các quân này kết thúc.
Việc thực hiện nước đi tiếp theo, sẽ là việc thiết lập chỉ số vị trí sẽ đến bằng với chỉ số hiện
tại cộng với một khoảng tiến trong một nước (của hướng đang xét), sẽ có mảng hai chiều lưu
các quân cờ, vị trí tiến trong mỗi hướng của từng quân, việc tính chỉ số tiếp theo sẽ chỉ việc lấy
tham số cần cộng trong mảng tương ứng với hướng đó, và giá trị cộng nước đi trong hướng đó
cộng với vị trí hiện tại.
Với quân tượng, mã có các vị trí cản mà ta không thể đi được việc này sẽ được kiểm tra
bằng các vị trí cản xung quanh quân tượng và quân mã có trống không, nếu không trống thì
không thực hiện nước đi này (sẽ có 2 mảng lưu tương ứng vị trí cản của hai quân này).
Với quân pháo có đặc tính là có khả năng nổ khi có quân chặn trước mặt nó, do vậy khi có
quân chặn trước mặt nó, ta có thể dùng một biến để đánh dấu rằng có quân chặn trước mặt nó,
và khi thực hiện nước đi tiếp theo trong hướng thì kiểm tra biến chặn trước mặt pháo, nếu có
nó và có quân đối phương tiếp theo thì thực hiện nước đi đó, sau đó lại thiết lập lại biến chặn
trước mặt.

Beta.
Trước khi nói về hàm alpha-beta ta nói về hàm minimax :
Chúng ta có một bộ phận phân tích thế cờ có thể áp dụng được tất cả các luật, các phương
pháp đánh cờ khác nhau vào từng thế cờ và chuyển đổi chúng thành một con số đại diện (cho
điểm thế cờ). Mặt khác ta giả sử con số đó là dương khi áp dụng cho thế cờ của một đấu thủ
(được gọi là người chơi cực đại – maximize), và là âm khi áp dụng cho đấu thủ bên kia (được gọi
là người chơi cực tiểu – minimizer). Quá trình tính toán cho điểm thế cờ được gọi là lượng giá
tĩnh (static evalution). Hàm thực hiện việc tính toán được gọi là một bộ lượng giá tĩnh, và giá trị
nhận được gọi là điểm lượng giá tĩnh. Cả hai đấu thủ đều cố gắng đi như thế nào đó để đạt
được điểm tuyệt đối lớn nhất. Người chơi cực đại sẽ tìm những nước đi dẫn đến điểm của mình
trở nên lớn hơn (hay cao nhất có thể được) hay điểm của đối thủ bớt âm hơn (nhỏ hơn về giá
trị tuyệt đối). Còn đối thủ của anh ta, người chơi cực tiểu, lại ra sức phản kháng lại, để dẫn tới
điểm âm của anh ta âm hơn hay điểm dương của đối thủ nhỏ đi.
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức
13
Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

Thuật toán minimax :
- nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm), tính giá trị tĩnh
của thế cờ hiện tại ứng với người chơi ở đó. Ghi nhớ kết quả.
- nếu như mức đang xét là của người chơi cực tiểu, áp dụng thủ tục Minimax này cho các
con của nó. Ghi nhớ kết quả nhỏ nhất.
Nếu như mức đang xét là của người chơi cực đại, áp dụng thủ tục Minimax này cho các con
của nó. – ghi nhớ kết quả lớn nhất.
Giả mã cho thuật toán :
Function Minimax(pos, depth) : integer;
Begin
If depth = 0 then
Minimax = eval(pos) – tính điểm giá trị thế cờ pos
Else begin

begin
if(depth = 0) then minimax = eval – tính thế cờ pos trong biến toàn cục
else begin
best = - INFINITY;
Gen – sinh ra mọi nước đi từ thế cờ pos
While còn lấy được một nước đi m do
Begin
Thực hiện nước đi m;
Value = - minimax(depth – 1)
Bỏ thực hiện nước đi m;
If(value > best) best = value;
End;
Minimax = best
end
end
Rõ ràng với Minimax khi độ sâu thực hiện càng tăng thì cây nước đi càng đồ sộ, số lượng
phép tính càng tăng, ta cần có thêm những cải tiến để cải thiện tình hình.
Thủ tục AlphaBeta : thủ tục AlphaBeta là một cải tiến thuật toán Minimax nhằm tỉa bớt
nhánh của cây trò chơi, làm giảm số lượng nút phải sinh và lượng giá, do đó có thể tăng độ sâu
của cây tìm kiếm. Giả sử hình 1.6 là một thế cờ mà hai nút đầu tiên đã được lượng giá. Nếu
thực hiện thủ tục Minimax đối với các nút đó sẽ cho thấy người chơi cực đại đã được đảm bảo
nếu đi nước bên trái sẽ được ít nhất là 2 điểm dù là các lượng giá của các nút khác cho kết quả
như thế nào đi nữa.
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức
15
Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

Hình : Thuật toán alpha-beta
Bây giờ ta lại giả sử nút tiếp theo được lượng giá cho kết quả là 1. Nếu đi vào nhánh này thì
đối phương sẽ đảm bảo làm điểm của người chơi cực đại không thể vượt quá được giá trị 1 dù

17
Chương Trình Chơi Cờ Tướng Tự Động – Sử Dụng Giải Thuật Alpha-Beta Pruning

3.2 HÀM LƯỢNG GIÁ THẾ CỜ
Hàm lượng giá thế cờ được thiết kế đơn giản (giống như cách chơi cờ vồ trong thực tế), đó
là nó đánh giá cho điểm bằng cách, lấy tổng điểm quân mình trừ đi tổng điểm quân bên đối
phương, được giá trị của thế cờ hiện tại.
Và để lấy được tổng điểm các quân của mỗi bên thì mỗi quân phải được gán một giá trị. Giá
trị các quân cờ được gán trong bảng sau (tham khảo nguồn http://cotuongonline.org/co-tuong-
nhap-mon/gia-tri-cua-cac-quan.html).
Quân cờ Giá trị
Tướng 1000
xe 90
pháo 45
mã 40
Tượng 25
Sĩ 20
Tốt 10
Bảng : Bảng giá trị các quân cờ
Từ trên ta thiết kế hàm lượng giá với giả mã như sau :
Function Eval
Begin
Int s = 0;
Duyệt hết các giá trị quân cờ trên bàn
If(quân mình) s += giá trị của quân đó
Else(quân đối phương) s -= giá trị của quân đó
Return s
End.
PHẦN 4: XÂY DỰNG CHƯƠNG TRÌNH MINH HỌA
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức

Đối với máy tính Thực hiện đi tự động sử dụng thuật toán
Alphabeta với độ sâu từ 2  5 hoặc có thể sâu
hơn nữa nhưng thời gian diễn ra rất chậm
Bảng : Kết luận
5.2 HƯỚNG PHÁT TRIỂN
1 Xây dựng tính năng máy tự động chơi cờ
( sử dụng 2 hàm đánh giá khác nhau, hoặc
cùng một hàm đánh giá với độ sâu giống nhau
và độ sâu khác nhau )
2 Tính năng chơi tự động và chơi thông
thường qua mạng Lan, Internet…
3 Bổ sung các tính năng âm nhạc, chat qua
mạng trong quá trình chơi, tính năng hỗ trợ
gợi ý người chơi bằng cách hiển thị các nước
có thể đi với mỗi quân
4 Nâng cấp giao diện có chọn chế độ chơi
(người – người, người – máy, máy – máy, qua
mạng …)
5 Cải tiến hàm lượng giá
6 Cung cấp chức năng lưu lại thế cờ (file hay
cơ sở dữ liệu) để có thể nạp lại và chơi tiếp
Cho phép người chơi được bầy cờ thế bầy
xong mới chơi tiếp
Bảng : Hướng phát triển chương trình
TÀI LIỆU THAM KHẢO
1. Slide bài giảng Ts. Phạm Văn Hải
2. http://docs.oracle.com/javase/tutorial/
3. Tài liệu hướng dẫn viết chương trình chơi cờ tướng Ts. Phạm Hồng Nguyên
4. Nguồn Internet…
Đinh Tiến Sĩ – Phan Văn Thìn – Lâm Viết Tùng – Đinh Văn Đông – Nguyễn Anh Dũng – Lê Minh Đức