Author: Robert Hyatt
Date: 19:21:02 08/29/98
Go up one level in this thread
On August 29, 1998 at 17:46:52, David Eppstein wrote: >On August 29, 1998 at 14:11:07, Robert Hyatt wrote: >>I hate to follow up on myself, but the above is not exactly the case you >>mentioned above: >> >>>>>I think this power of two thing is a red herring. Even for an 8x8 board you >>>>>have to mask so your pieces don't think they can wrap around from one side >>>>>of the board to the other. >> >>When I read that, it implies (to me) that I need a *bigger* mask to handle this >>"wraparound", where bigger means more bits than the basic bitboard. That is >>completely wrong. > >No, I meant 8x8 masks, exactly like what you use in that line of code. > >>In the above example you gave, I generate *all* the pawn moves in one step, >>which is faster than generating moves for each pawn separately. But in doing >>so, I do have to prevent "wrap" when I shift the pawns diagonally forward for >>capture moves, by simply eliminating pawns on the h-file before shifting diag- >>onally to the right, and eliminating pawns on the a-file before shifting diag- >>onally to the left. But notice both masks are 64 bit masks, and that they are >>only used in pawn captures, not normal pawn moves, nor in moves by any other >>piece of any type... > >...because only the pawn moves really take full advantage of the parallelism >available from bitboards. The piece moves are generated one piece at a time, >not so differently than what you might do with any other board representation. >(I don't have any ideas for how to do piece moves better, though.) > notice that piece moves also are generated in one "step"... two table lookups for a bishop/rook, 4 for a queen (to combine the bishop/rook bits) and all the potential target squares are enumerated with no "masking" needed of any kind. But there are other places where "bit-parallel" helps... pawn structure analysis, piece evaluation, etc... >>That was my point... the "red herring" caught my attention first, because I >>don't have *any* masks of any kind that are longer than 64 bits... in >>move generation, evaluation, or anywhere else... > >All I meant by the "red herring" remark was to counter some previous messages >implying that bitboards were simpler for 8x8 boards than they would be for >odd-sized boards that don't fit exactly into a machine word (such as in my case >5x9). As far as I can tell, there's nothing magic about powers of two here; >using bitboards to implement my 5x9 board is just as easy as it would be with an >8x8 board. I have to mask occasionally to find the bits that are actually on >the board, but only in the same type of situation (like pawn move generation) >that you use in crafty. OK... there we agree then...I misunderstood your "red herring". As I mentioned, the first bitmap I know of was on a 60 bit machine, so doing it in two pieces was forced... yet it worked well based on chess 4.x results... And we should have 128 bit ints within a year or two (on the PC) so that 128 bit bitmaps will be just as effective as 64 bit maps are on 32 bit architectures.
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.