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.

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.