Mục lục
Page 1 of 25
Lời mở đầu
Mục đích của chúng em về bài tập lớn này là xây dựng một chương trình với
một trí tuệ nhân tạo - thông minh, nhanh nhạy có thể đối kháng với con người
trong một trò chơi cụ thể. Ở bài tập lớn này chúng em xây dựng chương trình cờ
caro, áp dụng các giải thuật MinMax, cắt tỉa alpha-beta. Qua đó, giúp chúng em
hiểu được cách thực mà con người đưa trí tuệ và bản lĩnh của mình vào máy móc,
khiến máy móc có thể hoạt động tương đương hoặc thậm trí vượt trội hơn so với
con người!
Page 2 of 25
Phân công công việc:
Thành viên Thông tin Công việc
Nguyễn Đức Cường Nhóm trưởng
MSSV: 20101215
- Thiết kế các Form
- Các chức năng
thiết lập bàn cờ.
Mai Đức Anh 20101089 - Tìm hiểu và cài đặt
giải thuật
MiniMax,
AnphaBeta cắt tỉa
- Thiết kế class
Computer.
Lê Công Hưng 20101667 - Thiết kế các Form
- Các chức năng
thiết lập bàn cờ.
Chu Văn Định 20101378 - Thiết kế và cài đặt
Bàn cờ, class
CGoban.
- Viết báo cáo

o Bàn cờ 15 x 15, quân đen đi trước.
o Ai tạo được 5 quân liền nhau trước thì thắng
Như hình bên dưới thì O thắng:
Hình 2: Luật chơi Gomoku
Khi trình độ các kỳ thủ Gomoku được nâng cao, họ nhận ra rằng nếu chỉ
chơi đơn giản như trong Gomoku thì đó sẽ là một lợi thế quá lớn cho bên tiên tức
bên Đen (thực tế chính là ưu thế thắng). Sau đó một số nhà toán học đã chứng
minh được rằng nếu chơi với luật Gomoku trên bàn cờ bằng hoặc rộng hơn 15x15
thì Đen chắc chắn thắng (sure win), và sau đó cách đi cụ thể cũng đã được tìm ra,
hệ thống và phân loại.Và chính vì vậy, từ đó Gomoku lâm vào một giai đoạn khủng
hoảng. Khả năng đánh thắng 100 phần trăm của Đen đã làm trò chơi này mất đi ý
nghĩa của nó. Có nhiều cải tiến được đề xuất, một số đã bị bỏ qua nhanh chóng, số
khác làm xuất hiện các biến thể mới của Gomoku. Ý tưởng chung của các cải tiến
là đề ra một số hạn chế cho Đen, nhằm cân bằng ưu thế đi tiên. Dưới đây là một số
biến thể phổ biến:
- Gomoku. Hiện nay được chơi chính thức với bàn 13x13. Không có hoà.
Nếu hết đất thì Trắng thắng. Chưa tìm được chứng minh nào cho thấy Đen
chắc chắn thắng. Tuy nhiên Đen vẫn có ưu thế rất lớn.
- ProGomoku. Chơi trên bàn 15x15. Nước đầu của Đen đặt sẵn ở trung tâm.
Nước thứ ba (nước thứ hai của Đen) phải đặt ngoài hình vuông cấm. Hình
Page 6 of 25
vuông cấm là hình vuông trung tâm kích thước 5x5. Không có hạn chế cho
Trắng. Đã có chứng minh Đen chắc chắn thắng trong biến thể này.
- Pente. Biến thể này không còn giống Gomoku. Luật bổ sung là có thể ăn
quân đối phương. Nước ăn quân được thực hiện bằng cách chặn hai đầu một
nước hai quân đối phương và ăn hai quân đó. Ai tạo được nước năm hoặc ăn
được 5 cặp quân trước thì thắng. Rất phổ biến ở Mỹ. Chơi trên bàn 19x19.
II. Phân tích bài toán
1. Mục đích bài toán
Tìm hiểu về giải thuật MINMAX, cắt tỉa alpha-beta, áp dụng được các thuật

mức của cây, số tầng của cây.
Thường thì mỗi vị trí kết thúc của trò chơi (nút lá) sẽ gán một trọng số, chẳng
hạn gán 1 cho chiến thắng, 0 cho hòa và -1 cho thua trận.Tại mỗi nút cũng có một
trọng số tương ứng được xác định bằng một cách nào đó.Dựa vào cây trò chơi này,
người ta có thể tìm ra nước đi “tốt” để giành phần thắng cho mình (nếu có thể),
bằng cách tìm kiếm trên cây để tìm ra nước đi tốt nhất.
Dưới đây là ví dụ về cây trò chơi qua trò chơi bốc sỏi:

Giả thiết có 3 hộp bi, số lượng bi trong mỗi hộp là (1, 2, 2). Mỗi lượt chơi người
chơi chỉ được bốc trong 1 hộp bi, với số lượng tùy ý.Người chơi nào bốc bi cuối
cùng sẽ là người thua cuộc.
Dựa vào đánh giá ở cây trò chơi dưới, ta thấy được những nút lá mà có trọng số
là 1, tức là đi theo những nhánh nào đó mà cuối cùng đến được những là đấy thì
người chơi Max sẽ giành thắng lợi.
Page 8 of 25
Hình 4: Ví dụ về cây trò chơi qua trò chơi bốc sỏi
Page 9 of 25
Cây biểu diễn trò chơi cờ Caro
3. Chiến lược tìm kiếm
Như vậy với một trò chơi đối kháng, khi mà ta biểu diễn được trò chơi dưới
dạng một cây trò chơi, thì vấn đề đặt ra là phải tìm được chiến thuật đi trên cây trò
chơi đó để chiếm lợi thế.Tức là phải có chiến lược tìm kiếm tốt để đảm bảo đường
đi của mình là “tốt”
3.1 Thuật toán vét cạn liệu có được sử dụng?
Nếu như thuật toán vét cạn thực sự dùng được để tìm kiếm trên cây trò chơi
thì ta chỉ cần chọn nhánh cây dẫn tới nút chiến thắng để đi, và như vậy các trò chơi
không còn sự hấp dẫn thường có.Và thực tế là, trong các trò chơi đối kháng thì sau
Page 10 of 25
một vài lượt đi thì lại sinh ra rất nhiều khả năng đánh tiếp theo (bùng nổ tổ hợp),
chỉ có một số ít các trường hợp là có thể tìm kiếm theo kiểu vét cạn hết các khả

Hình 6: Class biểu diễn tọa độ các nốt
• Các trạng thái có thể xảy ra khi đang chơi:
+ Trạng thái WIN: khi một trong 2 người chơi đánh được 5 quân liên
tiếp theo một trong các trường hợp: 5 quân nằm ngang liên tiếp, 5 quân
thẳng đứng liên tiếp, 5 quân chéo trái liên tiếp hoặc 5 quân chéo phải liên
tiếp.
+ Trạng thái FILLED: Khi tất cả các nốt trên bàn cờ đã được đánh mà
không ai dành chiến thắng. Khi đó sẽ có cửa sổ thông báo hòa.
+ Trạng thái ILLEGAL: Phạm qui, không được đánh. Người chơi phạm
qui khi đánh vào nước mà người chơi hoặc máy đã đánh trước đó hoặc
đánh ra ngoài.
Page 12 of 25
+ Trạng thái OK: Khi 3 trạng thái trên không xảy ra thì người chơi có thể
được đánh tiếp!
Page 13 of 25
IV. Thuật toán sử dụng
1. Thuật toán MINIMAX.
- Các chiến lược tối ưu:
o M t chi n l c t i u là m t chu i các n c đi giúp đ a đ n tr ng thái đích mong ộ ế ượ ố ư ộ ỗ ướ ư ế ạ
mu n (vd: chi n th ng)ố ế ắ
o Chi n l c c a MAX b nh h ng (ph thu c) vào các n c đi c a MIN – và ế ượ ủ ị ả ưở ụ ộ ướ ủ
ng c l iượ ạ
o MAX c n ch n m t chi n l c gi a c c đ i hóa giá tr hàm m c tiêu – v i gi sầ ọ ộ ế ượ ữ ự ạ ị ụ ớ ả ử
là MIN đi các n c t i u. Min c n ch n m t chi n l c giúp c c ti u hoá giá tr ướ ố ư ầ ọ ộ ế ượ ự ể ị
hàm m c tiêu.ụ
o Chi n l c này đ c xác đ nh b ng vi c xét giá tr MINIMAX đ i v i m i nút trong ế ượ ượ ị ằ ệ ị ố ớ ỗ
cây bi u di n trò ch i. Chi n l c t i u đ i v i các trò ch i có không gian tr ng ể ễ ơ ế ượ ố ư ố ớ ơ ạ
thái xác đ nh (deterministic states).ị
- Giá tr MINIMAX ị
o MAX ch n n c đi ng v i giá tr MINIMAX c c đ i (đ đ t đ c giá tr c c đ i ọ ướ ứ ớ ị ự ạ ể ạ ượ ị ự ạ

o 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.
- Ví dụ:
Hình 1:
Page 16 of 25
- Thuật toán Cắt tỉa tỉa
α
-β (Alpha – Beta)
o
α là giá trị cảu nước đi tốt nhất đối với MAX (giá trị tối đa) tính đến hiện tại đối
với nhánh tìm kiếm.
o
Nếu v là giá trị tồi hơn α thì MAX sẽ bỏ qua nước đi ứng với v. Cắt tỉa nhánh
ứng với v.
o
β được định nghĩa tương tự với MIN.
Page 17 of 25
- Theo thuật toán, tại mỗi trạng thái con của hàm Max-Value, nếu giá trị của
trạng thái đó nhỏ hơn giá trị Max đang có , thì nhánh đó sẽ không được xét
tiếp.
- Tương tự với hàm Min –Value, trạng thái con nào có giá trị trạng thái lớn
hơn giá trị Min đang có thì sẽ không được xét tiếp.
- Thuật toán có hiệu quả rất nhiều trong việc cắt giảmkhông gian tìm kiếm, cải
thiện thời gian tìm kiếm một cách đáng kể.
- Một số hạn chế:
o Đối với các trò chơi có không gian trạng thái lớn, thì phương pháp cắt
tỉa
α
-β vẫn không phù hợp. Không gian tìm kiếm (kết hợp cắt tỉa) vẫn lớn.
o Có thể hạn chế không gian tìm kiếm bằng cách sử dụng các tri thức cụ
thể của bào toán.