Wednesday, December 16, 2015

Creating a chess engine from scratch

The following tutorial is taken from the blog of Zaifrun on Chess.com with the fin of keep the legacy and no have it lost like I see them before on the wold wide web 


(Part 1: Basics)

  • zaifrun
  •  
  • | Apr 12, 2010 at 2:29 PM
  •  
  • | Posted in:
  •  zaifrun's Blog
  •  
  • | 28751 reads
  •  
  • | 12 comments
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)

(Part 2: Move search)

  • zaifrun
  •  
  • | Apr 18, 2010 at 7:48 AM
  •  
  • | Posted in: zaifrun's Blog
  •  
  • | 6883 reads
  •  
  • | 1 comment
So in the first part we looked at the components of a chess engine. After 10 days of coding I now have a working chess engine. Its not fast enough yet and the evaluation function is still primitive, but it works and it does not make obvious blunders (the rating now is probably around 1400-1600 I would think) Part 2 will focus on how an engine searches for the best move. How does Rybka and Fritz find the best line? Part 3 - next time - will deal with the evaluation function of a position in details.
A chess engine chooses the next move by building a game tree of positions - see the image below (from wikipedia)

game tree
The root - the top node - is the current starting position and the leaves at the buttom are the resulting positions after 4 plys - i.e. 4 halfmoves (white, black, white, black for instance). The nodes in the middle layers are intermediary positions reached during the way to the resulting positions. How much is 4 ply - well, any state of the art engine can do 20 ply in less than a minute these days, so this is a fairly small tree.
How does the computer find the moves. Well, as you can see at the buttom the best possible position is given +9 (i.e. white is up 9 pawns) and the lowest is given +3 (white is up 3 pawns). So all positions in the example favour white - positions favoring black is negative numbers. Now, unfortunately we cannot just choose the path from the start to the +9 position, as black moves every other time and can prevent this. In fact - with best play from both players the best line is +6 (as indicated in the top node). 
You can see that there are two kinds of layers in the game tree - max and min. When it is whites turn to play we do a maxium of the next nodes - so 6 is the top because it is the maxium of 3,5,6. The node with 6 in the next layer is 6 because it is the minimum of 6 and 7 - remember it is now black's turn and with best play he will of course go for the position with a score of +6 instead of +7 as it is better for him to have +6 instead of +7. In the next layer it is again white's turn and you do a maximum. And in that fashion you continue down the tree until you reach the bottom and then the path is your best line! Now, in an actual implemenation this tree is built from the bottom up - i.e. starting with the bottom nodes and calculating backwards to the top.
Now, this game tree gets huge very fast. In chess you have on average about let us say 30 legal moves or so. So after 5 plys you have 30^5=24 million positions, after 7 plys you have 30^7 = 21 billion positions! So engines usually implement a lot of optimizing tricks. One such technique is alfa-beta search which cuts off a lot of nodes in the tree that you do not need to look at - in the picture these are marked with grey. You can read about this in detail in other places on the web - it gets a bit advanced and there are also even more advanced techniques than alfa-beta in order to cut down the search tree. 
Of course even if you can look 50 moves ahead you will not be good chess player if you do not know if a position is good or bad. That is the topic for next time - how to do the evaluation of a position. Right now my engine evaluates positions in a very simplistic way - but it can easily be improved. See you next time!

(part 3: Opening Book)

  • zaifrun
  •  
  • | Apr 25, 2010 at 10:44 AM
  •  
  • | Posted in: zaifrun's Blog
  •  
  • | 8181 reads
  •  
  • | 1 comment


Ok, I have not done much work on the evaluation code yet, so that will wait for another part. This part will instead focus how an engine can understand opening theory and how it chooses which openings to play. Several issues arise when creating an opening book (it's basically a database):

1. What lines will you have in the opening book and which games are they selected from?
2. How do you choose which lines from the book to play - you do not want your engine to play crap openings all the time or become too predictable   by always playing the same variation in the sicilian dragon.
3. How do your organize your opening book so its easy to find the next move for the computer to play?


1. What lines will be in your opening book

This really goes to the heart of what exactly is opening "theory" - what variations do we accept as established theory in chess openings? Well, there is no correct answer really. Most people regard the opening theory as the openings and variations defined as the lines and moves played by very strong players at GM level. You would probably not trust the analysis of opening variations done by a 800 ELO player. You would have more faith in variations analyzed by GMs. Indeed most opening books for computers are created from a large sample of games by 2400+ players. Why not just choose 2700+ players? Well, then you would not have any lines in your book covering openings such as b4, b3 and f4 and some people will play those openings against your computer, so you need to have them in the book. Therefore you cannot simply just compile the opening book from GM games - you need to have a broad book to cover all openings. Right now I have compiled an opening book with about 6000 different variations and 250.000 moves (plies) in total. It is a fairly decent sized opening book - it should be good enough to make sure my engine plays decently in the start phase of the game as both black and white. Commercial engines have huge and highly optimized opening books - but they are made by opening specialists. I based my openings on the games played at the European Team Championship in 2009 and the European Individual Championship in 2010. There are about 2500 high level games played at those events combined. I then added a basic book  containing all the ECO variations, so even if a variation like 1. f4 was not played in any single of the 2500 games my book still includes variations with the f4 move. 

2. Which variations from the opening book will your engine play.

So once you have managed to compile a comprehensive book, then the next questions is what lines from that book should the engine play. Should it just choose random variations from the book? One very common method is to stastitical analysis on a large number of games played and record the end result of the game in the variations in your book. Then you assign a weight (a percentage) to each of the variations based on this analysis. Of course whether a game is won or lost does not neccesarily depend on the variation itself, but given a large enough amount of games, then the statistical analysis begins to be useful and more accurate than just choosing a random move from the book. Below you can see what i mean by the percentage point (screenshot taken from the fritz opening book - version 8) Notice that. 95.1 and 4.8 only adds to 99.9 %. The last 0.1 % are distributed among all the moves where it says 0 % (they are close to zero - so they are rounded down to 0 when displayed to the user). Usually no move in the opening book will ever have a 0 % chance of being played - it that was the case then you could just as well remove the move from the book since it will never be played. My engine uses this technique and it tends to play much better lines than just choosing a random move from the book.




3. How do you organise your opening book efficiently?

Most opening books are keept in a binary or a text file and then read by the engine when it starts playing. An engine needs a efficient way to store the opening books so it is easy and fast to look up which move to play next. One very efficient way is to organize the book as a special kind of tree, called a prefix tree or a trie (sorry, computer science jargon here). Below you can see what I mean. The root called "start" is the start position. Then for each move from that position in your book you make a branch (here there are d4, e4 and c4 branches). For each move after d4 you store the next moves - here Nf6 and d5. So when the engine is playing a game it will always know exactly where it is in the tree at any point. At each branch the engine will choose which path to take based on the percentage probabilities described above. If at any point the opponent makes a move for which there is no branch to go down - well, then the engine is out of the book and have to start thinking for itself. It is pretty easy to get an engine out the book - just play h4 and it will be out of the book fast. Although this will probably not be to your advantage!







 I am kind of wondering how computers would play chess if they had no opening book at all. Maybe they would play in a completely different way than opening theory as it is constructed by humans. Of course you can simply turn the opening book off in your program, but then they still play according to the principles which humans thinks are best - after all chess engines are made by humans. It could turn out that for instance a4 or a3 is much better than e4 or d4. We simply do not know for certain at this point and we will not know for sure until (if ever) we get the 32-men tablebase (also known as God's algorithm in chess) and that is it not exactly around the corner! Chess will remain an enigma for a long long time.

(Part 4 - position evaluation)

  • zaifrun
  •  
  • | May 5, 2010 at 1:03 PM
  •  
  • | Posted in: zaifrun's Blog
  •  
  • | 7527 reads
  •  
  • | 0 comments

I have finally started working a bit more on the position evaluation part of the engine. This part will focus on how a computer evaluates a chess board position. The evaluation in my engine was quite primitive at first, now it is better - still plenty of room for improvement though. A chess engine is composed of so many different things and so many details that it seems there are always things you can improve somewhere! However, the position evaluation is a big part of any chess engine.
This part of a chess engine is more or less a black art (or black magic). Its really difficult to come up a position evaluation that is good for all positions. In fact even the best engines today are not as good as super GMs in evaluating a position in my opinion - but they compensate for that in search speed which gives them the advantage to look more moves ahead than humans. There is also a trade-off here between having a simple evaluation part in an engine which is fast to compute, thereby allowing greater search depth, or having a more advanced but slower evaluation part, which decrease the amount of computation available for searching but may be better in evaluating positions accurately. Difficult to find an optimal strategy for an engine here - balance is probably the best answer here.

1. Basic position evaluation.

An engine gives a numerical score to all positions. A value of 0.0 indicates the position is equal, a negative value indicates black is better and a positive value indicates that white is better in the position. Basic engine position evaluation simple assigns a value to each piece (for instance 1.0 to a pawn, 3.0 to a Knight and Bishop, 5.0 to a Rook, and 9.0 to a Queen) and then adds up all the values. Checkmate is usually indicated as +1000 or -1000 depending on whether black is check mated or white is check mated. Naturally this is a very bad evaluation function for an engine, but it covers the basic and all engines incorporate this as the basis and then adds advanced features.

2. Advanced position evaluation.

This is really the black art stuff - this is where you can make your engine different than other engines. In my engine I have included the following advanced evaluation methods (at the time of writing - the list is changing rapidly).
* bonus for king safety - i.e. castling and pawn shields in front of the king
* bonus for having the bishop pair.
* increase value of bishops and rooks when the number of pawns decrease - i.e. more open games.
* decrease value of knights when the number of pawns decrease - knights are not good in open games.
* decrease value if a pawn is a double pawn - usually not good.
* penalty for moving the queen too early in the game - do not want it to be chased around by the opponent.
* bonus for mobility - i.e. if a piece have more squares to move to it makes it more valuable.
* bonus for threats - i.e. if a piece is threatening to capture an enemy piece it gets a bonus.
* bonus for protecting own pieces - i.e. if it covers other pieces of the same color it get a defensive bonus.
* different activity bonus based on wether it's the opening, middlegame or endgame. For instance a king should not be active in the opening, but should be active in an endgame.
* penalty if there is many pawns of the same color as a bishop on the same color squares - i.e. a bad bishop vs a good bishop.
* bonus for pawns far advanced - i.e. close to promotion to a queen or other piece.
* bonus for development speed of minor pieces in opening game.

...and some other even more advanced pattern matching stuff. I should not spill all my secrets here..:-)

How do you fine-tune all those bonus/penalty parameters? Well, you can try statistically fine-tuning by letting the engine play lots of games and then see what gives the best results. However, I do not think this will give substantially better results than just fine-tuning the parameters manually (by a good human player). It is really difficult to find an optimal set of parameter values that will work in all positions.
Bottom line: position evaluation is not en exact science and I think humans are better than computers in the evaluation part of playing chess (at least for now).

(part 5: Endgames)

  • zaifrun
  •  
  • | May 11, 2010 at 1:46 PM
  •  
  • | Posted in: zaifrun's Blog
  •  
  • | 4369 reads
  •  
  • | 0 comments



This part will focus on the most difficult part in modern engine design today in my opinion - endgames. While openings are covered by having opening books and the middle game is dealt with by the large search depth of engine (20-25 ply  - or 10-12 full moves) the endgames still pose problems. Yes, for sure we now have the 6-men tablebases covering all positions of 6 pieces on the board or less which computers can use to know wether a position is won, draw or lost with 100 % certainty (with 6 or less pieces). But many common (and complex) endgames have more than 6 pieces - such as King, Rook, 2 pawns vs King, Rook, 1 pawn totalling 7 pieces and the endgame tablebases are worthless. Many endgames are also very technical in nature and the large search depth does not really help if the engine does not know the technique. Furtheremore, there is the 50 move rule and the 3. time repetition draw rule that often comes into play in the endgames as well as zugswang and stale mate motives. So this area is really challenging in engine design. For instance doing a mate with bishop+knight vs king cannot be solved by search depth alone (at the current depths possible for engines) - there you need to know the technique (the W path knight stuff) so most engines have specialized code for that (or use a table base).

Most engines try to incorporate some special functions to deal with endgames. Often they will change the evaluation of the position - i.e. a king is usually more valuable in the center in the endgame, while in the opening/middle game you probably do not want your king in the center! So the engine will try to recognise the position and see if it is one of the endgame types that it has some special evalution code for and then execute it. Also usually an engine will have a list of endgames that are known to be drawish or known to be won for the stronger side. For instance opposite colored bishop end games are often very drawish. 

Also you can use a form of transitivity to determine if a position is won. For instance if you know that an endgame is won where the stronger part has a set of pieces, X, and the weaker part has a set of pieces, Y, then all other games where the pieces of the stronger part has at least X pieces and the weaker part has Y pieces are also won . An example would be that King+rook vs king is won - then you can infer that King+rook+pawn vs king is won and king+rook+bishop vs king is won and so on. This lets you build a pretty large collection of sets (X,Y), (X1,Y)...(Xn,Y) which you know are won. The engine can then evaluation any position that is included in one of the sets as a good position to reach. My engine uses this technique - it does not use the 6 men tablebases  (tablebases are not really any fun when you are a programmer - its just a huge database that you plug in - there is no challenge).

In general, the reason why endgames are still difficult for engines is because position evaluation is often more important here than raw search depth and as discussed in a previous part I do not believe engines are better at evaluating positions than super GMs. But no doubt - engines will probably catch up in this area. Since CPU power is increasing exponentially (Moores Law) it is probably only a matter of time before engines will also reign supreme in the end game. For sure, at some point in time we will have the 12 men-tablebase and that would cover pretty much all end-games. But it will take years and years  - I think the current estimate is that the 7-men tablebase is going to be finished around 2015....:-)

(part 6: final thoughts and a game)

  • zaifrun
  •  
  • | May 13, 2010 at 4:21 PM
  •  
  • | Posted in: zaifrun's Blog
  •  
  • | 4607 reads
  •  
  • | 4 comments

This will be my final part (so far I think) of this small series concerning chess engines. I started this project about a month ago and in that time I have managed to create a fairly strong chess engine (and still do the day-job - need money for food:-)). Its not quite up there with rybka, fritz and stockfish and those state-of-the-art engines. But considering the low amount of time I have put into this project I am quite satisfied with the result. I have played few blitz games with it myself and it has also played a longer correspondance game against a friend of mine rated around 1950. Based on those results I would say it has an ELO of somewhere in the range of 2150-2300 in rating - its a bit difficult to say exactly. With this rating it will place itself on the list of top 50 engines (low yes, but would be there! This list is recognised by most people as the closest to an official ranking of engines - see http://ssdf.bosjo.net/list.htm) I do not think its at either IM or GM level yet. Mainly because it is not that good in endgames and it is not fast enough which means it cannot reach a high enough search depth within a reasonable time frame. But optimizing algorithms and code for a chess engine is simply a never ending project - I will let the professional engine designers worry about that. For me it has been much more fun to create the engine - doing more optimizations to increase the playing strength are not really that fun I think - it feels too much like a real job, not a hobby! The engine is pretty good in tactical situations and is playing the middle game quite well and the opening book is decent enough. The main problem is the endgames - room for improvement there. 

I will finish the series with comments of a game it played against a friend of mine around 1950 (he knew he was playing my engine - I was not trying to trick him!). Some of the moves there are quite easily spotted as computer moves and I will try to explain (if I can) what caused it to make those moves. Hopefully, this will give you some insights as to why computers make those strange moves sometimes. Hope you had as much fun reading this series as I had creating the engine. To be honest, in fact this is not my first chess engine! In my teenage years I also created a chess engine (in the Pascal programming language) with an opening book and a graphical user interface for people to play with. But once the engine was out of the opening book it just selected a completely random legal move. I was not clever enough at that time to implement optimized recursive tree algorithms. So in a way by making this into a real playing engine (in Java this time around) I feel I have finally vindicated my younger self's lack of skills:-) I guess those 5 years at university was not a complete waste of time then:-)

In closing I will say that I think it does not really matter how strong engines become - chess will always be a fun and challenging game for humans even if we have engines with 4000 in rating. A game that has been around for about 1400 years is not fading away! It is the knowledge that your opponent or yourself could at any moment make a blunder and that it is so difficult not to make any blunders at all that is the fun challenge in chess. I think serious OTB tournament chess is the most difficult mental activity I have ever tried. As we recently saw in the Topalov-Anand match in the final game 12:  Even the best players around 2800 elo can blunder and are still influenced by nerves and other human emotions when playing.
Retrived from
http://www.chess.com/blog/zaifrun/creating-a-chess-engine-from-scratch-part-1

No comments:

Post a Comment