Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Precomputed move information

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.