Author: Chan Rasjid
Date: 13:02:14 01/20/06
Go up one level in this thread
On January 20, 2006 at 14:29:34, Gerd Isenberg wrote:
>On January 20, 2006 at 02:51:01, Chan Rasjid wrote:
>
>>On January 19, 2006 at 14:26:11, Gerd Isenberg wrote:
>>
>>Thanks Gerd,
>>
>>As expected, we cannot trick the world. I did not suspect boolean may translate
>>to branching of 0/1, am still learning!
>>
>>Incidentally, I'll like to mention the bitboard vs offset debate. I can now see
>>a complete BB implentation as I have started from scratch and now have completed
>>a BB implementation except for eval() and 1 line trigering an assert(). So
>>everything's fine. It does not need a BB move generator! rather it is BB
>>incremental generation plus partial as we can easily extract 1 move at a time.
>>
>>In the past Christophe Theron argued against BB pointing out not a single BB
>>engine made it to to SSDF list. Now we have Rybka at the top so likely others
>>may think a little more about BB.
>>
>>1) BB_TO_SQ() call - I am not sure this was one of the main contentious issue.
>>I dont do rotated,just improvise. I doubt rotated will add much advantage as
>>there is the law of natural limitation in everything. For sliding pieces
>>and given a 2 bit BB of bbFrom, bbTo, I will have the fromSq and need to get
>>toSq. I try this. The sliding path space of 4 are +15, +17, +16, +1.
>>
>>signed i64 bbTo, bb2bit;
>>
>>bbTo -= bbFrom;
>>no_of_step = i = popcount(bbTo * (1 | bbTo >> 63) & dir_path);//may use abs()
>>toSq = fromSQ + i * (1 | bbTo >> 63) * positive_step;
>>
>>We may also use popcount((bb2bit & bb2bit - 1 - (bb2bit & -bb2bit))& dir_path);
>>
>>I have not tested if the above is better then BB_TO_SQ(), at least I'm happy not
>> having to shift by ranks with a table lookup.
>>
>>2) I think all BB engine don't have a generator, just incremental updates.
>>BB moves are basically the attack BB of all the pieces + 1 extra BB for pawns
>>push. N / K don't even need any update unless they move and I have this :-
>>
>>static const u64 kDzE4 = 0x0000382838000000;
>>static const u64 nDzE4 = 0x0028440044280000;
>>
>>static const u64 nMask[2] = {FILE_3TO8, FILE_1TO6};
>>static const u64 kMask[2] = {FILE_2TO8, FILE_1TO7};
>>
>>u64 getNMap(int sq){
>> if (sq >= E4)
>> return (nDzE4 << (sq - E4)) & nMask[FILE64(sq) - 4 >> 31 & 1];
>> return (nDzE4 >> (E4 - sq)) & nMask[FILE64(sq) - 4 >> 31 & 1];
>>}
>>
>>
>>u64 getKMap(int sq){
>> if (sq >= E4)
>> return (kDzE4 << (sq - E4)) & kMask[FILE64(sq) - 4 >> 31 & 1];
>> return (kDzE4 >> (E4 - sq)) & kMask[FILE64(sq) - 4 >> 31 & 1];
>>}
>>
>>Pawns are simple.
>>
>>We have :-
>>//pS is pointer to global stack for my non-recursive search.
>>
>> *(pS + 1)->bbMoveStack = *(pS - 1)->bbMoveStack;
>> doMove(board, pS, *pS->pCurrentMove, side);
>> if (genIncrementalBB(board, pS + 1, *pS->pCurrentMove, incheck,
>> pS->sqCaptureEP, side ^ 1 , side, *board->pAllBits));
>> else{//capt King, tmp
>> undoMove(board, pS, *pS->pCurrentMove, side);
>> //etc..
>> ++pS->pCurrentMove;
>> continue;
>> }
>>
>> genIncrementalBB(board, pS, *pS->pCurrentMove, incheck,
>> pS->sqCaptureEP, side, side, *board->pAllBits);
>>
>>At this point I have the complete BB attack-tables of the two sides and may
>>simply extract 1 move at a time and have complete info to select the best move
>>of each phase.With offset, I cannot see how incremental move generation may be
>>done. Fruit may have partial but not incremental generation.
>>
>>3) QS move generation - In the past debate, it seemed no one mentioned this.
>> 90% of all nodes are QS nodes. Getting BB captures are the simplest. With
>>offset we still have to start from the targets and test by sliding thru empty
>>squares etc. So BB here may have a significantly influential advantage. Is this
>>the "secret of Rybka" ?
>>
>>Best Regards,
>>Rasjid
>
>
>I had incremental update of from/to Attack-tables in my former Dos-IsiChess -
>not any longer. There are repetition detections, hash-hits or cuts, futile or
>"lazy" nodes where attack information is not needed at all or only partially to
>e.g. generate pxQ.
>
>But i don't want to spoil you for doing so. I might be ok for you and efficient
>and i can imagine that it is fun. My current program is no reference at all, but
>a bunch of crap ;-)
>
>Like Vas i think if you already have a bitscanned square index of a knight or
>king, getting none sliding attacks is faster with direct access of precalculated
>bitboard[64]-arrays - even if you do it quite rarely with your incremental
>stuff. Conditional shift of a e4-pattern with additional masks seems better
>suited for array initialization to me ;-)
>
>The approach i'm actually working on is complete different - but fun.
>Quad-bitboards with Kogge-Stone fillstuff, getting attacks direction wise - no
>bitscanning, but x & -x to get single pieces or move targets - directionwise De
>Bruijn like multiplication with "ored" from[-to]-bitboards to get move indices.
>One cacheline node-structure - one quadbitboard, two 64-bit hashkeys, side2move,
>ep- and castle rights move50 and piece counters. Make- and unmake move is
>basically xor of six 64-bit words together with and/add of of two 64-bit words -
>but huge const tables indexed by move.
>
>Gerd
I have not read any formal BB technique, too tough. So I just go ahead armed
with x & -x, x & x-1, x - y > 0 to get intervening bits, bits_E/LE/G/GE etc..
I now cannot see how any BB engine can be efficient w/o incremental updates of
all (sliding) attack maps of the b/r/q. The complete attack info is an
incidental good bonus. I can only see that to extract Q-moves, we need the
complete q-attack map. If we generate the Q-attack map anew at every node, we
need to manipulate all 8-rays. With incremental, at most 2-rays or none, need
updates. My 1-step-ahead IQ asks _how-to-be efficient?
May be the reason why Rybka quickly exchanges it's queen is not to deal with
8-rays. Vasik would likely go to trade all R-R, B-B, so nothing sliding to
worry. Then his Knight = 330, Bishop = 310, etc...
Best Regards
Rasjid
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.