• Categories

    Archives

  • Chess AI – Introduction

    No Comments

    ss_firstMove

    Introduction

    Recently I decided that I wanted to learn what makesĀ a chess AI tick. It turns out, at its heart, a chess AI is deceptively simple: white looks at every possible move it can make versus every possible move black can make as a response, versus white’s possible responses to that response, etc etc and chooses the move that seems to be the ‘best’. The complication comes in two forms: how to determine which move is actually ‘best’, and how to make the entire process as efficient as possible.

    Before I get this post into full-swing let me first direct you over to the wonderful ChessProgramming Wiki. This wiki contains a litany of information on pretty much any chess AI technique you can think of.

    Negamax

    Negamax is the tool we use to decide what move to make. Boiled down the its essence, the negamax function accepts the current state of the board, and the color being evaluated and returns an integer describing how favorable the given board state is for the given color. It does this by recursively calling itself with the resulting board state after every possible move that the given color can make (the ‘children’ of the current node). The function continues to recursively drill down until a certain maximum depth is reached where it simply returns the result of the static evaluation function for the current board state and color. On a level in which the maximum depth is not reached, the maximum value returned by all children of the current node is returned. When the actual root node of the tree returns the maximum value of its children, it also returns the potential move that is associated with this value.

    Pseudocode:

    int32 GameTree::_negamax(const board& boardState,
                             const piece_color color,
                             uint8 depthRemaining,
                             const uint8 actualHeight) {
        // is this a horizon node?
        if((depthRemaining == 0 || actualHeight >= settings.maximumDepth)) {
            stats.numLeaves++;
            return boardState.evaluate(color);
        }
    
        int32 score = -Infinity;
    
        // generate and sort move list
        TBoardPossibleMoves allValidMoves;
        boardState.runMoveGenerator(&allValidMoves,color);
        uint8 numMovesToSearch = allValidMoves.numMoves;
    
        if(numMovesToSearch == 0) {
            return boardState.evaluate(color); // no valid moves, mate/stalemate
        }
    
        for(uint8 validMoveIndex = 0; validMoveIndex < numMovesToSearch; validMoveIndex++) {
            const TBoardMove childMove = allValidMoves.moves[moveOrder[validMoveIndex]];
    
            board childBoardState = boardState;
            childBoardState.applyMove(childMove);
    
            uint8 continuationDepth = depthRemaining-1;
    
            const int32 childValue = -_negamax(childBoardState,
                                               NextColor[color],
                                               continuationDepth,
                                               actualHeight+1);
    
            if(childValue > score) {
                score = childValue;
                transpostionData.pvMove = childMove;
            }
        }
    
        goto jmp_done;
    
        // DONE
        jmp_done:
        ; {
            // are we the root node?
            if(actualHeight == 0) runtimeData.bestMoveAtRoot = transpostionData.pvMove;
    
            return score;
        }
    }
    

    Alpha-beta pruning

    While this function will work just fine, it will take a ridiculous amount of time to look more than a couple of moves ahead. To fix this we need a way to minimize the amount of processing that needs to be done. The main method for doing this is called alpha-beta pruning. This method works by establishing a window that the result of the negamax function can fall in, and if at anytime we see a score that is not within the window, we can stop searching children of the current node and just return the current best score.

    Pseudocode:

    int32 GameTree::_negamax(const board& boardState,
                             const piece_color color,
                             int32 alpha,
                             int32 beta,
                             uint8 depthRemaining,
                             const uint8 actualHeight) {
        // is this a horizon node?
        if((depthRemaining == 0 || actualHeight >= settings.maximumDepth)) {
            stats.numLeaves++;
            return boardState.evaluate(color);
        }
    
        int32 score = -Infinity;
    
        // generate and sort move list
        TBoardPossibleMoves allValidMoves;
        boardState.runMoveGenerator(&allValidMoves,color);
        uint8 numMovesToSearch = allValidMoves.numMoves;
    
        if(numMovesToSearch == 0) {
            return boardState.evaluate(color); // no valid moves, mate/stalemate
        }
    
        for(uint8 validMoveIndex = 0; validMoveIndex < numMovesToSearch; validMoveIndex++) {
            const TBoardMove childMove = allValidMoves.moves[moveOrder[validMoveIndex]];
    
            board childBoardState = boardState;
            childBoardState.applyMove(childMove);
    
            uint8 continuationDepth = depthRemaining-1;
    
            const int32 childValue = -_negamax(childBoardState,
                                               NextColor[color],
                                               -beta,
                                               -std::max(alpha,score),
                                               continuationDepth,
                                               actualHeight+1);
    
            if(childValue > score) {
                score = childValue;
                transpostionData.pvMove = childMove;
                
                if(score >= beta) {
                    stats.numCutoffs++;
                    goto jmp_done; // pruned
                }
            }
        }
    
        goto jmp_done;
    
        // DONE
        jmp_done:
        ; {
            // are we the root node?
            if(actualHeight == 0) runtimeData.bestMoveAtRoot = transpostionData.pvMove;
    
            return score;
        }
    }
    

    Whats Next

    In future articles I will describe other, more interesting, optimizations to negamax including transposition tables, history tables, move sorting, iterative deepening, and MTD(f) (a special form of null-window search). I will also write separate articles for the move generation and static evaluation as well.

     

    Comment RSS

    No Responses to “Chess AI – Introduction”

    Leave a Reply

  • Recent Posts

home login
content