Now that we have discussed the basics of Alpha Beta we can add some small modifications to increase the strength of our move searching and solve the problems of the Horizon Affect

Horizon Affect

The Horizon Affect is a problem that affects every chess engine whose search depth is limited to a certain depth or ply.  The Horizon of what your computer chess engine can see is set by the ply or depth limit on the Alpha Beta Search.  If we asked the computer to examine 5 moves then the computer will not see that the sixth move made by the opponent will possibly be detrimental to its position.  This is especially problematic when we start considering the long exchanges of chess pieces that often occur in a chess game. 

There are two ways to battle this problem.  The first solution is a simple hack.  The trick is to make sure that we always ask the computer to search to an odd ply or depth.  This means that the last move the computer will always consider will be the opponents move.  This very easily prevents the computer from leaving hanging or unprotected pieces.
 
However this odd ply solution does not solve the issue related to long exchanges.  During the middle game opponents will often build up an attack and defense of a weak piece located in a crucial position such as the center of the chess board.  It is not unusual to have a center pawn both protected and attacked by 5-6 chess pieces, including knight’s pawns bishops and even queens.  If your chess engine is limited to 5 or even 7 ply, it will never be able to search these exchanges to the end.  This means your chess engine will never know if during the course of the piece exchange it will come out on top or lose an extra piece.  To solve this issue most chess engines implement what is called a Quiescence Search.  

Quiescence Search

The word Quiescence means calm or still.  Quiescence Search in computer chess terms simply means searching for a calm position. 

The idea behind a Quiescence Search is simple, once your reach your horizon, the last ply you will search, perform a deeper search considering only moves that capture other chess pieces.  This deeper search occurs in the same Alpha Beta algorithm.  Now you might think that this will significantly slow down your search.  In practice however this is not the case.  First not every single move is evaluated, only captures so there are much fewer moves to evaluate.  Second with every single ply searched more pieces are captured and there are even less moves to evaluate.  Very quickly you will often end up with 0 possible captures a few ply down.  Third captures often make for very good beta cutoffs in our Alpha Beta.  At most your quiescence search should not take more than 10-20% of your search.  The difference in the accuracy of your search algorithm however is much higher than 20%.  Implemented correctly you will see a significant improvement in the strength of your chess engine.

Extensions

Extensions are a fairly simple concept.  An extension will allow your Alpha Beta to search deeper by 1 ply if the position is especially interesting.  Interesting positions can be checks or really valuable captures.

Extensions are really needed if your Alpha Beta search is limited to a shallow search such as 5 ply.  The usefulness of Extensions diminishes with the increase of the depth of the main Alpha Beta Search. 

First I will list the modified Alpha Beta code that makes use of Extensions and Quiescence at depth 0.

I would like you to notice that in the call to Alpha Beta now has a Boolean variable called: Extended.   No matter what we only want to extend the depth of the search a maximum of one time per leaf of the search.  Else we run the risk that the search will continue to perform extensions indefinitely.  For this reason once we start one of the extension we will set the Boolean value to true, preventing it from occurring again.

Here is the listing for the Quiescence Search method:

You may have noticed that the Quiescence Search uses a new method called EvaluateMovesQ.  This method is virtually the same as the previously discussed Evaluate Moves except it only collects moves that capture.

During the Quiescence Search we will often reach a position where no more captures are available.  Hence there will be no positions to evaluate.  For this reason we have to add the following line of code:

This last piece of code that I want to explain is called the Stand Pad.  It’s just a complicated way of saying that during the quiescence search we will set a default value for alpha that is equal to the board being examined.  It just prevents you from examining moves that make your situations worse than it already is.

That completes the post on Quiescence Search and Extension.  If you have any questions about this post feel free to post a comment below.  Chances are someone else has the same question and I would love a chance for improvement.

Over the last year of development of my chess engine, much of the time has been spent optimizing my code to allow for better and faster move searching.  Over that time I have learned a few tricks that I would like to share with you.

Measuring Performance

Essentially you can improve your performance in two ways:

• Evaluate your nodes faster
• Search fewer nodes to come up with the same answer

Your first problem in code optimization will be measurement.  How do you know you have really made a difference?  In order to help you with this problem you will need to make sure you can record some statistics during your move search.   The ones I capture in my chess engine are:

• Time it took for the search to complete.
• Number of nodes searched

This will allow you to benchmark and test your changes.  The best way to approach testing is to create several save games from the opening position, middle game and the end game.   Record the time and number of nodes searched for black and white.
After making any changes I usually perform tests against the above mentioned save games to see if I have made improvements in the above two matrices:  number of nodes searched or speed.

To complicate things further, after making a code change you might run your engine 3 times and get 3 different results each time. Let’s say that your chess engine found the best move in 9, 10 and 11 seconds.  That is a spread of about 20%.  So did you improve your engine by 10%-20% or was it just varied load on your pc.  How do you know?  To fight this I have added methods that will allow my engine to play against itself, it will make moves for both white and black.  This way you can test not just the time variance over one move, but a series of as many as 50 moves over the course of the game.  If last time the game took 10 minutes and now it takes 9, you probably improved your engine by 10%.  Running the test again should confirm this.

Finding Performance Gains

Now that we know how to measure performance gains lets discuss how to identify potential performance gains.
If you are in a .NET environment then the .NET profiler will be your friend.  If you have a Visual Studio for Developers edition it comes built in for free, however there are other third party tools you can use.  This tool has saved me hours of work as it will tell you where your engine is spending most of its time and allow you to concentrate on your trouble spots.  If you do not have a profiler tool you may have to somehow log the time stamps as your engine goes through different steps.  I do not suggest this.  In this case a good profiler is worth its weight in gold.  Red Gate ANTS Profiler is expensive but the best one I have ever tried.  If you can’t afford one, at least use it for their 14 day trial.

Your profiler will surly identify things for you, however here are some small lessons I have learned working with C#:

• Make everything private
• Whatever you can’t make private, make it sealed
• Make as many methods static as possible.
• Don’t make your methods chatty, one long method is better than 4 smaller ones.
• Representing your chess board as an array [8][8] is slower then representing it as an array [64]
• Replace int with byte where possible.
• Return from your methods as early as possible.
• Stacks are better than lists
• Arrays are better than stacks and lists.
• If you can define the size of the list before you populate it.
• Casting, boxing, un-boxing is evil.

Further Performance Gains:

I find move generation and ordering is extremely important.  However here is the problem as I see it.  If you evaluate the score of each move before you sort and run Alpha Beta, you will be able to optimize your move ordering such that you will get extremely quick Alpha Beta cutoffs.  This is because you will be able to mostly try the best move first.

However the time you have spent evaluating each move will be wasted.  For example you might have evaluated the score on 20 moves, sort your moves try the first 2 and received a cut-off on move number 2.  In theory the time you have spent on the other 18 moves was wasted.  

On the other hand if you do a lighter and much faster evaluation say just captures, your sort will not be that good and you will have to search more nodes (up to 60% more).  On the other hand you would not do a heavy evaluation on every possible move.  As a whole this approach is usually faster. 

Finding this perfect balance between having enough information for a good sort and not doing extra work on moves you will not use, will allow you to find huge gains in your search algorithm.  Furthermore if you choose the poorer sort approach you will want to first to a shallower search say to ply 3, sort your move before you go into the deeper search (this is often called Iterative Deepening).  This will significantly improve your sort and allow you to search much fewer moves.

Now that we have all the necessary parts for keeping track of our chess pieces, generating valid moves and searching for the best computer move, we are ready to put it all together and complete our chess engine.  We have already started to discuss the chess engine class in the previous post titled: Starting the Chess Engine.  Just to recap that post we have already:

Declared the class as:

Declared its internal members representing our chess board and the previous chess board as well as variables representing whose move it is.

Declared a constructor that will initiate the chess board, move history, pre-calculate all possible moves from all positions, register starting positions of a new chess game and calculate all valid moves from that position.

Since we now have discussed the Chess Board Evaluation class I will modify this listing slightly to evaluate the board score as its last operation.

We also created a Move Piece method that will allow us to move chess pieces around the board.  The important fact to notice here is that if the move fails, say because it would cause an invalid position, the chess board reverts to its previous state.

That’s it for the review now onto the remainder of the code needed for our chess engine to successfully play chess.

First we will introduce a few public variables:

We want to know which side of the board contains the human player.

We need to know how deep to perform the AI search, how many plies. Remember each ply is a single move.  So if white moves that is one ply, if black responds that is two ply.

We also would like to keep track of all of the moves made during the game.  This will solve two problems.  First in order to call a draw for a three move repetition we need to somehow know what moves have been made.  Second we might want to be able to display the move history to the human player as we go along.

First we need to declare the OpeningMove class:

The next method will add moves to the above declared Current Game Book as they occur.  This method also searches the Game Book to see if a repeat move has occurred.  Notice the use of FEN notation to store the chess board history.  More on FEN notation in the next post.
Now we have a mechanism for testing for 3 move repetition.  Remember our chess board class already handles the 50 move rule.  The last step is to create a method that will check for mate scenarios, check and stale.  This method takes advantage of the code we already wrote in the Move Search class that checks for all available moves and records if the king has any moves not in check.

The last method will make the chess move for the computer as well as check for mate, and save current game moves.  This is the method our external user interface calls when we want to get the computer to make the move.  Otherwise if the human player is moving you would just call the move method.  Notice that the check for mate method is called two times.  Once before the move is made and once after.  This is because the previous human move might have caused a mate (first call) or the computer move might have caused a mate (second call).
The above methods are all you need to start coding your chess user interface.  However because we have declared most of our variables as private or internal if your user interface is in another assembly you might need a few additional methods that will expose certain properties of your chess board and chess engine.  I have included some of these below.

Notice this method will check for all game ending scenarios including 50 move and 3 move repetition.

This post is a bit of a milestone as it wraps up the bulk of the chess engine source code.  There are still a few points I have not discussed such as an opening book or some more advanced search features such as Quiescence, FEN, Pondering, Iterative Deepening or Principle Variation Search.   However the sum of the code posted thus far will provide you will a working chess engine that will play fairly good chess.

If you feel like you don’t want to start typing up all the code posted here, I have made available a C# chess engine starter kit that includes most of the source code you will need to start a chess engine including a simple user interface.  You can download the development kit from here.

Last time I discussed Min Max and the Alpha Beta algorithms.  However you might have noticed that the algorithm I showed last time does not really tell you which of the available moves is the best, but rather which was the best score out of all the available moves.  To figure out which resulting chess board is the best I have implemented another method called Alpha Beta Root.

Alpha Beta Root is very similar to the regular Alpha Beta Method with the exception of keeping track of the best board found so far.  Alpha Beta Root is also our entry method into searching; it calls the regular Alpha Beta method.  You pass it a chess board and it returns Move Content containing the best move you can make.  Alpha Beta Root does not also need to perform a Quiescence Search since it is already performed in the regular Alpha Beta method.

The code below can be divided into 3 sections.

1. Initial examination of what legal moves I can make and what their resulting score is.  This is followed by a sort to give us the best chance of trying the best move first
2. Initial 1 ply call of Alpha Beta to see if there is an instant check mate so we can exit.
3. Regular Alpha Beta call.

Before we get started we will need a helper struct to keep a list of our starting positions.

Now onto the main Alpha Beta Root Method:

The obvious question might be why do we do this?  Why not simply copy the best board in the regular Alpha Beta method and return it.  The simple answer is performance.  Because the regular Alpha Beta method is recursive we want it to be as fast as possible.  It is much faster to copy integers rather than calling the copy constructor for the board object.

One last piece of code that I would like to add here is the Modify Ply method.  One thing I noticed while testing my chess engine is that during the end game my engine made moves at a much faster rate than it did during the opening and middle game.  This had a very simple explanation as during the end game there are far fewer chess pieces and there are less moves to calculate.  For this reason I added a small method to that adds 2 plies to my search if there are less then 6 root moves on the board.  This way I can search deeper during the end game, increasing my odds of finding a check mate.

If you have any questions about this post feel free to post a comment below.  Chances are someone else has the same question and I would love a chance for improvement.

If you want to get started on creating your own chess engine download my C# Chess Game Starter Kit.   

Out of all of the computer chess programming concepts I discussed on this website I found move searching to be the most complicated for me to understand, and the most time consuming to write.  Until this point all of the concepts of writing a chess engine were easy to understand.  Most developers will figure out some way of representing chess pieces, chess board and movement.  However I found that move searching is not like that.  Reinventing the wheel by writing your own move search algorithm is just not a good idea.  There are algorithms that you just have to implement for your engine to have a shot at searching enough moves to simulate even average chess playing.

Min Max & Negamax

Probably like most people starting to program a chess engine I started by looking at implementing the Min Max algorithm.  The idea is fairly simple, I look at all my moves I can make, evaluate them and make the best move.  Then I do the same for the opponent from his point of view. 

This led me to some really crappy code that did not really work very well.  Actually what I found out later is that min max works by going deep into the furthest leaf of the search tree and working backwards.  That’s not the same thing as going from the top down because what ended up being a spectacular move 5 nodes down could have been a really crappy move at the beginning.  A good example of this is a chess piece sacrifice to get a check mate.  So I look to all the possibilities of every move I can make along with all of the moves my opponent can make work backwards and I choose the root move that will get me the best score at the end.

The above Mix-Max implementation is not actually used anywhere in my chess engine, however I wanted to make sure it is we understand how it works before we move to the actual implementation of Alpha Beta. 

The first point I would like to make about the above code is that the algorithm is recursive.  It will call itself up to its furthest leaf and then return the score back to each parent branch so that the branch can evaluate which leaf was the best back as many levels as we decide are needed. 

The second point on the above Min-Max implementation is related to the depth variable.  It will set the limit of how far should our algorithm search.  This is often referred to as ply.  One ply equals one move by either side.  So if we set our algorithm depth to 1 ply the Min Max algorithm would simple search one move deep and return the best move available to the current side.  A depth 2 or ply 2 search would search each possible move and each possible response to every move. 

Furthermore the above algorithm is actually a variation of Min-Max often called Negamax because as mentioned above it always looks for the maximizing score rather than having to branches looking for either the maximum or minimum value depending on the chess piece color moving.

There is however a trick to implementing Negamax.  The issue is that the algorithm has to always look for the highest score, so we will need a helper method to help us out here by inverting the score for black. 

This above method is key, since without it your algorithm would not return the best move for black but rather the worst, highest scored. 

If we you had tried to implemented this algorithm in your chess engine you would find that move searching was probably very slow.  It was probably ok down to ply 3 or 4

Alpha Beta

The next evolution of my search algorithm was Alpha Beta. It took me of weeks reading articles on min max and alpha beta trying to fully grasp exactly was has to be coded and why it works.  

The main idea behind Alpha Beta is the fact that we don’t need to search every possible move.  Some moves just do not make sense. 

Let’s imagine your opponent has 5 bags of items.  You get to keep one of the items from one of the 5 bags.  You get to choose the bag, however your opponent will get to choose which item you get. Your opponent does not want to give away his valuable items so he will choose the one that is least valuable to you.  So you must choose the bag where the least valuable item is more valuable than the least valuable item in all of the other bags.

So let’s say you open the first bag and you look inside.  You see a gold ring, a diamond and a shovel.  You know your opponent is not going to give you the gold ring or the diamond.  If you choose the first bag you will end up with a shovel.  The shovel is the least valuable item in that bag you remember that for later.

So you look into the second bag and you see a laptop computer.  This is more valuable than a shovel, so you keep looking.  However the second item is a clump of dirt.  Dirt is less valuable than a shovel.  So you don’t need to keep looking through the other items in that bag, because you know that whatever else you find in the bag even if it is more valuable you will just end up with dirt.   Instead you can move on to the next bag and keep looking for something better than a shovel.

This is how alpha beta works.  You stop looking for responses to your move (bag) when you find one that has a worst result than the worst result from your previous move.  The name Alpha Beta refers to the two variables that you will pass around the algorithm that will keep the best scores for you and your opponent (The Shovel)

The main advantage of Alpha Beta is that it is free.  It does not affect the quality of the moves made by the computer.  It simply discards moves that would not have been considered anyways. 

One additional note I would like to make is that Alpha Beta works best when the moves are sorted in the order of best first.  If we think of our example above it is in our best interest to find the bag with the shovel first before finding the bag with the clump of dirt.  If you had found the clump of dirt first you would still have to look through all the other items in the second bag.

For this purpose it is in our best interest to sort the moves prior to trying Alpha Beta.  For that we need to declare a few methods.

Evaluate Moves

Evaluate Moves is a pseudo move generator and an evaluation function combined.  It organizes all the valid moves for a position into a list of positions and assigns them a score based on a very basic evaluation.  We don’t use this evaluation score to make any serious decisions we just use it to sort our moves.  You may be tempted to use your regular chess board evaluation function here.  This would improve sorting quite a bit, however a full evaluation is slow and there would be allot of wasted effort because you don’t need the actual score of the chess board until you get to depth 0 (the last ply you are going to look at).  In my tests I found that doing a simple sort based on a score resulting from Most Valuable Vitim Least Valuable Attacker, performs quite well.  Basically the idea is that you want to try a pawn attacking a queen before you try a queen attacking a pawn.  I achieve this by subtracting the values of the attacker and defender.  This generates lots of node cut-offs.  In addition to MVV/LVA I add some small easy evaluation points for castling moves and Piece Action Value.

Evaluate Moves stores its results in a List of Positions.  

Evaluate Moves also requires a helper sort method.

The actual Evaluate Moves method loops through all of the chess pieces on the board and records the source position and destination position of the move along its pseudo score.

Now for the actual implementation of Alpha Beta. 

In our chess engine we need to introduce the concept of the variables alpha and beta.  These will be used during our recursive search to affectively keep the leaf score during our search.  This will allow us to make the decision of whether or not we need to continue or we can cut the search short and return.

• Alpha will be the current best score for this leaf. 
• Beta will be the best score for the upper leaf thus far or the opponent’s best score for positions already searched.

If Alpha > Beta, meaning my move is better than my opponents other best move thus far we have reached the scenario where searching other moves are not relevant because a Shovel is better than clump of dirt.

Here is the Alpha Beta code from my chess engine

As you see this code is almost identical to the Min-Max code above with the exception of move sorting as well as the Alpha and Beta variables.  Furthermore if we do find a cut-off (alpha > beta) then we simply return beta as the best score.

Initially the Alpha Beta method is called with Alpha being the smallest possible integer and Beta being the highest possible integer.  This ensures that we search at least one move all the way down to its last ply before performing any cut-offs.  In the next post I will discuss how to make that initial Alpha Beta call from my chess engine and some of the other modifications of Alpha Beta that will improve its speed and accuracy.

Before we can discus move searching and the Alpha Beta algorithm we need a way to check for check mates.  This method will actually be located in our static Search class.  This method will loop through all of the moves for all the chess pieces on the board and see if they actually have a valid move.  If they do then we are not in a check mate situation.  If there aren’t any valid moves for this board position that we know that this is either a check mate (if the king is in check) or a stale mate.

This method is very expensive to execute so we only call it if there is a check on any king on the board or if there are 0 possible moves.  I will explain in more detail in my Alpha Beta method.

The Search for Mate method returns true if a check mate or stale mate is found. The actual values of type of mate and side mated are stored in the three reference variables passed into the method.

The Search for Mate method is also used in your Chess Engine Make Move method which will check if the last move made by the human player caused a check mate.  This will be done every time a player makes a move.

That’s it for this post.  If you have any questions feel free to email me or post a comment below.  Chances are if you have a question, other people might have it too.