{"content":{"sharePage":{"page":0,"digests":[{"id":"55678324","dateCreated":"1344349821","smartDate":"Aug 7, 2012","userCreated":{"username":"Bretwa","url":"https:\/\/www.wikispaces.com\/user\/view\/Bretwa","imageUrl":"https:\/\/www.wikispaces.com\/i\/user_none_lg.jpg"},"monitored":false,"locked":false,"links":{"self":"https:\/\/chessprogramming.wikispaces.com\/share\/view\/55678324"},"dateDigested":1531478087,"startDate":null,"sharedType":"discussion","title":"One piece, one bitboard ?","description":"Hello,
\n
\nI have a question about piece representation with bitboard. Actually it seems that the approach, one kind of piece for each color <=> one bitboard is very common on Internet. But this approach implies that a "nextbitset" call has to be done, which can require quite a lot of cpu time. It's also require a mask to eliminate the other piece on the bitboard. If we use one bitboard for a piece (exception for pawns) we don't have to do this. For example we would have a bitboard for the left white rook, another bitboard for the right white rook. And we create special treatment for pawn promotion. Is this relevant for a faster moves generation ? Thanks beforehand.
\n
\nBretwa","replyPages":[{"page":0,"digests":[{"id":"55683284","body":"Hi Betwa,
\nwhat you propose is the purpose of piece lists with square indices given for each individual piece. Keeping single populated bitboards, despite low data density, still requires a bitscan. With bitboards you like to intersect for instance all white rooks with rook attacks of the black king, to determine whether a rook gives check.
\n
\nAlso, the inner loop over target squares takes much more time in move generation than the outer loop over source squares of a rook, bishop or knight.
\n
\nGerd","dateCreated":"1344375592","smartDate":"Aug 7, 2012","userCreated":{"username":"GerdIsenberg","url":"https:\/\/www.wikispaces.com\/user\/view\/GerdIsenberg","imageUrl":"https:\/\/www.wikispaces.com\/user\/pic\/1202793136\/GerdIsenberg-lg.jpg"}},{"id":"55684862","body":"Hi Gerd,
\n
\n
\nI'm sorry but I do not understand why we still need a bitscan with single populated bitboards. For example if we generate white rooks moves in pseudocode we have :
\n
\nif(white_left_rook != 0) optional
\n{
\n long left_rook_mask = rook_mask_list[white_left_rook]; <\/em> a hashmap of course
\n long left_bitboard_with_mask = left_rook_mask AND current_bitboard;
\n long white_left_rook_moves = rook_moves_list[left_bitboard_with_mask];
\n}
\n
\nWe do same for right rook and a special case for pawn subpromotion with another bitboard. If we use traditional two rooks bitboard we have something like :
\n
\nint first_rook_index = get_next_bit_index(white_rook_bitboard, 0);
\nlong first_rook_mask = rook_mask_list[first_rook_index];
\nlong first_rook_bitboard_with_mask = first_rook_mask AND current_bitboard;
\nlong white_first_rook_moves = rook_moves_list[first_rook_bitboard_with_mask];
\n
\nint last_rook_index = get_next_bit_index(white_rook_bitboard, first_rook_index + 1);
\nlong last_rook_mask = rook_mask_list[last_rook_index];
\nlong last_rook_bitboard_with_mask = last_rook_mask AND current_bitboard;
\nlong white_last_rook_moves = rook_moves_list[last_rook_bitboard_with_mask];
\n
\nOf course we can create a buckle for pawn subpromotion. To my point of view it appears that we don't need a bitscan with the first approach. Concerning the
\ncheck topic, we just have to make OR between left and right rooks bitboards, this seems to be a little drawback regarding the gain of not using
\n
\nget_next_bit_index. Where do you think is the mistake ? Hashmap could have a strong negative impact ?
\n
\n
\nBretwa","dateCreated":"1344385878","smartDate":"Aug 7, 2012","userCreated":{"username":"Bretwa","url":"https:\/\/www.wikispaces.com\/user\/view\/Bretwa","imageUrl":"https:\/\/www.wikispaces.com\/i\/user_none_lg.jpg"}},{"id":"55688316","body":"Sure you can use a hashmap, but hashing the single populated bitboard for a dense index is exactly what the bitscan is about - minimal perfect hashing for instance ala DeBruijn multiplication. It seems cheaper to me instead of keeping single populated bitboards, to keep and incrementally maintain (make, unmake) the logarithm dualis of the power of two value inside a piece list, that is the square index itself.
\n
\nGerd","dateCreated":"1344406250","smartDate":"Aug 7, 2012","userCreated":{"username":"GerdIsenberg","url":"https:\/\/www.wikispaces.com\/user\/view\/GerdIsenberg","imageUrl":"https:\/\/www.wikispaces.com\/user\/pic\/1202793136\/GerdIsenberg-lg.jpg"}},{"id":"55713384","body":"Ok Gerd, but I thought to another advantage of using single populated bitboards. It's about the evaluation function. If we use several pieces on a single bitboard, we will have to compute the hamming weight of this bitboard, then multiply by the piece value. According to Wikipedia, this need 4\/5 operations with the many 0 method. If we use single populated bitboards, we just have to check if the bitboard is not null and add the piece value to the total evaluation. The evaluation function is called many times, so this could be a great advantage, no ?
\n
\n
\nBretwa","dateCreated":"1344477656","smartDate":"Aug 8, 2012","userCreated":{"username":"Bretwa","url":"https:\/\/www.wikispaces.com\/user\/view\/Bretwa","imageUrl":"https:\/\/www.wikispaces.com\/i\/user_none_lg.jpg"}},{"id":"55716342","body":"I fear not. Material is calculated by incremental update during make\/unmake anyway, i.e. only updated after captures\/promotions. You don't use popcount for that, except perhaps in initialization. Keeping explicit single populated bitboards inside a piece-list as board representation makes no sense.
\n
\nGerd","dateCreated":"1344499937","smartDate":"Aug 9, 2012","userCreated":{"username":"GerdIsenberg","url":"https:\/\/www.wikispaces.com\/user\/view\/GerdIsenberg","imageUrl":"https:\/\/www.wikispaces.com\/user\/pic\/1202793136\/GerdIsenberg-lg.jpg"}},{"id":"55717628","body":"Ok thanks for this advice. Calculating material during the tree construction should be faster, even if the type of the captured piece has to be known explicilty.
\n
\nBretwa","dateCreated":"1344514072","smartDate":"Aug 9, 2012","userCreated":{"username":"Bretwa","url":"https:\/\/www.wikispaces.com\/user\/view\/Bretwa","imageUrl":"https:\/\/www.wikispaces.com\/i\/user_none_lg.jpg"}}],"more":0}]}],"more":false},"comments":[]},"http":{"code":200,"status":"OK"},"redirectUrl":null,"javascript":null,"notices":{"warning":[],"error":[],"info":[],"success":[]}}