Thuật toán tìm kiếm
Tìm kiếm Minimax đơn giản
Cờ tướng là trò chơi có tổng bằng không, có bên Đỏ và bên Đen, tổng lợi ích của hai bên bằng 0, ưu thế của bên này luôn đi kèm với thế yếu của bên kia. Lúc này ta có thể dùng Minimax để tìm kiếm.
Để dễ hiểu, tạm gọi Maximizing Player là "Đỏ", Minimizing Player là "Đen" (thực tế không nhất thiết), hàm đánh giá của ta tạm thời trả về điểm số theo góc nhìn của Đỏ (điểm cao nghĩa là Đỏ có ưu thế, điểm thấp nghĩa là Đỏ yếu thế).
Hai bên đều muốn tối đa hóa lợi ích: Đỏ muốn điểm càng cao càng tốt, Đen muốn điểm càng thấp càng tốt, như vậy mới đảm bảo tối đa ưu thế cho bên mình đồng thời để đối phương có ưu thế ít nhất.
Ví dụ, Đỏ ở một thế cờ có hai cách đi. Một cách đi ăn được Xe của đối phương, điểm lúc này là +500; cách kia là dâng Xe của mình, điểm là -500. Đỏ đương nhiên chọn cách có lợi cho mình, tức cách thứ nhất, nên điểm của nút này là +500.
Mã giả như sau:
int minimax(int depth, bool isMaximizingPlayer) { // độ sâu, có phải Đỏ không
if (depth == 0 || isGameOver()) { // tìm đến nút lá hoặc ván cờ kết thúc, trả về đánh giá ngay
return evaluate();
}
if (isMaximizingPlayer) { // nếu hiện tại là Đỏ
int maxEval = INT_MIN; // khởi tạo là âm vô cùng, để chương trình tìm ra điểm lớn nhất trong mọi nước đi
for (Move move : getPossibleMoves()) { // sinh nước đi
makeMove(move); // đi quân
int eval = minimax(depth - 1, false); // tìm kiếm xuống một tầng, lấy điểm của nút con ứng với nước đi này
undoMove(move); // khôi phục về thế cờ trước khi đi
maxEval = std::max(maxEval, eval);
}
return maxEval;
} else { // nếu hiện tại là Đen
int minEval = INT_MAX; // khởi tạo là dương vô cùng, để chương trình tìm ra điểm nhỏ nhất trong mọi nước đi
for (Move move : getPossibleMoves()) { // sinh nước đi
makeMove(move); // đi quân
int eval = minimax(depth - 1, true); // tìm kiếm xuống một tầng, lấy điểm của nút con ứng với nước đi này
undoMove(move); // khôi phục về thế cờ trước khi đi
minEval = std::min(minEval, eval); // lấy giá trị nhỏ nhất
}
return minEval;
}
}Quá trình cắt tỉa Alpha-Beta
Tìm kiếm Minimax đơn giản ở trên thực ra rất kém hiệu quả. Lúc này ta cần đưa vào một chiến lược tìm kiếm mới, cắt tỉa Alpha-Beta. Phương pháp cắt tỉa này có thể giảm đáng kể số nút phải tìm kiếm mà không làm thay đổi kết quả.
Như đã nói ở trên, mục đích của Đỏ là làm cho điểm càng cao càng tốt, tức là điểm của nút hiện tại là giá trị lớn nhất trong điểm của các nút con; Đen thì ngược lại.
Tham khảo hình trên, ta có thể lấy một ví dụ để giải thích nguyên lý của cắt tỉa Alpha-Beta.
Sau khi engine tìm xong hai nút lá 5 và 6, có thể suy ra điểm của nút cha của hai nút này (ID: 2 trong hình) là min(5,6)=5. Nút cha của nó nằm ở tầng MAX (ID: 1 trong hình), lấy giá trị lớn nhất của điểm các nút con, nên điểm của nó ít nhất là 5. Điểm của nút con chỉ khi >5 thì mới cần tìm tiếp, nếu không sẽ không tốt hơn đường "ID: 2".
Tiếp theo ta tiếp tục tìm đường "ID: 3", sau khi tìm xong hai nút lá "7" và "4", vì "ID: 3" nằm ở tầng MIN, điểm của nó là giá trị nhỏ nhất của điểm các nút con, nên điểm của nút này chắc chắn ≤4, không thể tốt hơn đường "ID: 2", không cần tìm tiếp nữa, ta có thể cắt bỏ các nút con phía sau (tức số 5 màu xám).
Các phần màu xám khác cũng tương tự, mọi người có thể tự suy ra theo các bước trên.
Suy luận lý thuyết thì hiểu rồi, nhưng đây vẫn là "lý thuyết suông", viết mã thế nào để hiện thực chức năng này? Mời xem phần sau.
Hiện thực cắt tỉa Alpha-Beta bằng mã
Để hiện thực cắt tỉa Alpha-Beta bằng mã, ta cần đưa vào hai đại lượng alpha và beta: alpha là điểm tối thiểu mà Đỏ có thể đảm bảo đạt được, beta là điểm tối đa mà Đen có thể đảm bảo (điểm ở đây đều tính theo góc nhìn của Đỏ). Nói cách khác, điểm của nước đi tối ưu chắc chắn ≥alpha và ≤beta.
Khi bắt đầu gọi hàm "alphaBeta", ta nên đặt alpha là âm vô cùng, beta là dương vô cùng.
Khi tìm kiếm một nút, ta cần nhận giá trị alpha và beta truyền từ nút cha, rồi xác định nút đó ở tầng MAX hay tầng MIN.
Ở đây lại lấy một ví dụ để bạn đọc dễ hiểu: giả sử ta đang ở tầng MAX (tức Đỏ), giá trị alpha nút cha truyền xuống là 5, beta là 8.
Vì điểm của nút hiện tại là giá trị lớn nhất trong điểm các nút con, nên khi tìm kiếm ta có thể đảm bảo điểm của nút hiện tại ≥ điểm của các nút con, và cần cập nhật alpha theo điểm của nút con. Nếu lúc này ta tìm thấy một nút con có điểm là 10, thì điểm của nút hiện tại chắc chắn ≥10. Nhưng đừng quên tầng trên là MIN, lấy điểm nhỏ nhất trong các nút con. Nếu điểm của nút hiện tại vượt quá beta, chắc chắn không thấp hơn điểm của một nút con nào đó mà nút cha đã tìm trước đó, sẽ không được nút cha chọn; nếu điểm của nút hiện tại bằng beta, chắc chắn cũng không tốt hơn một nút con mà nút cha đã tìm trước đó. Ta có thể dùng break để thoát vòng lặp, thực hiện cắt tỉa Beta, đồng thời trả về điểm lớn nhất của các nút con đã tìm (trong mã tìm kiếm hiện tại, giá trị trả về ở đây không quan trọng, chỉ cần đảm bảo nút này không bị nút cha chọn).
Việc kiểm tra điểm của nút hiện tại có ≥beta hay không có thể quy về kiểm tra alpha≥beta, vì alpha được cập nhật bằng cách lấy giá trị lớn nhất theo điểm của các nút con.
Tầng MIN cũng tương tự, không nhắc lại ở đây.
Mã giả như sau:
int alphaBeta(int depth, int alpha, int beta, bool isMaximizingPlayer) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
if (isMaximizingPlayer) { // nếu hiện tại là Đỏ
int maxEval = INT_MIN; // khởi tạo là âm vô cùng, để chương trình tìm ra điểm lớn nhất trong mọi nước đi
for (Move move : getPossibleMoves()) { // sinh nước đi
makeMove(move); // đi quân
int eval = alphaBeta(depth - 1, alpha, beta, false); // tìm kiếm xuống một tầng, lấy điểm của nút con ứng với nước đi này
undoMove(move); // khôi phục về thế cờ trước khi đi
maxEval = std::max(maxEval, eval); // lấy giá trị lớn nhất
alpha = std::max(alpha, eval);
if (beta <= alpha)
break; // cắt tỉa Beta
}
return maxEval;
} else { // nếu hiện tại là Đen
int minEval = INT_MAX; // khởi tạo là dương vô cùng, để chương trình tìm ra điểm nhỏ nhất trong mọi nước đi
for (Move move : getPossibleMoves()) { // sinh nước đi
makeMove(move); // đi quân
int eval = alphaBeta(depth - 1, alpha, beta, true); // tìm kiếm xuống một tầng, lấy điểm của nút con ứng với nước đi này
undoMove(move); // khôi phục về thế cờ trước khi đi
minEval = std::min(minEval, eval); // lấy giá trị nhỏ nhất
beta = std::min(beta, eval);
if (beta <= alpha)
break; // cắt tỉa Alpha
}
return minEval;
}
}Tiếp tục đơn giản hóa: đưa vào Negamax
Ở trên điểm số luôn theo góc nhìn của Đỏ, phải xét riêng Đỏ và Đen, rõ ràng làm mã phức tạp hơn. Để giải quyết vấn đề này, ta cần đưa vào Negamax.
Sau khi đưa vào Negamax, ta có thể dùng cùng một chiến lược xử lý cho cả hai bên, không cần viết mã cho bên MIN, nhưng hàm đánh giá cần đổi thành điểm theo góc nhìn của bên đang đi.
Nếu bên đi hiện tại là Đỏ, cần trả về điểm theo góc nhìn của Đỏ; nếu bên đi hiện tại là Đen, cần trả về điểm theo góc nhìn của Đen.
Vì đã gộp hai trường hợp làm một, tham số xác định Đỏ hay Đen có thể bỏ đi.
Khi tìm kiếm nút con, ta cần chuyển từ tầng MAX sang tầng MIN, hoặc từ MIN sang MAX, làm thế nào?
Ở đây tiếp tục lấy ví dụ. Giả sử alpha nút hiện tại nhận từ nút cha là 5, beta là 8, nghĩa là điểm của nước đi tối ưu nhất định nằm giữa 5 và 8; tiếp theo ta chuyển góc nhìn điểm sang đối thủ, điểm của nước đi tối ưu nhất định nằm giữa -8 và -5, -8 và -5 lần lượt là giá trị alpha và beta truyền cho nút con.
Vì vậy, alpha và beta truyền cho nút con nên là -beta và -alpha.
Dưới đây là mã giả sau khi đưa vào Negamax:
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
int maxEval = INT_MIN; // khởi tạo là âm vô cùng, để chương trình tìm ra điểm lớn nhất trong mọi nước đi
for (Move move : getPossibleMoves()) { // sinh nước đi
makeMove(move); // đi quân
int eval = -alphaBeta(depth - 1, -beta, -alpha); // tìm kiếm xuống một tầng, lấy điểm của nút con ứng với nước đi này
undoMove(move); // khôi phục về thế cờ trước khi đi
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta)
break; // cắt tỉa Beta
}
return maxEval;
}Mã trong một số tài liệu có thể như sau:
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
for (Move move : getPossibleMoves()) {
makeMove(move);
int val = -alphaBeta(depth - 1, -beta, -alpha);
undoMove(move);
if (val >= beta) {
return beta; // cắt tỉa Beta
}
if (val > alpha) {
alpha = val; // cập nhật giá trị Alpha
}
}
return alpha;
}Thực ra hai cách này tương đương. Trong trường hợp bình thường alpha<beta, nên trường hợp alpha≥beta chỉ có thể do cập nhật điểm làm alpha tăng lên mà xảy ra cắt tỉa Beta, vì vậy so sánh trực tiếp với val cũng như nhau.
Cắt tỉa nước rỗng (Null Move Pruning)
Nói chung, ở một thế cờ nếu bên ta không đi gì cả (hay nói cách khác đi một "nước rỗng"), nhường quyền đi cho đối phương, thì bên ta chịu thiệt. Tức là điểm của nước đi tối ưu nói chung sẽ không thấp hơn điểm của việc đi "nước rỗng".
Ta có thể tận dụng điều này để viết một chiến lược cắt tỉa, đó là cắt tỉa nước rỗng. Cắt tỉa nước rỗng là chiến lược mạo hiểm, dựa trên giả thuyết trên, cắt bỏ những nước đi có điểm thấp hơn "nước rỗng".
Để tăng tốc tìm kiếm, ta có thể giảm thêm R tầng (thường là 2-3) khi tìm kiếm "nước rỗng". Vì ta chỉ quan tâm điểm của "nước rỗng" lớn hơn hay nhỏ hơn beta, nên nên dùng tìm kiếm cửa sổ không ([beta - 1, beta]), để cắt tỉa Alpha-Beta phát huy tác dụng tối đa khi tìm kiếm nước rỗng.
Vì bên đi bị hoán đổi, giá trị alpha và beta truyền cho nút con cũng phải chuyển đổi theo cách trước, tức là -beta và -beta + 1.
Dựa trên giả thuyết điểm của nước rỗng ≤ điểm của nước đi tối ưu, nếu đánh giá trả về ≤beta-1, nghĩa là alpha của nút này sau đó có thể không đạt tới beta, không cắt tỉa; nếu đánh giá trả về ≥beta, nghĩa là điểm của nước đi tối ưu cũng chắc chắn ≥beta, tức là khi cập nhật alpha sau đó cũng sẽ ≥beta, có thể cắt tỉa ngay.
Tuy nhiên một số thế cờ không thỏa giả thuyết nêu trên, như thế cờ bắt buộc phải đi (Zugzwang) trong cờ vua, nếu dùng cắt tỉa nước rỗng sẽ khiến engine đánh giá sai, vì vậy ta có thể thiết kế hàm "isNullMoveAllowed" để kiểm tra có thỏa điều kiện cắt tỉa nước rỗng hay không, cố gắng tránh hiện tượng này.
Mã giả như sau:
// R là số tầng giảm thêm trong tìm kiếm cắt tỉa nước rỗng
const int R = 3;
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
// Null Move Pruning
if (depth >= R + 1 && isNullMoveAllowed()) {
makeNullMove(); // đi một "nước rỗng"
int nullMoveEval = -alphaBeta(depth - R - 1, -beta, -beta + 1); // tìm kiếm với [beta - 1, beta]
undoNullMove(); // khôi phục
if (nullMoveEval >= beta) {
return beta; // nếu beta còn không cao bằng điểm của "nước rỗng" thì cắt bỏ ngay
}
}
int value = INT_MIN;
for (Move move : getPossibleMoves()) { // sinh nước đi
makeMove(move); // đi quân
value = std::max(value, -alphaBeta(depth - 1, -beta, -alpha));
undoMove(move); // khôi phục
alpha = std::max(alpha, value);
if (alpha >= beta) {
break; // cắt tỉa Beta
}
}
return value;
}PVS (tìm kiếm biến chính)
PVS là bản nâng cấp của cắt tỉa Alpha-Beta, có thể nâng cao hiệu quả của cắt tỉa Alpha-Beta. Nói đơn giản, PVS trước hết tìm kiếm nút con đầu tiên với cửa sổ đầy đủ [alpha, beta], rồi tìm các nút con còn lại với cửa sổ không [alpha, alpha+1]. Sau khi tìm kiếm cửa sổ không xong, nếu đánh giá trả về của nút nằm trong khoảng (alpha, beta), nghĩa là nút này có triển vọng, nên tiếp tục tìm kiếm lại một lần với cửa sổ đầy đủ. Nếu đánh giá trả về nằm ngoài (alpha, beta), nghĩa là nút này chắc chắn sẽ bị cắt tỉa.
Mã giả như sau:
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
int maxEval = INT_MIN; // khởi tạo là âm vô cùng, để chương trình tìm ra điểm lớn nhất trong mọi nước đi
bool firstChild = true; // đánh dấu có phải nút con đầu tiên không
for (const Move& move : getPossibleMoves()) { // sinh nước đi
makeMove(move); // đi quân
int eval;
if (firstChild) {
// nút con đầu tiên dùng tìm kiếm cửa sổ đầy đủ
eval = -alphaBeta(depth - 1, -beta, -alpha);
firstChild = false;
} else {
// các nút con còn lại dùng tìm kiếm cửa sổ không
eval = -alphaBeta(depth - 1, -alpha - 1, -alpha);
if (eval > alpha && eval < beta) {
// nếu tìm kiếm cửa sổ không chưa thể khẳng định cắt tỉa, thì tìm lại với cửa sổ đầy đủ
eval = -alphaBeta(depth - 1, -beta, -eval);
}
}
undoMove(move); // khôi phục về thế cờ trước khi đi
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta) {
break; // cắt tỉa Beta
}
}
return maxEval;
}Lưu ý
Để đơn giản hóa mã, ở đây không thêm cắt tỉa nước rỗng; phần sau cũng chỉ giới thiệu riêng từng phương pháp, không chồng lên nhau.
Tìm kiếm tĩnh
Tìm kiếm tĩnh (Quiescent Search) có thể dùng để khắc phục hiệu ứng đường chân trời (horizon effect). Nói chung khi hai bên đổi quân ăn nhau, hàm đánh giá sẽ thay đổi mạnh; đưa vào tìm kiếm tĩnh có thể trả về giá trị đánh giá ổn định hơn. Sau khi đưa vào tìm kiếm tĩnh, khi đến nút lá ta không trả về ngay giá trị của hàm đánh giá mà thực hiện một lần tìm kiếm tĩnh, tiếp tục khám phá các nước ăn quân.
Mã giả như sau:
int qsearch(int alpha, int beta) {
int standPat = evaluate(); // giá trị đánh giá của thế cờ hiện tại khi không làm gì
if (standPat >= beta) {
return beta; // cắt tỉa
}
if (alpha < standPat) {
alpha = standPat; // cập nhật alpha
}
for (Move move : getPossibleCaptures()) { // chỉ xét các nước ăn quân
makeMove(move);
int eval = -qsearch(-beta, -alpha); // tìm kiếm tĩnh tầng tiếp theo
undoMove(move);
if (eval >= beta) {
return beta; // cắt tỉa
}
if (eval > alpha) {
alpha = eval; // cập nhật alpha
}
}
return alpha;
}
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return qsearch(alpha, beta); // vào tìm kiếm tĩnh khi độ sâu bằng 0 hoặc ván cờ kết thúc
}
int maxEval = INT_MIN; // khởi tạo là âm vô cùng
for (Move move : getPossibleMoves()) { // sinh mọi nước đi
makeMove(move); // thực hiện nước đi
int eval = -alphaBeta(depth - 1, -beta, -alpha); // tìm kiếm đệ quy
undoMove(move); // hủy nước đi
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta) {
break; // cắt tỉa Beta
}
}
return maxEval;
}