In my last two blogs, I outlined the key functions and basic architecture for my chess-playing FPGA project. As part of this, I showed an example structure for the move generator that uses an array of cells -- just like those on a chessboard -- to generate all possible legal moves from a defined position.
The outlined approach will look at all moves in parallel. This is a dramatic departure from the traditional sequential techniques to implementing algorithms that we tend to use as a default "go-to approach." My hope is that once we better understand this chess-playing example, we can begin to look for similar (cellular) implementation possibilities in other types of applications and designs.
As one example, maybe in the future video compression algorithms could use a cellular approach in which there is a cell for each pixel. These cells could communicate as necessary to other nearby cells in order to implement the compression algorithm. I know, we would need lots of cells, but by then FPGAs will be big enough!
Now, before we dive into the "guts" of the chess-playing FPGA design we will first need to brush up on some aspects of game theory...
Game theory quick start for a chess-playing FPGA
Game theory is a fun and interesting topic. If you want to get into the details (like Nash Equilibrium, Backward Induction, Imperfect Information, Sequential Games, etc.), then I highly recommend the Yale University Game Theory Course offered free online (either via iTunes University or through the Open Yale University online course. I will cover just a single topic from the many covered in that course: Sequential Games using Game Trees and Backward Induction.
Chess is a good example of a perfect information sequential game -- both players know the "state" of the game and they see the other player's move prior to making their own. These games can be analyzed using a Game Tree that shows (a) all the move options a player has and (b) the "result" of the game after the moves results in either a win or a loss.
In chess, since there are so many moves required to arrive at the end of the game, it's difficult to follow the game all the way through to the conclusion of a checkmate, so a short-cut approach is to evaluate the position of the board after some number of moves have been 'made' by each player. A simple evaluation would be to count the value of the pieces a player has (or maybe the difference in value since both players start with the same material value). Consider a small portion of a chess game tree with each player (W for White and B for Black) making two moves as shown below:
Example move tree showing terminal board values.
In this highly-simplified representation of a full tree, White has three possible moves from the starting position at the top of the tree (I know this sort of looks like an inverted tree with the branches pointing down instead of up, but let's not be too literal with our analogy). From this starting point, W1 is White's first move; B1 is Black's response to W1; W2 is White's response to B1; and so forth. Each node represents a position on the board and the tree expands based on how many moves are available to a player in each position.
To Page 2 >
Tweet This
