Author: Dan Newman
Date: 17:03:44 02/12/00
Go up one level in this thread
On February 12, 2000 at 15:21:20, Tom Kerrigan wrote:
>On February 12, 2000 at 13:17:48, KarinsDad wrote:
>
>>I think the issue may be one of degree. If a program got modified from
>>non-bitmap to bitmap (which would probably be a lot of work since so many
>>elements of a chess program are dependent on each other), it may increase in
>>speed by 10% to 20% (maybe). And, this may correspond to a 7 to 18 ELO
>
>I doubt that bitmap programs are inherently faster than everything else.
>
Well, there may be something no one's thought of yet (or perhaps hasn't
revealed) that's faster than bitboard, piece list, etc. In fact I have one
oddball scheme (that I'd like to try again sometime) that really screams on
capture generation. The problem is it has the slowest make()/unmake() that
I've ever tried...
>I know how to write a bitmap program, and they use a lot of "extra" memory and
>do a lot of "extra" work. It just doesn't make sense to me that they would be
>inherently faster.
>
>-Tom
I'm not sure about this. I did think this a few months ago however...
In a piece list program you might cram the piece list into a byte array
(if you want to only store piece coordinates). That would take 32 bytes.
But in experiments I've done, int sized arrays are somewhat faster, so
perhaps 128 bytes for the piece lists.
In a bitboard program you have the bitboards for the various pieces:
bitboard_t piece[16]; // I waste a little here
for 16x8 == 128 bytes.
I also have two more for occupancy by each color and one for occupancy by
any color. 24 bytes more.
There are of course all those rather large bitboard arrays:
bitboard_t pseudo_attacks[8][64];
and
bitboard_t block_masks[4096];
that get accessed a lot...
So, yeah, it does seem a little weird...
I haven't actually tested this, but it could be that my bitboard program is
a good bit slower than the 0x88 when the piece count is very low. But in
positions with lots of pawns or multiple other piece types, it seems to be
a good bit faster.
Here's an example. Generating captures by the knight(s). In the bitboard
program I do this:
bitboard_t knights = piece[W_KNIGHT];
while( knights.exist() ) {
int from = knights.next_one();
bitboard_t victims = pseudo_attacks[KNIGHT][from] & color[B_SIDE];
while( victims.exist() ) {
int to = victims.next_one();
(movep++)->add_wn_capture( from, to);
}
}
I've played around with the above, but have only managed to slow it down so
far...
In the 0x88 program I do something like this:
while( !p->end() ) {
int from = p->from();
switch( p->type() ) {
....
case W_KNIGHT: {
int to = from + 33;
if( on_board( to) && is_black( to) )
(movep++)->add_wn_capture( from, to);
to = from + 31;
if( on_board( to) && is_black( to) )
(movep++)->add_wn_capture( from, to);
//and so on, 6 more times...
break;
}
....
}
p++;
}
The two seem like they could be doing comparable amounts of work, but I guess
I need to look at the machine code to really tell...
-Dan.
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.