Creating a chess engine from scratch (Part 1: Basics)

Hi.

I have a master degree in computer science and mathematics. As a hobby project I will blog about the design and implementation (writing software code) of what goes into a chess engine - I am creating my own engine for fun. For those who wants to learn how a chess engine actually works this will probably be interesting as I will also talk about general principles of chess engines. 

So how does a chess engine work:

Well, there are basically two components of all chess engines:

1. position evaluation

2. Searching for the next move (and choosing the best)

The first is a piece of code that evaluates any position and gives it a numerically value (positive means white is better, negative means black is better, while a evaluation value of 0.0 means the position is equal). How is a position evaluated by a computer? Well, basically it adds up all pieces on the board (for instance 1.0 for a pawn, 3.0 for knight and bishop, 5.0 for a Rook, 9.0 for a Queen - negative values for black) and then applies a lot of heuristic rules. These rules are known as rules of thumb such as a double pawn is usually not good, a knight on the rim is dim (bad), castling is usually good etc etc. All these heuristics are usually hard-coded by the programmers with help from Grand Masters. A good chess program can easily have 100s or 1000s of these heuristics that modifies (up or down) the evaluation of the position. 

2. Searching for the next move

Since there are about 10 raised to the power of 120 different chess games (compare that to the estimated number of particles in the universe - around 10 raised to the power of 80 is the estimate) then even a computer cannot simply look at all moves. So all engines generate a tree of moves where the root is the current position, then for each legal move there is a branch from the root to all the new positions resulting from one move, then from each of these branches you add new branches for all legal moves etc etc. 

Obviously this search tree gets extremely big very fast (it grows exponentially) so you have to cut off branches that looks unpromising and concentrate on the promising branches - i.e. the critical lines. This is what humans are extremely good at - we usually only look at a very narrow search tree with 1 or 2 branches for each move. Computers use brute force - i.e. computational speed to evaluate a much wider tree (because they are too stupied to know what the narrow branches should be automatically).

A computer can easily evaluate a few million positions per second, a human probably 1-2 positions per second!! Usually speed is measured in MNodes/sekund which means million positions (Nodes in computer science jargon) per second. Fritz running on my old laptop does about 2.5 MNodes while Deep Blue did about 200 MNodes per second. Raw power is not all - the evaluation function is also very important. Pretty much all engines use the same algorithm for searching through the search tree of possible moves to find the next move. This algorithm is known as alfa-beta search or it is some variant of this. This technique builds on a simpler method known as min-max method, which I will discuss in part 2. 

Basically, results have shown that this brute-force way of playing chess works extremely well - massive calculations are what computers do best, which is why all engines are remarkably similiar in design. 

To further enhance an engine you will usually add a database of opening moves - an opening book and end game databases as well. For instance now there are databases for ALL positions with 6 or fewer chess pieces which will tell you whether any move from any position will lead to draw, win or lose. If we will ever get a 32-men database then we will have solved chess. i.e we will know if chess is draw, win for white or win for black (with perfect play from both sides). Recently checkers (or draughts as it is know in British English) was solved. We know now that with perfect play checkers is always a draw. Checkers has about 10^20 legal positions, while chess has about 10^40 or so legal positions. So we are looooong way from solving chess - will probably not happen in my life time (my guess is that chess is actually a draw game with perfect play from both sides. You can tell me if I am wrong or right in the year of 2134 or so!)

In my next blog I will describe my basic design (which is a bit different from the standard method described above - I want to try a new approach to the move evaluation part - no reason to make yet another rykba-crafty-fritz-ivanhoe clone. My engine will be a hybrid of several ideas)