In this column I will continue my posts on a chess-playing FPGA, which was introduced in a previous blog. Now that we have a Move Generator and an Evaluation Function, how do we use them to traverse the tree of all possible moves to determine the best move from a given position? Is there something important missing from our Move Generator?
Hopefully, you will remember my earlier blog on Game Theory, in which I demonstrated how chess (most two-player games, in fact) could be treated as a game tree with each node representing a position on the board. We can repeatedly generate all the possible moves (using our Move Generator) at each node, resulting in a very large tree structure that must be explored to some target depth. This target depth depends on how quickly we can generate moves since we only have a fix amount of time -- usually just a few minutes -- for each move. At the "bottom" of the tree, the resulting positions are evaluated (using our newly defined Evaluation Function) so we can determine whether or not a position is "good" for us. We weed out the bad positions, focus on the good ones, and "roll" the end position evaluations back up the tree to determine which initial move will result in the best "pay-off" (the best value at the terminal node).
How do we actually traverse the game tree? Is something missing?
Thus far we have discussed the Move Generator and the Evaluation Function separately, but we have not yet figured out how to use them (as functional blocks) to help traverse the game tree as described above (and in more detail in my blog on Game Theory). Let’s pick a good example position to consider how the Move Generator and Evaluation Function can work together to traverse the Game Tree starting from the initial position:
White to mate in one move.
If we load the above position into our Move Generator, we will identify the "best move" as being "hardwired" into the design. The FPGA logic looks for the biggest capture it can make using the smallest piece (the best "trade" in value). In some cases the first move made by the Move Generator may actually be the best move; in other cases, however, there may be a better, less "greedy" move that results in an even better position (or a win) later on. With our example position above, the Move Generator will identify that the knight can capture the queen and that is the move generated. Unfortunately there is an even better move! Can you see it?
Well, if white moves the knight to F7 (column F and rank 7), this results in checkmate! The black king has no safe escape route and black can’t capture the knight. Game over! Now how can we find this move if the Move Generator has prioritized the queen capture first? That is, how can we make sure that we traverse the rest of the Game Tree?
Well let’s think about adding a little more logic to the Move Generator so we can find other moves, hopefully still in priority order. What we need to do is "mask out" the move we first find (our "best move") so that we can identify the "next best move." We can borrow an idea from a common microcontroller (MCU) function -- the interrupt controller -- to help us figure out how to make our required change.
To Page 2 >
Tweet This
