Trường Đại Học Bách Khoa Hà Nội
Bộ Môn Hệ Thống Thông Tin

Báo Cáo Trí Tuệ Nhân Tạo
Đề Tài: Game Cờ Caro Trên Android
Nhóm sinh viên: SHSV:
Đặng Tiến Đạt 20090656

Chúng em xin chân thành cảm ơn!
3
NỘI DUNG TRÌNH BÀY
1. Giới thiệu bài toán
2. Phân công công việc
3. Công nghệ sử dụng
4. Chiến lược tìm kiếm
5. Kỹ thuật lượng giá
6. Các khó khăn gặp phải
7. Hướng cải tiến và phát triển
8. Tài liệu tham khảo
4
I. Giới thiệu bài toán
Trò chơi cờ caro được thực hiện bởi hai đối thử trên bàn cờ hình
vuông kích thước n*n (n tùy ý). Hai ký hiệu X và O sẽ đại diện
cho hai quân cờ. người chơi có nhiệm vụ thay phiên nhau điền ký
hiệu của mình vào các ô trên bàn cờ. Người thắng sẽ là người đầu
tiên tạo được 5 quân của mình thành một chuỗi liên tiếp trên một
hàng ngang, dọc, chéo.
II. Phân công công việc
• Đạt + Hoàng: nghiên cứu thuật toán và tìm kiếm hàm lượng giá
• Quang + Sơn : Code
• Hùng : Cài đặt, kiểm thử cộng viết báo cáo
III. Công nghệ sử dụng
• Tool: eclipse

• Các thuật toán tìm kiếm với chi thức bổ xung: Minimax và Alphabeta
cắt tỉa.
• Ngôn ngữ sử dụng : Javas
• Nền tảng phát triển: Hệ điều hành Android

giúp đưa ra các quyết định chung khi có sự hiện diện của sự không chắc
chắn. Minimax thường dùng để giải quyết những trò chơi có tính chất
đối kháng.
Giả sử hai đối thủ trong trò chơi có tên là MAX và MIN
• Max: biểu diễn cho mục đích của đối thủ này là làm lớn tối đa lợi

thế của mình
• Min: biểu diễn cho mục đích của đối thủ này là làm nhỏ tối đa lợi

thế của đối phương.
6
Trên cây tìm kiếm sẽ phân lớp thành các lớp Max và Min.
7
Minimax sẽ truyền các giá trị này lên cao dần trên đồ thị, qua các nút
cha mẹ kế tiếp theo các luật sau:
• Nếu trạng thái cha mẹ là Max, gán cho nó giá trị lớn nhất có trong
các trạng thái con của nó.

• Nếu trạng thái bố, mẹ là Min, gán cho nó giá trị nhỏ nhất có trong
các trạng thái con của nó.


for a,s in SUCCESSORS(state)do
vMAX(v,MIN-VALUE(s))
return v function MIN-VALUE(state) returns a ultility state
if TERMINAL-TEST(state) then return UTILITY(state)
v -∞
for a,s in SUCCESSORS(state)do
vMIN(v,MAX-VALUE(s))
return v Ta thấy để gán giá trị cho một nút nào đó ta phải xét hết tất cả các nút
con của nó rồi truy hồi dần về nút gốc. Vấn đề gặp phải ở đây là một sự
bùng nổ hàm mũ số lượng các nút phải xét. Để giải quyết vấn đề này ta
dùng phương pháp cắt tỉa Alphabeta
4.4 Phương pháp cắt tỉa Alphabeta
• Ý tưởng: Nếu một nhánh tìm kiếm nào đó không cải thiện đối với
giá trị(hàm lượng giá) mà chúng ta xét ở phần sau, thì không cần
xét đến nhánh tìm kiếm đó nữa.

• Việc cắt tỉa các nhánh tìm kiếm “tồi” không ảnh hưởng đến kết quả
cuối cùng.
9
GIẢI THUẬT
function ALPHA-BETA-SEARCH(state) returns an action
Min A= α Z
α - cut =z
z ≤α • Cắt tỉa β
Min S= β
Hình 2: định trị cây trò chơi bằng phương pháp cắt tỉa α- β
V. Kỹ thuật lượng giá
Hàm lượng giá cực kỳ quan trọng trong phương pháp cắt tỉa α- β. Một
hàm lượng giá tốt sẽ rút bớt cho ta rất nhiều những trạng thái phải xét.
Trong bài toán cờ caro, hai yếu tố có vai trò quyết định cho trận đấu là
tổng số nước có thể thắng của quân X và tổng số nước có thể thắng của
quân O tại một trạng thái bất kỳ. Vì vậy ta sẽ sử dụng hàm lượng giá
sau.
Xét tại trạng thái n thì:
Eval(n)=Eval1(n)+Eval2(n)
Trong đó:
• Eval1(n) là hàm tấn công
• Eval2(n) là hàm phòng thủ
12
Cụ thể tính giá trị tính nhu sau:
 Eval1(n)=X(n)-O(n) với X(n) là tổng bình phương số quân X
liên tiếp trên các đường ngang, dọc, chéo và O(n) là tổng bình
phương số quân O liên tiếp trên các đường ngang, dọc, chéo
Ví dụ trên một hàng ngang có 1 2 3 quân X liên tiếp thì

Vậy Eval=0+0=0
VI. Các khó khăn gặp phải
• Việc xây dựng chương trình gặp một số khó khăn như việc tìm

hàm đánh giá, việc xử lý từ thuật toán chụng cho trò chơi đối
kháng thành code riêng của cờ ca rô
• Tố ưu thuật toán và giảm thời gian tính toán của máy, tăng
cường xét các độ sâu cao hơn.
14
VII. Hướng cải tiến và phát triển
1. Cải tiến không gian trạng thái
Do không gian trạng thái bàn cờ rất lớn, vì vậy ta phải xét rất nhiều
nút con từ một nút cha. Nhưng ta có thể cải tiến bằng cách chỉ xét
những ô trống xung quanh những ô đã đánh, bởi vì những ô trống
gần khu vực đánh là những ô có tầm quan trọng cao hơn những ô ở
xa khu vực đánh. Những ô càng xa thì tầm quan trọng càng giảm.
Như vậy số nút phải xét sẽ giảm đi thay vào đó ta sẽ tăng độ sâu
cho cây tìm kiếm => như vậy máy sẽ thông minh hơn.
2. Dùng tri thức bổ sung bên ngoài
• Ta sẽ sử dụng 1 openingbook để lưu trữ những thế cờ mà máy chắc
thắng để cho máy luôn có xu hướng đưa đối thủ vào 1 trong số thế
đó

• Ta sẽ tao cho máy lưu lại những ván mà máy thua để lần sau máy
không bị tái phạm nữa
15
VIII. Tài liệu tham khảo
• Slide trí tuệ nhân tạo của thầy Phạm Văn Hải
• Slide trí tuệ nhân tạo của thầy Nguyễn Nhật Quang
• Giáo trình trí tuệ nhân tạo của thầy Đinh Mạnh Tường