Sinh viên thực hiện:
- Mai Đức Anh. 20101089
- Lê Công Hưng. 20101667
- Nguyễn Đức Cường. 20101215
- Chu Văn Định. 20101378
- Nguyễn Trung Đức. 20096258
- Trần Nam Sơn. 20096270
BÀI TẬP LỚN
Đề tài: Game cờ Caro sử dụng thuật toán Min-Max và cắt tỉa alpha - beta
Mục đích bài toán:
Xây dựng một chương trình game cờ Caro bằng Java 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, ứng dụng thuật toán Min-Max và cắt tỉa alpha-beta
I. Giới thiệu về game cờ Caro
Cờ caro hay gomoku chính là môn cờ logic lâu đời và cổ
xưa nhất trên Trái Đất.
Là trò chơi đối khàng giữa 2 người.

Một số dạng biến thể của gomoku:
- Gomoku .
- ProGomoku.
- Pente.
Luật chơi:
- Bàn cờ chuẩn 13 x 13, quân đen đi trước.
- Ai tạo được 5 quân liền nhau trước thì thắng
Ví dụ: quân O thắng

Biểu diễn bài toán dưới dạng cây trò chơi (Game tree)
Trò chơi có thể được biểu diễn như một cây gồm gốc, những nút, những lá và những nhánh
Phân tích bài toán
- Gốc là trạng thái ban đầu của trò chơi.Với mỗi trò chơi cụ thể thì trạng thái (ở mỗi
thời điểm) lại được đặc trưng bởi nhưng thông số riêng

cho nước đi đó là “tốt” . Và để đánh giá được nút đó thì thường phải “nhìn xa”, liên quan
đến độ sâu của cây
Máy tính thì thế cờ này được đánh giá tốt hơn thế cờ kia nhờ so sánh điểm của thế
cờ đó do bộ lượng giá trả lại.Vì không gian tìm kiếm là quá lớn nên chúng ta giới
hạn cho máy tính chỉ tìm kiếm ở một đọ sâu nhất định,
=> Và tất nhiên độ sâu càng lớn thì chương trình càng “thông minh” nhưng trả
giá về mặt thời gian…
Biểu diễn các trạng thái
- Bàn cờ với kích thước nxn (với n từ 10 đến 18)
- Các quân cờ được đánh tại giao điểm của các đường kẻ (số đường kẽ tùy thuộc vào kích thước
bàn cờ) tức các nút.
- Mỗi nút được biểu diễn bằng một trang ba trạng thái:
+ Trạng thái 0 (EMPTY): Ô cờ trống
+ Trạng thái 1(BLUE): Ô cờ được đánh bởi người thứ nhất
+ Trạng thái 2(RED): Ô cờ được đánh bởi người thứ hai
Các trạng thái có thể xảy ra khi đang chơ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.
+ 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.
+ 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.
+ 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!
IV. Thuật toán sử dụng
1. Thuật toán Min-Max.

Các chiến lược tối ưu

Chiến lược tối ưu là chuỗi các nước đi giúp đưa đến trạng thái đích


Có: 1 đối thủ luôn chọn nước đi tối ưu

Độ phức tạp về thời gian

O(b^m)

Độ phức tạp về bộ nhớ

O(bm).theo tìm kiếm sâu
Thuật toán cắt tỉa α-β

α là giá trị của 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

Nếu v là giá trị tồi hơn α, MAX sẽ bỏ qua nước đi ứng với v, Cắt tỉa 
nhánh ứng với v

β được định nghĩa tương tự đối với MIN
2. Thuật toán cắt tỉa alpha-beta

Ý tưởng: Nếu một nhánh tìm kiếm nào đó không thể cải thiện đối với
giá trị (hàm tiện ích) mà chúng ta đã có, 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
Thuật toán Cắt tỉa α-β
Thuật toán Cắt tỉa α-β
Hạn chế thuật toán Cắt tỉa α-β