Computer Chess And How It Works
The first record of a chess computer is the “Chess Automaton”, which was built by Wolfgang Von Kempelen in the year of 1769. You’re probably wondering how that would’ve been possible given the resources at the time, and the answer is, it wasn’t. The automaton turned out to be a hoax, with a person hidden under its cloak. But this managed to fool people, and great ones too, such as Napoleon Bonaparte, Benjamin Franklin and significant others for nearly 84 years. It wasn’t until a century and a half later, in 1912, when the first chess computer (a real one, this time) was built. It was made by Leonardo Torres, A Spanish civil engineer and mathematician. The machine could play king and rook versus king endgames using mechanical hands and magnets (a significant accomplishment at the time). Fifty or so years later, Alan Turing wrote the program for a chess computer on paper, and then several years later, the chess computer ‘Deep Blue’ beat Garry Kasparov, the reigning world champion at the time. Right now, the fastest chess computer is ‘Blue Bene’, and it can compute a mind boggling 500 trillion (5 x 10¹⁴) operations per second.
Chess computers have evolved incredibly in the last few decades. A chess game is found with almost every PC nowadays and is played leisurely for recreation. But not many people appreciate the tremendously complicated coding behind it, and this is what I’ll be trying to explain in this article.
The technicalities and actual programming algorithms will be gone into later, but for now, let’s address the basic questions. Is the computer actually “playing” chess? Is it “thinking”? Thinking and playing (with will) are attributes of a self-aware intelligent species (a.k.a. humans), but computers are neither of these. They cannot think logically (or think at all) and they do not either. To the computer, chess is a game of numbers, and it is provided with certain algorithms to compute certain values for certain moves on the chess board. So the computer basically has to run through several permutations and combinations depending on its opponent’s move and calculate the ‘best move it can make’, but this is far from basic. Let’s put the computers on hold and actually get into the math of it (I’ll try to make it fun, I swear). At the beginning of the chess game, 20 moves can be made by both sides. There are 8 pawns which can move one step or two steps forward, and 2 knights, which have 2 moves each. After one move is made, more number of possible moves open up.
Now, back to computers. How do you determine how good a computer is at chess? The answer lies in its ability to look into the future, not in a fortune teller sort of way, but in a way that examines all the possibilities and differentiates between the good and bad ones. So, imagine you’re up against a computer and you go first. There are 20 moves you can make, but when the computer makes a move, it has to examine 20 x 20 = 400 possible moves before it makes its own. By examining, what I mean is, it takes a look at every move you can possibly make and works out an effective counter move. The number of possibilities add up exponentially every time. At 5 moves, there are 3, 200, 000 possible board positions and at 10 moves, 10, 000, 000, 000, 000 possible board positions. There are a finite number of board pieces and another finite number of places you can move, so the total number of board moves must be finite, and it is. The total calculated number of possible board moves in a chess game is, wait for it, 10¹²⁰. To put this into perspective, the number of atoms in the universe is only 10⁷⁵. Considering the number of people and planets and suns and moons and stars there are, the number of atoms is dwarfed by the number of chess moves.
So, the best computer would look through all the 10¹²⁰ possibilities and pick out the best moves to make but for practical purposes, that is nowhere near possible. Instead, what the computer does is it constructs what is known in programming as a tree. The tree tells the computer what move the opponent has made, what moves the computer can possibly make and the good and bad moves are separated.
But how does the computer know which move is good and which move is bad? That is yet another human attribute. As mentioned before, the computer only computes. So how does it do this? When the chess program is designed, each piece on the chess board is given a value- a numeric value and the computer tries to protect the pieces of higher value (queen, rook, etc.). Now, if everything is numeric to the computer, then surely there must be a numeric value which tells the computer where to move, and yes, there is. The computer constructs the aforementioned tree with ’n’ number of levels, each level consisting of all the possible board moves of one board piece of one side (black or white). The higher the processing speed of the computer, the more number of levels on the tree (depth of the tree). This is when the problem of ‘good or bad move’ decision making arises. Thousands of parameters govern a good move- the position of the king, the position of its queen, what pieces is it putting at risk, how many pieces it will have left, etc. Taking all these into account, an ‘evaluation formula’ is designed, which brings down all the permutations and possibilities to a single integer, which depicts the value (value here, refers to both numeric and actual value in terms of asset or liability) of that board position. After this is calculated, the move with the highest value is made.
Three-level trees are popular when explaining this process. So, let’s consider a three level tree and at the same time, delve into the technicalities of computer chess. The total number of moves at any given point in the game is about 20, but instead of shuffling through every single possibility, it observes the opposition move, and it derives a move based on that move. So for every opponent move, the tree is constructed.
We have considered a computer which is fast enough to only construct a three level tree (in real life, 30 to 40 levels are made). The opponent’s move is at the top, and all the moves the computer can make in response, or ‘Successor Functions’ branch out from that point. The last level of the tree is called the ‘Terminal State’ and the computer works upward from the terminal state to the top to see what move to make. Now, obviously, all of these conclusions drawn by the computer must be in the form of an integer. Therefore, every terminal state has something known as a ‘Utility Value’. The goal of the computer is to maximize this utility value (win, basically). The move with the highest utility value is best for the computer and worst for the opponent and does its best to infiltrate the opposition’s defense. The best utility value that a move achieves is called its ‘Minimax Value’. The computer works from the bottom to the top. As you know, every move and every piece on the board has an integral value, and the value secured by the first move (or ‘node’) is the best utility value (Minimax Value). The Minimax value corresponds to a particular move and the move is made. Simple, right? (also, major overkill on the terminologies)
The algorithm used to find the Minimax Value or to take what is known as the ‘Minimax Decision’ is called the ‘Minimax algorithm’. To consume less memory and speed up the process of making a move, a concept called ‘Alpha Beta Pruning’ is adopted, which seeks to decrease the number of nodes evaluated by the Minimax Algorithm.
And this, in a nutshell (an insanely small nutshell) is how a chess computer works. The technology however, is continually expanding, seeking to traverse new heights and raise the bar. No doubt, within the next few decades, we’ll have computers which can actually play the game.
