Thuật toán alpha-beta python

Từng bước một, chúng tôi sẽ cải tiến tiến trình 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 chuyển đổi và cờ bàn

Chúng tôi sẽ sử dụng thư viện cờ vua. js để phát triển các bước chuyển đổi và bàn cờ. js to display table flags. Thư viện tạo ra các bước chuyển đổi cơ bản tuân theo tất cả các quy định 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 hình tốt nhất

Hình dung chức năng tạo các nước đi. based on the position started to tính toán ra tất cả các nước đi có thể từ vị trí đó

Việc sử dụng các thư viện này sẽ giúp chúng ta có thể quan sát toàn tâm toàn ý vào công việc thú vị nhất. tạo 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ả cá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 ra nên chống lại phần 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ó

Cờ đen tự động chuyển các nước đi ngẫu nhiê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 tranh của 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 cờ nướ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 chuyển đổi nếu có thể

Cờ đen chơi với sự hỗ trợ của chức năng dự đoán đơn giản

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 chuyển đổi 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 cờ nước có thể được tính toán kỹ thuật trong từng tình huống rõ ràng nhất, 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 nút con cho nút cha, tùy thuộc vào công việc đó là cờ trắng hoặc đen để 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. ]

Hình dung thuật toán minimax cho trí thông minh nhân tạo. Nước đi tốt nhất cho cờ trắng là b2-c3, bởi vì chúng tôi có thể chắc chắn rằng tại vị trí mà tính toán là -50

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

Tính toán Minimax trước 2 nước đi

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 đó 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 chỉnh sửa 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 loại bỏ một số hướng trong tất cả các hướng có thể đi được. Điều này giúp chúng tôi dự đoán định hướng bằng hiệu quả minimax, 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ể tiếp tục đư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 có hiệu quả hơn nếu chúng ta tìm ra những hướng đi đến các cờ nước tốt nhất

Các vị trí chúng ta không cần phải quan tâm nếu việc tinh chỉnh alpha-beta được sử dụng và hướng đi tuân thủ theo thứ tự được mô tả

Với bản 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 liên kết này để thử phiên bản cải tiến alpha-beta của AI flags vua

Bước 5. Dự kiến ​​khả năng cải thiện chức năng

Chức năng dự đoán ban đầu khá đơ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 bổ sung vào dự đoán một yếu tố có tính đến vị trí của quân cờ. Ví dụ, một con mã nằm ở giữa bàn cờ 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] vì vậy với một con mã trên màn che 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ờ như vậy mà chất lượng AI được cải thiện

Các ô minh họa để dễ hình dung. Chúng tôi có thể tính điểm tăng hay giảm của mỗi nước đi, tùy thuộc vào vị trí của mỗi quân cờ

Với những cải tiến sau đây, chúng tôi bắt đầu 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

Cải thiện dự kiến ​​và tinh chỉnh alpha-beta với khả năng tính toán trước 3 nước. Can't try on https. //jsfiddle. net/q76uzxwe/1/

Kết luận

Sức mạnh của ngay cả một thuật toán trò 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ể thiết lập một chương trình 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 mã, đ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ố tiến trình khác mà 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]
• thế hệ di chuyển nhanh hơn [tính toán các nước đi nhanh hơn]
• và đánh giá cụ thể về cuối trò chơi. [dự đoán khi nào cờ kết thúc]

Nếu bạn muốn tìm hiểu thêm, hãy thử xem qua wiki lập trình cờ vua. Đó 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 viết này