Periodically I will take a break from my interviews with programmable technology experts to post about other topics that I think might be of interest to readers.
In this post, I will continue the first of these topics, introduced in my previous blog, the definition and design of a chess-playing FPGA.
First pass Architecture Definition
Previously, I described the Problem Definition and Key Functions of the chess-playing FPGA. From these I will develop an initial, top-level architecture definition.
Problem Definition: We want to create, in a single FPGA, an electronic, chess-playing opponent. The FPGA will accept moves from the outside world, "think" for a while, and then provide its move back to the outside world.
Key Functions: We will need functions to perform the following tasks:
- Communicate with the outside world to send and receive moves.
- Generate all possible legal moves from a given position.
- Evaluate the "value" of a specified board position.
- Search through the sequences of possible moves to find the "best" move from a specified starting position.
I find that it usually helps to revisit the Key Functions list after a few days of working on something else so you can get a fresh perspective on them. After I revisited the above list (and after reading the comments associated with my previous blog) I thought of some additional functions the design might require, as follows:
Best Move Selector: The Move Generator can generate legal moves, but it would be helpful if we could select the "best" move from all the possible moves from a given position. If we can begin our "search" from a good move instead of a bad one, this will speed our search through the tree of all possible moves. (We will see later exactly how much of a speed-up this will be, but for now we will just assume it is useful to do.)
Timing Control: In my previous blog, I mentioned that the FPGA design should comply with established rules for making 40 moves in the first 90 minutes. Thus, we will need a timing and control function that allocates the FPGA's "think" time among these first 40 moves.
Opening Book: Most computer chess programs use an Opening Book to improve responses during the first several moves of the game. Of all the possible opening moves, a few have been studied in great detail and several "best" or "better" lines of play have been identified. If the FPGA has a "book" of these sequences stored internally (since we are limited to a single FPGA, any book will need to be internal to the FPGA after configuration), it can simply look them up and eliminate a large number of branches of the tree from consideration.
Next page >
Tweet This
