Author: Gerd Isenberg
Date: 11:29:34 01/20/06
Go up one level in this thread
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
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.