Author: Vincent Diepeveen
Date: 14:05:45 08/30/03
Go up one level in this thread
In REBEL as we can read from its homepage it is also 1 instruction. Because Ed doesn't know the difference between C and BASIC, i'll write down the code for REBEL here in C (of course rebel-engine is 100% assembly so 'decompiling' is not happening here) attackers = MyAtt[sq] & 7; He that looks very similar to what i do in DIEP! Now fritz: attackers = MyAtt[sq] & 7; He HOW SIMILAR that looks to rebel? Must i go on? On August 30, 2003 at 17:02:24, Vincent Diepeveen wrote: >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.