Author: Bruce Moreland
Date: 14:28:05 05/07/98
Go up one level in this thread
On May 07, 1998 at 15:51:16, Bas Hamstra wrote: >Do you think it would be possible to generate moves incrementally? Most >of the legal moves remain the same after a move is made, it seems. I >think it might be possible to generate only moves for the pieces that >are "affected" by the prior move. Yes, this has been tried, successfully. You even named it the same way it's been named in the past. >If I'm not mistaken KnightCap does this (or was in another program?). It >has a board representation in which each square is a 32 bit number, each >bit representing the (uniquely identified) piece by which that square is >attacked. There can be no more pieces on the board than 32. > >Suppose a move a2-a3 is made. Adjust the board (="attackmap") for the >new squares a3 attacks and delete the a2-attacks. If a2 OR a3 is >attacked by a piece (of both colors) only the moves for those pieces are >to be regenerated and the board has to be updated again, for just those >pieces. > >Would that work you think? > >Problem: what to do with unmake? Compute it all "back" seems exspensive. >Or no unmake at all and fetch the previous board? Wouldnt that be >expensive too on a PC (bandwitdh and all)? > >Could someone please react on this thoughts? Sometimes you see concrete statements having to do with algorithms, but you won't see very many in computer chess. Move generation is pretty simple, but it's still more complex than, say, a sort. And assuming you could prove that one system generates moves more quickly than another, the move generator doesn't exist in a vacuum. The order in which moves are searched matters. If a move generation scheme is very fast, but generates moves in a non-useful order, and it is impossible to reorder the move list, it is likely (but not certain) that the move generation scheme is poor. Moves will be generated more quickly, but more nodes will need to be searched in order to reach the same depth. The move generator and the make/unmake subsystems tend to work together. It is possible to make a move generator that generates moves in such a manner that the make/unmake have less work to do, so overall throughput is increased even though the move generator goes slower. The move generator can cooperate with other sub-systems as well, it can speed up or help out the evaluation function or the search. So real move generator performance is hard to measure. I wouldn't listen to anyone who claims to generate N moves per second, where N is a huge number, because you don't win games by generating more moves than the opponent. bruce
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.