Thuật toán tự động phá đảo game 2048: Từ chiến lược người chơi đến AI expectimax

1. Ôn lại: bản chất bài toán 2048 là gì

Tóm tắt luật chơi 2048:

• Bàn cờ 4×4.
• Mỗi lượt:
  • Người chơi chọn một trong 4 hướng: lên, xuống, trái, phải.
  • Các ô trượt hết cỡ theo hướng đó, các ô cùng giá trị sát nhau sẽ gộp: 2+2, 4+4, 8+8, …
  • Hệ thống sinh thêm một ô mới: 90% là 2, 10% là 4, tại một ô trống ngẫu nhiên.
• Thua khi không còn nước đi hợp lệ nào.
• Mục tiêu thường là đạt ô 2048 hoặc cao hơn.

Nếu nhìn dưới góc độ thuật toán:

• Người chơi là một agent.
• Mỗi nước đi là một action thuộc tập {Up, Right, Down, Left}.
• Việc sinh ô 2/4 ngẫu nhiên là môi trường (stochastic environment).
• Mục tiêu là tìm một chiến lược (policy) giúp:
  • Tối đa hóa điểm số, hoặc
  • Tối đa xác suất đạt được ô lớn nhất (2048, 4096,…), hoặc
  • Tối đa hóa kỳ vọng ô lớn nhất trên bàn.

Đây là bài toán tìm kiếm trong không gian trạng thái, có yếu tố ngẫu nhiên. Thuật toán phù hợp là expectimax, thay vì minimax truyền thống.

2. Chiến lược cơ bản của người chơi giàu kinh nghiệm

Trước khi dùng AI phức tạp, cần hiểu cách một người chơi “tay to” thường sử dụng chiến lược nào. Những chiến lược này sau đó sẽ được đưa vào hàm đánh giá của bot:

• Giữ ô lớn nhất ở một góc cố định (thường là góc dưới bên trái hoặc phải).
• Ưu tiên sử dụng hai hướng chính (ví dụ: trái + xuống), hai hướng còn lại chỉ dùng khi cần thiết.
• Tránh tạo ra các hàng/cột “gãy sóng” với các giá trị lớn nằm kẹt giữa các giá trị nhỏ.
• Luôn ưu tiên trạng thái có nhiều ô trống để giảm nguy cơ bế tắc.

Các nguyên tắc này sẽ được biến thành các tiêu chí cụ thể trong evaluation function khi xây bot.

3. Mô hình hóa 2048 thành cây tìm kiếm

Để áp dụng thuật toán tìm kiếm, ta mô hình hóa ván 2048 thành cây trạng thái với hai loại node:

• Player node (lượt người chơi):
  • Đầu vào: trạng thái bàn cờ hiện tại.
  • Đầu ra: chọn một trong bốn hướng hợp lệ.
• Chance node (lượt ngẫu nhiên của môi trường):
  • Xử lý việc sinh ô mới:
    • Chọn một vị trí trống.
    • Chèn ô 2 với xác suất 0.9 hoặc ô 4 với xác suất 0.1.

Nếu dùng minimax, môi trường sẽ bị xem như một đối thủ “xấu nhất”. Tuy nhiên trong 2048, môi trường chỉ sinh số ngẫu nhiên chứ không cố tình chống lại người chơi, do đó mô hình phù hợp hơn là expectimax, nơi node “chance” sử dụng giá trị kỳ vọng theo xác suất.

4. Thuật toán expectimax cho 2048

Ý tưởng của expectimax:

• Giới hạn độ sâu tìm kiếm (ví dụ 4–6 lớp).
• Tại node người chơi:
  • Duyệt tất cả các hướng hợp lệ.
  • Tính giá trị trạng thái sau khi đi.
  • Chọn hướng có giá trị cao nhất.
• Tại node ngẫu nhiên:
  • Duyệt tất cả ô trống và khả năng sinh ô 2/4.
  • Tính giá trị kỳ vọng có trọng số theo xác suất 0.9 và 0.1.

Một phiên bản giả mã đơn giản (giả lập theo kiểu JavaScript):

function expectimax(board, depth, isPlayerTurn) {
    if (depth === 0 || isGameOver(board)) {
        return evaluate(board); // Hàm đánh giá trạng thái
    }

    if (isPlayerTurn) {
        let best = -Infinity;
        const moves = [UP, RIGHT, DOWN, LEFT];

        for (const move of moves) {
            const newBoard = applyMove(board, move);
            if (!boardsEqual(newBoard, board)) {
                const value = expectimax(newBoard, depth - 1, false);
                if (value > best) {
                    best = value;
                }
            }
        }

        return best;
    } else {
        // Node ngẫu nhiên: sinh 2 hoặc 4 vào các ô trống
        const emptyCells = getEmptyCells(board);
        if (emptyCells.length === 0) {
            return evaluate(board);
        }

        const p2 = 0.9;
        const p4 = 0.1;
        let expectedValue = 0;

        for (const [r, c] of emptyCells) {
            const board2 = cloneBoard(board);
            board2[r][c] = 2;
            expectedValue += (p2 / emptyCells.length) *
                expectimax(board2, depth - 1, true);

            const board4 = cloneBoard(board);
            board4[r][c] = 4;
            expectedValue += (p4 / emptyCells.length) *
                expectimax(board4, depth - 1, true);
        }

        return expectedValue;
    }
}

Khi bot chơi, tại mỗi bước ta chọn nước đi có giá trị expectimax tốt nhất:

function chooseBestMove(board, searchDepth) {
    let bestMove = null;
    let bestValue = -Infinity;
    const moves = [UP, RIGHT, DOWN, LEFT];

    for (const move of moves) {
        const newBoard = applyMove(board, move);
        if (boardsEqual(newBoard, board)) {
            continue; // Nước đi không hợp lệ, không thay đổi board
        }

        const value = expectimax(newBoard, searchDepth, false);
        if (value > bestValue) {
            bestValue = value;
            bestMove = move;
        }
    }

    return bestMove;
}

Khung này chỉ là phần khung thuật toán. Điều quan trọng nhất để bot chơi tốt là hàm evaluate(board).

5. Thiết kế hàm đánh giá (evaluation function)

Hàm đánh giá biến một trạng thái bàn cờ thành một con số. Số càng lớn thì trạng thái càng “tốt” theo quan điểm chiến lược của bot. Cách phổ biến là kết hợp tuyến tính nhiều tiêu chí (features):

score(board) =
    w_empty   * emptyCells(board)
  + w_mono    * monotonicity(board)
  + w_smooth  * smoothness(board)
  + w_corner  * maxTileCorner(board)
  + w_merge   * potentialMerges(board)
  + ...

Trong đó các w_* là trọng số, có thể chỉnh tay hoặc tối ưu hóa bằng các kỹ thuật khác. Giải thích từng tiêu chí:

5.1. Số lượng ô trống (empty cells)

Càng nhiều ô trống, khả năng hết nước đi càng thấp, và bàn cờ càng “dễ thở”. Một phiên bản đơn giản:

function countEmptyCells(board) {
    let count = 0;
    for (const row of board) {
        for (const cell of row) {
            if (cell === 0) {
                count++;
            }
        }
    }
    return count;
}

5.2. Độ đơn điệu (monotonicity)

Bàn cờ tốt thường có các hàng/cột tăng dần hoặc giảm dần đều, ví dụ:

1024 512 256 128
 64   32  16   8

Cách tính phổ biến:

• Cho mỗi hàng và mỗi cột, xem chuỗi giá trị có “mượt” không.
• Phạt các đoạn “gãy sóng” nơi giá trị nhảy ngược chiều.
• Độ đơn điệu cao được thưởng điểm.

5.3. Độ mượt (smoothness)

Độ mượt phản ánh việc các ô kề nhau có giá trị gần nhau hay không. Lý do: các giá trị gần nhau sẽ dễ merge hơn về sau.

Ý tưởng:

• Duyệt các cặp ô kề nhau (trên dưới, trái phải).
• Phạt theo |log2(a) − log2(b)|, càng nhỏ càng tốt.
• Tổng smoothness có thể là số âm, và được cộng với trọng số âm trong score.

5.4. Ô lớn nhất nằm ở góc (max tile in corner)

Chiến lược phổ biến là giữ ô lớn nhất ở một góc cố định. Ta có thể thêm một điểm thưởng nếu ô lớn nhất nằm ở một trong bốn góc:

function getMaxTile(board) {
    let max = 0;
    for (const row of board) {
        for (const cell of row) {
            if (cell > max) {
                max = cell;
            }
        }
    }
    return max;
}

function maxTileCorner(board) {
    const maxTile = getMaxTile(board);
    const corners = [
        board[0][0],
        board[0][3],
        board[3][0],
        board[3][3],
    ];
    return corners.includes(maxTile) ? 1 : 0;
}

5.5. Khả năng merge (potential merges)

Đây là số lượng cặp ô kề nhau có cùng giá trị. Càng nhiều cặp tiềm năng, khả năng tạo ra các ô lớn trong tương lai càng cao. Ta có thể đếm các cặp bằng nhau theo chiều ngang và dọc, rồi nhân với một trọng số dương.

6. Cân bằng giữa độ sâu tìm kiếm và hiệu năng

Cây tìm kiếm của 2048 có thể rất lớn:

• Mỗi node người chơi có tối đa 4 nhánh (4 hướng).
• Mỗi node ngẫu nhiên có tối đa 16 ô trống × 2 loại ô (2 và 4) = 32 nhánh.

Nếu tìm kiếm quá sâu, bot sẽ tính rất chậm, không phù hợp chạy trong trình duyệt. Một số cách cân bằng:

• Giới hạn độ sâu: thường 4–6 lớp là hợp lý cho trình duyệt.
• Cắt giảm nhánh ở node ngẫu nhiên:
  • Chỉ xét một subset các ô trống.
  • Ưu tiên chọn một số ô trống “ít gây hại”, ví dụ tránh phá góc lớn.
• Tối ưu biểu diễn bàn cờ:
  • Mã hóa board thành bitboard để tính toán nhanh hơn (trong các bản tối ưu cao).
  • Precompute kết quả trượt cho từng hàng/cột.

7. Demo 2048 AI auto-play

Đoạn dưới đây là một demo nhỏ: một bản 2048 mini chạy trong trình duyệt với bot expectimax đơn giản. Nút “Bắt đầu Auto-play” sẽ cho bot tự đánh, mỗi lượt có một khoảng trễ nhỏ để bạn quan sát, và game sẽ dừng khi xuất hiện ô 2048 hoặc không còn nước đi.

8. Kết luận

Game 2048 là một ví dụ điển hình cho việc một trò chơi đơn giản có thể trở thành bài toán AI thú vị. Thuật toán expectimax kết hợp với một hàm đánh giá được thiết kế tốt cho phép bot đạt được kết quả rất ổn định, thường vượt xa người chơi thông thường.

Bằng cách chuyển kinh nghiệm chơi game (giữ góc, tối đa ô trống, giữ cấu trúc đơn điệu, ưu tiên merge hợp lý) thành các tiêu chí định lượng, chúng ta có thể xây dựng một bot 2048 vừa hiệu quả, vừa dễ mở rộng.