Author: Dann Corbit
Date: 17:04:58 02/27/06
Go up one level in this thread
On February 27, 2006 at 19:57:27, Gerd Isenberg wrote:
>On February 27, 2006 at 19:22:55, Dann Corbit wrote:
>
>>On February 27, 2006 at 18:57:09, Gerd Isenberg wrote:
>>
>>>On February 27, 2006 at 17:45:10, Dann Corbit wrote:
>>>
>>>>On February 27, 2006 at 15:13:59, Gerd Isenberg wrote:
>>>>
>>>>>On February 27, 2006 at 14:16:38, Dann Corbit wrote:
>>>>>
>>>>>>You have a special genius for bitboards and I always enjoy reading your posts.
>>>>>
>>>>>Thanks Dann,
>>>>>
>>>>>i appreciate that - but i have not special genius but morbus knuth ;-)
>>>>>I like interactive brainstorming and to formulate ideas so that they become more
>>>>>clear. I had some difficulties to understand your switch approach first.
>>>>>
>>>>>What do you think about masking off outer occupied bits?
>>>>>As well inside your switch cases as well as a 64-bit factor of a De Bruijn
>>>>>multiplication?
>>>>>
>>>>>They are redundant for attacks and also for possible xrays.
>>>>>It reduces the number of occupied cases to max 2**(raylenght-2) if source square
>>>>>is an outer square - or most often to 2**(raylenght-3), if source is some inner
>>>>>square, for instance bishop on e5 on the a1-h8 diagonal:
>>>>>
>>>>>0 0 0 0 0 0 0 x
>>>>>0 0 0 0 0 0 1 0
>>>>>0 0 0 0 0 1 0 0
>>>>>0 0 0 0 b 0 0 0
>>>>>0 0 0 1 0 0 0 0
>>>>>0 0 1 0 0 0 0 0
>>>>>0 1 0 0 0 0 0 0
>>>>>x 0 0 0 0 0 0 0
>>>>>
>>>>>Thus some 64-states and most 32-bit or less states fits perfectly to a 2**6
>>>>>range by "De Bruijn folding" with empirical determined individual magics for
>>>>>each source square and direction.
>>>>>
>>>>>Obviously each single bit-subset of the five or six bits leaves unique upper six
>>>>>bits after a multiplication with a DeBruijn constant, because the DeBruijn is
>>>>>per definition a sequence of 64 unique 6-bit strings - and mutiplication with
>>>>>power of two is like shifting left by log2. That is the original idea of using
>>>>>De Bruijn multiplication as log2 or bitscan.
>>>>>
>>>>>Having more bits set produces modulo 64 sums of appropriate unique subsequences.
>>>>>So we have "only" to choose a De Bruijn or "modified" De Bruijn where all sums
>>>>>modulo 64 are unique.
>>>>
>>>>I am not really sure that I understand your suggestion about ignoring outer
>>>>occupied bits.
>>>>
>>>>I need to x-ray for some depth for battery calculations.
>>>>
>>>>If I have a queen and two rooks on a file (likely and desirable) or if I have a
>>>>bishop and two queens on a diagonal (rare in practice but desirable), then I
>>>>need to know about it. I also want to know what is behind my ram for as deep as
>>>>I can batter. E.g. does this queen sacrifice make sense?
>>>>[D]7k/3n2q1/5p2/8/6N1/2Q5/1B6/Q1K5 w - -
>>>
>>>Now i'm also not sure whether i completely understand our switch approach ;-)
>>>
>>>I mean from h8 to a1 there is no square "behind" a1.
>>>So whether a1 is attacked or not is not affected by it's occupied state. Same is
>>>true for the black king considering a1-h8 direction.
>>>
>>>The pure occupied state on that ray is not appropriate for batteries, pins and
>>>discovered checkers, but subsets of occupied - all other own/opposite pieces
>>>with same attack directions and own/opposite king...
>>
>>We can know that Qxp is winning only by eval (no search needed). Not fully
>>accurate without search, of course, but sort of like a free SEE. But without
>>knowing the king is in the corner, then we will not consider Qxp very seriously,
>>because the half-pin information is vital for the move.
>
>
>Yes, you are rigth - kings should be considered over the whole ray, aka must not
>be subset of the up to six inner occupied squares.
>
>>
>>Maybe what you are referring to is that for some rays, I do not need all 127
>>states? For instance on a1 we have one null ray (0 states) and one ray with all
>>127 states for the diagonals.
>
>I aware of that.
>
>>
>>I do not see how I can do away with the chessmen that sit in the corners in the
>>example that I posted.
>
>My current focus was for simple attack sets - like rotated.
>Getting attacks of a sliding piece which of course can resist on an outer
>square. Only potential blockers are considered on inner squares only. I can
>imagine to get "shadow" attacks of Qa1 and Bb2 to make a second lookup/switch
>considering the "innner" own sliders of same attack direction.
>
>In your position you want also the information that d4,e5 and f6 are attacked
>one time directly and two times inderectly (on that ray), and that g7 is "half"
>pinned. So your "index scheme" seems a bit more sophisticated than only
>switching by occupied state, as your initial switch sample suggested to me.
Yes. I think you can easily see that "everything" can still be precomputed
before hand and so that with just a few operations you can figure out a lot of
information to be returned by lookup.
There are a lot of detailed structures that are not explained in any detail.
For instance, for a pin/spear/battery -- you can store pin type (battery, pin)
pin level (pawn-pin..king-pin), square of the pinned piece and square of the
piece behind the pin, the intervening piece type, etc. There is a lookup for
that (of course) but we just examine our board array to see who sits on the
intervening bit.
The main idea is to have a "nearly free" SEE {it should at least be considered
an incremental SEE, though there is obviously work involved} and also to
completely avoid managing any board rotations.
It turns out that the scheme is useful for other things as well (e.g.
incremental evaluation, an alternative method to create an undo...)
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.