HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO MÔN HỌC
TRÍ TUỆ NHÂN TẠO
Giáo viên hướng dẫn: Ngô Hữu Phúc
HÀ NỘI 3/2010
Học viện Kỹ thuật quân sự
Khoa CNTT
Đồ án Nhập môn trí tuệ nhân tạo
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 cắt
tỉa Anpha-Beta
Họ và tên: Đặng Minh Sang
Lớp: Tin học 5A
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


);
begin
if u là lá của cây hạn chế hoặc u là đỉnh kết thúc
then MaxVal

eval(u)
else for mỗi đỉnh v là con của u do
{



max[

, MinVal(v,

,

)];
// Cắt bỏ các cây con từ các đỉnh v còn lại
if





then exit};
MaxVal





then exit};
MinVal



;
end;
Thut toỏn tỡm nc i cho trng s dng k thut ct ta
Anpha-Beta c ci t bi th tc Alpha_beta(u,v) trong ú v l
tham bin ghi li nh m trng cn i ti u.
procedure Alpha_beta(u,v);
begin



-

;





;
for mỗi đỉnh w là con của u do
if



lại các nước đi.
Màn hình hiển thị chi tiết nước cờ
Màn hình chi tiết hiển thị chi tiết các nước cờ đã chơi, tên người chơi
cũng như thời gian chơi.
Màn hình trợ giúp
Ngoài ra chương trình còn đưa ra những trợ giúp cơ bản giúp cho
người chơi có thể sử dụng chương trình một cách tối ưu nhất.
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. Đ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. Lời cuối
Khuôn khổ bản đồ án chỉ dừng lại ở mức độ 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 xây dựng
chương trình, không tránh khỏi những sai sót, cũng như thiếu kinh nghiệm