Chess AI

2022 Dec 05 See all posts

Chess AI

I built an AI that plays chess and it kicked my ass

Play a game Visit App

Source code Github

What does it do?

Plays "good" moves
Beats the other player
Talks when beating the other player

How?

You might be wondering, how one creates an Chess AI? or how bad is Daniel at Chess exactly?

For those two questions, two short answers:

It's easy
Very bad

Let's elaborate on the how

First of all, we need an GUI. I chose Javascript since there are many chess libraries available to choose from. That's very convenient since I didn't want to re-invent the wheel.

I used:

Board's UI: cm-chessboard
Move validation and chess functionality: chess.js

Once we got the board and input validation going, things start to get interesting...

AI 🤖

"AI without data, go prrrrrrrrrrrrr."

– Anonymous Philosopher

We don't want an AI that just plays random moves, so we need to give it data to evaluate which moves are better.

First, each piece needs a value:

Pawn: 100
Knight: 280
Bishop: 320
Rook: 479
Queen: 929
King: 60,000

Each piece's position in the board needs a value too

// PAWN
p: [
    [100, 100, 100, 100, 105, 100, 100, 100],
    [78, 83, 86, 73, 102, 82, 85, 90],
    [7, 29, 21, 44, 40, 31, 44, 7],
    [-17, 16, -2, 15, 14, 0, 15, -13],
    [-26, 3, 10, 9, 6, 1, 0, -23],
    [-22, 9, 5, -11, -10, -2, 3, -19],
    [-31, 8, -7, -37, -36, -14, 3, -31],
    [0, 0, 0, 0, 0, 0, 0, 0]
]
...

Get the whole table scores here: Board scores

I'm not a chess expert. I took these values from the incredible chess engine Sunfish

Evaluate

Chess is a zero-sum game. (One player's advantage is equivalent to the other player's loss). There are various existing algorithms that solve ‘zero-sum' problems. Like: Negamax or Minimax

No matter the algorithm we chose, we need an evaluation function that calculates the board's positions and returns a score.

We will use this score to let the AI know which positions are good or bad.

// Idea behind evaluation function
function evaluateBoard(game: Chess) {
  const board = game.board();
  let totalEvaluation = 0;
  for (let row = 0; row < 8; row++) {
    for (let col = 0; col < 8; col++) {
      totalEvaluation += getPieceValue(board[row][col], row, col);
    }
  }
  return totalEvaluation;
}

Get the whole function: Evaluation function

Think AI, think! 🧠

I chose to implement the Minimax algorithm with Alpha-beta prunning. What do those fancy words mean?

Minimax algorithm:

A minimax algorithm[5] is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. The player then makes the move that maximizes the minimum value of the position resulting from the opponent's possible following moves.

– Wikipedia

Alpha-prunning:

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. – Wikipedia

Wow, that is awesome! but I didn't understand a single word!

I recommend watching John Levine's awesome video explaining how the Minimax algorithm with Alpha Prunning works: Minimax Explanation

In simple words: Minimax recursevily evaluates the possible moves and alpha-prunning makes it go fast*

/**
Alpha = best value for MAX
Beta = best value for MIN
Depth = depth of search
maximizingPlayer = AI
**/
type AlphaBetaReturn = [bestScore: number, bestMove: Move | null];
type AlphaBeta = {
  game: Chess;
  alpha: number;
  beta: number;
  depth: number;
  maximizingPlayer: boolean;
};

function minimax({
  game,
  alpha,
  beta,
  depth,
  maximizingPlayer,
}: AlphaBeta): AlphaBetaReturn {
  movesAnalised++;
  let bestMove: Move | null = null;
  if (depth === 0) {
    return [evaluateBoard(game), null];
  }

  const possibleMoves = game.moves({ verbose: true }) as Move[];
  // Sort randomly to avoid same moves being chosen every time
  possibleMoves.sort(() => 0.5 - Math.random());

  let maxValue = Number.NEGATIVE_INFINITY;
  let minValue = Number.POSITIVE_INFINITY;

  for (const move of possibleMoves) {
    game.move(move);

    const [childValue, _] = minimax({
      game,
      alpha,
      beta,
      depth: depth - 1,
      maximizingPlayer: !maximizingPlayer,
    });

    game.undo();

    if (maximizingPlayer) {
      if (childValue > maxValue) {
        maxValue = childValue;
        bestMove = move;
      }
      if (childValue > alpha) {
        alpha = childValue;
      }
    } else {
      if (childValue < minValue) {
        minValue = childValue;
        bestMove = move;
      }
      if (childValue < beta) {
        beta = childValue;
      }
    }

    if (alpha >= beta) {
      break;
    }
  }

  return maximizingPlayer ? [maxValue, bestMove] : [minValue, bestMove];
}

function calculateBestMove(depthLvl: number): [Move, number] {
  movesAnalised = 0;
  let alpha = Number.NEGATIVE_INFINITY;
  let beta = Number.POSITIVE_INFINITY;
  let move = chess.moves({ verbose: true })[0] as Move;

  const [bestScore, bestMove] = minimax({
    game: chess,
    alpha,
    beta,
    depth: depthLvl,
    maximizingPlayer: true,
  });

  return bestMove === null ? [move, bestScore] : [bestMove, bestScore];
}

Good to know:

There is a thing called The horizon effect, which is caused by limited depth of the search algorithm. You can further reduce it by adding quiescence search.

More humane AI 🔊

To soft things off, I added some voice audios to the AI, to make the ass whooping more fun!

type  playAudioParams  =  {
    chess: Chess;
    move: Move;
    isPlayer: boolean;
};
export  async  function  playAudioOnMove({  chess,  move,  isPlayer  }:  playAudioParams)  {
    const flags  =  move.flags  as  MOVE_FLAGS;
    const audioData  =  isPlayer  ?  defensiveAudio  :  ofensiveAudio;
    const piece  =  move.piece;

    if (chess.isCheck()) {
    const audio = new  Audio(audioData.check);
    await playAudio(audio);
    return;
    }

    if (chess.isCheckmate()) {
    const audio = new Audio(audioData.check);
    await playAudio(audio);
    return;
}

const audio = audioData[flags]?.[piece];
    if (audio) {
    await playAudio(new Audio(audio));
    }
}

function playAudio(audio: HTMLAudioElement) {
    return new Promise((res) => {
    audio.play();
    audio.onended = res;
});

Audio data schema and rest of functionality available here: source code

Outro

I encorage you to try it out and play a game here 👌❤️: Play a game

Hope you have a fun time!

UI Design: