Author: Bo Persson
Date: 10:36:40 02/27/01
Go up one level in this thread
On February 27, 2001 at 11:36:43, Severi Salminen wrote: >On February 27, 2001 at 10:23:08, Robert Hyatt wrote: > >>On February 26, 2001 at 16:21:15, Severi Salminen wrote: >> >>>>Note that in crafty I don't do the attack_to/attack_from stuff, I dynamically >>>>compute it as needed with the rotated bitmap table lookups... that might make >>>>a difference. >>> >>>What is this attack_to/attack_from you are talking about? I do this in >>>gen_captures(bishop, for example): I take one white bishop from Board.Bishops. >>>Then I extract the necessary diagonal states which I use to get a bitboard which >>>has all bits on where a bishop might capture to. Then I AND this with black >>>pieces and scan through those. In make_move() I just move the pieces around and >>>update all bitboards. My board structure has only the necessary bitboards which >>>are needed to store the board and 3 rotated bitboards. So what are these >>>attack_to and _from bitboards and where are they used? >>> >>>Severi >> >>The original Slate/Atkin paper described their incremental move generator. They >>maintained (for each piece) a bitmap that defined the squares that piece could >>move to. Whenever the board was updated, the affected bitmaps were also >>updated. This means that at any instant in time, you _always_ have a bitmap >>showing which piece attacks which squares. They also incrementally updated the >>inverse bitmaps as well, those bitmaps that indicate which squares hold a piece >>that attacks one specific square. >> >>I did this in early versions of crafty, but the rotated bitmap approach soon >>made that approach obsolete... > >Oh yes, I think I have read about this somewhere. Actually it was Levy's Chess >Computer Handbook. It introduced a move generator that only alters the list of >all possible moves if necessary. I think it would slow things down a lot. > >Severi No, that's another thing. As they mentioned in "Chess Skill in Man and Machine" (and also in the Chess .5 program published in Byte magazine 20 years ago) Slate&Atkin used attack bitboards that were updated during make/unmake. This is relevant here, as move generations are *extremely* fast when you have all the info available at the start. Unfortunately, this is just because the work is moved to MakeMove()... Nowadays, if you have a megabyte to spare, rotated bitboards strikes a better balance between move generation speed and the amount of work done by MakeMove(). 20 years ago you didn't have enough RAM to do this (unless you had a Cray, of course). Bo Persson bop@malmo.mail.telia.com
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.