Author: Vincent Diepeveen
Date: 14:02:24 08/30/03
Go up one level in this thread
On August 30, 2003 at 15:20:45, Anthony Cozzie wrote: in my datastructure finding out how many pieces attack a square X (very important for move ordering, forward pruning if i would have it, and all evaluation) is very important. 1 AND instruction and at most a lookup in L1 cache do the job. How about bitboards? I realize that hyatt says he doesn't need this in his software, but knowing that all commercial programs consider this in code that eats loads of system time for them for whatever reason (either evaluation or forward pruning or move ordering or whatever), how to do it in bitboards quickly? Please take into account loading the bitmaps too. in diep: attackers = MyAtt[sq] & 15; Thanks, Vincent >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.