Chess AI Deep Dive

Try it out!

Below is a playable demo of my chess AI, see if you can beat it!

This Chess AI is by far one of the projects I am most proud of. It uses many programming techniques that I had not used before. Some of the more noteworthy techniques I used are magic bitboards, alpha-beta pruning, a custom hashing function, and transposition tables.

Magic Bitboards

A bitboard is a 64-bit integer representing the entire board state for one piece type. As an example, let's make a bitboard for the black pawns. First we assign a number to each board square. Then for every square with our desired piece type, we set that square's number bit to 1 on our bitboard. Now we have a single number representing the board for black pawns.

But why use bitboards?

It's fast
Using bitboards allow us to, using bit operations, very quickly determine many things about the current board state. For instance, it lets us get all pieces of a specific type in a single quick bit operation, where as if all pieces were stored in an array we would have too slowly loop over every square. Bitboards are also very information dense, storing a lot of information in a small amount of memory.

Putting the magic in Magic Bitboards

When generating the moves for a sliding piece (rook, bishop, queen) we need to know how far the sliding piece can move before getting blocked. We could check every square in each direction but that would be very slow and inefficent. A much faster way would be to just precalculate a lookup table of every possible combination of starting square and blockers. This is where the magic comes in.

At compile time generate a unique 64 bit magic number and shift amount for each square. We also generate an array of possible movement bitboards for a given slider.
Now to access these precomputed legal moves we:

1. Mask the relevent bits that, on an empty board, the slider could move to. This gives us our key.
2. Multiply the key by this square's magic number to get an index mapping.
3. Right shift the index mapping by (64 - this squares shift amount), giving us an index.
4. Use the index in the precomputed array of possible movement bitboards to get the slider's movement bitboard.

Doing all of this allows us to trade some extra space complexity for a lot less time complexity.

Alpha Beta Pruning

To find the best possible move, the AI simulates every series of possible moves and responses up to a certain depth. In general, the further the AI looks ahead, the smarter it becomes. However, due to the nature of this approach, the time it takes to search grows exponentially. To reduce the time taken, we employ alpha-beta pruning.

Alpha-beta pruning removes possible branches that we know are bad compared to a better move we saw beforehand. So if we test a move and it results in a neutral state, and we test another move that results us losing a rook. We can then safely discard all possible moves after the bad move because we know that it ends up poorly for us.

This reduces the amount of moves we have to check by upwards of 98%. Making the AI significantly faster.

Transposition Tables

There are many different moves that can lead to the same board state. In order to not waste time re-evaluating these board states we have seen before, we need an efficient way to store and retrieve our previous findings.

To do this we can implement a transposition table. We start by making a large dictionary of previous board states that we have seen, with the positions of all the pieces as a key. Now as we evaluate board states, we add them to this dictionary, storing the depth evaluated at, who the board is advantageous to, and whose turn it is. Then whenever we try to evaluate a board state, we first check if we have already evaluated it by seeing if it's in the transposition table. If it is, we can then skip this board state, as we have already evaluated it.

But how do we turn an entire chessboard into a unique number for the key?

Simple, we use a hash function.

Hashing Board States

The specific hash function we use is called Zobrist Hashing.
The way it works is by assigning a unique random number for every piece on every square. Whenever we have a piece on a specific square, we XOR the random number assigned to that piece square combo into a running total. Once we do this for every piece on the board, we have a semi-unique number for each board state.

Due to the amount of possible board states, it is impossible to store all 2¹³³ possibilities in a 2⁶⁴ integer. So at this point the goal becomes minimizing hash collisions as much as possible. The way we accomplish this is by making the randomly generated numbers have a high degree of linear independence. We treat each board square as a vector and try to make as many of them as possible, only able to add up to 0 when they each have a coefficient of 0. Doing this minimizes the number of inputs. that can lead to one output.

Code Sample

/// <summary>
///     Takes in a board state then recursively finds best move
/// </summary>
/// <param name="board"> A pointer to the current board state </param>
/// <param name="alpha"> Previous best move for us </param>
/// <param name="beta"> Previous worst move for enemy </param>
/// <param name="depth"> How many moves ahead are we </param>
/// <returns>
///     Returns the best move found in that generation and its score
/// </returns>
private (int score, Move bestMove) Search(Board* board, int alpha, int beta, int depth)
{
    nodesVisited++;

    //Make sure this move wouldnt repeat a previous board state (stops 3 fold repetition)
    if (RepetitionTable.Contains(board.zobristHashKey)) return IS_REPEAT;
    if (depth == AISearchDepth)
    {
        return EvaluateBoardState(board, board.currentColorTurn, depth);
    }

    //Check if we have already evaluated this state and return if so
    int evaluation = (int)TranspositionTable.ReadEntry(board.zobristHashKey, alpha, beta, depth);
    if (evaluation != -1) return evaluation;

    TranspositionTable.TableFlag flag = TranspositionTable.TableFlag.alpha;
    int bestEvaluation = int.MinValue + 1;

    //Generate all legal moves, then order based on estimate of how good they are
    List<Move> moves = MoveGenerator.GenerateLegalMoves(board);
    OrderMoves(moves, board);

    //Check if current team is in mate
    if ((Piece.IsSameTeam(board.currentColorTurn, Piece.White)) ? board.whiteInMate : board.blackInMate)
        return int.MinValue + 2 + depth;

    Move bestMoveSoFar = new Move { };
    foreach (Move move in moves)
    {
        //Make a move and recursively check its value
        board->MakeMove(move);
        evaluation = -Search(board, -beta, -alpha, depth + 1).score;
        board->UndoMove(move); 

        bestEvaluation = (evaluation > bestEvaluation) ? evaluation : bestEvaluation;
        //if current eval is better than supplied best move then store move
        if (bestEvaluation > alpha)
        {
            alpha = bestEvaluation;
            bestMoveSoFar = move;
            flag = TranspositionTable.TableFlag.exact;
        }

        //If this move is too good enemy will avoid it
        if (alpha >= beta)
        {
            //Write position to transposition table then prune branch
            TranspositionTable.WriteEntry(board.zobristHashKey, depth, (short)bestEvaluation, TranspositionTable.TableFlag.beta);
            return bestEvaluation;
        }
    }

    //Write newly evaluated state to transposition table
    TranspositionTable.WriteEntry(board.zobristHashKey, depth, (short)bestEvaluation, flag);
    return (alpha, bestMoveSoFar);
}

/// <summary>
///     Takes in a list of moves and pointer to current board and estimates how good each move is
/// </summary>
/// <param name="moves"> A list of currently possible moves </param>
/// <param name="board"> A pointer to the current board state </param
private void OrderMoves(List<Move> moves, Board* board)
{
    Move curMove;
    int scoreGuess;
    ulong enemyPawnThreatSquares = BitboardHelper.GenerateAllPawnAttackBitboard(Piece.ReverseColor(board->currentColorTurn), board);

    //Guess a moves score based on common criteria
    for (int i = 0; i < moves.Count; i++)
    {
        scoreGuess = 0;

        if (moves[i].destPiece != 0x00) //if can capture a piece with a less valuble piece
        {
            scoreGuess += 8 * PieceValues.GetPieceValue(moves[i].destPiece, moves[i].destSquare, board, false) 
				- PieceValues.GetPieceValue(moves[i].startPiece, moves[i].destSquare, board, false);
        }
        
        if ((enemyPawnThreatSquares & (1ul << moves[i].destSquare)) != 0)//if moving into pawn attack map
        {
            scoreGuess -= PieceValues.GetPieceValue(moves[i].startPiece, moves[i].destSquare, board, false) + 1000;
        }

        curMove = moves[i];
        curMove.score = (short)scoreGuess;
        moves[i] = curMove;
    }
    //Sort by each moves score
    moves.Sort((a, b) => b.score.CompareTo(a.score));
}

/// <summary>
///     Takes in a pointer to a board and returns its value relative to the passed in team
/// </summary>
/// <param name="board"> A point to the current board </param>
/// <param name="teamColor"> The color of the current team </param>
/// <param name="depth"> How many moves ahead is this </param>
/// <returns>
///     Returns the score of the board relative to the input team color
/// </returns>
private int EvaluateBoardState(Board* board, int teamColor, int depth)
{
    if ((Piece.IsSameTeam(teamColor, Piece.White) ? board->whiteInMate : board->blackInMate) == true)
    {
        return int.MinValue + 2 + depth;
    }

    //objective board value is always from white perspective so invert if we want blacks value
    int evaluation = Piece.IsSameTeam(teamColor, Piece.White) ? board->boardValue : -board->boardValue;
    evaluation += depth; //Add depth to bias faster play

    return evaluation;
}