BÁO CÁO BÀI TẬP LỚN
Đề tài:
Chiến lược Minimax – Alpha-Beta Pruning
Game cờ Caro
Nhóm 8
• Lê Phương Nam 20093538
• Hoàng Mạnh Tiến 20092693
• Trịnh Văn Thắng 20202223
• Bùi Xuân Trường 20092906
• Lê Hồng Văn 20093231
• Lê Anh Vi 20093679
1
MỤC LỤC
I. Giới thiệu thuật toán minimax và cắt tỉa alpha-bêta
1. Thuật toán Minimax
Thuật toán Minmax hay còn gọi là Minimax là một thuật toán dùng trong tìm kiếm
có đối thủ. Cải tiến của thuật toán này là thuật toán cắt tỉa Alpha-Beta (Alpha -
Beta Pruning) rất hay được sử dụng làm chiến lược cho tìm kiếm nước đi trong
không gian tìm kiếm của trò chơi có tính chất đối kháng (vd cờ Tướng, cờ Vua, cờ
caro ). Nói một cách dễ hiểu, thì ý nghĩa của thuật toán này bạn có thể hiểu một
cách đơn giản như sau: Giả sử bạn đang đánh cờ với máy, thì cả bàn cờ sẽ được
biểu diễn trong một cái gọi là không gian trạng thái (KGTT) - bạn có thể hình dung
KGTT chính là cách mà máy tính biểu diễn bàn cờ thực lên bộ nhớ máy tính. Với
mỗi nước đi (mỗi thay đổi) sẽ làm cho KGTT của bàn cờ thay đổi thành một
KGTT mới. Như vậy, đến nước đi của máy. Chiến lược tìm kiếm nước đi Minimax
sẽ được sử dụng để làm sao tìm ra nước đi tốt nhất cho máy. Để có được nước đi
tốt thì cần có một sự lượng giá tốt - là kết quả từ một hàm lượng giá (tức là cách
đánh giá, như lúc mình tính ở trong đầu í == độ uyên thâm). Độ sâu (depth) là số
nước mà máy sẽ tính trước. Như vậy giả sử với độ sâu là 4 thì sẽ tìm với tầm nhìn
2
là 4 nước đi. Nút có kết quả lượng giá cao nhất ở mức gốc (mức 0) sẽ được chọn

begin
if u là đỉnh kết thúc then MaxVal(u) ¬ f(u)
else MaxVal(u) ¬ max{MinVal(v) | v là đỉnh con của u}
end;
function MinVal(u);
begin
if u là đỉnh kết thúc then MinVal(u) ¬ f(u)
else MinVal(u) ¬ min{MaxVal(v) | v là đỉnh con của u}
end;
Trong các hàm đệ quy trên, f(u) là giá trị của hàm kết cuộc tại đỉnh kết thúc u. Sau
đây là thủ tục chọn nước đi cho trắng tại đỉnh u. Trong thủ tục Minimax(u,v), v là
biến lưu lại trạng thái mà Trắng đã chọn đi tới từ u.
procedure Minimax(u, v);
begin
val ¬ -¥;
for mỗi w là đỉnh con của u do
if val <= MinVal(w) then
{val¬ MinVal(w);
v ¬ w}
end;
4
Thủ tục chọn nước đi như trên gọi là chiến lược Minimax, bởi vì Trắng đã chọ
được nước đi dẫn tới đỉnh con có giá trị là max của các giá trị các đỉnh con, và Đen
đáp lại bằng nước đi tới đỉnh có giá trị là min của các giá trị các đỉnh con.
Thuật toán Minimax là thuật toán tìm kiếm theo độ sâu, ở đây ta đã cài đặt thuật
toán Minimax bởi các hàm đệ quy. Bạn đọc hãy viết thủ tục không đệ quy thực
hiện thuật toán này.
Về mặt lí thuyết, chiến lược Minimax cho phép ta tìm được nước đi tối ưu cho
Trắng. Song nó không thực tế, chúng ta sẽ không có đủ thời gian để tính được
nước đi tối ưu. Bởi vì thuật toán Minimax đòi hỏi ta phải xem xét toàn bộ các đỉnh

+s2w2+. . .
+snwn.
Trong đó, wi là giá trị mỗi loại quân, còn si là số quân loại đó. Trong cách đánh giá
này, ta đã không tính đến sự bố trí của các quân, các mối tương quan giữa chúng.
Thuật giải:
6
2. Cắt tỉa Alpha-Beta
Minimax yêu cầu phải có sự phân tích qua hai bước đối với không gian tìm kiếm:
Bước đầu truyền xuống đến độ sâu của lớp áp dụng heuristic và bước sau để truyền
ngược các giá trị trên cây. Minimax lần theo tất cả các nhánh trong không gian bao
gồm cả những nhánh mà một thuật toán thông minh hơn có thể bỏ qua hay tỉa bớt.
Các nhà nghiên cứu trong lĩnh vực chơi game đã xây dựng một kỹ thuật tìm kiếm
gọi là cắt tỉa alpha –beta nhằm nâng cao hiệu quả tìm kiếm trong các bài toán trò
chơi hai đối thủ.
Ý tưởng của tìm kiếm alpha – beta rất đơn giản: Thay vì nếu như tìm kiếm toàn bộ
không gian đến một độ sâu lớp cố định, tìm kiếm alpha – beta thực hiện theo kiểu
tìm kiếm sâu. Có hai giá trị, gọi là alpha và beta được tạo ra trong quá trình tìm
kiếm. Giá trị alpha liên quan với các nút MAX và có khuynh hướng không bao giờ
7
giảm. Ngược lại giá trị beta liên quan đến các nút MIN và có khuynh hướng không
bao giờ tăng. Giả sử có giá trị alpha của một nút MAX là 6, MAX không cần phải
xem xét giá trị truyền ngược nào nhỏ hơn hoặc bằng 6 có liên quan với một nút
MIN nào đó bên dưới. Alpha là giá trị thấp nhất mà MAX có thể nhận được sau
khi cho rằng MIN cũng sẽ nhận giá trị tốt nhất của nó. Tương tự nếu MIN có giá trị
beta là 6 nó cũng không cần xem xét các nút nằm dưới nó có giá trị lớn hơn hoặc
bằng 6.
Để bắt đầu thuật toán tìm kiếm alpha – beta, ta đi xuống hết độ sâu lớp theo kiểu
tìm kiếm sâu, đồng thời áp dụng đánh giá heuristic cho một trạng thái và tất cả các
trạng thái anh em của nó. Giả thuyết tất cả đều là nút MIN. Giá trị tối đa của các
nút MIN này sẽ được truyền ngược lên cho nút cha mẹ (là một nút MAX). Sau đó

2. Áp dụng thuật toán min–max và cắt tỉa alpha-bêta
Sử dụng hàm minimax như sau:
Xây dựng các hàm chính:
score(): Hàm lượng giá một trạng thái bàn cờ.
min(int n): Trả về giá trị score() thấp nhất cho bên Min (bên X) sau n nước cờ.
max(int n): Trả về giá trị score() cao nhất cho bên Max (bên O) sau n nước cờ.
a. Hàm lượng giá eval():
Sau đây là quy ước hàm lượng giá đối với bên Max, bên Min cũng vậy nhưng thêm
dấu “-” cho mỗi giá trị đạt được.
Trả về 100000 nếu bên Max thắng;
Trả về 10000 đối với:
Trạng thái dãy 4 mở hai đầu (openFour):
11
Hai dãy 4 mở 1 đầu (halfOpenFour):

Trả về 5000 đối với 1 dãy 3 mở hai đầu + 1 dãy 4 mở 1 đầu:
Trả về 3000 đối với Hai dãy 3 mở hai đầu:
Trả về 1000 điểm đối với 1 dãy 3 mở hai đầu + 1 dãy ba mở một đầu:
12
Trả về 500 điểm đối với 1 dãy 4 mở 1 đầu:
200 điểm cho trạng thái có 1 dãy 3 mở hai đầu
100 điểm cho trạng thái có 1 cặp dãy 2 mở hai đầu:
13
50 điểm nếu trạng thái chỉ có 1 dãy 3 mở một đầu:
10 điểm cho trạng thái có 1 cặp dãy 2 mỗi dãy chỉ mở 1 đầu:
5 điểm cho trạng thái có 1 dãy 2 mở hai đầu:
3 điểm cho 1 dãy 2 mở một đầu:
0 điểm Các trạng thái còn lại và trạng thái hòa
b. Xây dụng hàm minimax và cắt tỉa alpha-beta
Minimax:

min = 100000;
for(k=0;k<=openArea.top;k++){ //Vòng lặp duyệt các trạng thái tiếp
theo
i = openArea.a[0][k];
j = openArea.a[1][k];
b[i][j] = 1; //Đánh nước đi giả thiết
closeArea.push(i, j);
updateArea();
temp = max(n-1);
b[i][j] = 0;
closeArea.pop();
updateArea();
if(temp<min){ //Chọn nước đi có giá trị max(n-1) thấp nhất.
min = temp;
}
}
return min; //Trả về giá trị thấp nhất
}
Tuy nhiên max(n) và min(n) mới chỉ là hai hàm tính giá trị, chưa phải hàm ra quyết
định, vậy xây dựng hàm ra quyết định cho bên Max và Min:
16
Hàm đưa ra quyết định cho bên Max:
public void maxPlay(int n){
updateArea();
int i,j,im,jm,k,top,max,temp;
top = openArea.top;
if(top==-1) {
b[11][11] = 2;
u[11][11].setNO();
updateArea();

}
Cắt tỉa alpha-beta
Xét hàm maxPlay(n) :
Trong khi xét các trạng thái tiếp theo, giả sử trạng thái đầu tiên cho giá trị max(n)
= x;
Như vậy trong các trạng thái tiếp theo ta chỉ quan tâm đến các trạng thái cho giá trị
max(n) < x; nếu biết trước một trạng thái nào đó có max(n) >x, ta có thể bỏ qua
trạng thái này.
Bởi vì nguyên tắc hoạt động trong hàm max(n) là chọn ra giá trị lớn nhất trong các
trạng thái kế tiếp, nên chỉ cần tồn tại 1 trạng thái kế tiếp cho giá trị > x thì ta có thể
bỏ qua không cần tính tiếp hàm này nữa và quy cho kết quả max(n) = x+1, bởi ta
18
không cần quan tâm kết quả chính xác của hàm này, chỉ cần nó > x ta không chọn
phương án đó.
Từ đây ta có thể xây dựng hàm minimax kết hợp cắt tỉa alpha-betha hoàn chỉnh
như sau:
min( n, prunValue) // Tham số đầu vào là độ sâu n và giá trị cắt prunValue
{
m = 100000; //Khởi tạo m vô cùng lớn
for each: Các trạng thái tiếp theo
if(max(n-1,m)<prunValue) //Nếu giá trị < prunValue thì cắt tỉa
{
return max(n-1,m);
}
if(max(n-1,Min)<m)
{
Min = max(n-1,m);
}
return m; //Nếu không có giá trị nào < prunValue thì chọn ra GTNN.
}

i = closeArea.a[0][k];
20
j = closeArea.a[1][k];
if(i>0){
if(b[i-1][j]==0&&u[i-1][j].area==0){
openArea.push(i-1, j);
u[i-1][j].area = 1;
}
}
if(i>0&&j<23){
if(b[i-1][j+1]==0&&u[i-1][j+1].area==0){
openArea.push(i-1, j+1);
u[i-1][j+1].area = 1;
}
}
if(j<23){
if(b[i][j+1]==0&&u[i][j+1].area==0){
openArea.push(i, j+1);
u[i][j+1].area = 1;
}
}
if(i<23&&j<23){
if(b[i+1][j+1]==0&&u[i+1][j+1].area==0){
openArea.push(i+1, j+1);
u[i+1][j+1].area = 1;
}
}
if(i<23){
21
if(b[i+1][j]==0&&u[i+1][j].area==0){

đầu, thì hiển nhiên MAX cần phải chặn, lúc này có thể bỏ qua không cần xét duyệt
bằng MIMAX. Hoặc trường hợp MIN tạo được một hàng 3 mở hai đầu thì hoặc
MAX phải chặn một đầu ngay, hoặc MAX phải tạo được một hàng 4 ngay, lúc này
hàm MIMAX chỉ cần xét duyệt trong các trường hợp này xem trường hợp nào cho
giá trị cao nhất chứ không cần phải duyệt hết tất cả các trạng thái.
Từ ý tưởng trên chúng ta xây dựng hàm một số hàm đánh giá trạng thái, thu
nhỏ vùng xét duyệt openArea thành vùng xét duyệt thu nhỏ miniArea:
Định nghĩa:
Trạng thái thắng: Là trạng thái hình thành 1 hàng 5 ô liên tiếp.
Trạng thái thắng sau 1 nước: Là trạng thái tồn tại ít nhất 1 dãy 4 mở hai đầu hoặc
2 dãy 4 mở một đầu. Bởi vì thời gian tồn tại của đối thủ tối đa chỉ là 1 nước chặn,
sau đó phía mình sẽ đat đến trạng thái thắng.

Trạng thái thắng sau 2 nước: Là trạng thái tồn tại ít nhất 2 dãy ba mở hai đầu
hoặc 1 dãy 3 mở hai đầu và 1 dãy 4 mở 1 đầu. Vì từ trạng thái này đối thủ không
thể ngăn cản phía mình đạt đến Trạng thái thắng sau 1 nước.
23
Từ đó ta hình thành thứ tự ưu tiên cho các nước đi như sau:
Giả sử đến lượt MAX đi, thủ tục xét duyệt như sau:
Cho trước:
openArea: vùng xét duyệt ban đầu.
miniArea: là vùng xét duyệt rút gọn, khi bắt đầu thủ tục khởi tạo A rỗng.
1) IF(MAX Tồn tại nước đi để đạt đến Trạng thái thắng) THEN <Đi nước đi
này; return;>
ELSE <Chuyển qua bước 2>
2) IF(MIN Tồn tại nước đi để đạt đến Trạng thái thắng) THEN <Chặn nước
đi này; return;>
ELSE <Chuyển qua bước 3>
3) IF(MAX Tồn tại nước đi để đạt đến Trạng thái thắng sau 1 nước) THEN
<Đi nước đi này; return;>