As part of my ongoing project to design a chess-playing FPGA, I will describe some of the logic used to determine the best move from a specific position on the chessboard. This will -- perhaps surprisingly -- be a fully combinatorial implementation.
Building on the parallel implementation of the move generator block from my previous post, I will begin to describe the logic used to implement a portion of the move generator. In particular, I will focus on the logic used to determine the value of the best move for a particular square. I am using a cellular approach to the design, so this logic will be replicated for each of the squares, organized as an eight-by-eight array, just like the game board.
Generating moves -- a fully combinatorial implementation
The algorithm being used to identify the best move into a specific square is fairly simple. The logic will examine all the possible attacks by enemy pieces into the square. The attacking piece with the smallest value is assumed to be the best aggressor, since it is usually better to capture an enemy piece with the smallest piece you can. For example, you would rather capture a rook with a pawn than with your own rook, in case the enemy rook is protected. The value of a move is thus the difference between the value associated with the piece in the square and the value associated with the smallest available aggressor.
There are a few possible implementations of this logic. A sequential implementation might scan all the possible aggressors, select the one with the lowest value, and subtract its value from the value of the piece in the square. It might take several clock cycles to do this, but the process is fairly simple.
An alternative approach would be to use combinatorial logic and perform all of the comparisons in parallel. In this case, we would examine all the possible aggressors, compare them (using a priority function similar to that used in interrupt generation in MCUs), and select the lowest-valued aggressor. To generate the best move value for this square, we would simply subtract the selected aggressor's value from the square's piece value -- something easy to do with combinatorial logic. A block diagram showing the key signals coming into the square is given below. N stands for knight. The letters associated with the other pieces are easy to decode.
Best move logic for one square of the chessboard.
The logic in the squares near our example square will generate aggressor signals that can be used by our combinatorial logic block. (I will describe the process for generating these signals in my next blog. For the moment, let's just assume they are available.) The square below and to the right of our square could generate an attack from a pawn, a bishop, the queen, or the king. Only one of these pieces could be the attacker at any given time, because only one piece can occupy a square at a time. This can be used to simplify the comparison logic. Usually, the values associated with the different pieces are something like this:
In our example, if a pawn were attacking from below and to the right, and a rook were occupying the example square, the best move value from that direction would be 5 - 1 = 4 (rook minus pawn). Our combinatorial logic could be duplicated to perform similar calculations from all the other directions (upper left, upper, upper right, etc.), and a central comparison could combine all eight directions to arrive at a final best move value. That value would be produced as an output from the block, and it would be combined with outputs from the other squares, perhaps initially by comparing eight squares at a time (maybe on a column basis) to obtain eight intermediate results. Those results would be compared to determine the best move value for the entire board.
Now, it would be helpful to compute some housekeeping data at the same time. Eventually, we will want to identify the pieces that are the aggressor and the victim for the best move value. That's because we will want to modify the board by moving the aggressor piece to the victim square while we traverse the game tree (as we discussed this month) by making the series of moves created by the move generator.
These additional details will be described in the next blog. Until then, think about what other information we will need to traverse our game tree and make alternating moves by the black and white pieces as we try to checkmate our opponent.
I think it is the typical approach to use an MCU (or some other sequential control) and then accelerate portions of the algorithm using an FPGA. In the chess playing FPGA we will probably have a central controller to manage the human interface and other 'house keeping' parts of the system. A sequential controller could also be used to manage the opening book (the list of all the best known lines of chess play) to take advantage of this large body of chess knowledge.
I'd like to start out in the current design I'm describing, doing as much as possible using the cellular array to see how far we can get just using that approach. I'm sure that as the design progresses a sequential controller will be useful...
MarcinSidus 1/2/2013 4:36:05 AM User Rank Beginner
Re: Advanced questions
Warren, thank you very much for your comments to my questions.
I did not know about the chess programming wiki page and thank you for this link. Up to now I did not dig into this subject. I am involved into FGPA projects currently too much, just having fun with playing chess :)
As I can see you recently dig this subject much more.
Now, I have only one question. I used to prepare an algorithm on an ordinary CPU and then adjust it to FPGA implementation. Why have you decided to go into FPGA at the very beginning?
In other words: should it not be as other implementations just improving performance using FPGA?
Let's imagine that the parallel algorithm is prepared and verified on an ordinary CPU. Then the most crucial parallel parts are implemented into FPGA.
As I have such questions I have in my mind current Zynq solution from XILINX, which is suited for such implementation the best, in my opinion.
Or, there is something, which we do not know yet and you know and it will be in next posts?
Interesting idea. Map the floor as a series of 'squares' with different values. It might make it easy to find the 'fastest' path between two points if you generate some 'attacks' that can be pushed forward to find the 'goal' location. The squares could be expanded as the robot explores the area (hopefully without falling down the stairs to find the -infinity value there).
There are some great oints to your post MarcinSidus. Here are some responses- others will come in future posts.
0) Goal of the chess playing FPGA is to actually create a real design that would be able to play competitively against highly rated human and computer opponents. Hopefully we can get people to do their designs and host a playoff maybe at DesignWest in 2014!
1) I'm a chess player and years ago I was very good. I have not studied the openings for many years so I'm way behind the times now.
2) If we can get the chess playing FPGA to look ahead many moves then there will never be a case of losing to a pawn (or other piece) sacrific in 2 moves (since the FPGA will be able to look many moves ahead. However- there is always the problem that the FPGA looks 10 moves ahead but just over the 'horizon' there is a checkmate that the FPGA doesn't see. Whoever sees ahead the furthest probably wins! More on this topic in a future blog!
3) As explained above, hopefully the parallel thinking will get deeper into the move tree (look further ahead) and thus end up with better moves!
4) Yep- chess is still too complicated to do a full evaluation (to always win, or draw like in tic-tac-toe) but the idea of evaluating positions at the terminal nodes can give us a very good 'player' from the FPGA.
5) There are actually some good electronic chess games (some that use FPGAs to accelerate move searching and evaluation). Check out info here if you are intersted in more details: http://chessprogramming.wikispaces.com/Home
6) Neuron network is an interesting idea too. I like the idea of a chess playing FPGA that can play against itself (or maybe against 'mutations' of itself with different position evaluation functions) to find improvements in its algorithm. Even better thousands of different chess playing FPGAs that 'mutate' and play each other- survival of the fittest!
Thanx for you well considered comments. Hopefully my future psts will answer all your questions in even more detail.
MarcinSidus 12/30/2012 4:53:15 AM User Rank Beginner
Advanced questions
At the very first comment I would say that this approach is very interesting. And the blog itself is interesting for me as I am an FPGA engineer playing chess.
My question at the very beginning is what is the goal of a chess-playing fpga: do we want to have a never loosing machine for chess? Or do we want to implement and verify only an idea?
If the answer is for only the idea verification and having some fun or research, then it is ok.
However, if we want to have a never loosing machine then I have several questions, which require answers to properly go further with a chess-playing FPGA on this forum.
1. Are you a chess player, good chess player? Or do you play well any other turn-games? Or, are there really good chess players on the forum? If yes, please help to evaluate the idea.
2. The question above is fundamental in my opinion, because in every turn-game it is required to predict the situation in 1, 2, 3 and even 30 moves. If you evaluate the position by values of the pieces only on squares then it is very easy to give you a checkmate with for example one pawn sacrifice in 2 moves.
3. Taking into consideration point 2 the value of parallel "thinking" by each square separately, simply will not work. Another point is that for example a queen can reach a lot of squares, which affects the whole idea of the separate notes.
4. One of the most interesting implementations as never loosing machine is done for checkers. Do you know the idea? And how it could be used to implement chess thinking FPGA?
5. No matter as I like the baby approach: "I have done it, becasue I did not know that the problem could not be solved." I would suggest to get more knowledge from engineers who have already done something in standard implementations of the chess game on any CPU. Simply, how to use opennings base, how to score the middle game and how to implement the end games?
6. I like the approach of a neuron network. FPGA is good for such tests, however it is still possible to implement and verify such an approach using standard CPU programming. The FPGA could be used to speed up such an implementation. In this way I would suggest to turn the idea a little bit. Is it possible to achieve good results in chess game using a neuron network approach (squares approach or any other similar)? If yes, then lets think how we could implement this in FPGA to achieve amazing results.
My summary as a pragmatic FPGA engineer could be: any algorithm implementation can be done on a CPU and I use FPGA only to speed up the real solution and have an amazing results in counting speed, which is not available on a standard CPU.
Duane Benson 12/24/2012 11:26:45 AM User Rank Blogger
Obstacle avoidance
Warren - After following this series of yours, it occurred to me that what you're doing might have application for my robot. In my case, the basic movement will be primarily remote controlled but I want the robot to have enough awareness to keep someone from driving it down a staircase in into a garbage can.
A similar logic set might just work for that. Instead of attacking pieces, the ranking could be on the hazards presented to the robot, even if not visible to the remote driver. Maybe something along the lines of:
0 - open floor 1 - Small obsticle ... 8 - wall 9 - ledge (like down a stair case)
Warren Miller 12/23/2012 3:13:46 PM User Rank Blogger
Re: But what about...
As we get further into the design we will see that there is state information associated with each square. The square contains a piece (or a blank) and the piece determines the various 'attack' signals that go out from the square into surrounding squares. As these threats enter a square they are prioritized and then combined with the value of the piece under attack to determine the 'best' attacker (the highest priority attacker is the one with the lowest piece value).
The state of the square is changed when a move is made, usually by moving the attacking piece into the overall (board level) best move square (also removing the attacking piece from its original square).
We will find there are some additional state values that must be saved as we traverse the move tree in search of the path to a win (or at least the best increase in overall position value). More on these details once we finish with the combinatorial logic used to determine the best move and move on to the tree search controller...
Warren Miller 12/21/2012 12:50:24 PM User Rank Blogger
Re: But what about...
Max- Creating a move generator for each piece is a possibility. I'm not sure how you would identify the various squares the piece could move thru (like when a Bishop moves thru a vacant square). Each piece needs a location and then the various attacks generated from that location. Seem so me that placing the piece in the square and using the physical layout of the board to generate various attackes is much more 'logical'.
I'd be interested to hear how a piece centric organization might create the possible moves however. Any specific ideas?
When traversing serial links with optics or backplanes, high-speed signals are degraded by impairments in the link, such as insertion loss, reflections, crosstalk, and optical dispersion.
Warren has finally started to write some HDL code to implement his chess-playing FPGA, but he's not a professional coder, so he needs our help and advice.
What might we see in new Ultra Low Density (ULD) CPLD families three-to-five years down the road? Are there new technologies or programmable structures that will find their way into ULD devices?
To save this item to your list of favorite All Programmable Planet content so you can find it later in your Profile page, click the "Save It" button next to the item.
If you found this interesting or useful, please use the links to the services below to share it with other readers. You will need a free account with each service to share an item via that service.
Tweet This
