Author: David Dory
Date: 22:14:16 05/25/02
Go up one level in this thread
On May 25, 2002 at 09:32:58, Russell Reagan wrote: >I hear about how great bitboards are because they [insert one of the many >reasons here]. I'm interested in two reasons in particular, because I do not see >how these reasons work. > >The first thing I'm curious about is computing whether or not a square is >attacked by a certain side. This is supposed to cost about a couple of array >lookups and an AND operation, right? Look up the white king bitboard, look up >the black pieces attack bitboards, AND them together, and you can tell if the >king is in check. That's what I've always heard anyway. Clearly this is much >faster than ray tracing the board looking for opposing pieces, but I don't see >how this bitboard method would even work. For example, for this to work, you >have to have a valid "black pieces attack" bitboard. To compute this you could >OR together all of the attack bitboards for each piece. The problem is that you >have pseudo-attacks. So this computation above where bitboards calculate whether >or not a square was attacked really only says "this square MIGHT be attacked", >right? At which point, you would have to do the ray tracing anyway, and it's not >really any faster, right? I'd like some clarification on this. > >The other thing I recall Bob saying was that using bitboards you can calculate >mobility for "free". Again, this seems like you could calculate pseudo-mobility, >but to calculate actual mobility, you'd have to do ray tracing just like you >would with another board representation scheme. I'd appreciate some explaination >of this also. > >Thanks, >Russell Russell, R.H. is the guy you need to answer your question. AFAIK, Crafty does the "in check" check by seeing if the king could actually be taken on the next move. Bitboards are NOT as clunky as they seem. Vincent's posts are frequently on target, but his opinions here are not quite spot on. (Especially his statement that GCP doesn't know much about programming). I'm afraid this is just VD being VD when someone disagrees with him. Diep's data structures may indeed be faster than bitboards (I surely don't know), but "galaxies faster", I'm sure, is an overstatement. :-) There are several ways to "streamline" any chess program - which makes the direct comparison of speed/effeciency of data structures a tough call. From posts a long while back, my understanding of Hyatt and Moreland's (Moreland's Ferret was a premier 0x88 based program) discussion on this was that 0x88 was initially very fast, but you had to slow the process down more than you had to slow down a bitboard based program to give it knowledge. In other words, 0x88 based programs are initally very fast - faster than bitboards (and both are naturally faster than mail-box), but you have to now add knowledge into the program. This seemed to slow down the 0x88 based programs more than the slow-down experienced by good bitboard programs with that same amount of knowledge being added to it. In the end, the 0x88 programs were still slightly faster than the bitboard based programs, but not as easy to add new knowledge into, without slowing them down more than the bitboard based programs. Of course, the expectation is that with a good 64 bit CPU, the 0x88 design will no longer be faster, at any level of added knowledge. In the end, the skill of the programmer is paramount to make either design work well, be adaptable, and run fast! Have you checked out the bitboard info on the web sites? David
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.