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.

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.