Author: KarinsDad
Date: 15:32:08 01/27/99
Go up one level in this thread
On January 27, 1999 at 05:50:50, Andrew Wood wrote: >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 ? I am currently using this in my code. I call it a non-xraying attack table. I use it in my legal move generation. I also use it to generate my xraying attack table (since they are virtually identical, the xraying one just indicates how many pieces are attacking a square, regardless of whether they are xraying through other pieces of the same side) which I use in my evaluation code. It takes up a LOT of memory to save it for every position. I do not have one for "can move to, but not capture" or for "can move to, but supports a piece from my side" since I can derive that information from my bitboards quicker. I use the information in similar ways to how you do. So far, it works fine. However, since I am also still in the process of creating my program, I have not yet done any performance tests on it yet. KarinsDad >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.