Author: Robert Hyatt
Date: 06:16:43 07/02/02
Go up one level in this thread
On July 02, 2002 at 08:25:42, Sune Fischer wrote: >HI > >I've read that GNU chess used to have a precomputed list of moves, and it would >use a lookup in that list rather than generate the moves. > >I don't like that idea, but if instead one created a large table to contain >information needed when _making_ the moves, then that would probably yield a >good speedup. > >For instance if using rotated bitboards, then at every move one needs to update >the rotated bitboards which requires lookups in tables, masking and additional >hassle to remove a piece if the move is a capture. >Some of that is has got to be very cache inefficient. > >Now, with a precomputed makemove table, we could have these delta keys ready for >one single mask, and we need but one lookup to get all the required delta-keys. > Early Crafty versions did this, based on the description by Slate/Atkin of how they did the same thing. The problem is that for deep searches, you end up doing a lot of redundant calculations. IE if you search to a 12 ply nominal search depth, you can easily hit 25 plies with extensions and captures. That is 25 "move table" update operations, most of which over- write updates at previous plies. There comes a point where it is more efficient to do a bit of calculation where you need it, rather than trying to incrementally update something multiple times before it is needed... >Downside: the size of such a table is quite large: >64*64*6*6*2*sizeof(MoveInfo); // from,to,pawn-king,null-queen,color >(enpassent and promotions are special cases) >I get a total of about 14 MB, which is a little high I think. > >Assume this gives a boots of overall 2%, is that worth 14 MBs? >Probably not, however it does actually simplify the code since fewer lines are >needed in making moves. >I would no doubt use it had it been 1 MB, but 14 MB that is a lot IMO. > >I couldn't find anything via the search engine about this (though I'm sure it >has been discussed), so has anyone done something like that and are willing to >share their experiences? > >-S.
This page took 0.01 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.