Building Betafish

A Javascript Chess Engine & AI.

start-position.png

Betafish: a (very weak) amalgamation of Stockfish and AlphaZero. This picture was generated by DALL·E

Introduction

The Queen's Gambit was my first taste of chess. Before the show came out on Netflix, I didn't even know the rules of the game. During the pandemic, the show, combined with the growing popularity of chess live streams on Twitch, propelled chess into the limelight.

For a couple of weeks, I was hooked on the game, playing on popular sites such as chess.com and Lichess. However, I was never really good at it. The patience and practice needed to become mildly competitive in chess was too much of an investment.

So I decided to try building an AI that would be able to consistently beat me at chess. And thus, I created Betafish.

Betafish

Betafish is an amalgamation of AlphaZero and Stockfish, 2 of the most famous chess engines. I estimate its rating to be around 2000 elo, having beaten Fairy Stockfish Level 6 on Lichess.com and the 2200 elo bot on chess.com.

The searching algorithm is a conventional Negamax algorithm, searching to a depth of around 7 plies per second. (~800k nodes)

Play against it here, or check out the source code here.

Read on if you're interested to learn more about the process of building Betafish. I honestly think chess programming is an awesome project as the hidden complexity involved and satisfaction derived really kept me interested.

Initial Attempts

A great resource when I first started was this HackerNews article titled: Chess Engines: Zero to One. Following it, I made use of popular libraries such as Chess.js and Chessboard.js in order to understand what goes into a Chess AI.

You can play Version 1 here.

It was a good taste of chess programming, but faced severe limitations as it was based on a library. Chess.js was good for beginners and simple logic, but quickly became too slow in move generation and logic handling once the computations became more complex.

Implementing My Own Engine

After trying for several weeks to speed up and improve version 1, I was still getting computational speeds of around 2000 nodes per second. I reached out to Maksim Korzh, creator of the Chess Programming Youtube Channel, and sought his advice.

Using chess.js is fine for start but you're missing the whole joy of creating a chess move generator. Writing a chess engine is one of the best ways to learn how to accurately debug a program, by dividing and conquering every tiny little piece. You're trying to make it 'all at once' (like in that movie with Michele Yeoh - everything everywhere and all at once). Calming down, splitting tasks and debugging modularly helps a lot.

~ Maksim Korzh

He referred me to a couple of his tutorials and pointed me towards Bluefever Software's YouTube channel, which was how he got started.

Taking heavy reference from The Programming a Javascript Chess Engine Playlist, after around 2 weeks I had a chess engine that could process around 800k nodes per second and managed to pass all the cases in PerftSuite, which was a collection of test cases for different positions on the chessboard to check the accuracy of your engine's move generation.

Search Algorithm

There are many ways to code a Chess AI.

I went with the traditional, easier approach, which revolves around the Minimax algorithm.

The Minimax Algorithm

The Minimax Algorithm is the foundation of most traditional chess engines. Chess is a zero-sum game — by maximizing your chances of winning, you are also minimizing your opponent's chances of winning.

Let's say it's your turn to move, the minimax algorithm can look something like this:

  1. What are all my possible moves
  2. What are my opponent's possible responses to my moves
  3. Rinse and repeat until you reach a terminal node
  4. Evaluate the terminal node
  5. Evaluate the second-last node... all the way up until you find your best possible move

minimax-pic.png

Visual representation of Minimax algorithm

While this works in theory, we very quickly run into issues.

First, a game of chess can have hundreds of moves. Many games also end in draws with insufficient material, especially if both sides play perfectly. Only evaluating at a terminal game state is impractical.

Second, chess has a big branching factor. Branching factor refers to the number of children each node can have. In chess, the branching factor is an average of 35 — meaning at each turn, a player has an average number of 35 legal moves to consider. This means that at a depth of 6 (3 moves per person) after the starting position, our engine has to compute 119 MILLION MOVES.

One way to reduce the number of nodes to search is done through Alpha-Beta pruning.

Alpha-Beta Pruning

Alpha-Beta pruning is a way to trim the search tree. By keeping track of good moves, it cuts off branches in the tree that don't have to be searched because there already exists a better move. The difference can be dramatic, reducing the number of nodes that have to be searched by over a factor of 10, but is highly dependent on which moves are searched first.

But Alpha-Beta pruning only cuts down on search time if we search the best nodes first. For example, if the best variation is the last path the algorithm searches, we wouldn't be able to trim any branches.

Evaluation Function

A central component in the minimax algorithm is an evaluation() function. This is a function that takes the current state of the board and returns a score. Essentially, it's a way for the computer to tell if a certain position is favourable or not. For example, +100 means that white is winning, while -100 will mean that black is winning.

Sounds easy... but what's winning? How do we quantify whether a position is winning or losing?

Well, one very simple way of doing that will be counting all the pieces. If white has more pieces, white is winning.

Then we also factor in the weight of pieces. A Queen is worth a lot more than a pawn in most cases.

Using this, our engine will start to try and hang on to its material and look for favourable trades.

Piece-Square Tables

Simply evaluating material score is not enough for an evaluation function. Currently, our program doesn't know anything about positioning, a fundamental part of chess, and thus resorts to repetitive moves as it weighs all moves equally when it's not under threat.

This is where Piece Square Tables come in.

As the saying goes: "Knights on the rim are grim" — positions are not made equal. A rook on the second last rank is doing a lot more than a rook in its starting square. A knight wants to be on the centre of the board, where it can exert the most amount of pressure of the board.

By making use of Piece Square Tables, we weigh squares differently, and coax our pieces onto more traditionally better squares.

// Knights are encouraged to go to the middle of the board
// prettier-ignore
const knight_pst = [
  -50,-40,-30,-30,-30,-30,-40,-50,
  -40,-20,  0,  0,  0,  0,-20,-40,
  -30,  0, 10, 15, 15, 10,  0,-30,
  -30,  5, 15, 20, 20, 15,  5,-30,
  -30,  0, 15, 20, 20, 15,  0,-30,
  -30,  5, 10, 15, 15, 10,  5,-30,
  -40,-20,  0,  5,  5,  0,-20,-40,
  -50,-40,-30,-30,-30,-30,-40,-50
]

Tapered Evaluation

An improvement to a simple evaluation function is a tapered evaluation function. During different stages of the game, we want our pieces to be placed differently. For example, during the midgame, we want our King castled and safely behind pawns. But, once the endgame starts, we want our King to be actively involved and more central in the board.

By having 2 sets of Piece-Square tables, one for the middlegame and one for the endgame, we can interpolate between the 2 to get a more accurate state of the board.

Move-Ordering

To optimize our alpha-beta pruning, we want to put the best possible moves first. This increases our chances of pruning more branches and saving more time.

So what constitutes a good move?

Promotions: Promotions are good, we can look at them first. Captures: Captures are good, we should prioritize them. Checks: Checks are often beneficial as well.

We also want to order captures. A pawn taking a Queen is likely to be extremely good, while a knight taking a knight can be considered later. This is called MVV-LVA (Most Valuable Victim, Least Valuable Attacker)

Quiescence Search

At this point, our engine is faster. However, our current search algorithm is a fixed-depth. That leads to something called the Horizon Effect.

For example: imagine we are on our terminal depth and we capture a pawn with our Queen. Since we only check up to this depth, we evaluate that position to be winning for us — after all, the material advantage is now in our favour.

But, if we go one move deeper, we can see that our Queen can be taken by the opponents' pawn.

This problem leads to quirky variations where your engine blunders pieces because it doesn't look far enough.

As always, this problem can be solved by increasing the search depth. However, this time we do a specific form of it called the Quiescence Search — we search the board until its "quiet".

betafish_2022-10-09-12-42-37.png

We search certain lines deeper than others in Quiescence search.

A quiet board

A quiet board is one that has no captures, no checks and no promotions left to play.

Iterative Deepening

Most Minimax algorithms calculate up to a fixed depth. However, this isn't always ideal. Depending on the board state, a calculation of up to depth 5 can take drastically different times. Instead, we use something called Iterative Deepening, where we allocate a fixed amount of time and let the engine search till time runs out.

let time = 1 second
function search() {
  for (let i; i++; i<MAXDEPTH) {
    if (time.up) break
    else {
      minimax(alpha,beta,depth)
    }
  }
}

So first we search to a depth of 1, we check if time is up. No? Search to depth 2, etc...

This may seem inefficient, as compared to searching to a depth of 6 straight away, we first have to search depth 1, then 2... all the way back up to 6, which seems like we're wasting time calculating the same positions. To solve this, we store information about our previous searches and use it to make our subsequent searches faster.

Principal Variation Search

By storing the best moves from each previous branch, the time taken to calculate up to a deeper depth is reduced as we can search these lines straight away and reach our beta-cutoffs faster.

Conclusion & Future Improvements

Opening Book - I'd like to add a opening book as currently the AI does the same moves in response each time. An opening book would add more variety and allow more variation in the game.

Rewrite in compiled language - Rewriting Betafish in something like C++ or Rust seems like it'd be a great way to learn a new language and get major performance improvements.

UCL Interface - Universal Chess language support would allow me to deploy Betafish on sites like Lichess to test against other engines.

Transposition Tables - Would greatly speed up the search, but Javascript isn't really suited for it due to the lack of typing.

Ok but for now I've already spent wayyy too long on this and I'm gonna call this stable for now.

References