Author: Anthony Cozzie
Date: 12:20:45 08/30/03
Go up one level in this thread
On August 30, 2003 at 14:37:44, Tord Romstad wrote: >My program has reached the stage where it is so complicated and ugly that I >no longer understand clearly how it works (it's rather miraculous that it >works at all), and there are many parts of the code which I am afraid of >touching because I am sure I will break something. Besides, the program >is horribly slow, searching only about 120 kN/s on a PIV 2.4 GHz. > >Because of this, I think it is time to throw away all the old code and >start from scratch. Before I do this, I will consider replacing my >data structures with something more efficient. > >Today, my board representation consists of a 256-byte array of squares >(visualised as a 16x16 board with the real board in the left half of >the middle 8 ranks) and a Phalanx-style piece list. At every node in >the tree, I generate "attack tables" similar to those found in Rebel, >Phalanx and Diep (the tables are not updated incrementally). > >I have never really liked bitboards, but because my next computer will >almost certainly be a PowerMac G5, I am considering to give them a try. >First, however, I have a few questions to the more experienced bitboard >users: > >1. One of the things I dislike about bitboards (at least the modern >approach with rotated bitboards) is that even very simple operations >like generating moves seem to require either using huge lookup tables >(like in Crafty without -DCOMPACT_ATTACKS) or writing some extremely >complicated and unreadable code (like Crafty _with_ -DCOMPACT_ATTACKS). >Is there a way to use rotated bitboards without having big tables, >and still keeping the code short, clean and readable? > >2. Another problem with bitboards is that there is no obvious way to >compute "weighted mobility". While it is trivial to compute the number >of pseudo-legal moves for a piece with bitboards, this number is usually >not very interesting (at least not in my program). In most cases, some >squares are much more valuable to attack than others. Given a 64-byte >array of weights, and a bitboard of squares attacked by a piece, is there >a fast way to compute the "dot product"? I have browsed the archive >and noticed that this question has been discussed numerous times before, >but I have never seen a good answer (Bob has explained a lot of times >how to do this on a Cray, which is not very useful to me). > >3. I also dislike the fact that bitboards are much too big to be used >as indexes to lookup tables, and that extracting information from them >is often difficult to do without looping through all the 1 bits. It is >easy to compute a bitboard of all pieces which attack a given square, >but in my evaluation I want to extract information about the number and >types of attackers in a small and compact bitfield (which can be used >as an index to a lookup table), while throwing away information about >the locations of all the attackers. How do I achieve this with bitboards? > >Tord Zappa uses bitboards (a mistake perhaps, I chose them for the same reason most amatuers chose them I think: Crafty uses them, and crafty is open source :) That said, you can do some really cute things with bitboards. Bob's rule of the square KP code is a good example. Want to find out if your king is in the center? 1 operation. Want to find if you have pawns on the same color as your bishop? 1 operation. etc. Another example: Suppose in Q search you prune by SEE (Zappa does). With bitboards, I can do get_queen_attacks() & ~(pmaskl & pawns >> 7) | (pmaskr & pawns >> r) & enemy_pieces, and boom: I can generate captures of pieces that aren't defended by pawns. Also, Zappa doesn't do *everything* with bitboards: it maintains a 8x8 char array with pieces. If you want to know whats on square N, its only a table lookup away :) Nothing is preventing you from building the same attack tables you already have just because you have a few U64s lying around except for dogmatism :) The way I see it is this: There are two questions that are usually interesting in chess: What is on Square Y, and What square is X on. A chessboard answers the first question very well; for the second either a piecelist or a set of bitboards is needed. So, here goes: 1. At least in Zappa, the only difference between 'compact' and regular attacks is that the index is >>1 and & 63 rather than &255. (512KB -> 128KB). 2. If you really wanted to, you could unroll the multiplication: A[64] . B[64] (assuming A is 0/1) = pop_count(A&B0) * W0 + pop_count(A & B[1]) * W1 etc. Probably pretty slow, but see above: why discard your board datastructure. Even crafty has a char[64] member. 3. see 2. Anyway, I think the bitboard debate that rages constantly on CCC is rather silly. A bitboard is just another form of a piece list. The advantage is that certain operations on the piece list are easy; the disadvantage is that lookup is slow (14 cycles for Matt Taylor's code I think). Anything you can do with piecelists I can do with bitboards: some things will be slower and some faster. YMMV. anthony
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.