This document serves to outline the logic and implementation of common chess engine technical functions. 

____________________________________________________________________________

Bitboards:

Bitboards are 64 bit board representations which can be combined to form a full chess board. The board is composed of 15 bitboards, one for each piece of each color, two for all white and black pieces and one for all occupied squares. This board representation is not intuitive and the move generation is even less so, but hopefully, this tutorial will explain it in sufficient detail. 

How it Works:

Modern processors are exceptionally efficient at x86 instructions. Therefore, doing bit operations on bitboards are very fast. Not only that, but as you’ll soon see, the logic of move generation on bitboards means that we can compute many different piece moves in parallel. For example every pawn move for all black pawns can be calculated in the same time as it takes to get the moves for any one black pawn. I will expect you to have a solid understanding of the fundamental bit operations like bit shifts, xor, and, union, and bitscan. Let’s start with a simple example. Say we wanted to generate only the moves for a pawn with no available attacks and who has already moved during the game. To calculate that pawn's one pushing move we need two things: a bit board with only the pawn we want to generate moves for, and a bitboard containing all occupied squares. Now if we bitshift the bitboard containing our single white pawn 8 units to the left and use the and operator with the opposite of the squares occupied bitboard. The resulting bitboard will contain all pseudo legal moves for that pawn. Now if we also want to generate moves for a pawn who has yet to move we need to calculate the single push, but also the double push. If we first bitshift the pawn by 8 and then check against the occupied squares like we did before we will have our board with the single pawn push. Now we can union that board with a new bitboard we generate using the exact same logic as the single push. You can see how we might generate the attacking moves for our pawns as well using that same simple logic. Knights and kings work similarly to pawns, but sliding pieces get a little more complicated. In order to quickly generate moves for a sliding piece we can’t calculate from scratch its possible lines of attack the way we do for pawns. It would be far too slow. So, when the program starts up, we precompute all ray attacks in each direction for each possible square assuming there are no other pieces on the board. Then to start the move generation we just get the precomputed attacks for the piece (Queen uses a union of bishop and rook attack patterns which themselves use a union of the different precomputed ray attacks). The next step is a little complicated. Because the bit shifting arithmetic is difficult to verbally explain so I feel obligated to link to the chess programming wiki and their explanation of sliding piece movement (https://www.chessprogramming.org/Classical_Approach). It works like this for a rook:

1. Foreach ray attack (up, down, left, right)
   1. Intersected Board = Occupied Squares & Ray Attack (results in only the intersected squares)
   2. Blocked Board = Ray Attack xor bitscan_forward(Intersected Board)
   3. Final Attack = Ray Attack xor Blocked Board
2. Foreach Final Attack
   1. Total Move union Final Attack
3. Total Move xor Friendly Pieces

Minimax with Alpha Beta:

Due to the fact that I do not want to, I won’t be going into detail on the Negascout because Minimax is easier to explain. In a two player game each player is trying to make the optimal move knowing that his opponent will also try to make the optimal move. You can image that each player is trying to find the best position they can reach regardless of how perfectly their opponent plays. In chess, the “score” or evaluation is positive if white is winning and negative if black is winning. Now you might be able to see why the algorithm is called “Mini” “Max.” White looks for the highest evaluation and vice versa. Imagine this node tree (each node is the evaluation of the position after each move):

                                                                                                                                     0

                                                                                                       4                                                               -5

                                                                                 3                                        -6                          4                           2

                                                                           -5     9                               -8     -15              5     8                -1      2

White goes first and sees that the highest score he can end up with is 9 and so naturally he would want to take the path which approaches the 9 value. However, white is a smart player and knows that if he takes the path to get to the 9, black will want to minimize the score. Black will take the path which leads to an outcome of either -8 or -15. White would really not like this outcome so he can’t take that path. White does see that if he first goes to the -5 node, black can’t guarantee any negative score. Even if black choses the 2 value node where the below options are -1 and 2, white will easily choose the score of 2. Therefore white decides to take the path to the -5 node. Black sees that if he chooses the 4 node white will obviously choose the 8 value node and so black goes for the 2 value node instead. White likes this idea and choses the 2 value node at the end of the tree. White has won the position and is winning the game!

This is a perfectly good way to find the best move in any position. In our simulated game, each node only had two children, but in chess each node has around 40 children. That means that after only 3 steps of generating this node tree, insead of 8 possible positions, we get 64,000! And just one more iteration later and we reach 2,560,000 positions. We clearly can not search all these nodes, so we need a technique that allows us to skip some nodes. After all, when you play chess you only consider positions which are not obviously bad, so we can teach our computer to not search positions which are obviously bad too.

Alpha Beta Pruning:

Let's consider another node tree:

                                                                                                                   0

                                                                                       4                                                              -5

                                                                    5                                      -6                        -1                            -2

                                                                6      12                          -7      -15            1       -3                  -5    0

White goes first and starts by checking the value -5. He sees that black will want to go for the -2 which will leave the position at 0. Next white looks at the 4 value node. He sees that black will counter with the -6 node and then he looks to see that he could end up with -7 at best. Now we don’t even need to look at the value 5 node because white will still avoid this position either way because black can ganentee himself a -7. There is no possible value under the 5 value node which will change white’s decision. If he goes right he can at least get a score of 0 so there is no need to further evaluate the left side because he knows that at least black can guarantee a score of -7.

Move Ordering: 

For alpha beta to be most efficient we want to check the best possible moves for each player as soon as possible. However, we can’t know how good a move is until we trace it all the way down the node tree which would completely negate any effect of more ordering in the first place. However, a pawn taking a queen sounds like a good move in most situations. In fact, a piece of lower value capturing a piece of higher value is almost always a good idea. So if we search moves that are good captures first we will be able to prune far more moves as most moves will be weaker than the good capture. This is the essence of move ordering, the ability to put the best moves first. There are many ways to order moves, but in Linear Chess, I use the static exchange evaluation and the history heuristic. 

The static exchange evaluation describes the difference in value between the attacking piece and the target. The larger the static exchange value, the closer the move will be to being searched first. 

The history heuristic is slightly more complicated. When the program starts up a table is created with indexes for each possible type piece of at each possible position for each possible target. The array is a int[12][64][64]. When a move causes a beta cutoff, we increment the table like this: History_Table[pieceType][startSquare][targetSquare] += (depth * depth). We use depth * depth to ensure that moves close to the end of the tree don't count for as much because they are less likely to have a correct evaluation. Then we order moves based on their history and check them in order after all good capture moves. Then we check all bad captures after history moves.

Transposition Table:

While not yet implemented in Linear Chess, a transposition table is an invaluable resource for speeding up a search. The transposition table is a hash table that stores the best move at any possible board position which we have already examined. Then if we see that a position has been reached that is contained within the hash table, we just do whatever move was stored in the table for said position (as long as the depth to evaluate that move is greater than the current search depth). To store entries in the hash table we need a unique key for every possible board position. Zobrist Hashing is a very good way of doing this. We initialize a table of random values for each piece at each position as well as en passant and castling rights. Then, foreach piece on each square of the board, we xor their respective values from the table of random values. Finally we modulate that value by the size of the hash table (a very fast hashing function) to get our hash key. This Zobrist Hash key is incrementally updated as moves are made and unmade to save time. In the hash table we store the best move, the depth to which that move was searched, the age of the entry, and a flag concerning the type of entry (PV, Hard Fail, Soft Fail).