Author: Andrew Wood
Date: 02:50:50 01/27/99
Hello, I'm completely new to computer chess, but I've started to implement a chess engine in C++. I've looked around the internet to get a feel for the algorithms used, but I haven't seen an incremental move generator anywhere. I realised that if each individual piece keeps a list of the moves that are legal (or even just pseudo-legal) for itself, then there is a board to board coherence through a move in that some or most pieces may not have to change there move lists when a particular piece moves. So for some pieces when a move is done all you have to do is copy the movelist you generated for that piece for the previous position. The way it decides which pieces need a regenerated move list is using what I call a touch board. This consists of a 64 bit integer (__int64 in MSVC++4.1) with one bit per square. Each piece marks a square on its touch board if it can move to that square (touching that square), either directly or by way of a capture or if it's supporting a piece of it's own side on that square. When a move is done each piece checks to see if it's touching the square 'from' or 'to', if it is, the movelist is regenerated, if it's not it just uses the same movelist it had for the pre-move board. The touch board is easy to generate as a by-product of the move generator, just mark the touch board square if its the destination square of a legal move for that piece whilst the move is being validated. I actually use several touch boards per piece. One for touching squares that the piece can simply move to, one for squares a piece can move to and capture, one for squares a piece can't move to, but is supporting a piece of it's own side. These are useful for other things than move generation, such as the static evaluation function (mobility, threat value, support value) and checking for check. You just need to check to see if the king is on a square touched by a piece of the other side. You can also check if king moves are legal and castling is illegal by way of moving the king through or into check in the same way. You could keep a checking touch board, if a piece has the opposing side in check, by simple virtue of a threatened king capture, mark the touch board, if the value of the integer represented by the board is non-zero, then that side is in check. What does everyone you think of this idea ? Does anyone know if it's been done before ? My chess engine isn't finished yet, but it would certainly seem to me to save time only generating a movelist for a pieces which you need to, and make checking for check easy. I'd be interested in any comments. Thanks. ...Andrew...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.