Hồ Chí Minh, ngày 07 tháng 08 năm 2012
Học viện Kỹ thuật quân sự
Khoa CNTT
Đồ án nhập môn
Trí Tuệ Nhân Tạo
Đề tài:
Giảng viên: Ngô Hữu Phúc
Họ và tên: Nguyễn Đình Chính
Lớp: K23 – Hồ Chí Minh
Nghiên cứu phương pháp cắt tỉa
Anfa - Beta cho trò chơi cờ vua
Mục lục
I. Lời nói đầu
Năm 1950, Claude Shannon đã viết chương trình chơi cờ
đầu tiên. Đó là hành động đầu tiên đánh dấu việc nguyên cứu Trí
tuệ nhân tạo và đưa nó vào chơi cờ. Điều này là một bằng chứng rõ
ràng về khả năng máy tính có thể làm được những công việc đòi
hỏi trí thông minh của con người.
Ngày này, việc nguyên cứu Trí tuệ nhân tạo và đưa nó vào
các ứng dụng thực tế đang ngày càng nhiều, và ngày càng chứng tỏ
được thế mạnh của mình trong các công việc đòi hỏi khả năng suy
nghĩ và tính toán giống như con người. Trong đó, vấn đề Tìm kiếm
có đối thủ đang được áp dụng rất rộng rãi trong các trò chơi đối
kháng, tất nhiên, tuân theo những tiêu chuẩn nhất định. Bản đồ án
này được xây dựng, cũng nằm một trong số đó. Áp dụng lí thuyết
Trí tuệ nhân tạo, kết hợp với các hàm đánh giá, từ đó xây dựng một
chương trình cờ vua mang tính chất minh họa thuật toán hơn là xây
dựng một chương trình có tính ứng dụng cao trong thực tế.
II.Cơ sở lí thuyết
1.Backtracking
a.Giới thiệu:

Backtracking là một kỹ thuật rất chung có thể được sử dụng để giải quyết một
loạt các vấn đề liệt kê tổng hợp. Nó cũng là cơ sở kỹ thuật khác như cắt tỉa
Alpha – Beta và cũng được ứng dụng rộng rãi trong các hoạt động nghiên
cứu.
Ở đây em xin giới thiệu một bài toán nhỏ của cờ vua là xét bài toán đặt n con
Hậu trên n x n bàn cờ. Hoàng Hậu tấn công tất cả các quân trên một hàng hay
một cột hay hai đường chéo. Em xin xem xét giá trị cụ thể của n = 4. Em bắt
đầu với một bàn cờ trống và cố gắng xây dựng cột giải pháp theo cột và bắt
đầu từ bên trái. Hình 1 cho thấy cây backtracking. Cây được xây dựng như
sau: Bắt đầu từ một bàn cờ trống không có quân Hậu nào, và thử đặt một con
Hậu trong một cột. Có 4 vị trí cho quân Hậu, tương ứng với việc đi tìm
đường. Lần đầu cố gắng đặt một Hậu trong một cột, tiếp theo đặt các Hậu
khác theo thuật toán quay lui. Nếu gặp khó khăn tại k cột, sau đó quay lại k-1
cột, cố gắng đặt Hậu trong k-1 từ vị trí hiện tại của nó. Độ sâu của cây là n=4.
Xem xét trong trường hợp tiêu chuẩn bàn cờ là 8x8. Sẽ gặp phải khó khăn
trong dùng backtracking bằng tay, dễ ràng hơn là dùng một chương trình.
Quá trình backtracking như mô tả ở trên là đệ quy, chúng ta có thể dùng cho
thủ tục đệ quy giải quyết tám con Hậu. Thủ tục Pseudo – Pascal để giải quyết
bài toán. X giải pháp bao gồm hoán vị từ 1 đến 8, đại diện các địa điểm hàng
của Hậu trong các bước tiếp theo. Đối với 4 Hậu vấn đề hoán vị cho bài toán
là x=[2,4,1,3] và x=[3,1,4,2].
Khi thuật toán được tiến hành , ta cần một số cách để xác định xem một Hậu có
tấn công một Hậu khác hay không. Cách đơn giản nhất là ta duy trì ba mảng
Boolean, gọi là {a,b,c}. a mảng cho thấy nếu một hàng không chứa một Hậu.
b cho biết một số đường chéo không có một Hậu, và c cho biết một số đường
chéo không chứa một Hậu. Tổng của các hàng và chỉ số cột là hằng số đường
chéo, và sự khác biệt của hàng và chỉ số cột là không đổi dọc theo đường
chéo.
Vì vậy, mảng a được lập chỉ mục tứ 1 … 8, mảng b được lập chỉ mục từ 2 …
16, và c được lập chỉ mục -7 … 7.

Hình 1: Sơ đồ cây bốn Hậu với backtracking
procedure Queen ( col : N )
local row : N;
for row := 1 to 8 do
if a[row] and b[row+col ] and c[row−col ] then
x[col ] := row;
a[row] := b[row+col ] := c[row−col ] := false;
if col < 8 then Queen( col + 1 ) else PrintIt;
a[row] := b[row+col ] := c[row−col ] := true;
Thuật toán 1: Thuật toán cho vấn đề 8 Hậu
Nó chỉ ra rằng có 92 nghiệm của bàn cờ 8x8.
b.Thuật toán Backtracking
Công thức chung của Backtracking là tạo ra tất cả các chuỗi đáp ứng một số S và
P.
Mỗi Ai là một tập hợp hữu hạn. Trong hầu hết các ứng dụng dây sẽ có một chiều
dài cố định. Để đáp ứng được kỹ thuật Backtracking P phải được mở rộng để Q
được xác định trên dây “tiền tố” như sau:
Nói cách khác, nếu một chuỗi không đáp ứng được các Q, sau đó không thể được
mở rộng một chuỗi mà không đáp ứng P. Với giải pháp một phần x= x
1
x
2
…x
k-1
ta
cho Sk(x) biểu thị tất cả các hợp lệ của việc mở rộng chuỗi bởi một trong những
yếu tố.
Các đỉnh của cây Backtracking là tất cả các chuỗi đáp ứng Q. Còn một đỉnh là tất
cả những trình tự thu được từ chuỗi mẹ bằng cách phụ thêm một số yếu tố.
Là một minh họa cho việc xem xét bàn cờ 8x8. Ai là {1,2, …,8} cho mỗi i = 1, 2,

…, 8. Q chỉ đơn giản là xem các Hậu đặt có đúng không.
procedure Back ( k : N; x : string);
local x : Ak; Sk : set of Ak
begin
if P(x) then PrintSolution( x );
compute Sk;
for x ∈ Sk do Back( k + 1, xx );
end {of Back};
Thuật toán 2: Thuật toán Backtracking
Thuật toán sau đây sẽ cải thiện tốc độ của thuật toán.
Thuật toán 3: Cải thiện thuật toán Backtracking
2.Alpha – Beta
Vấn đề chơi cờ có thể xem xét như vấn đề tìm kiếm trong không gian
trạng thái. Mỗi trạng thái là một tình thế (cách bố trí các quân cờ trên
bàn cờ).
- Trạng thái ban đầu là sự sắp xếp các quân cờ của hai bên lúc bắt
đầu chơi.
- Các toán tử là các nước đi hợp lệ.
- Các trạng thái kết thúc là các tình thế mà cuộc chơi dừng, thường
được xác định bởi một điều kiện dừng nhất định.
- Một hàm kết cuộc ứng mỗi trạng thái kết thúc với một giá trị nào
đó.
Tư tưởng của thuật toán cắt tỉa Anpha-beta như sau:
- Chiến lược tìm kiếm Minimax là chiến lược tìm kiếm theo độ
sâu.
- Giả sử trong quá trình tìm kiếm, ta đi xuống đỉnh A là đỉnh
trắng, đỉnh A có người anh em V đã được đánh giá.
- Giả sử cha của đỉnh A là B và B có người anh em U đã được
đánh giá, và giả sử cha của B là C.
- Khi đó ta có giá trị đỉnh C ít nhất là giá trị của U, giá trị của đỉnh

B nhiều nhất là giá trị V.
- Do đó, nếu eval (U)>eval(V), ta không cần đi xuống để đánh giá
đỉnh A nữa mà không ảnh hưởng gì đến đánh giá đỉnh C. Hay
nói cách khác, ta có thể cắt bỏ cây con gốc A. Lập luận tương tự
cho trường hợp đỉnh A là đen, trong trường hợp này, nếu eval
(U)<eval(V) ta cũng có thể cắt bỏ cây con gốc A.
Hình 2: Cắt bỏ cây con gốc a, nếu eval(u) > eval(v)
Hình 3: Mô hình alpha – beta cho 4 con Hậu
III. Chương trình Chess
Ứng dụng thuật toán alpha – beta vào chò chơi cờ vua.
Hình 4: Màn hinh tổng quan trò chơi cờ vua
Hình 5: Màn hình người chơi và máy tính
Hình 6: Màn hình xuất hiện thong báo nếu một trong 2 thắng
Hình 7: Màn hình tùy chỉnh chế độ cho trò chơi
Một chương trình chơi cờ được đánh giá dựa trên tiêu chí mức độ thông
minh của các nước đi và nguồn tri thức đã được học. Điều này phụ thuộc
phần lớn vào hàm đánh giá được cài đặt trong trò chơi. Từ đó có thể thấy
mức độ quan trọng của hàm đánh giá trong bất cứ một chương trình chơi
cờ nào. Không nằm ngoài ý kiến đó, chương trình cũng xây dựng hàm
đánh giá riêng, với mục đích phản ảnh rõ nhất cục diện bàn cờ cũng như
đưa ra được lựa chọn tốt nhất ứng với trạng thái cụ thể.
Hàm đánh giá của chương trình được xây dựng dựa trên các yếu tố về các
giai đoạn của ván cờ, giá trị các quân cờ và vị trí của chúng. Cụ thể:
- Ứng với mỗi giai đoạn chơi của ván cờ, giá trị của các quân cờ sẽ
được thay đổi.
- Mỗi vị trí quân cờ sẽ được đánh giá với mức độ tốt khác nhau.
- Khả năng ăn các quân cờ.
- Khả năng bảo vệ các quân cờ khác
- Các vị trí có thể bị đối phương ăn.
Dựa trên các yêu tố trên, chương trình xây dựng một hàm đánh giá cùng

các trọng số, với mục đích phản ánh một cách chân thực nhất cục diện
của bàn cờ, từ đó đưa ra được phương án tốt nhất ứng với trạng thái cụ
thể.
IV. Tài liệu tham khảo
[1]. Tiến sĩ Ngô Hữu Phúc , Bài giảng AI.
[2]. Frank Ruskey, 1995–2001
[3]. Parallelizing a Simple Chess Program
[4]. />[4]. Google
V. Lời cuối
Khuôn khổ bản đồ án chỉ dừng lại ở mức độ nghiên cứu và minh
họa thuật toán đối với không gian trạng thái cụ thể là bàn cờ vua. Trong
quá trình nghiên cứu và xây dựng chương trình có nhiều vấn đề bất cập
do kiến thức còn hạn hẹp, không thể tránh khỏi những sai sót, cũng như
thiếu kinh nghiệm trong quá trình xây dựng. Hy vọng sẽ nhận được sự
giúp đỡ của thầy để tiếp tục phát triển bản đồ án để ngày càng tốt hơn
Cuối cùng, em xin cảm ơn thầy Ngô Hữu Phúc đã tận tình giúp đỡ
em trong quá trình xây dựng và hoàn thành bản đồ án này.
Em xin cảm ơn thầy!