Today I will continue my posts on the design of a chess-playing FPGA. As you may recall, we have just finished going over the Move Generator in some detail, showing how it can select a "preferred" move from a given position. In my blog on game theory, I described how -- in general -- we can use the concept of a "Move Tree" to identify all the possible moves and counter moves from a specified position. Let's look at this concept in more detail now that we know how the Move Generator works.
The Move Generator thus far
The Move Generator, as we have defined it thus far, is organized as a cellular array of very similar combinatorial logic functions (except for some extra logic in certain cell locations to take care of any exception conditions, like an "Initial Pawn" that can move two squares forward from its starting location). We have a logic "cell" associated with each square on the chess board, thereby making the Move Generator an 8x8 array of logic functions.
The Move Generator considers all the pieces that can move and all the pieces they could capture (blank squares are considered "pieces" too) and identifies the "preferred" move -- that is, the move that results in the least valued piece on the FPGA's side capturing the most valued piece on its opponent's side (of course, the opponent could be another FPGA). This selection is performed as a combinatorial function and uses prioritization-like functions (similar to those used in more familiar interrupt-generation or bus-request logic blocks) to find the "preferred" move. This move is the main output of the Move Generator, with the "input" being the current state of the chess board (the collection of pieces loaded into the cells of the Move Generator) along with some control signals (like which side's move it is).
So far, so good, but we have only a portion of the logic we will need to implement the full algorithm that can play a good game of chess. Of course, we could simply use our Move Generator to select the "preferred" move as our move and a legal game would ensue, but in many cases this "greedy" strategy (just taking the opponent's biggest piece with our smallest piece) isn't sufficient to play a good game. It may be that not taking a piece will be the better move -- the act of positioning the pieces (threatening to capture or setting up a checkmate) can be more important. An example is shown in the diagram below. What move would the "greedy" algorithm select? What is the actual "best" move? Give this some thought before you continue with the rest of this column.
Example chess position -- white to move.
"In fact, the "greedy" algorithm would tell us to take the black queen with the white knight. This looks like a great move since we can capture a high value piece (a queen) with a lower value piece (a knight). If we just used our Move Generator logic and took the first move it generated, it would be just this move, but that would be a "bad thing" because there is a much better move -- knight to F7 is checkmate. In this case, irrespective of what legal move black makes, the next move will allow us to take the black king.
To Page 2 >
Tweet This
