Hướng dẫn tạo một đối thủ AI đơn giản cho cờ vua

Tác giả: Lauri Hartikka

Chúng ta hãy cùng khám phá một số khái niệm cơ bản sẽ giúp chúng ta tạo ra một AI cờ vua đơn giản:

• move-generation (Khởi tạo các bước di chuyển)
• board evaluation (Khả năng tiên đoán nước cờ của đối thủ)
• minimax (Thuật toán tính toán nước đi)
• alpha beta pruning. (Tinh chỉnh phương thức Alpha-beta)

Ở mỗi bước, chúng tôi sẽ cải tiến thuật toán bằng một trong những kỹ thuật lập trình game cờ vua đã qua thử nghiệm. Tôi sẽ chứng minh làm thế nào để tác động đến lối chơi của thuật toán.

Bạn có thể xem thuật toán AI hoàn chỉnh trên GitHub.

Bước 1: Hiển thị các bước di chuyển và bàn cờ

Chúng tôi sẽ sử dụng thư viện chess.js để phát triển các bước di chuyển và chessboard.js để hiển thị bàn cờ. Thư viện tạo ra các bước di chuyển cơ bản tuân theo tất cả quy luật của cờ vua. Dựa vào điều này, chúng ta có thể tính toán tất cả các bước đi hợp lý cho một ván chơi nhất định.

Sử dụng các thư viện này sẽ giúp chúng ta có thể dồn toàn tâm toàn ý vào công việc thú vị nhất: tạo ra thuật toán tìm nước cờ tốt nhất.

Chúng ta sẽ bắt đầu bằng cách tạo ra một chức năng chỉ trả về một nước đi ngẫu nhiên từ tất cả hướng có thể:

var calculateBestMove =function(game) {
    //generate all the moves for a given position
    var newGameMoves = game.ugly_moves();
    return newGameMoves[Math.floor(Math.random() * newGameMoves.length)];
};

Mặc dù thuật toán này không tạo nên đối thủ cứng tay, tuy nhiên đó là một khởi đầu tốt, chúng ta thực sự đã có thể chơi với nó:

Bước 2: Dự đoán các nước đi

Bây giờ chúng ta hãy cố gắng hiểu được bên nào mạnh hơn ở vị trí nào đó. Cách đơn giản nhất để đạt được điều này là tính toán sức mạnh tương đối của các quân cờ trên bàn bằng cách sử dụng bảng sau:

Với chức năng dự đoán, chúng ta có thể tạo ra một thuật toán chọn nước cờ đạt hiểu quả cao nhất:

var calculateBestMove = function (game) {

    var newGameMoves = game.ugly_moves();
    var bestMove = null;
    //use any negative large number
    var bestValue = -9999;

    for (var i = 0; i < newGameMoves.length; i++) {
        var newGameMove = newGameMoves[i];
        game.ugly_move(newGameMove);

        //take the negative as AI plays as black
        var boardValue = -evaluateBoard(game.board())
        game.undo();
        if (boardValue > bestValue) {
            bestValue = boardValue;
            bestMove = newGameMove
        }
    }

    return bestMove;

Cải tiến duy nhất đạt được là thuật toán của chúng ta sẽ nắm bắt được một phần phương thức di chuyển nếu có thể.

Bước 3: Tìm kiếm nước đi hiểu quả nhất bằng Minimax

Tiếp theo, chúng ta sẽ tạo ra các hướng đi có thể xảy ra từ đó thuật toán có thể chọn bước di chuyển tốt nhất. Điều này được thực hiện bằng cách sử dụng thuật toán Minimax.

Trong thuật toán này, hướng đi của tất cả các nước cờ có thể được tính toán kỹ trong từng tình huống nhất định, và vị trí được dự đoán cuối cùng là hiệu quả nhất.

Sau đó, chúng ta sẽ trả lại giá trị nhỏ nhất hoặc lớn nhất của child cho parent node, tùy thuộc vào việc đó là cờ trắng hoặc đen để di chuyển. (Đó là, chúng tôi cố gắng để giảm thiểu hậu quả hoặc tối đa hóa hiệu quả ở mỗi tình huống.)

var minimax = function (depth, game, isMaximisingPlayer) {
    if (depth === 0) {
        return -evaluateBoard(game.board());
    }
    var newGameMoves = game.ugly_moves();
    if (isMaximisingPlayer) {
        var bestMove = -9999;
        for (var i = 0; i < newGameMoves.length; i++) {
            game.ugly_move(newGameMoves[i]);
            bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
            game.undo();
        }
        return bestMove;
    } else {
        var bestMove = 9999;
        for (var i = 0; i < newGameMoves.length; i++) {
            game.ugly_move(newGameMoves[i]);
            bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
            game.undo();
        }
        return bestMove;
    }

Với minimax, thuật toán của chúng tôi bắt đầu hiểu một số chiến thuật cơ bản của cờ vua:

Hiệu quả của thuật toán minimax chủ yếu dựa vào khám phá ra nước cờ tiếp theo đó mà chúng ta có thể đạt được. Đây là điều chúng tôi sẽ cải thiện trong bước tiếp theo.

Bước 4: Tinh chỉnh Alpha-beta

Việc tinh chỉnh Alpha-beta là một phương pháp tối ưu hóa thuật toán minimax cho phép chúng ta bỏ qua một số hướng trong tất cả hướng đi có thể. Điều này giúp chúng tôi dự đoán hướng bằng minimax hiệu quả, trong khi sử dụng cùng một thuật toán.

Việc giảm thiểu alpha-beta dựa trên tình huống mà chúng ta có thể ngừng đưa ra hướng đi nếu chúng ta thấy hướng đi đó dẫn đến một kết quả tồi tệ hơn là bước di chuyển đã tìm ra từ trước.

Việc điều chỉnh alpha-beta không ảnh hưởng đến kết quả của thuật toán minimax, nó chỉ làm cho thuật toán nhanh hơn.

Thuật toán alpha-beta cũng hiệu quả hơn nếu chúng ta tìm ra những hướng đi dẫn tới các nước cờ tốt đầu tiên.

Với alpha-beta, chúng tôi đạt được sự cải thiện đáng kể cho thuật toán minimax, như thấy trong ví dụ sau:

Theo link này để thử phiên bản cải tiến alpha-beta của AI cờ vua.

Bước 5: Cải thiện chức năng dự đoán

Chức năng dự đoán ban đầu khá là đơn giản vì chúng chỉ đếm các nước đi được tìm thấy trên bàn cờ. Để cải thiện điều này, chúng tôi thêm vào dự đoán một yếu tố có tính đến vị trí của các quân cờ. Ví dụ, một con mã nằm ở giữa bàn cờ là tốt hơn (vì nó có nhiều lựa chọn hơn và vì vậy hoạt động mạnh hơn) so với một con mã trên mép của bàn cờ.

Chúng ta sẽ sử dụng các ô mà từng quân cờ có thể đi được dựa trên nguồn chess-programming-wiki nhờ vậy mà chất lượng AI được cải thiện.

Với những cải tiến sau đây, chúng tôi bắt đầu có được một thuật toán chơi cờ với những nước đi “hợp lý”, ít nhất là từ quan điểm của một kỳ thủ bình thường:

Kết luận

Sức mạnh của ngay cả một thuật toán chơi cờ vua đơn giản cũng có là không tạo ra những sai lầm ngu ngốc. Tuy nhiên, nó vẫn còn thiếu về phần lên chiến lược.

Với các phương pháp tôi giới thiệu ở đây, chúng tôi đã có thể lập trình một thuật toán chơi cờ vua có thể chơi cơ bản. Về phần “AI” (các nước đi ngẫu nhiên bị loại bỏ) của thuật toán cuối cùng chỉ có 200 dòng code, điều này khá đơn giản để thực hiện. Bạn có thể kiểm tra phiên bản hoàn chỉnh trên GitHub.

Một số cải tiến khác chúng tôi có thể thực hiện cho thuật toán như:

• move-ordering (sắp xếp các nước đi)
• faster move generation (tính toán các nước đi nhanh hơn)
• và end-game specific evaluation. (dự đoán khi nào kết thúc ván cờ)

Nếu bạn muốn tìm hiểu thêm, hãy thử xem qua chess programming wiki. Đó là một nguồn thông tin hữu ích để bạn có thể khám phá vượt qua khái niệm cơ bản mà tôi giới thiệu ở bài này.

Cảm ơn bạn đã đọc bài viết này!

Đừng bỏ lỡ những bài viết hay về Machine Learning:

• Machine Learning thật thú vị: Dự đoán giá nhà đất
• Sử dụng Machine Learning trên Compute Engine để recommend sản phẩm (phần 1)
• Sử dụng Machine Learning để visualize customer preferences

Xem thêm tuyển dụng kỹ sư AI hot nhất trên TopDev

Bài viết gốc được đăng tải tại Freecodecamp