HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
Đồ án
Nhập môn trí tuệ nhân tạo
Đề tài: Không gian trạng thái là trò chơi cờ vua. Xây dựng
chương trình giải quyết bài toán theo phương pháp Minimax
Thầy giáo hướng dẫn: Ngô Hữu Phúc
Học viên: Nguyễn Trần Quyết
Lớp: Tin học 5A
Hà Nội, 3 - 2010
1
I. Lời nói đầu
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ế. Sau đây là cơ sở lý thuyết về không
gian trạng thái cờ vua theo phương pháp Minimax.
II. Cơ sở lí thuyết
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

định giá trị cho các đỉnh đen.
function MaxVal(u);
3
begin
if u lµ ®Ønh kÕt thóc then MaxVal(u)
←
f(u)
else MaxVal(u)
←
max{MinVal(v) | v lµ ®Ønh con cña u}
end;
function MinVal(u);
begin
if u lµ ®Ønh kÕt thóc then MinVal(u)
←
f(u)
else MinVal(u)
←
min{MaxVal(v) | v lµ ®Ønh con cña u}
end;
Trong các hàm đệ quy trên, f(u) là giá trị của hàm kết cuộc tại đỉnh kết
thúc u. Sau đây là thủ tục chọn nước đi cho trắng tại đỉnh u. Trong thủ tục
Minimax(u,v) v là biến lưu lại trạng thái mà trắng đã chọn đi tới từ u
procedure Minimax(u, v);
begin
val
←
-
∞
;

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
(vị trí trung tâm). Cụ thể:
7
Hàm tính giá trị của từng quân cờ:
For i = 0 To 7
For j = 0 To 7
If mangdanhgia.Vitri(i, j) > 0 Then
tgiatri(mangdanhgia.Vitri, i, j,
mangdanhgia.Vitri(i, j))
End If
Next
Next
Vị trí trung tâm:
For i = 0 To 7
For j = 0 To 7
If 3 <= i And i <= 4 And 3 <= j And j <= 4 And
mangdanhgia.Vitri(i, j) > 0 Then
eval += 200
ElseIf 2 <= i And i <= 5 And 2 <= j And j <= 5 And
mangdanhgia.Vitri(i, j) > 0 Then
eval += 100
End If
Hàm MinVal: tính giá trị nhỏ nhất
Public Sub Minval(ByVal u As Trangthai, ByVal a As Integer, ByVal b As
Integer)
Dim i, j As Integer
If u.cls = 2 Then

Duyet(u, i, j, u.Vitri(i, j))
End If
Next
Next
For i = 1 To chiso
If Mangduyet(i).Father = u.Name Then
Minval(Mangduyet(i), a, b)
End If
Next
max = a
End If
End Sub
Hàm Minimax: Áp dụng giải thuật Minimax vào chương trình
Public Sub Minimax(ByVal u As Trangthai, ByVal v As Trangthai)
Dim a, b, i, j As Integer
a = -100
b = 100
For i = 0 To 7
For j = 0 To 7
If u.Vitri(i, j) > 0 Then
Duyet(u, i, j, u.Vitri(i, j))
End If
Next
Next
For i = 1 To chiso
If Mangduyet(i).Father = u.Name Then
Minval(Mangduyet(i), a, b)
If a <= min Then
a = min
ketqua = Mangduyet(i)