I’ve been developing chess engines as a hobby since high school.
At the moment I continue to maintain the last of this series: an xboard chess engine that I call "Avenger", with an average search speed of 1.2 million positions/sec and a search depth of 7 moves in Blitz games when running on a modern machine. The engine is developed primarily for chess competitions and releasing its source code will defeat this purpose (or at the least make its building blocks reusable and hence diffuse its identity). I have therefore decided not to published its source code. This article will nevertheless give an overview of its internal operation, which is essentially the same as all other chess engines.
Avenger uses alpha-beta pruning (a modified min-max tree exploration algorithm) to enumerate the state space from a chess position and direct opponents towards their “worst future”. Below I'll illustrate how this works.
Min-max Search
Assume that you’re playing a turn-based game against a friend. In the game, there are multiple bags with several items of different material values in each. The rules of the game are:
- You select a bag
- Your opponent selects an item from that bag to give to you.
The bags and their contents are shown below.
Naturally, you are interested in getting an item with a high material value. Your opponent, however, is interested in the exact opposite: giving you one with a low material value. How do you proceed?
Some bags with high value items such as £100 may be tempting. However, since you only select the bag and your opponent selects the item then you'll never get your hands on these: your opponent will never give them to you. Instead, what you're likely to get is the worst item in any bag you select.
Your best strategy, therefore, is to select the bag whose worst item has a higher value than the worst item in every other bag. In this case, this is bag 3 because it guarantees a minimum value of £7 while bags 1 and 2 guarantee minimum values of £3 and £2 respectively.
This is called a min-max strategy and is used when players take turns to direct the outcome of a zero-sum game (e.g. chess, checkers and go). In this example, the state space is small and so a computer can explore all the possible outcomes quickly. In chess, however, the average number of moves per position is 36 and so a chess engine which needs to consider all the possible outcomes say, 7 moves ahead, will need to enumerate and evaluate 367 chess positions. If it can do so at a speed of 1 million positions/sec then it will take about 22 hours to make a single move.
Now here’s a neat trick to speed this up:
Alpha-Beta Pruning
Assume you’re a computer who’s playing the game above with the bags. As a computer, you explore bags and evaluate items in a serial manner (i.e. one by one) which may take a long time if there are many options to consider. You’ve already finished peeking through the first bag and found that the worst item is worth £30. You begin exploring the second bag and the first item you pull out is a measly £1. This situation is depicted below.
At this point, continuing to examine the contents of bag 2 is useless: you already know that it contains a very bad item that your opponent will select to give you. You therefore abandon exploring this bag, decide that you'll not select it (given that you already have a better option – bag 1 with a guaranteed outcome of £30) and start exploring the next bag.
What you’ve effectively done is cut down the search tree without sacrificing your evaluation accuracy. This algorithm is called alpha-beta pruning.
Avenger (and all chess engines) do the same. When they encounter a bad move which the opponent might capitalize on, they declare this as a bad option and don’t waste time thinking about it. The saved time is invested in exploring promising moves more thoroughly and allows chess engines to search the state space to deeper levels.
Chess Board Representation
On another performance front, Avenger uses bitboards to represent chess positions and can generate moves and evaluate positions very efficiently using bitwise operations (some of these operations are written in inline assembly to maximize performance).