In this column, we will continue our discussions regarding the design of a chess-playing FPGA. As you may recall, in my previous blog, we looked at a couple approaches to implementing the Evaluation Function (i.e., how we value the board when we can't search any further into the game tree) using many adders to sum the piece values on the board. This seems like an expensive (in hardware) approach, so it might be best to revisit the implementation taking a different look at the problem.
Rethinking the Evaluation Function
Instead of finding a way to calculate the value of all the pieces on the board via use of an adder at each square to gradually sum up the value of all the pieces on the board (kind of a snapshot of the piece value), maybe we can use the fact that the total piece value only changes when a piece is captured to keep an ongoing record of the board value such that we don't need to compute it each time. (This is similar to an approach taken when many analog-to-digital (A/D) conversions are captured as the front-end process in a control function.
Each time a value is captured from the analog-to-digital converter (ADC), we can add its effect to the previous calculation (this is very common and convenient in filter functions) so we don't get stuck with a long calculation after we fill our capture buffer. Many times, we can overlap the wait associated with the conversion with the processing needed to add the previous capture to the function we are calculating, thereby dramatically improving processing efficiency. In our case, each capture will subtract a value from the board, which means that it's only during a capture event that we need to update the board value. Whenever we wish to evaluate the new board value, we will have an accumulator with the current board value handy.
As usual, there are a few special cases we need to consider. For example, we need to account for pawn promotions, where a positive value is added to the player who is making the promotion move, but this should be fairly simple to implement. We also need to make sure we can put pieces back as we move around the "move tree" and take back a capture move. Again, this shouldn't be too difficult. The hardware needed for this approach will be just an accumulator and an adder-subtractor. This is much less hardware-intensive than the previous approaches we discussed in which we required adders at every square of the board. In the case of our new solution, we just need a single adder for the entire board! This seems like a good improvement to me.
Now, let's figure out how many bits we need for our board value and any other requirements we need to place on the Evaluation Function. Piece values will be important. Typically, a queen is 9 points, rooks are 5 points, bishops and knights are 3 points, and pawns are 1 point each (unless they are promoted as discussed on the next page). The king should have the maximum value possible, since if you take it you win. So what's the maximum value of pieces (excluding the king) that we can have?
To Page 2 >
Tweet This
