I'm Krystian. I make games and teach game design. I recently wrote a Chess Engine from scratch in Pico-8. In this series of posts I will walk you through the process and share with you some resources I relied on.

Chess Engine Tuning

In the last episode, we've sketched up a basic Minimax function that could search for the best move in a given position. Considering how Chess Engines are often presented as these ingenious feats of programming, the function we had seemed pretty simple, right? Well, we were just scratching the surface. If a high-end Chess Engine is akin to a modern fighter jet, what we have so far is a kite. It flies alright but that's about it. Let's see if we can spice things up a bit.

Alpha–Beta Pruning and Move Ordering

The issue we'll quickly run into with a basic Minimax function is that it's not very efficient. It just blindly checks all of the possible moves, wasting a lot of processing power on really bad moves. Which means our AI won't be very smart. We won't have the processing power / time to search a lot of moves ahead. A lot of Chess Engine optimization is about tweaking this algorithm to only focus on the most promising moves. This means the engine somehow needs to realize when it's researching a bad move and stop that line of "thought". This is where Alpha-Beta Pruning comes in.

Admittedly, Alpha-Beta Pruning is a bit of a brain-twister and it pays off to take the time to run down a specific example. Here is a good one:

Basically, as we recursively call our function, we also let the instances of our functions know what's the best move scores for white (Alpha) and black (Beta) are that we've found so far. If a function realizes it's researching a decision branch that can't possibly have a better score than what we found somewhere else, it will abandon - "prune" that branch. If I already found a move that will allow me to capture a Rook, I don't need to research a branch that starts with me losing  a queen. Of course, I'm over-simplifying here. We need to make sure we aren't pruning away moves that require us to  lose some ground to get into a good position - sometimes you need to sacrifice a piece to get your Checkmate. So as always, the devil's in the details, which is why it pays off to run through a specific example.

But Alpha-Beta Pruning is just the beginning. Now that our Chess Engine has the ability to reject hopeless lines of play, we can start looking for ways to take advantage of this. One way of doing it is by ordering the moves and doing the really good moves first. The pruning only triggers once we've found a promising move already. If we first go through our garbage moves only to stumble on the ingenious game-saver at the end of our search, our pruning will do little for us. On the other hand, if we can somehow guess which move is the best one and search that one first, we will be able to prune away large portions of the search tree and save us a lot of work.

The heuristics for Move Ordering is again one of those cases where Chess Engine development gets a little more subjective. Different developers may have different opinions on how to guess what a promising move is. It's certainly a good idea to check all of the captures first. Among the captures it makes sense to focus on the valuable pieces first. If I can successfully capture the Queen, that's a good candidate for the best move on that turn. Beyond that, different techniques and schools of thought exist. One heuristic might work better in certain situations but perform worse in others. But a good move ordering heuristic must be something that is relatively easy to calculate. After all, the idea is to save processing power.

Note that Move Ordering is not really biasing the engine towards making certain plays, even if it looks like it. After the Move Ordering, the Minimax function will still figure out what the best move rally is. Move Ordering won't change which move is ultimately picked. The only thing a Move Ordering function can do is to save some time. Also, remember that Move Ordering only really works with Alpha-Beta Pruning. An unmodded Minimax doesn't care about the move order because it searches all of the moves anyway.

Iterative Deepening and Principal Variation

We're deep into the super-fancy terminology now. Among all the techniques to do Move Ordering, I left out the most effective one. And I did it because it's shockingly counter-intuitive. Here is how a Chess Engine would search at a depth of 3.

• First, it searches at a depth of 1.
• Then it starts the search again at a depth of 2.
• Then, finally it starts from scratch and searches again at a depth 3.

At first this sounds incredibly wasteful. Why are we searching at depth 1 and 2? Why not going immediately for depth 3? Well, this principle is called Iterative Deepening and there are three good reasons to apply it.

Firstly, it'a good pragmatic solution if you don't know how long the search will take. A good approach for a computer Chess game is to give the Chess Engine a time limit of how long they are allowed to "think" on their move. If the time runs out while searching at depth 3, you'll still have the results of depth 2 to fall back on. Full disclosure - I did NOT use this technique in Pico Checkmate. It's easy to overwhelm Pico-8  and I was worried the Chess Engine would get dumber when it encountered demanding positions.

Secondly, each successive depth costs a significantly more processing power than all of the previous ones together. The requirements grow so fast that if the computer is quick enough to complete a depth 3 search in a reasonable time, depth 1 and 2 should be a piece of cake.

Let's quickly math this out. The average branching factor of Chess is 35 - on average you can make about 35 moves at any given point.

• A depth 1 search is 35 positions.
• A depth 2 search is 1,225 positions
• A depth 3 search is 42,875 positions.

If you're about to search over 40,000 positions, a thousand more won't make a big dent.

Finally, you can feed the results of a search into your next search to get more efficient move ordering. The results of a search are stored in what is called Principal Variation. It's a fancy-schmancy name but it's really just the series of moves that has been determined to be the best by the Minimax function up to its set depth. One of the most powerful Move Ordering techniques is to give the moves from the Principal Variation of the previous search a high priority for Move Ordering. Moves, which have deemed to be good previously are likely to be winners as we deepen our search.

The Horizon Effect and Quiescence Search

A well-known problem of classical Chess Engines is the so-called Horizon Effect. As we saw, Chess Engines only search up to a given depth. Once they reach their destination depth, they roughly estimate how favorable a given position is. We already know this evaluation can be short-sighted and misguided. That's why we're doing this in-depth search in the first place.

One problem that can occur is that a Chess Engine will be blind to any potential events beyond its maximum depth - its horizon. It will then pick lines of play that have horrible consequences down the line as long as those consequences are beyond its horizon. It might even artificially stall the game - make small sacrifices to "push" a big loss beyond the horizon. It would be akin to a politician saving the unpopular legislation until the very end of their legislative period.

The effects are quite visible. A Chess Engine suffering from the Horizon Effect might have troubles keeping track of a complicated series of exchanges. It might decide to go for a bad exchange of pieces because it can't see deep enough to know how it will play out in the end.

One feature that helps with the Horizon Effect is a so-called Quiescence Search. A Chess Engine with Quiescence Search will search BEYOND it's set depth but will only consider capture moves. It will continue doing capture moves until there are no capture moves possible anymore. Only then it will try to estimate the board position. That way, a Quiescence Search has the potential to see complicated exchanges all the way through to the end. It can also take into consideration which pieces are under attack and how well they are protected.

A Quiescence Search is a fascinating feature idea to add to a Chess Engine. On the one hand, it can greatly add the number of positions it needs to calculate - increasing the search time for a given depth. This is exactly what we have been trying to prevent all this time. On the other hand, Quiescence Search greatly enhances a Chess Engine's ability to evaluate a position - increasing its quality of play.

Missing Features

There is a lot more I could talk about. I wanted to quickly list some of Chess Engine features that I wasn't able to cram into Pico Checkmate and why.

Threefold Repetition - As it stands, Pico Hero doesn't recognize a draw by Theefold Repetition. This is because implementing that check would currently cost too many tokens and possibly seriously bog down the Engine. At least that's what I estimate. In order to check for Threefold Repetition, each board state needs to be "rewinded" until a pawn is moved or a capture is made. So you would keep undoing moves and checking each resulting board state against the current board state. Comparing two board states isn't so easy either. The slow way is to loop through all 64 squares on the board and compare the two boards square by square. But that would take too much time. Instead, you can hash out a board state into a single integer. There is a popular method for this called Zobrist Hashing. I actually already use this for the Principal Variation. But since Pico-8 is using 32bit variables, there is a good chance you get false positives. So in case of a positive you'd still need to do a manual check. I eventually decided I'm going to skip that one rule in order to focus on other parts of the Engine. But eventually I might give it a go. Perhaps I'm over-estimating the problem?

Opening Book - So currently, the AI in Pico Checkmate will always play the same opening. It will also always react in the same manner. Meaning that if you can remember how you've beaten the AI, you can always beat it by playing the same moves again. One way to mix things up a bit would be to add an Opening Book. This is essentially a database of pre-programmed responses to common early-game board states. With an opening book, an AI can "choose" different openings and respond to common openings in a smarter fashion. The reason why Pico Checkmate doesn't have an opening book is simply space. An opening book can be a huge amount of data. I don't see how I could make even a modest Opening Book fit within the token limit or the compressed program size of Pico-8.

Transposition Table - A Transposition Table is a database of previous board states and their scores the Chess Engine builds as it's searching for the best move. During a search, it is common to encounter the same board state multiple times. For example, the two players can be moving their kings back and forth arriving at the same position again. In such cases you can speed things up by just looking up in the Transposition Table what the previous score was. You no longer have to calculate the score for the same position twice. This sounds like a great feature! The only reason why I decided not to implement it is because of the severe memory restrictions of Pico-8. I wasn't really sure how to neatly implement a Transposition Table and make sure it never causes the Chess Engine to run out of memory. Also, a Transposition Table relies heavily on Zobrist Hashing and I wasn't too confident about the 32bit hashes.

Future Development

I really enjoyed working on Pico Checkmate! In many ways, the project turned out to be exactly what I needed. I've gained a basic understanding of how Chess Engines work and I'm ready to tackle more challenging Chess projects. Currently, I'm thinking of doing a Pico Checkmate port on the TIC-80 fantasy console. It's a engine that also uses LUA so I hope I can just copy & paste large portions of the code over. Since a lot of the Pico-8 restrictions no longer apply on the TIC-80, this would also give me an opportunity to implement some of the missing features. 

Until then, thank you for sticking with me on this series of articles and let me know if you have any questions.