As part of my ongoing project to design a chess-playing FPGA, I will describe some of the logic used to determine the best move from a specific position on the chessboard. This will -- perhaps surprisingly -- be a fully combinatorial implementation.
Building on the parallel implementation of the move generator block from my previous post, I will begin to describe the logic used to implement a portion of the move generator. In particular, I will focus on the logic used to determine the value of the best move for a particular square. I am using a cellular approach to the design, so this logic will be replicated for each of the squares, organized as an eight-by-eight array, just like the game board.
Generating moves -- a fully combinatorial implementation
The algorithm being used to identify the best move into a specific square is fairly simple. The logic will examine all the possible attacks by enemy pieces into the square. The attacking piece with the smallest value is assumed to be the best aggressor, since it is usually better to capture an enemy piece with the smallest piece you can. For example, you would rather capture a rook with a pawn than with your own rook, in case the enemy rook is protected. The value of a move is thus the difference between the value associated with the piece in the square and the value associated with the smallest available aggressor.
There are a few possible implementations of this logic. A sequential implementation might scan all the possible aggressors, select the one with the lowest value, and subtract its value from the value of the piece in the square. It might take several clock cycles to do this, but the process is fairly simple.
An alternative approach would be to use combinatorial logic and perform all of the comparisons in parallel. In this case, we would examine all the possible aggressors, compare them (using a priority function similar to that used in interrupt generation in MCUs), and select the lowest-valued aggressor. To generate the best move value for this square, we would simply subtract the selected aggressor's value from the square's piece value -- something easy to do with combinatorial logic. A block diagram showing the key signals coming into the square is given below. N stands for knight. The letters associated with the other pieces are easy to decode.
Best move logic for one square of the chessboard.
The logic in the squares near our example square will generate aggressor signals that can be used by our combinatorial logic block. (I will describe the process for generating these signals in my next blog. For the moment, let's just assume they are available.) The square below and to the right of our square could generate an attack from a pawn, a bishop, the queen, or the king. Only one of these pieces could be the attacker at any given time, because only one piece can occupy a square at a time. This can be used to simplify the comparison logic. Usually, the values associated with the different pieces are something like this:
In our example, if a pawn were attacking from below and to the right, and a rook were occupying the example square, the best move value from that direction would be 5 - 1 = 4 (rook minus pawn). Our combinatorial logic could be duplicated to perform similar calculations from all the other directions (upper left, upper, upper right, etc.), and a central comparison could combine all eight directions to arrive at a final best move value. That value would be produced as an output from the block, and it would be combined with outputs from the other squares, perhaps initially by comparing eight squares at a time (maybe on a column basis) to obtain eight intermediate results. Those results would be compared to determine the best move value for the entire board.
Now, it would be helpful to compute some housekeeping data at the same time. Eventually, we will want to identify the pieces that are the aggressor and the victim for the best move value. That's because we will want to modify the board by moving the aggressor piece to the victim square while we traverse the game tree (as we discussed this month) by making the series of moves created by the move generator.
These additional details will be described in the next blog. Until then, think about what other information we will need to traverse our game tree and make alternating moves by the black and white pieces as we try to checkmate our opponent.