1

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


LỜI NÓI ĐẦU

Trí tuệ nhân tạo là trí tuệ được biểu diễn bởi bất cứ một hệ thống nhân tạo nào. Thuật ngữ
này thường dùng để nói đến các máy tính có mục đích không nhất định và ngành khoa
nghiên cứu về các lý thuyết và ứng dụng của trí tuệ nhân tạo.
Tuy rằng trí thông minh nhân tạo có nghĩa rộng như là trí thông minh trong khoa học viễn
tưởng, nó là một trong những ngành trọng yếu của tin học. Trí thông minh nhân tạo liên
quan đến cách cư xử, sự học hỏi và khả năng thích ứng thông minh của máy móc. Các ví
dụ ứng dụng bao gồm các tác vụ điều khiển, lập kế hoạch và lập lịch (scheduling), khả
năng trả lời các câu hỏi về chẩn đoán bệnh, trả lời khách hàng về các sản phẩm của một
công ty, nhận dạng chữ viết tay, nhận dạng tiếng nói và khuôn mặt. Bởi vậy, trí thông
minh nhân tạo đã trở thành một môn học, với mục đích chính là cung cấp lời giải cho các
vấn đề của cuộc sống thực tế. Ngày nay, các hệ thống nhân tạo được dùng thường xuyên
trong kinh tế, y dược, các ngành kỹ thuật và quân sự, cũng như trong các phần mềm máy
tính thông dụng trong gia đình và trò chơi điện tử.
Để áp dụng những kiến thức về AI được học trên lớp cũng như tìm hiểu qua internet,
nhóm chúng em đi đến quyết định chung là xây dựng trò chơi cờ ca rô trên nền tảng
Android.
Trong quá trình làm bài tập lớn, chúng em xin chân thành cảm ơn thầy Phạm Văn Hải đã
tận tình hướng dẫn, cảm ơn các bạn đã đóng góp những ý kiến bổ ích để trò chơi được tốt
hơn. Do chưa có nhiều kinh nghiệm cũng như kiến thức về AI còn hạn hẹp nên trò chơi
chưa được tối ưu lắm. Mong thầy và các bạn góp ý để game được tốt hơn.
Chúng em xin chân thành cảm ơn!

4

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


IV. Chiến lược tìm kiếm
 Phân tích
Đến lượt đi của mình, mỗi người chơi cố gắng tạo ra các nước đi uy
hiếp đối phương là cao nhất và đưa tướng của đối phương về trạng thái
chiếu hết (checkmate)
Ở chế độ chơi người với máy tính : Nguời lập trình phải xây dựng hàm
để tìm kiếm cho máy tính các nước đi tối ưu nhất. Mỗi nước đi mà máy
tính lựa chọn sẽ một trong số các khả năng mà máy tính có thể đi, ta gọi
6

đây là các trạng thái nước đi của máy tính. Việc xét hết các trạng thái
nước đi của bàn cờ là một việc không mấy dễ dàng .Việc duyệt hết các
khả năng này có thể làm cho không gian trạng thái sẽ rất lớn ảnh hưởng
tới khả năng xử lý của CPU và do đó thời gian cho máy chọn một
phương án tối ưu sẽ rất lâu.
Vấn đề này yêu cầu sử dụng giải thuật heuristic cho máy để tăng khả
năng tối ưu, giảm thời gian “suy nghĩ” cho những phương án lựa chọn
của máy. Người lập trình áp dụng thủ tục cắt tỉa alpha - beta
(alpha-beta prunning) để cài đặt cho chương trình.
 Cây trò chơi
Trong quá trình chơi, trạng thái của bàn cờ được thay đổi liên tục bởi
một nước đi của 1 trong 2 đối thủ. Ta có thể biểu diễn các trạng thái này
dưới dạng một cây tìm kiếm(gọi là cây trò chơi), mỗi nút tương ứng với
một trạng thái bất kỳ, các nhánh nối giữa các nút cho ta biết từ trạng
thái này sang trạng thái kia thông qua một nước đi nào đó.
 Thuật toán MiniMax
Minimax(còn gọi là minmax) là một phương pháp trong có mục
đích là tối thiểu hóa (minimize) tổn thất vốn được dự tính có thể là "tối
đa" (maximize). Có thể hiểu ngược lại là, nó nhằm tối đa hóa lợi ích vốn

Hình 1: Cây nhị phân tìm kiếm Max-Min
 Các nút lá được gán các giá trị heuristic
 Còn giá trị tại các nút trong là các giá trị nhận được dựa trên giải
thuật Minimax

8

Giải thuật
function MINIMAX-DECISION(state) returns an action
vMAX-VALUE(state)
return the action in SUCCESSORS(state) with value v


cuối cùng.
9

GIẢI THUẬT
function ALPHA-BETA-SEARCH(state) returns an action
v MAX-VALUE(state,- ,+ )
return the action in SUCCESSORS(state) with value v
function MAX-VALUE(state) returns a ultility state
if TERMINAL-TEST(state) then return UTILITY(state)
v -∞
for a,s in SUCCESSORS(state)do
vMAX(v,MIN-VALUE(s,α,β))
if(v≥β) then return v
αMAX(α,v)
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,α,β))
if(v≤ α) then return v
ß MIN(β,v)
return v
10

 Cắt tỉa α
Min S= β

Max A= β Z
ß - cut
=z
z ≥ β
Z ≤ α
Z ≥ β
11

Ví dụ minh họa
 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ì
Eval1+=1*1+2*2+3*3
Trường hợp riêng:
 nếu số quân X liên tiếp bằng 4 thì cộng thêm 50 vào giá trị hàm
Eval1(n) và cộng thêm 100 nếu số quân X liên tiếp bằng 5 để
thấy rõ sự cấp thiết của nước đi này
 nếu số quân O liên tiếp bằng 4 trên một phương nào đó thì trừ đi
50 vào giá trị hàm Eval 1(n) và trừ đi 100 nếu số quân O liên tiếp
bằng 5
 Eval2(n) =X’(n)-O’(n) với X’(n) là tổng bình phương số quân O
liên tiếp mà X chặn được và O’(n) là tổng bình phương số quân
X liên tiếp mà O chặn được trên các đường ngang, dọc, chéo
Trường hợp riêng:
 Nếu X chặn được 4 quân O liên tiếp trên một phương nào đó thì
cộng thêm 100 vào giá trị hàm Eval(n)
 Nếu O chặn được 4 quân X liên tiếp trên một phương nào đó thì
trừ đi 100 vào giá trị hàm Eval(n) Eval1=(1+1+4+1+1+4+1+1+1+1+4+1+4+1+1+1)-
(1+1+9+1+1+1+1+1+1+1+1+1+1+1+1+1+4)=0
Eval2=(1+1+9+1+1+1+1+1+1+1+1+1+4)-
(1+4+1+1+4+1+1+4+1+4+1+1)=0
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.

 http://www.java2s.com/Tutorial/Java/0280__SWT/Catalog028
0__SWT.htm
 -Kéo thả giao diện với Eclipse:
http://www.ptpsoft.com.vn/?page=hotnews&id=694&catid=96
IX. Hướng dẫn cài đặt
1. Trên smartphone Android
Trong thư mục gửi code bọn em có build file demo-co-ca-ro.apk. Thầy chỉ
cần copy file này vào thư mục download của smartphone Android rùi tiến
hành cài đặt là chạy bình thường
2. Trên PC
Muốn chạy chương trình trên PC trước hết phải cài phần mềm bluestacks.
Đây là phần mềm giả lập Android trên PC.
Link dowload bulestacks.
http://www.bluestacks.com/
Sau khi tiến hành tải và cài đặt thì chạy file demo-ca-ca-ro.apk trên PC bình
thường.