Thuật toán Minimax + Alpha-Beta Pruning là gì? Giải thích dễ hiểu kèm demo chơi Tic-Tac-Toe

Trong bài viết này, chúng ta sẽ:

• Hiểu Minimax đang cố gắng giải bài toán gì.
• Nắm được ý tưởng Max/Min và hàm đánh giá trạng thái.
• Thấy Alpha-Beta Pruning cắt bớt được những nhánh vô nghĩa.
• Xem demo trực quan Minimax + Alpha-Beta trên trò chơi Tic-Tac-Toe bằng JavaScript.

Minimax là gì?

Minimax là một thuật toán dùng cho các trò chơi hai người dạng zero-sum game (tổng điểm hai bên luôn bằng 0, bên này được thì bên kia mất). Ta giả định:

• Một bên là Max: luôn cố gắng tối đa hóa điểm số.
• Bên còn lại là Min: luôn cố gắng tối thiểu hóa điểm số.

Ý tưởng cơ bản:

1. Xây dựng cây trò chơi: mỗi node là một trạng thái bàn cờ, các cạnh là những nước đi hợp lệ.
2. Lá của cây (trạng thái kết thúc) được gán điểm:
   • Max thắng: điểm dương (ví dụ +10).
   • Min thắng: điểm âm (ví dụ -10).
   • Hòa: 0.
3. Khi lan ngược từ lá lên:
   • Tại node là lượt Max → chọn giá trị lớn nhất trong các con.
   • Tại node là lượt Min → chọn giá trị nhỏ nhất trong các con.
4. Node gốc (trạng thái hiện tại) sẽ có một điểm Minimax. Nước đi tương ứng với con có điểm tốt nhất sẽ là lựa chọn tối ưu.

Alpha-Beta Pruning: tăng tốc Minimax

Nhược điểm của Minimax “thuần” là phải duyệt gần như toàn bộ cây trò chơi, rất tốn thời gian khi số trạng thái lớn. Alpha-Beta Pruning giúp cắt bỏ bớt các nhánh chắc chắn không thể cải thiện kết quả, nhờ hai giá trị:

• Alpha (α): điểm tốt nhất Max đã thấy.
• Beta (β): điểm tốt nhất Min đã thấy.

Trong quá trình duyệt:

• Tại node của Max: nếu tìm được giá trị ≥ β, Min sẽ không bao giờ chọn nhánh này, vì vậy các nhánh còn lại có thể bỏ qua.
• Tại node của Min: nếu tìm được giá trị ≤ α, Max sẽ không chọn nhánh này, nên cũng có thể bỏ qua.

Điều quan trọng là: Alpha-Beta Pruning không thay đổi kết quả Minimax tối ưu, mà chỉ giảm số lượng node phải duyệt, giúp thuật toán chạy nhanh hơn rất nhiều.

Mô hình demo: AI chơi Tic-Tac-Toe

Để trực quan, ta sử dụng trò chơi Tic-Tac-Toe (XO) trên bàn cờ 3×3:

• Bạn là X.
• AI là O.
• Sau mỗi nước của bạn, AI sẽ tính toán và chọn nước đi tối ưu bằng Minimax + Alpha-Beta.

Trong demo:

• Bàn cờ 3×3 hiển thị dưới dạng lưới.
• Bạn click vào ô trống để đánh X.
• AI tự động đánh O bằng thuật toán.
• Khu vực “Log” hiển thị chi tiết quá trình AI duyệt và cắt tỉa.

Demo Minimax + Alpha-Beta Pruning bằng JavaScript

Giải thích ngắn gọn đoạn code Minimax + Alpha-Beta

1. Biểu diễn bàn cờ và kiểm tra thắng/thua

Bàn cờ Tic-Tac-Toe 3×3 được biểu diễn bằng một mảng 1 chiều có 9 phần tử:

var board = ["", "", "", "", "", "", "", "", ""];

Mỗi ô có thể là:

• "": ô trống.
• "X": nước đi của người chơi.
• "O": nước đi của AI.

Hàm checkWinner(b) sẽ kiểm tra tất cả các hàng, cột và đường chéo để xem có bên nào thắng hay không. Nếu không còn ô trống mà vẫn chưa ai thắng thì trả về "draw" (hòa):

function checkWinner(b) {
    const lines = [
        [0,1,2],[3,4,5],[6,7,8],      // hàng
        [0,3,6],[1,4,7],[2,5,8],      // cột
        [0,4,8],[2,4,6]               // chéo
    ];
    for (const [a, c, d] of lines) {
        if (b[a] && b[a] === b[c] && b[a] === b[d]) return b[a]; // "X" hoặc "O"
    }
    if (b.every(x => x !== "")) return "draw"; // không còn ô trống
    return null; // chưa kết thúc
}

2. Hàm Minimax với Alpha-Beta Pruning

Hàm minimax nhận vào:

• b: trạng thái bàn cờ hiện tại.
• depth: độ sâu trong cây (dùng để điều chỉnh điểm).
• isMax: nếu là true thì đang tới lượt Max (X), ngược lại là Min (O).
• alpha, beta: hai ngưỡng dùng để cắt tỉa nhánh.

Đầu tiên, nếu trạng thái hiện tại đã kết thúc (X thắng, O thắng, hoặc hòa), ta trả về điểm:

• X thắng: 10 - depth (thắng càng sớm càng tốt).
• O thắng: depth - 10 (AI muốn X bị thua, nên điểm âm).
• Hòa: 0.

function minimax(b, depth, isMax, alpha, beta) {
    var result = checkWinner(b);
    if (result === "X") return 10 - depth;
    if (result === "O") return depth - 10;
    if (result === "draw") return 0;

    if (isMax) {
        var best = -Infinity;
        for (var i = 0; i < 9; i++) {
            if (b[i] === "") {
                b[i] = "X";
                var score = minimax(b, depth + 1, false, alpha, beta);
                b[i] = "";
                best = Math.max(best, score);
                alpha = Math.max(alpha, best);
                if (beta <= alpha) {
                    break; // cắt nhánh nếu không cần xét thêm
                }
            }
        }
        return best;
    } else {
        var bestMin = Infinity;
        for (var j = 0; j < 9; j++) {
            if (b[j] === "") {
                b[j] = "O";
                var scoreMin = minimax(b, depth + 1, true, alpha, beta);
                b[j] = "";
                bestMin = Math.min(bestMin, scoreMin);
                beta = Math.min(beta, bestMin);
                if (beta <= alpha) {
                    break; // cắt nhánh nếu không cần xét thêm
                }
            }
        }
        return bestMin;
    }
}

Phần if (beta <= alpha) break; chính là chỗ Alpha-Beta Pruning phát huy tác dụng: khi nhận ra rằng các nhánh còn lại không thể cho kết quả tốt hơn, ta dừng duyệt những nhánh đó để tiết kiệm thời gian.

3. AI chọn nước đi dựa trên Minimax

Khi tới lượt AI (O), ta thử đặt O vào từng ô trống, tính điểm Minimax cho mỗi lựa chọn, rồi chọn nước đi có điểm nhỏ nhất (vì O là Min, muốn tối thiểu hóa điểm):

function aiMove() {
    var bestScore = Infinity;
    var bestMove = null;

    log("AI bắt đầu chạy Minimax + Alpha-Beta...");

    for (var i = 0; i < 9; i++) {
        if (board[i] === "") {
            board[i] = "O";
            var score = minimax(board, 0, true, -Infinity, Infinity);
            board[i] = "";
            log("Thử ô " + (i + 1) + " → điểm = " + score + ".");
            if (score < bestScore) {
                bestScore = score;
                bestMove = i;
            }
        }
    }

    board[bestMove] = "O";
    log("AI đánh O vào ô " + (bestMove + 1) + ".");
    renderBoard();

    var winner = checkWinner(board);
    if (winner) {
        endGame(winner);
        return;
    }

    currentPlayer = "X";
    updateResult("Tới lượt bạn.");
}

Nhờ cách đánh giá này, AI sẽ luôn chọn được nước đi không thua (trên Tic-Tac-Toe chuẩn 3×3). Nếu người chơi đi sai, AI có thể tận dụng để giành chiến thắng.