Due to the complexity of this topic I have divided this post into two entries.  This article will discuss the Transposition Table and Zobrist Hashing techniques with no code samples.  The second part in the series will discuss the code used in my chess engine.

An Alpha Beta search will often have to consider the same position several times.   This occurs due to the fact that in chess there are many ways to reach the same piece arrangement.   For this reason most chess engines implement a Transposition Table that stores previously searched positions and evaluations.

The problems

The first problem is that although same chess positions do often re-occur during an alpha beta search, we can only count on having this happen somewhere between 15%-20%.  We can’t know which positions these will be ahead of time so for every 100 entries we save in our Transposition Table we might only use 20 entries.  Hence whatever Transposition Table scheme we choose, it has to be very efficient because we will be storing and searching more useless entries than useful ones.

In a perfect world we would have the ability to simply save every single node we search in our Transposition Table.  Unfortunately this is simply not practical.  The memory requirements for this scheme would be higher than most computers can accommodate.  Furthermore the time wasted on searching such a large table would outweigh any time saving benefits.  So we have to accept that our Transposition Table is limited in size will not store all the nodes we search.

Implementation

First we need to figure out how uniquely identify each position we come across.  This has to be extremely efficient since we will have to do this for every node in our search.  Simply converting the chess board to a string of values like FEN is far too slow. 

Zobrist Hashing

Fortunately for us a process for indexing game positions called Zobrist Hashing has already been invented by professor at the University of Wisconsin by the name of Albert Zobrist.

The Zobrist Hash uniquely representing our chess board will be a 64 bit variable.  In C# we can implement this as an unsigned long (ulong).  We calculate a chess boards Zobrist Hash using the following steps

1.       Generate an array of 12 * 64 Pseudo Random numbers representing each chess piece type on each of the 64 positions on a chess board.  You only do this once at when your chess engine initiates.  This will give you a single hash value for every single chess piece for every single position on the board.  You will have to elect which portions of the array represent which chess piece.  Let’s say you choose to have the first 64 entries in your array represent the white pawn.  So the 9^th value in your array will be White Pawns A2 square etc.

2.       For each chess piece on the chess board XOR its positions random number against the current Zobrist hash value.  So a white pawn on B2 might be the 10^th value in the array.

This is easy enough, however we don’t necessary want to calculate the Zobrist hash from scratch each time we make a move.  That would be very slow and would make the whole exercise futile.  For this reason each time a move is made on our chess board, whether during game play or alpha beta search we simply update the Zobrist Hash by:

1.       XOR the chess pieces previous positions random number against the current Zobrist hash value, this erases the chess piece from our hash.

2.       XOR the chess pieces new positions random number against the current Zobrist hash value adding the chess piece back to its new position.

A bit about the XOR operator:

If you don’t understand what I mean by XOR in the above paragraphs you may want to read this:

 XOR or Exclusive Or is one of the standard bit operators available to you in most programming languages.  By bit operator I mean it allows you to manipulate the individual bits in a value.  If you are not sure what that means, you might need to Google this first.  The one nice side effect of the XOR operator is that if you XOR a value 2 times by the same value it will return to its original value.    

For example

1110 XOR 1001 = 0111

0111 XOR 1001 = 1110

In order to add and remove chess pieces from our hash we will be using the XOR operator to add the chess piece to a position and then use the XOR again to erase it once it moves.  For example if we XOR the Zobrist Hash representing our chess board against the 64 bit number representing a white pawn on A2 it would be like adding the pawn to the chess board on A2.  If we do it again we remove or erase the pawn from A2.  We can than XOR the hash against the 64 bit value representing a white pawn on A3.  The last 2 operations would essentially move the white pawn from A2 to A3.

Collisions

Right about now you might have noticed that a 64bit value is not large enough to represent every single possible chess position.  So using the above scheme it is possible to have 2 different chess positions evaluate to the same 64 bit hash value.  This is called a collision and no matter how you implement this, you will always have a small chance of a collision.  The key here is to minimise the chance of a collision down to a small enough value so that the speed gain you get from having a transposition table (and perhaps constantly deeper search) outweighs the negative effect of the possibility of a collision.  In most chess circles a 64 bit value is considered to be large enough to make collisions not a practical problem.

Transposition Table Contents

So what goes in a transposition table entry?  Here are the items included in my Transposition Table:

Hash: This is a Zobrist Hash representing the chess position

Depth: The depth remaining in the alpha beta search.  So depth 5 would mean the score is recorded for a 5 ply search.  This can also be referred to as the Depth of the Search Tree.

Score: The evaluation score for the position.

Ancient: Boolean flag, if false the node will not be replaced with a newer entry.

Node Type:  There are 3 node types, Exact, Alpha and Beta.  Exact means this is an exact score for the tree.  However in the events that an alpha beta cut-off occurs we can’t use the score as an exact score.  An Alpha Node Type means the value of the node was at most equal to Score.  The Beta Node Type means the value is at least equal to score.

Replacement Schemes

Since your Transposition Table can’t hold all the moves searched in a game you will have to start replacing your entries fairly soon.   In the same time you don’t simply want to replace all entries regardless of their usefulness.  For this reason in the event that I find an entry that is useful (was used in a lookup), I set a Boolean flag Ancient to false, meaning doesn’t replace.  This way you always replace entries that are unused and keep the ones that were historically useful.  To prevent your table from filling up with Ancient nodes from 10 turns ago, the Ancient flag gets set to true for every entry after every search.

Table Lookup

The last problem we have to find is how to we quickly search a Zobrist Table.  We can’t just do a for loop.  This would be slow.  The trick is actually in how we store the entries in the first place.  Rather than simply adding an entry in the order we received them we calculate the entry index as follows:

Table Entry Index =  Hash mod TableSize

This way when we search the table to see if a certain Hash exists we know there is only one place it could be stored Table[Hash mod TableSize]

That’s it for this article on the Transposition Table.  Stay tuned for the next article that will discuss C# implementation.

It’s this time again.  The time where I realize that I made a poor decision somewhere in my design and a small portion of my code has to be re-written.

I already spoke about this briefly in this post.  Currently my chess engine will make all possible moves for a position ahead of time and evaluate each resulting chess board before entering Alpha Beta.  Although this gives me an almost perfect sorting algorithm (just sort the fully evaluated positions), on a whole this design is not very efficient.  The problem lies in the fact that often the algorithm will be evaluating moves that I will never explore due to an Alpha Beta cut-off.   Imagine having 30 possible moves, making each move, and evaluating the score of the resulting position, just to later find out there is a cut off in the 5th position.  This means that I have just evaluated 25 unnecessary positions.

The new design makes one move at a time and generates the next move only after the Alpha Beta call.  This means that I need a separate algorithm for sorting, choosing which moves to make first to give me the best chance for a cut-off.  This sorting is done by a tested algorithm called:

MVV/LVA Most Valuable Victim, Least Valuable Attacker.  This works exactly as it reads, a move where a pawn attacks a queen would be sorted first, king attacking pawn would be sorted last.

I have already implemented this new Alpha Beta and noticed a significant performance improvement over the previous version.  The current version with the new algorithm of Chess Bin Chess now searches to ply 6 (from 5) on Medium Setting and Ply 7 on Hard setting.  Although previously the Hard setting was already searching to ply 7 it was painfully slow.  On ply 7 I can now easily do one move per 30 seconds average.

I will be updating all of the posts with the newest version of the source code over the next few weeks.

Update January 19th 2010 - Well it took longer than I thought but all the posts are now updated to the new faster source code.  It took so much longer to debug all the code then expected.  I found so many mistakes, however I think now I have a fairly stable and bug free version.

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.

In this post I am going to discuss Forsyth-Edwards Notation (FEN) and its implementation in a chess engine.   FEN is a standard way of describing a chess position, containing enough information to restart the chess game from that position.  It is based on a notation developed by a Scottish journalist, David Forsyth in the 19th century.

Why is FEN useful to us?

1. We can use FEN to store game history allowing us to search for move repetitions as well as display the history of the game to the user.  Furthermore if we find a FEN position that has occurred in the past, we can skip searching for the best move and use the same response we used before.

2. We can use FEN strings to implement an Opening Book.    With two FEN strings I can store position pairs representing a starting position and the prescribed response.

The implementation of Forsyth–Edwards Notation

FEN notation uses only ASCII characters stored in a single line.  A FEN string or record contains 6 fields.  These are separated by a space.

• Piece placement from white’s perspective.  Each row is noted, starting from row 8 (blacks row0 and ending with row 1 (white’s row).  Each piece is described from column to column h.  Each piece is identified by a single letter. 

Pawn: P

Knight: K

Bishop: B

Rook: R

Queen: Q

King: K

White pieces are noted using capital letters and black using lower case.  So P would be a white pawn and p would signify a black pawn.
Empty squares (spaces) are described using numbers, each number representing the number of empty squares before the next chess pieces.  The number 8 would describe a completely empty row. 
The character / describes a new row.

So for a starting position we may see: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

• The second column in the Forsyth–Edwards Notation represents whose turn it is.  A single character is used w for white and b for black.
• The third column represents if castling is still allowed.  If neither side can castle then the character – is used.   Otherwise the following letters are used.  K means white can castle King Side, Q means White can castle Queen side.  Lower case k and q mean the same for black.
  
• The fourth column represents an En Passant target square.  The square that the pawn hopped to get to its row, or the position behind the pawn.  If there is no En Passant square then the character – is used.  So if the last move was pawn to e4, we will record e3 in this column.
  
• The fifth column contains the number of half moves since the last pawn move or capture.  This is used to determine the 50 move draw scenario.  
  
• The last column contains the full move number.  The number starts at 1 and is incremented after black’s move.

Examples:

FEN for the starting position:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

FEN after the white pawn moved to E4:

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

FEN after the black pawn moved to C5

rnbqkbnr/pp1ppppp/8/2p5/4P3/8/PPPP1PPP/RNBQKBNR w KQkq c6 0 2

And then after the white knight moves to F3:

rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R b KQkq - 1 2

Forsyth–Edwards Notation Code

In my chess engine FEN is implemented in two methods.  The first method will produce a FEN string for any chess Board.

The second method is a Board constructor that will accept a FEN string and create a Chess Board based on the content of the string.  Strictly speaking you will not need this code.  I only use this to allow people to enter FEN strings in the user interface.   Since FEN is a standard used in many chess programs allowing users to input FEN strings will allow them to visualize chess positions they might find on the internet. 

This concludes the post on Forsyth–Edwards Notation.  If you want to get started on creating your own chess engine download my C# Chess Game Starter Kit. 

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.   

This is the second re-design I am doing on the ChessBin Chess Engine.  You can read all about the first one here, so you don’t make the same mistakes as me.  I guess that is what you get for re-inventing the wheel.  At least I am still having fun. 

This re-construction is related to how my chess engine stores the chess board.  Currently the chess board is described as a two dimensional array.  This way with a column and row you can locate any square on the board.  This is makes my chess engine easy to understand but slow. 

The new design will modify the chess board to be a single array of 64 squares.  This makes it necessary to refer to board positions via an index.  An index of 0 will locate the top left most square on the board and an index of 63 will locate the bottom right one.  This also allows me to drop the entire Position struct as it is no longer necessary to describe the position by two bytes. 

The new version of my ChessBin chess engine that I am currently testing is about 25% faster due to these changes.

I will be modifying each of the posts and the development kit over the next few weeks.  Stay tuned for updates.

Updated April 22nd 2009, I have finished updating all of the posts and the Chess Game Development 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.