Chess engine - so what is it that you're doing?

   A good friend of mine - an orthopedic surgeon - told me once: "You know, there must have been a point in time where we took very different paths in our lives". He referred to the fact that once we were just two kids playing soccer in the same team, hanging out, having no idea about what we would do for living. "I use iPhone and I fill in forms on PC at work, but 'chess engine'? You are proud that you have written a 'chess engine'? Well probably you should be, but I mean, what is that?", he added. By the way he plays "normal" chess quite well, so it was not the chess word that confused him.

   So after I had decided to start writing this blog afresh I thought it would be good to start simply - with a post where I would try to explain what a chess engine actually is. Well, with some interesting detours, of course....

A brief history of chess

   Let's start with the game of chess itself. It's an ancient board game with a rich history. It originated in India between 3rd-6th century and came from there to Persia. There it was adopted by Arabs, who brought it to Europe in the early Middle Ages. Although Europe in the Middle Ages was not an ideal place to play chess, it gradually gained interest. The first book exclusively on chess was published by a Spaniard Lucena in 1497. First tournaments were organized in 19th century and in 1886 Wilhelm Steinitz (born in my home city of Prague!) became the first world chess champion.

The memorial desk of Wilhelm Steinitz in Prague

   Since then chess has been drawing even more attention. You might know names like Capablanca, Aljechin, Bobby Fisher or Kasparov. All of them were world chess champions that came after Steinitz, but there have been many other very interesting personalities in the world of chess, now reigned by Magnus Carlsen, a super talent from Norway. There would be many interesting stories to tell, but - even though I feel this chess history was just too short and incomplete - let's move on and I promise I will come back to tell more about the subject.

Rules

   Just kidding! Wait a minute though!

   What I usually hear from people that don't play chess are things like: "The only thing I can remember is how the knight can move" or "what is this alarm clock for?" I won't explain the rules of chess here - it would be easier if you just look them up if interested. Let me just tell you that some of the rules are really easy to get (like how knights move), some of them are more difficult - like castling rules or en passant move rule. Some of them are rather related to playing in official games and tournaments - like the rules around time control (yeah that's about the alarm clock), writing down the moves, players having to have their cell phones turned off during the game (yes, you heard me) and so on.
   But if you think you don't need to know the details ... then you are actually right! For now let's just say that chess is a board game where 2 players switch turns and sometimes it's good for you to capture opposing player's pieces. Just like checkers.

A chess clock

A brief history of computer chess 

   I mentioned that nowadays players have to turn off their cell phones during official games. This is not only to avoid bothering ringing but also because that way it's harder for the players to cheat with chess programs running on their phones. Now a good chess program running on a cell phone can beat every human player.

   But this is only the end (so far) of a long story of computer chess, which started as soon as in the 18th century. Then in 1770 Wolfgang von Kempelen, a Hungarian engineer born in Bratislava, constructed a machine that was believed to play chess without anyone's help. It was called The Mechanical Turk or simply The Turk. It played chess very well indeed and impressed nobles at European royal courts. Napoleon himself played against it and lost. Even though it was just an illusion, because there was actually a human player hidden inside the machine playing the moves, it was a great engineering piece of work.

The Mechanical Turk

   Still long before any computers, in 1912, Leonardo Torres y Quevedo, a Spanish civil engineer, constructed the first chess machine* that worked without any tricks involved. This machine was called "El Ajedrecista" (the Spanish for 'the chess player') and could play an endgame rook with king against king (that means it could give the opponent player a check mate while playing for the side with the rook). Again, a very impressive engineering work.

 * This first "thing" that played chess was a machine only capable of playing chess. Nowadays we would say it was a "computer appliance" or "dedicated hardware" (even though in this case it was actually neither). On the other hand now we see mostly computer software running on a general purpose hardware (PCs, Macs, cells,...) and so it's the software that is responsible for the chess playing capabilities. Even though this distinction between dedicated hardware and specialized software is important, I ignore it in this article and the terms chess machine, chess hardware, chess software and the like are used rather interchangeably 

   Next important chapter in computer chess was written by no one else than the father of computer science - Alan Turing (known mostly either for his theoretical model of computing machine - the Turing machine - or for breaking the code of the Nazi German encryption machine Enigma; apparently theory meets practice with this scientist). In early 1950's he wrote a chess program, but there wasn't yet a computer powerful enough to execute it. However he did play a game against a human player when he himself simulated the computer's execution of the program with a pencil on a paper. He (or his program to be correct) lost eventually. Actually, you can check the game yourself here.

   The first game ever to be played by a computer was in 1956 in Los Alamos laboratories by computer called MANIAC I. It played three games - in the last game it played against human novice player and it won. It is the first time in history when computer beat human player in chess. Pretty impressive, right? Well, on the other hand, it actually was a modified variant of chess. It was played on a 6 by 6 board (see the initial setting of the board below). An 8 by 8 board would be still too difficult to play on for the computers at that time.

Los Alamos chess - initial position on 6x6 board

   It's noteworthy that another well known computer scientist, Ken Thompson, also became a part of chess history with his successful chess machine called Belle. It took many years until somebody came with a program that could beat it. And it was a program running on a Cray supercomputer(!)

    As computers improved in playing chess over time, it was only a matter of time when they would be better than humans, even better than the world champion. It was inevitable, even though there were many people who thought this would never happen.

   But in 1997, Deep Blue, a special super-computer only capable of playing chess, built as part of a dedicated project by IBM, beat Garry Kasparov - a reigning chess world champion at that time. For many it was a big milestone in history and certainly it was a moment that drew wide attention. As you might guess, since 1997 computers have become even stronger and the gap between them and human players is getting bigger and bigger. 1997 wasn't the end of development of computer chess. But for know, let's make it the last chapter and move on again.

Deep Blue, a supercomputer only capable of playing chess 

So what is it that I am doing...

   So now, after giving you some context, when I say I have written a chess engine (and I keep improving it), it just means I have created a computer program that plays chess. As simple as that! Well, conceptually it's clear, but you might be still asking many questions, like

Why 'engine'?

   The word engine is actually important there. In this context, it means that it's a program that can play chess - can calculate possible moves and output the "believed" best move, but it doesn't have any convenient user interface. It doesn't show the board, it doesn't make it possible for the user to play the moves or configure the program. This is done by chess GUI programs. They can communicate with the engine and show the moves it does. It is actually very practical that these two types of modules (i.e. engines and GUIs) are kept separate - for many reasons. Most importantly, this allows users to plug one to the other as they see fit. It also allows for tournaments among chess engines.
   The truth is I have written also a chess GUI, but that's another story and the core of my work is still the chess engine.

Arena GUI - one of the most favorite chess GUI for desktop

How does it work with the GUI then?

   It uses a specific protocol. There are two major chess protocols: XBoard and the UCI protocol. I use the UCI protocol. The messages of the protocol are sent through the standard input and output of the engine, but that's just a technical detail. More importantly, the messages are text messages even though reading them is kind of hard. Basically the engine receives the current position on the board and is given the time it is supposed to spend on the computation, after which (or sooner) it is expected to output the best move. 

   The problem - or the beauty of it actually - is that there is so much more to it. First of all, the position is not given only by indicating where the pieces stand and which side is to move. There are other properties of the position that have to be described. Beside indication of which side is to move, the rights to castle also need to be indicated as well as the possible right to take en passant. Another important rule to capture in the position is the 50 move rule. The trickiest thing to capture is the threefold repetition rule. This is the reason why the position is given as starting position (mostly the initial position for the start of the game but not necessarily) and then the list of the moves that lead to the current position.
   There are many details to other parameters that are passed to the engine or details about information that the engine sends back. I can go on and on until I bore you. But I won't. If you are interested, be sure to check out this UCI specification  

So how does it work? How does it 'think'?

   I won't go into much detail here because I feel I wouldn't be able to keep it reasonably short otherwise. But conceptually, a chess engine has an internal representation of the position on board. It 'knows' the rules - i.e. it's programmed to generate just the moves that are allowed (and do them in its internal board representation). Therefore it can 'try' what the position looks like after doing certain move and then after the opposite player plays another move and then when another move is done by the program's side... and so on. This goes on to some number of moves played from the current position (to some depth of computation). After doing the last move, the program can "evaluate" the emerged final position (even though this is one of the trickiest parts of the engine) - it can recognize how (dis)advantageous the position is for its side and it remembers that. It does many possible combinations of possible moves. Based on the evaluations of positions that these combinations of moves lead to, it can decide which one of the possible next moves is the most advantageous for its side and mark it as the best move .

   This explanation is rather vague, but if you want to know the details, you are in luck, because this is what I will be writing about in this blog.

   The way computer "thinks" when plating chess is conceptually not different to what human players are trying to do in their heads. However there are some important differences. Most importantly, chess engine 'thinking' is based on (even though very advanced) brute force. It can do millions of moves in a second back and forth. It never (well if not buggy) make a mistake in the sense that it overlooks that a move is possible just by forgetting it or in the sense that it thinks a move is possible even if it's not (a human player might as well say: "I wanted to end my combination with a rook that I sacrificed two moves before...". This won't ever happen to a computer). Computer brute force seems very powerful compared to human players that can process no more than a few moves per second, are moody and get tired. But human players, on the other side, can asses the positions better. They can see if there are going to be some threats to the king, they can see if this running pawn is going to be decisive, they can "obviously" see that this rook that is not active is effectively of no value at the moment. They can see the position is blocked and it's therefore a draw. This is also very powerful and sometimes it can - at least partially - outweigh the brute force power of computers.
   These two types of thinking also lead to two different styles of play. Computers don't fear sharp positions and are usually very confident there, unlike humans. Computers also find surprising combinations (surprising to human players) very easily. But they sometime struggle to find a good move in a quiet end position where a long series of obvious moves (obvious to human players) just naturally leads to win or a desired position.
   In fact, human players, when they face computers, often choose to play anti-computer chess style. This means: no experiments in opening game, prefer close and safe positions and also rather close or blocked end games. On the other hand, if there is an opportunity to safely exchange material (i.e. to exchange it's own captured piece for an opponent piece of the same kind), go for it. 

Will you explain the internals of computer chess programs in more depth?

   Absolutely! In following blog posts.

Do you make some money out of it?

   No. It's not against my beliefs to earn some that way, but given there is such a big competition in this field and given it's only my hobby, it's not very realistic. Still it's very rewarding in many other aspects. It allows me to try out new technologies and practices. It's a good mind training. It's given me the opportunity to see what it's like to manage a software project in its entirety - I actually see this very important because this would be a whole new experience for many that work for big companies and maybe even for those working for the small ones.  

What is your ultimate goal here?

   My goal is to keep improving the engine - in many aspects. One obvious aspect is the mere strength of the program, which is not yet big enough. The other could be that the program can go beyond just playing chess. For example it can be more configurable - it can be made to play on different levels for one. Also, there is much more than programming the chess engine. I've written a chess GUI also, I maintain the web page, I am trying to write blog, I am getting to know people from the computer chess world. Last but not least, I want to learn new things from the computer engineering perspective. I want to be satisfied with every single line of code (very idealistic yet not a wrong goal to have).
   So to get back to the original question, there is no single ultimate goal.  

How can I try out the engine

   Check out the project page. You will find a detailed instructions on how to install it. The easiest way is to download the bundle with GUI and engine, but unfortunately this currently works only for windows. There is a version for Android. A version for Linux is soon to come.  

More to come

   In this post I wanted to explain what it means to be writing a chess engine and to give some historical and other context. I actually found it very hard to do so in one blog post, which is probably already too long. But I think this will get better as the following posts will be more focused. There is definitely more to come. Stay tuned!