Create an easy chess AI: 5 simple steps



    We translated for you an article by Lori Hartikka about creating the simplest AI for chess. It was written in 2017, but the basic principles remain the same. All the files that Laurie used are also available.

    A simple artificial intelligence that can play chess can be created on the basis of four concepts:

    1. 1. Relocation;
    2. 2. Score board;
    3. 3. Minimax ;
    4. 4. Alpha Beta Clipping . At each stage of working with the algorithm, one of them will be used, this will allow to gradually improve the game abilities of AI.

    Skillbox recommends: Applied online course "Python Data Analyst" .

    We remind: for all readers of "Habr" - a discount of 10,000 rubles when writing to any Skillbox course on the promotional code "Habr".

    Ready source code can be found on GitHub .


    Stage 1. Visualization of the chessboard with the generation of moves


    At this stage, we will use the chess.js libraries to generate moves and  chessboard.js to render the board. The library, which is responsible for the generation of moves, allows you to apply all the chess rules, so that we can count each action for a specific arrangement of the pieces. When you click on the picture, it will open in full resolution. Working with these libraries allows you to concentrate on the main task - searching and creating an algorithm that allows you to find the optimal course. We begin the work by writing a function that returns a random move from the list of all possible.






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

    Despite the fact that the algorithm is not an ideal chess player, for most players its level will be quite enough.


    Black goes randomly. ( source and game online )

    Stage 2. Position evaluation


    Now let's see which side has the advantage in one position or another. The easiest way is to calculate the relative strength of the pieces on the board; this can be done using a table.



    Using the evaluation function, we get the opportunity to create an algorithm that selects the course with the maximum rating.

    var calculateBestMove = function (game) {
        var newGameMoves = game.ugly_moves();
        var bestMove = null;
        //use any negative large numbervar 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 blackvar boardValue = -evaluateBoard(game.board())
            game.undo();
            if (boardValue > bestValue) {
                bestValue = boardValue;
                bestMove = newGameMove
            }
        }
        return bestMove;
    };

    In principle, the level is the same, but the algorithm can already take someone else’s figure when there is such an opportunity.


    Black got the opportunity to take white pieces. (Source and game here ).

    Stage 3. Search tree with minimax


    After that we create a search tree. Now the program can choose the best move from it. This is done using a minimax algorithm.

    Here, a recursive tree with the display of all possible moves is analyzed to a predetermined depth. The position is estimated by the leaves of our tree.

    Next, we return the minimum or maximum value of the child to the parent node. It all depends on which turn is being calculated. In other words, the result is maximized or minimized at each level.


    Here, the best move for White is b2-c3, since he guarantees that the player will get to the position with a score of -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;
        }
    };

    With the minimax algorithm, our AI has already begun to understand the basic tactics of chess.

    Minimax with a depth of 2 (Sources and game here )

    It is worth noting that the effectiveness of the minimax algorithm increases with the depth of the search. The next step is responsible for this.

    Stage 4. Alpha Beta Clipping


    This is a minimax optimization method that makes it possible to ignore some branches in the search tree. And this allows you to increase the depth of search, spending the same amount of resources.

    Alpha-beta pruning is based on a situation where we can stop evaluating a particular branch, if it is found that a new move will lead to a worse situation than the one we saw when evaluating the previous one.

    The result of minimax optimization does not affect, but everything starts to work faster.

    This algorithm is much more efficient if you first check the paths leading to good moves.


    The image shows moves that are no longer needed when using alpha-beta clipping.

    As you can see, with alpha-beta clipping, the minimax is optimized, and quite significantly.


    The number of positions that need to be evaluated in the case of a search with a depth of 4 and a starting position as shown above. (source and game are available here )

    Stage 5. Improved evaluation function


    The initial evaluation function is quite simple, since it simply counts the points of the pieces on the board. To optimize it, you can take into account the position of the figures. For example, if you place a horse in the center of the board, it becomes more expensive - the range of available moves for this figure will expand.

    At this stage, we will work with a slightly modified version of the square tables, originally described in the Chess Programming wiki .



    And now our algorithm is playing quite well, of course, compared to the average player.


    Sources and game are available here.

    Conclusion


    The advantage of the proposed algorithm is that it does not make very stupid mistakes. Of course, the strategy here is hardly perfect, but nonetheless.

    The implementation of our algorithm is only 200 lines of code, so the basic principles are quite simple. The final version of the program can be <a href=room github.com/lhartikk/simple-chess-ai'> on GitHub.

    Other modules can be added to the algorithm, including:



    You can learn more about chess algorithms at the Chess Programming Wiki .

    Skillbox recommends:


    Also popular now: