Chess Engines: A Zero to One

Chess Engines: A Zero to One

♟️
This a guide on how to build a Chess engine from scratch, updated periodically as I further explore the space. This assumes some basic knowledge of Chess, search algorithms, and coding. Want to know how chess engines work? Or how AI is now better than every human on earth in chess? Or maybe how you can beat your younger brother who is stupidly good at chess? This is the place.
👋
This is getting a lot more traffic than I thought it would! This is one of my weekly projects, so if you like it, consider following me on Twitter to get updates when I release something new. - Thanks, Will DePue.
Color Key

bold and red means it’s something you should do

“bold, blue, and in quotes” means a new important topic.

underlined means it’s a key point

this means it’s an even more important point

this means code

Setting up your space

Before you start on your engine, you need a board representation and some form of visualization. I’ve chosen Chess.js and Chessboard.js to start.

Of course, you could build this yourself, but that isn’t really the point of this project. If you’re interested in learning about chess engine board representations, lookup “bitboards” and go from there - lots of interesting ways move generation and board state can be handled with maximum efficiency.

In looking for a good library to work in, I found the Chess.js package. This is a great place to start. It handles all move generation, board state, FEN notation (will get to that in a sec if you don’t know what that is), etc.

I do most of my work in Javascript, so this is perfect for me. Super simple (not the fastest) but great for speed and learning fast. Lots of space to mess around, though I’d recommend porting to a strongly typed and compiled language once you start optimizing for performance.

Even if you don’t code in Javascript I would heavily recommend using chess.js, because of it’s super quick implementation with chessboard.js, a HTML chessboard representation.

These hook together so well it’s unbelievable. Being able to publish a website with your chess engine live in the browser is awesome. Here’s a link to a super simple starter repo you can download and run right now, which you’ll be able to follow along with the whole time.

👆 Download and run this, it’ll load up what we’re starting with.

Starting up…

It’s important to start with a good baseline, so we’ll start with an engine that only makes random legal moves. Yeah, it’s dumb, but it’s a great starting point for the rest of the project.

If you download the above repo, you’ll see this. All it does is generate random moves for each player. Run this code! Boom, we have our first engine.

var board = null
var game = new Chess()

function makeRandomMove () {
	// chess.js gives us all the possible moves in an array
	// [ move1, move2, move3 ... ]
  var possibleMoves = game.moves()

  // exit if the game is over
  if (game.game_over()) return

	// choses a random index in the list  
  var randomIdx = Math.floor(Math.random() * possibleMoves.length)

	// updates javascript board state 
  game.move(possibleMoves[randomIdx])

	// changes html board state
  board.position(game.fen())

	// call this function again in 5 secs
  window.setTimeout(makeRandomMove, 500)
}

board = Chessboard('myBoard', 'start')

window.setTimeout(makeRandomMove, 500)
Here Chess.js is helping us by generating all the legal moves at every point in the game, we just pick one randomly out of the hat.

Okay let’s make it smarter…

Now that we have a bot that makes random moves, let’s make it a bit better. Every time we call game.moves() it loads an array of moves, and actually shows us which ones are captures. Captures are good right? Why don’t we just do more of those?

Strategy #1: Let’s filter for moves that have a capture in them. If none exist, we can just choose a random move.

We can tell which moves are captures because they have a lower case x in them. Here, the one capture move is Qxb6, which tells us it’s a move where our Queen takes the piece on b6.

['a3', 'Qxb6', 'b3', 'b4', 'c3', 'c4', 'd3', 'd4', 'e3', 'e4',
//     'f3', 'f4', 'g3', 'g4', 'h3', 'h4', 'Na3', 'Nc3', 'Nf3', 'Nh3']

These moves are in a format called algebraic notation”. A couple tips about algebraic notation:

  • The last two characters stand for what position on
  • If it’s only two characters (’a3’ for example) it’s a pawn move!
  • If it has more (like ‘Nf3’) it means it’s a piece moving.
    • The codes are Q for queen, R for rook, B for bishop, K for king, and N for knight (since K is taken).

There’s more to algebraic notation but just remember that the piece comes first, then the square. You can read more here:

Try building an engine that only makes captures. Compare it against our previous random move engine.

You might also want to build into your bot the ability for human players to play against the engine, so you can test different moves. Just call different code depending on who is black or white: https://chessboardjs.com/examples#5001

⚠️
P.S: I’m not going to provide implementations of my work, because I think it hurts other people’s ability to learn - try to implement what I’m talking about yourself 🙂

Measuring performance

But wait…. how do we know how we’re doing?

Well at the end of the game, we can print something called a “PGN”. It’s basically a list of all the moves that happened in a row. For example, here’s a full game PGN.


1.Nf3 Nf6 2.c4 g6 3.Nc3 Bg7 4.d4 O-O 5.Bf4 d5 6.Qb3 dxc4 7.Qxc4 c6 8.e4 Nbd7 9.Rd1 Nb6 10.Qc5 Bg4 11.Bg5 Na4 12.Qa3 Nxc3 13.bxc3 Nxe4 14.Bxe7 Qb6 15.Bc4 Nxc3 16.Bc5 Rfe8+ 17.Kf1 Be6 18.Bxb6 Bxc4+ 19.Kg1 Ne2+ 20.Kf1 Nxd4+ 21.Kg1 Ne2+ 22.Kf1 Nc3+ 23.Kg1 axb6 24.Qb4 Ra4 25.Qxb6 Nxd1 26.h3 Rxa2 27.Kh2 Nxf2 28.Re1 Rxe1 29.Qd8+ Bf8 30.Nxe1 Bd5 31.Nf3 Ne4 32.Qb8 b5 33.h4 h5 34.Ne5 Kg7 35.Kg1 Bc5+ 36.Kf1 Ng3+ 37.Ke1 Bb4+ 38.Kd1 Bb3+ 39.Kc1 Ne2+ 40.Kb1 Nc3+ 41.Kc1 Rc2# 0-1

You can take a PGN like this and plug it into a chess analysis tool, like Chess.com’s analysis tool. This comes in handy for stepping through the game + it also tells you how well each opponent did against each other. We can now walk through the game and use Chess.com’s analysis to see how good each move was.

Go to chess.com/analysis, then click Paste FEN/PGNs, and paste in the above moves! I wont go into the evaluation bar or how chess scoring works here, but you should look that up, since it’ll help you understand your engine’s strength.

Now when you run your new engine, print out the PGN to the console and copy it to chess.com. You can call chess.pgn() and print the PGN to the console.

Another important idea to know about is “Forsyth-Edwards Notation” which is a way to represent a position in chess, rather than a game of a sequence of moves, in a single string. They look like this: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Low effort explanation: If you read left to right as each row top to bottom (marked by a / ), and black pieces are lowercase and white uppercase. The stuff on the right stores state info like who’s turn it is, castling, etc.

The way to read these is a tad bit unintuitive, just know this is a position in chess. You can read more below, but the important thing to remember is that the PGN is a sequence of moves from some position that describe a game, while the FEN represents an exact layout of pieces.

With this data, you now can take your order of moves or a certain weird position where your bot messed up in and feed it to any machine or give it to someone else to mess around with. Trust me, it’s super helpful when your machine is blundering for some ungodly reason and you need to keep replaying the same thing over and over.

Ok… back to our engine playing the random bot.

If we only ever make capture moves, we actually do pretty well - the random bot doesn’t really take back our pieces super often, so if we take his pawn with our queen, it doesn’t really mind.

The problem is that our engine has no clue how to make a checkmate and we trade away our pieces until it’s a stalemate. Now we could choose to make a bot that sees checkmate moves and prioritizes those (they’re actually marked by # signs in algebraic notation, like Rg4# or Rook to g4 checkmate), but that’s dumb, we can get a whole lot better than this.

Minimizing the maximum

Try it yourself: Sit down for a moment with paper and pencil and write down some ideas on how to build an engine. For real, try to do this without reading ahead, this a great opportunity to wrestle a hard problem.

The first thing to remember is the limits of hard-coding: even if we wrote down all the ways to not mess up (don't throw away pieces) remember that many aren’t universal laws. The best grandmasters and bots frequently gambit pieces and break rules in complicated situations. Sometimes losing your Queen by taking a pawn is a great move.

If you guessed we need to use a form of tree search, you guessed right.

If you have no experience with search algorithms, this may be hard to understand. Try watching this video if you’re a beginner (or need some review):

We need to look into the future to see what the best move to make is. We can’t just take every piece we see and not think about what will happen next. Our engine must understand that taking a defended pawn with our Queen is bad because the next move they’ll probably make is take our Queen back.

When it comes to looking through all possible sequences of moves, it’s not going to be super simple. We can’t just look all the way down for the best position in the future which has us winning the most, then make that move. Imagine a possible move order:

I take your defended pawn with my queen, you blunder your rook, then I checkmate you.

That seems like a great scenario for us, right? 🎉  Since we end up winning, so why don’t we pursue that direction? Well… the other player probably isn’t going to blunder their rook, they’ll likely just take back our queen with their pawn and we’ll be losing.

This leads to the important realization: in order to choose the best possible move, we have to consider the game from our opponents perspective. We have to assume the other player is going to choose the best response to our move. It’s somewhat unintuitive to how humans play games (sometimes with tricks and hoping to slide by unnoticed), but the best strategy is assuming that they always respond with the best possible move against us.

image

This is called the minimization-maximization algorithm: we look through all sequences of moves and assume that each player tries to screw the other player over maximally at each step. If both players are perfect, what’s the best strategy? The best move is the one where our opponent can screw us over the least.

Let’s walk this through with Tic-Tac-Toe:

image

Okay, looks kind of confusing. We start at the top at move #1. It’s our turn, so we decide what move we make and where the future can go.

Let’s say we choose to make the middle move, move #3: we put our square in the top middle slot and now it’s our opponent’s turn.

You can see they have two choices, move #5 and move #6. In one of them, she can place in the middle and win, and in the other, she can choose to place on the right middle and in the next move, we win.

In order to make the best move, we have to assume that our opponent will choose the move that inconveniences us the most. They’ll probably choose move #5 and we’ll lose the game.

Okay, we now know this is a bad direction to take the game in. In this situation we’ve marked wins as +10 pts and losses as -10 pts, so making move #3 has the equivalent value of -10 pts, since we know our opponent will choose that option.

image
image

How about the right option, move #4?

Same situation as before, our opponent has the choice between two moves, one which results in a win for them immediately, and one where we win in the next move.

We assume that they will try to screw us over, which means they’ll choose the -10 pts option, the smallest one. Here they are minimizing the score for themselves.

We can mark move #4 as also causing the score of -10 pts.

Finally, let’s check out move #2.

Looks like we win if we make move #2. This ends the game, and we get a score of +10 points for this move.

Remember, if there were a move that resulted in immediate loss, we would choose between a -10 pts and +10 pts option, and we’d obviously chose the move in which we win, the larger of the two point options. We’re the maximizing player here, since we always will choose the move which benefits us the most.

image

Okay so we have three moves, two that result in -10, one that results in +10. Since we want to win, we’ll choose the move that nets us the most points, and make move #2.

I hope this gives a better grasp of how mini-max works. Each player chooses the option that benefits them, one always trying to make the score more positive (maximizing) or more negative (minimizing).

Clarification: Which side is positive or negative is arbitrary, all that matters is that each player’s score is opposite the others, this way your enemy always chooses the move that hurts your score the most. In Chess it’s normal to make white the maximizing player (+10 means white is up 10 points) and black the minimizing (-10 means black is up 10 points).

Time to implement.

Try to implement mini-max. It’s not an easy challenge, so no fault if you go and look up how people have done it, but I’d recommend messing around with it for 30 minutes.

Some tips:

Limit your search In the above example, we search down moves until the game ends. This isn’t possible in chess, since you might need to search down 50 moves to get to a terminal state, so you should choose a point at which you’ll stop and evaluate the board.

Evaluation functions: just subtract pieces I’ll talk about about evaluation functions in the next section but a decent algorithm is to add up all the pieces on the board by points and see who has more. The normal piece weights are that pawns are worth 1 point, knights and bishops are 3 pts, rooks are 5 pts, the queen is 8 pts, and the king is worth 10000pts (since you lose without it). Add each side’s points and subtract them to get who’s winning.

When to evaluate We only care about the state of the game once we reach a terminal node. In simpler terms, we don’t care who looks like they’re winning, we only care who’s winning once we reach the end or stop looking. This is important: you’re searching down all possible paths to a certain “depth” or “ply” (the number of moves you look into the future before you stop and evaluate) and then evaluating the state of the game.

Choosing the best move Once you reach the end for each path, you can compare them to each other and move all the way up the tree you’ve built to choose the best move. Not to give too much away on how to build this, but here’s a visualization. Remember that the maximizing player chooses the highest option, while the minimizing chooses the lowest.

image

Don’t get stuck There’s some issues with mini-max that we’re about to get to, so don’t get stuck on tiny ways that this might end up choosing badly. This algorithm is going to crush your last two, don’t worry.

We aren’t very good…

So we’re still blundering pieces.

Why did my engine just take a pawn with a queen? Why is this happening? Weren’t we supposed to be avoiding this with our new algorithm? - You, probably

Okay, so there’s an issue: by putting a limit on how far we can look into the future we’re occasionally blind to trades.

If I take your pawn with my queen on the 5th move, and I can only look 5 moves into the future, I evaluate the position as if it were done. I’m completely blind to the fact that in the next move I lose my queen and potentially losing me the game.

This is called the “horizon issue”: we’re blind to anything beyond the horizon of how far we can look. This is a tough one, since it doesn’t matter how far we look. Even if we looked 50 moves down if there’s something big that happens on the 51st move, we’ll miss it.

How do you think we solve this? Try to figure it out.

This is a fun one: try to think for 15 minutes on your own.

Don’t look ahead and rob yourself of a challenge.

I’m not kidding…

Don’t keep scrolling…

Did you think about it yet?

Okay last chance.

Solving the horizon issue

The solution is to extend our search until we’re positive that there aren’t any surprises lurking ahead of us. This is called “quiescence search”.

We do this by calling a board “quiet” when it no longer has any available captures (or checks, if you want to include that). When you reach the end of your search and the board isn’t quiet, play out all captures until the board is quiet.

This is done by continuing your minimax search, except with only moves you consider to be “loud moves”. For example, if we reach a terminal node and we have 3 captures on the board still: Rxb4, Bxh7, Qxa7 we simulate each, then re-evaluate to see if they’re quiet. Let’s say Bxh7, Qxa7 are quiet (don’t have any further captures available) after we make our move, but Rxb4 isn’t. We search all of the captures at the state of the board after Rxb4… and so on.

When you finish and begin to collapse all searches upwards, simply treat these capture chains as replacing the starting terminal node. This majorly works, but creates a small issue - can you catch it?

image

Even though quiescence searches looks through far fewer moves than our normal search, it’ll still account for 50% to 90% of search time in terms of nodes search. Ouch. This is due to quiescence beginning at the deepest level of the tree: adding a couple searches to each branch at the bottom is very significant.

We aren’t forced to capture:

Quiescence has an issue…

In most even positions, you have pieces that are lined up and aimed at each other (like the position below). Both of the players have the option to capture and are choosing not to: if either person decides to capture, the other will capture back and it’ll be even.

image

It makes sense here to evaluate this position by trading away all the pieces and then checking the score. Because our engine isn’t good at pattern recognition as us, it’s usually a good measure for it to trade all the pieces and then check the state of the game to be sure. It doesn’t know when it might be about to blunder or when it’s just in a position with a lot of pieces aimed at each other.

The issue here is that by replacing the terminal node, it makes the assumption that if the board isn’t quiet, you must make a capture. It only evaluates possible futures after making chains of captures, even though either player can choose not to take.

Imagine if the situation above implied that your opponent taking your pawn was good for you but taking his pawn would result in you losing. If choosing to make any capture is a mistake, any move, even not moving at all would be better. Quiescence thinks you have to take.

There could be situations in which all captures/trade lines are bad for you and it would be far better to avoid making them, instead opting for a small developing move or useless pawn move.

Since quiescence search replaces this position only with the available capture lines, it would think this position was far worse that it is, since it’s only evaluating futures where you trade down all the pieces and must end up taking his pawn.

Here’s a more obvious example of this. It’s black’s turn to play and he’s evaluating this position using quiescence:

This board is inverted lol.
This board is inverted lol.

There is only one move here that’s a capture for black, taking the center pawn.

Obviously a bad move.

A human player will just not take at all, choosing to develop his position further elsewhere (maybe shifting your king or repositioning the rook), but not our algorithm:

If it only evaluates positions that involve captures, it thinks that here we’ll be down 4 points after losing our rook for a pawn.

How do consider not capturing in code?

We include the the possibility of doing nothing into our calculations with “null move proving.”

As we collapse quiescence moves, assume chess includes an option to pass on your turn, maintaining the evaluation at the parent terminal node. This is just a good substitute, since we don’t need to find a random useless pawn move to compare to the quiescence lines, we just assume it exists and has no effect on the game.

In this position, we wouldn’t evaluate this to being down a rook, since we assume that there exists at least one other non-capturing move. Problem solved!

* The Zugzwang

My younger brother has pestered me at length the idea of the Zugzwang, the situation in which the fact that you are forced to make a move is a serious disadvantage.

image

This game begins in a position where it’s white’s turn to play, yet all available moves force him to move away from his pawn, allowing black to take it in the next move.

Null-move pruning makes the assumption that there will always be a move elsewhere, when obviously, that is not true here.

Our engine will assume this position is better than it truly is.

Imagine having a situation in which you’re in a solidified position but since you must make a move, you have to seriously break up your pieces.

There’s a lot edge-case positions where any move is a bad one, and null move pruning can create issues since it assumes there is a move that will have negligible on the game. But honestly, that’s pretty complicated and our bot isn’t even close to being smart enough to care about that.

It’s too slow

So…. uhhhh… we can’t search very far.

This is because the average # of available moves per turn is about 31.

This means to look two moves down, you’ll have to look through 31 of your own possible moves and then look at 31 ways your opponent could respond for each. Every time we look down one more move we take 31x longer.

How do we fix this?

A
A cool graph of the average # of moves available over time.

Branching factor

By the way, the number of average available moves is called the “branching factor” of a game. Tic-Tac-Toe has a branching factor of 4, which means on average you’re considering 4 moves each turn. The game of Go took so long to beat because its branching factor is around 250.

How do we fix this?

How are we supposed to be any good at chess if we can barely look a couple moves into the future? Well you’re never going to avoid the exponential nature of this type of search, but we can get a whole lot smarter in restricting the number of moves we consider each turn.

Instead of considering every possible move we can make in a position (around 31 moves), what if we only considered the ones that were potentially interesting. Good human chess players only think about a handful possible moves in any position, far less than 31. You can’t change the exponent, but we can significantly reduce the base.

Reducing the base

💡
This also is a hard problem, and once again I’d suggest that you try this one on your own. It’s not very easy, since there are a lot of traps in thinking through the problem.

Ok, so how do we eliminate considering moves?

For one, just because a move is dangerous, like trading a queen for a pawn, it doesn’t mean we shouldn’t consider it. There are lots of checkmate patterns that involve dangerous trades like these. While we could increase a degree of pessimism in the way we evaluate dangerous positions, this isn’t a mathematical solution.

The most applicable solution (there are many) to this problem is called “alpha-beta pruning”, and is fairly complicated. With alpha-beta pruning, we can skip entire sections of our search tree with no impact to our results. Time for more diagrams:

image

A short explanation

As I search through possible moves, I can set a baseline for the best option I’ve found so far, which allows me to eliminate other moves as soon as I realize that they will already be worse than something I found already.

A weird short explanation

Keep track of how much your opponent can screw you over. If you’re going through a new move and see that it gives your opponent an opportunity to screw you over even more than before, you can stop immediately.

A long-winded explanation:

Imagine I’ve already searched the possible implications of a specific move and that regardless of what my opponent does after I make that move, I’ll end with a +3 score. If I explore another move, and as I’m searching through my opponents possible moves, I see that there is a potential response that will result in me ending with a +2 score, I can immediately stop any further search into making this move: I already know I have a better option elsewhere.

How to read the diagram:

Nodes with the blue background are the maximizing player, who always chooses the highest option. Nodes with the yellow background are the minimizing player, who always chooses the lowest option.

image

This graph shows our search algorithms with the first moves we evaluate starting on the left. Let’s start there to get how this works.

We first go all the way down the left.

We examine our first leftmost node, a 5. There’s nothing to do here, as this is the first move we’ve ever seen.

We then move back up to the parent node (marked with a 5 and a yellow background) and try the next move, which we evaluate to a score of 6.

It seems we’re out of nodes to explore in this parent, so as the minimizing player (shown in yellow) we mark the parent node as having a score of 5, the score of the best option.

We then move up even further up the tree, where we’re evaluating from the maximizing player’s perspective.

As the maximizing player (blue) we know that at worst, we can make the move that results in at least a 5 here. We’re going to keep looking for better options but we can always go back to that.

We now look down to the right, where we’ll go back to looking from the minimizing player’s perspective.

The first possible move here leads us to a 7, which looks great for the maximizing player. Remember though, the minimizing player will be choosing, and they’ll choose the best move for them and the worst for the maximizing.

image

Oh crap, the next move is a 4. We know the minimizing player will at best choose this move or at worst one that we find later that’s worse.

As the maximizing player we can now give up looking at this area, since it doesn’t matter what we find next: it’ll always be smarter to go with the option on the left. There’s no reason to look at other moves (which is the 5 marked in grey).

Important point: We could always explore the grey areas, however, it’s useless, since we already know that the minimizing player will choose a move that’s at most 4. The maximizing player, knowing that, will choose to go left, never right. We can quit and keep looking at other moves.

Where is Alpha-Beta Pruning efficient?

At the lower layers, like above, it’s not too big a deal to prune a branch. We only stopped ourselves from visiting an extra node or two. However, at the top, pruning means we can skip visiting entire sections of the tree

It’s also incredibly valuable to look at the best moves first. For example, if we first examine a move that results in us winning our opponents queen (+8 score for us), we can eliminate our other moves after only searching through a small percentage of the move tree. Any other move where our opponent has an option to avoid losing their queen is worse, we can quit.

image

See below how if we had reordered the branches, we would have first seen a potential future which resulted in a +6 score, then almost immediately pruned the next tree. We’re 25% faster!

Unordered, random move orders.

image

Optimally ordered moves

The right move will always be worse than the left.
The right move will always be worse than the left.

It’s very likely that my explanation here doesn’t work for you, so here are some good places to read/watch. In my opinion, this is the best video out there:

Time to implement.

Try to implement alpha beta pruning! This is a pretty hard one.

Spend at least a couple minutes trying to figure out how this would work, but there’s no fault in searching for examples of alpha beta pruning. It’s not the most intuitive to implement.

Some important helpful pointers if you’re going alone:

Alpha-beta pruning happens “between two layers” The top layer maintains a memory of the “best move I’ve seen so far” and the layer below is iterating through possible moves, cutting off if it finds worse possibilities. The bottom layer iterations can quit as soon as they know that their enemy will never go in that direction.

It’s only about limiting computation There’s no changes to the way that moves are calculated and selected, alpha beta pruning only changes when you can stop searching and limit computation in a certain direction.

A final hint… There is a relationship between each layer’s best move value that can help you create cutoffs. Trying to not give too much away. Know that the implementation has an elegant solution.

Ok done, what next?

Move ordering!

There are a lot of ways you can implement move ordering. So many, in fact, that I probably couldn’t fit them all in this article. But here’s a good starting place:

A promotion of a piece is usually better than most else. Captures cause a cut-off more than non-captures. So prioritize looking at captures: You can sort captures by the chance they will be good: - A weak piece taking a strong piece is usually good. (A pawn taking a queen) - An equal piece taking an equal piece is usually neutral. (A knight taking a knight) - A strong piece taking a weak piece is rarely good. (A queen taking a pawn)

There’s so many strategies out there, so go research and explore! Also, make sure that your move ordering isn’t too inefficient 🙂

Evaluation functions

We glossed over evaluation functions earlier, mostly because just subtracting all piece values from each side works surprisingly well for a while. It could be time to start considering positional, not just material advantage.

Here’s an example of piece square tables, a way to encourage moves in move ordering or in board evaluation towards positions where your pieces are in smarter areas. Nobody wants to see their knights on the edge of the board.

image

As with before, there’s so many directions you can go in here. There’s tons of resources out there for chess evaluation functions and the different strategies you can take - it’s more open-ended than you think.

Oh how far we’ve come…

We’ve covered a lot, so much, in fact, that it’s hard to choose what to talk about next.

MiniMax search with Quiescence search and Alpha-Beta pruning is the foundation on which most chess engines are built. There’s tons of incredible directions you can head in from here.

This is also the point where I’d consider quitting Javascript as a language. The efficiency and speed of your engine is what decides its strength, Javascript is not built for either. I rebuilt my engine in Golang, a strongly typed language with some cool functionality around concurrency.

I’ve built this engine, from scratch, in Golang as well. This repository includes 20+ engines, allowing you to watch as we go from the simplest possible engine to the most advanced. Would recommend checking it out (it’s a lot faster than Javascript haha)!

It’s also very likely that you’re already moving forward in a specific direction that you’re excited about, and if so, go do that. Come back here later, just go build. If not, that’s fine too, we’re going to go into the last few important new improvements to your engine.

The biggest is…

Your engine has no time restraint

Very likely, your engine just keeps running and running until it finishes it’s given depth. Sometimes it can take forever and sometimes it finishes way too fast. If we’re going to play actual humans, we need to stick to a reasonable time control.

The simplest solution is called iterative deepening:

  1. Start by only looking 1 move into the future + quiescence.
  2. Check if time has ran out.
  3. Look one move deeper.
  4. Go back to step 2.

We just keep searching deeper and deeper until time runs out. This way we’ll always have an answer ready and can stick to a certain time limit. Problem solved, right?

Unfortunately no, this makes us much worse. We’ll just end up searching the same nodes over and over again as we go deeper, wasting precious computation time.

Instead of having time to search all the way to depth 4, I have to search depth 1, depth 2, then depth 3 and then run out of time - You

Yes, and here’s where 🌈 hashing 🌈 comes in. Hashing is amazing. Let’s get started.

Saving our work

To prevent us from wasting our work when we’re running iterative deepening, we can build transposition/hashing tables. This way, we save all the computation we did at each game state so we can retrieve it once we start again.

Even further, we want to make sure that we never evaluate the same node twice. It shouldn’t matter whether we arrive at a position in two different ways →

To start, we need a hashing algorithm. If you don’t know what a hashing algorithm is, it’s a way to turn our chessboard state into something we can use to access our saved work.

It shouldn’t matter whether we arrive at a position in two different ways.
It shouldn’t matter whether we arrive at a position in two different ways.
image

You could use a FEN string (rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1) to save information at each state, since FEN strings accurately represent a game state, but that’s not the greatest idea.

This doesn’t work: Using strings as hash keys is inefficient + FEN strings store information about the number of moves played, which we don’t care about.

We’d prefer to use an integer as a hash key (for efficiency) so we’ll need a way to convert a chessboard state into a unique large number. The most popular way to do this is through Zobrist hashing.

image

Each square on the board stores 12 unique random numbers.

These 12 unique random numbers are for the 12 different pieces: 6 types of pieces (king, queen, rook, bishop, knight, pawn) and 2 colors (white and black).

If you take every piece on the board, grab the corresponding random number for that square, and use an XOR bit operation, you can generate a random bitstring.

Include a starter random number depending on who’s turn to move it is at the board state.

It really doesn’t matter that you know why this works, but I’ll explain it anyways a bit.

Two random numbers, let’s say 54 and 43, have a bit representation that looks like this: 110110 and 101011. If we XOR them together (an XOR combines two bitstrings, read more here), we’ll get 010101. We can convert that result back into a number to get 21, which would be our Zobrist key. This works because we’re combining as many numbers as pieces on the board and each one is 128 bits long, generating a unique number for each position.

The math for how unique this bitstring is, hash conflicts, etc. is pretty complicated and very math heavy. Feel free to research more into hashing algorithms!

Awesome!

Now we can convert our chessboard to a unique hash key and use this to store data. Up to you what you want to use (remember that this might end up taking a lot of memory as you scale up).

Overall, it’s most helpful to:

  1. Keep the best move in a position to help with move ordering.
  2. The bounds of the previous search + the depth it was explored at. This way, if you search a position and found it’s already been explored at a similar or larger depth, you can just use the stored value rather than re-searching.
{
	depth_explored_at: ?,
	best_move: ?
	cut_off: ?
}

That’s all for now folks!

If you implement all of this, your engine should be rated > 1000 ELO, probably more!

I had to stop building my engine because of how much time and effort it was soaking up, but I’ll be back soon with more. Be sure to check back here soon :)

If you would like to support me, drop me a follow on Twitter to get updates every time I launch something awesome like this.

I want to go deeper!

Great! I’ve also built Antikythera, an engine written in Golang that implements all of these techniques with far more efficiency. To make this as understandable as possible, I built 20+ different engines, each one with an increasing level of complexity compared to the last, allowing you to slowly ramp up your understanding.

Other resources

If any of this didn’t fully make sense, check some other tutorials and articles:

Amazing video which explains tons about Minimax and Go

ChessProgramming.org is amazing and holds a great amount of information.

I found this far too long into this process, this guy explains things super well. Check this out:

This is another good overview of how to build a Chess engine, but more technical

A shorter but also well-explained guide:

Other topics

Parallel Processing

You can massively speed up computation by running things in parralel, though it may prove technically very difficult. Check out YBW and other methods of building parralel minimax algorithms.

Opening Books

It’s taken humans a very long time to come up with the optimal ways to play the openings, it’s hard to reconstruct them on the fly. You can integrate an opening book so your engine knows the best lines to respond with in certain positions.

These are widely available and can be simply integrated. Big brain.

Monte-Carlo Tree Search

This is a type of search that was used in many of DeepMind’s models, specifically to build AlphaGo which beat Lee Sedol. It’s truly fascinating and is also applicable to chess, though just less so.

MCTS is a way to statistically calculate the value of positions using random sampling and probability. If you give it enough time, it converges on the same ground evaluation as minimax search does, just differently.

It’s really good at games where there are super large branching factors like Go and not great at games with many “trap states” like Chess (where blundering is easy and straightforward). Still, you can implement it for Chess and achieve some incredible things 😀

Here’s a great paper on MCTS and its uses:

Relevant:

Endgames

Endgames are be coded differently (we didn’t get to talk about them) since the way we act as a player changes towards the end. Read more here:

Draw Detection

You probably don’t want to ever lose because of a draw. Self-explanatory.

Tablebases

Essentially, all endgames with less than 8 pieces is already solved. You can use this to make your engine play perfectly at that point.

“By 2005, all chess positions with up to six pieces had been solved. By August 2012, tablebases had solved chess for almost every position with up to seven pieces” - Wikipedia

Pondering

“Anticipate opponents move and search on their clock.”

Sounds cool right? It’s called pondering to think on your opponent’s time.

Null-Window Searches

Null-Window Searches involve having a good guess of the current evaluation in order to more quickly create a bound on where we should be looking.

From Wikipedia:

A "zero-window" search is an alphabeta search whose upper and lower bounds are identical, or differ by one unit, so that the return value is guaranteed to fall outside the bound(s) (or in an exceptionally lucky case, be equal to the bound). MTD(f) derives its efficiency by only performing zero-window alpha-beta searches, with a previously determined "good" bound (i.e. beta). In MTD(f), AlphaBeta fails high or low, returning a lower bound or an upper bound on the minimax value, respectively. Zero-window calls cause more cutoffs, but return less information - only a bound on the minimax value. To find the minimax value, MTD(f) calls AlphaBeta a number of times, converging towards it and eventually finding the exact value. A transposition table stores and retrieves the previously searched portions of the tree in memory to reduce the overhead of re-exploring parts of the search tree

In easier terms, we’re using our guess as the starting alpha and beta value, rather than -infinity and positive infinity.

This means you create tons of cutoffs, and likely get back a value that fails above or below your guess. The value that you get back is your new starting guess, while your old guess is the lower or upper bound, depending on whether the value you got back was higher or lower. You keep doing this until you converge on your own guess.

I don’t fully understand it, honestly, but they can make engines a whole lot more powerful.

PVS

This involves saving the previous path of search, called the principal variation. Principal variation uses the assumption that the chances are that this path is one of the best, and tries to confirm that.

image

From the wiki:

In most of the nodes we need just a bound, proving that a move is unacceptable for us or for the opponent, and not the exact score. This is needed only in so-called principal variation - a sequence of moves acceptable for both players (i.e. not causing a beta-cutoff anywhere in the path) which is expected to propagate down to the root. If a lower-depth search has already established such a sequence, finding a series of moves whose value is greater than alpha but lower than beta throughout the entire branch, the chances are that deviating from it will do us no good. So in a PV-node only the first move (the one which is deemed best by the previous iteration of an iterative deepening framework) is searched in the full window in order to establish the expected node value.

When we already have a PV-move (defined as the move that raised alpha in a PV-node) we assume we are going to stick with it. To confirm our belief, a null- or zero window search centered around alpha is conducted to test if a new move can be better. If so, with respect to the null window but not with respect to the full window, we have to do a re-search with the full normal window. Since null window searches are cheaper, with a good move ordering we expect to save about 10% of a search effort.

Razoring

This is mentioned a lot of places but I’ve never looked into it. I think it’s important to look into, lots of good engines mention it.

Ok. That’s it, for real now.

Made with Super