In this column, we will continue our discussions on the creation of a chess-playing FPGA, which I introduced some time ago in an earlier blog. Following our recent musings, we now have a new approach to the Move Generator.
This new approach is borrowed from a typical MCU interrupt function, which will allow us to generate all possible moves from a given position. This will allow us to completely navigate the game tree. In this column, we will consider how this approach can be implemented in more detail.
In my previous blog on this topic, I explained that we needed to be able to mask off our best move in order to find the next best move (similar to the way in which an interrupt system in an MCU can mask off a high-priority interrupt to let through lower-priority interrupts). This will allow us to traverse the entire game tree in search of the best position we can expect. But where exactly should we put the mask?
Possible mask locations
There are a few obvious spots where we could place our masking register. For example, we could mask off an attack signal from exiting its cell, or we could mask of the attack signal as it enters a target cell, or we could mask it off as it enters the priority logic in the attacked cell. (Those of you familiar with how interrupt masks are handled in an MCU may be able to infer from this where we need to place our mask!)
If we mask off the attacking signal going out of a cell, we will end up missing some moves (think about this for a bit and see if you can figure out which moves we will miss).
The thing is, some pieces (like a bishop or a rook) can attack through blank squares. This means that if we mask off the attacking signal as it exits the initial cell, we will miss all of the other moves into blank squares, so this won't work. This same problem will come up if we mask off the attacking signal as it enters an attacked cell.
The end result is that we need to allow the attack signal to enter the propagation logic, but keep it out of the best move priority logic. A diagram illustrating this approach is as follows:
Mask logic in the Move Generator.
All of the attacking signals enter the cell and continue into the Propagate Block. If the cell is blank, signals from bishops, rooks, and queens will continue into the next cell. This will work out fine, because if the cells need to get masked off, this will happen "downstream" at the appropriate attacked cell.
The Mask Bit (inside the various Mask Blocks in the above diagram) will be loaded automatically when a move is "taken back" as we navigate up the Move Tree, thereby allowing us to find the next best move.
So, this approach looks like it will work fine. We need lots of mask bits, but since registers are so inexpensive in FPGAs, this will be easy to implement.
One last feature we need to think about is determining when all possible moves have been generated and masked. Is there an easy way to do this with the logic we already have? If there are no moves into a cell, this means that all possible attacks have been masked off, and there is no input into the Best Move block. In that case, we can generate a "special" best move value that is treated as the lowest priority by the arbitration logic.
If all other cells generate the same low priority, then we have exhausted all possible moves for the starting position. We can now "back-up" the branch in the move tree, mask off the move that created the exhausted position, and continue looking at other moves from that position.
It looks like we have all the combinatorial logic identified that will be required to implement the Move Generator and the Evaluation functions. We have also started thinking about traversing the Move Tree, but now we need to get into the details of how this is actually implemented. We will pick up this topic in my next chess blog (this will be in two weeks, since I'm currently alternating between "Chess-Playing" and "FPGA Futures" columns).
Related posts:
Tweet This
