Bài 12: Máy tính chơi cờ giỏi hơn người thế nào? Minimax, cắt tỉa alpha–beta và AlphaZero

Năm 1997, máy tính Deep Blue của IBM đánh bại nhà vô địch cờ vua thế giới Garry Kasparov. Ngày nay, một ứng dụng cờ miễn phí trên điện thoại cũng mạnh hơn mọi kỳ thủ con người. Bí mật nằm ở một thuật toán tìm kiếm trên cây trò chơi: minimax và kỹ thuật cắt tỉa alpha–beta.

Bài thứ mười hai của chuyên mục "Thuật toán trong đời sống". Nếu bạn đã quen với đệ quy và duyệt cây, bạn có thể tự viết một "AI" chơi cờ ca-rô không bao giờ thua ngay sau bài này.

1. Cây trò chơi và thuật toán minimax

Mỗi thế cờ là một đỉnh, mỗi nước đi là một cạnh dẫn tới thế cờ mới. Hai người chơi luân phiên:

• MAX (máy) muốn điểm số lớn nhất;
• MIN (đối thủ) muốn điểm số nhỏ nhất, và ta giả sử đối thủ luôn chơi tốt nhất.

Giá trị một thế cờ được tính đệ quy: ở lượt MAX lấy max các con, ở lượt MIN lấy min các con; ở thế kết thúc, thắng = +1, hòa = 0, thua = −1. Năm 1950, Claude Shannon viết bài báo kỹ thuật đầu tiên về lập trình máy tính chơi cờ, mô tả đúng ý tưởng này.

Con số Shannon: Shannon ước tính cờ vua có khoảng 10¹²⁰ biến thể từ thế ban đầu. Nếu mỗi micro giây tính một biến thể, máy tính sẽ mất hơn 10⁹⁰ năm chỉ để tính nước đi đầu tiên. Vì vậy không thể duyệt hết cây – phải cắt tỉa và đánh giá.

2. Cắt tỉa alpha–beta: bỏ qua những nhánh vô ích

Trong hình, nhánh trái cho MAX giá trị 3. Ở nhánh phải, vừa thấy con đầu tiên bằng 2, ta biết MIN sẽ chọn giá trị ≤ 2 – kém hơn 3. MAX chắc chắn không đi nhánh phải, nên không cần xét các con còn lại.

Thuật toán duy trì hai giá trị: α – điểm tốt nhất MAX chắc chắn đạt được, và β – điểm tốt nhất MIN chắc chắn đạt được. Khi α ≥ β, cắt nhánh. Kết quả giống hệt minimax, chỉ nhanh hơn. Năm 1975, Donald Knuth và Ronald Moore công bố phân tích toán học về alpha–beta, chứng minh thuật toán tối ưu theo một nghĩa nhất định.

3. Code: AI chơi cờ ca-rô 3×3 không bao giờ thua

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
// Cờ ca-rô 3x3: X = máy (tối đa điểm), O = người (tối thiểu điểm)
char b[10] = "         ";
long long nodes = 0;
int winner(){
    int L[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
    for(auto& l : L) if(b[l[0]] != ' ' && b[l[0]] == b[l[1]] && b[l[1]] == b[l[2]])
        return b[l[0]] == 'X' ? 1 : -1;
    return 0;
}
int minimax(bool xTurn, int alpha, int beta, bool prune){
    nodes++;
    int w = winner(); if(w) return w;
    bool full = true;
    int best = xTurn ? -2 : 2;
    for(int i = 0; i < 9; i++) if(b[i] == ' '){
        full = false;
        b[i] = xTurn ? 'X' : 'O';
        int v = minimax(!xTurn, alpha, beta, prune);
        b[i] = ' ';
        if(xTurn){ best = max(best, v); alpha = max(alpha, v); }
        else     { best = min(best, v); beta  = min(beta, v); }
        if(prune && alpha >= beta) break;   // cắt tỉa: nhánh này không thể tốt hơn
    }
    return full ? 0 : best;
}
int main(){
    nodes = 0; int v1 = minimax(true, -2, 2, false);
    cout << "Minimax thuan:   ket qua " << v1 << ", duyet " << nodes << " trang thai\n";
    nodes = 0; int v2 = minimax(true, -2, 2, true);
    cout << "Co alpha-beta:   ket qua " << v2 << ", duyet " << nodes << " trang thai\n";
}

LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
board = [" "] * 9
nodes = 0

def winner():
    for a, b, c in LINES:
        if board[a] != " " and board[a] == board[b] == board[c]:
            return 1 if board[a] == "X" else -1
    return 0

def minimax(x_turn, alpha, beta, prune):
    global nodes
    nodes += 1
    w = winner()
    if w: return w
    moves = [i for i in range(9) if board[i] == " "]
    if not moves: return 0                    # hòa
    best = -2 if x_turn else 2
    for i in moves:
        board[i] = "X" if x_turn else "O"
        v = minimax(not x_turn, alpha, beta, prune)
        board[i] = " "
        if x_turn: best = max(best, v); alpha = max(alpha, v)
        else:      best = min(best, v); beta = min(beta, v)
        if prune and alpha >= beta: break     # cắt tỉa alpha–beta
    return best

for prune in (False, True):
    nodes = 0
    v = minimax(True, -2, 2, prune)
    print("alpha-beta" if prune else "minimax   ", "-> ket qua", v, "| so trang thai:", nodes)

Thuật toán	Kết quả	Số trạng thái phải duyệt
Minimax thuần	0 (hòa)	549.946
Minimax + alpha–beta	0 (hòa)	18.297

Cả hai cho kết quả 0: nếu hai bên đều chơi hoàn hảo, cờ ca-rô 3×3 luôn hòa. Nhưng alpha–beta chỉ duyệt khoảng 1/30 số trạng thái. Với cờ vua, tỉ lệ tiết kiệm còn lớn hơn rất nhiều khi các nước tốt được xét trước.

4. Từ Deep Blue đến AlphaZero

Deep Blue (1997): sức mạnh tính toán

Theo IBM, Deep Blue dùng 32 bộ xử lý và đánh giá được 200 triệu thế cờ mỗi giây. Năm 1996, Kasparov thắng trận đấu 4–2; nhưng trận tái đấu tháng 5/1997 ở New York, Deep Blue thắng 3,5–2,5.

AlphaZero (2017–2018): tự học

Theo bài báo trên tạp chí Science (2018) của DeepMind, AlphaZero chỉ được cho biết luật chơi, rồi tự chơi với chính nó để học. Sau khoảng 9 giờ huấn luyện, trong 1.000 ván với Stockfish – chương trình cờ mạnh nhất lúc đó – AlphaZero thắng 155 ván, thua 6 ván, còn lại hòa. Điều thú vị: AlphaZero chỉ tìm kiếm khoảng 60.000 thế cờ/giây, so với 60 triệu của Stockfish – nó "nghĩ ít nhưng nghĩ đúng chỗ" nhờ mạng nơ-ron.

Stockfish ngày nay: kết hợp cả hai

Stockfish vẫn dùng tìm kiếm dựa trên alpha–beta, và từ tháng 8/2020 có thêm hàm đánh giá bằng mạng nơ-ron NNUE chạy hiệu quả trên CPU. Theo blog chính thức của Stockfish, thay đổi này giúp tăng hơn 80 điểm Elo.

5. Bạn học được gì từ đây?

• Đệ quy + duyệt cây là nền tảng của AI chơi game.
• Cắt tỉa giúp bỏ qua phần lớn không gian tìm kiếm mà vẫn cho kết quả đúng.
• Thuật toán cổ điển và học máy không loại trừ nhau – chương trình mạnh nhất thường kết hợp cả hai.
• Các bài "trò chơi hai người" (lý thuyết trò chơi, Nim, Sprague–Grundy) rất hay xuất hiện trong đề thi.

Bài tập luyện tập

• CSES – Stick Game (trò chơi thắng/thua bằng quy hoạch động)
• CSES – Nim Game I
• AtCoder DP Contest L – Deque (minimax bằng quy hoạch động)

Thử thách: sửa code để máy chơi với bạn – bạn nhập vị trí, máy chọn nước có giá trị minimax tốt nhất. Bạn có thắng được nó không? Chia sẻ trong phần bình luận nhé!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 13: Mã QR bị rách vẫn quét được? Bí mật của mã sửa lỗi Reed–Solomon

Đọc tiếp: mã QR & Reed–Solomon →

← Bài trước: Wordle & entropyXem tất cả 27 bài →

Nguồn tham khảo

• History of Information – Shannon (1950), Programming a Computer for Playing Chess
• Fermat's Library – Programming a Computer for Playing Chess (Shannon)
• Chess Programming Wiki – Donald Knuth (Knuth & Moore 1975)
• IBM – Deep Blue
• Silver và cộng sự (2018) – AlphaZero, Science
• Stockfish (2020) – Introducing NNUE evaluation
• Wikipedia – Stockfish (chess)