Author: Robert Hyatt
Date: 13:25:23 11/28/97
Go up one level in this thread
On November 28, 1997 at 13:08:04, Chris Whittington wrote:
>
>On November 28, 1997 at 12:08:23, Don Dailey wrote:
>
>>Hi guys, we just started writing a bit board based program and have
>>some observations to make and some comments on the comments!
>>
>>
>>>>I personally think that algorithm for algorithm, offset and bitmap are
>>>>equal.
>>
>>So far based on new experience with bitboards I believe this is only
>>true
>>for 8, 16 and probably 32 bit machines.
>>
>>>1. We go for speed. Bit map approach is neat, you just do some count
>>>bits. Offset is slower, we need to trawl through all the squares,
>>>looking for attacks.
>>
>>I once did a really fast mobility with offset by incrementally updating
>>a bit board type of structure for sliding pieces it was fast and was not
>>too much slower than bit boards.
>>
>>>2. We go for intensive knowledge. We say mobility is some function of
>>>SAFE movement capability into each square. Now, bitmap or no bitmap, we
>>>have to process each square for safety. Basically a swap-off or exchange
>>>evaluation for each piece movement into each square. Isn't offset
>>>faster, because we already have the attack/defence bits ranked on each
>>>square, smallest attacker value first ?
>>
>>>I think you can find many examples of quick and easyness. But my case is
>>>that intensive knowledge processing is probably better with offsets.
>>
>>Since using bitboards, we have been able to add knowledge we would not
>>have attempted with offset style programs.
>
>Can you expand on this ?
>
>What knowledge ?
>
here's one example: suppose you want to recognize a set of possible
pawn configurations on a certain part of the board. IE suppose you have
gotten tired of losing Stonewall attacks, and want to pick up on what is
going on to avoid castling into an overwhelming attack. With bitmaps,
this
is quite easy. I can ask "does white have a pawn on d4, e3 and f4?"
with
one simple operation, not three separate tests. As I said, I call this
"bit parallel operations" because I can test multiple bits at one time,
an off-beat form of parallel computing...
>>It really seems to be the
>>case for us that intensive knowledge processing is better with bitboards
>>but maybe we are missing some techniques that others have discovered.
>>
>>>And this argument then gets taken further. If you select or promote the
>>>bitmap paradigm, you are already promoting and selecting a design.
>>>Namely that of fast searcher with less qualitative knowledge ........
>>
>>I hope we are not making a big mistake but we are moving toward more
>>knowledge
>>and thought that bit boards and the new 64 bit stuff comming out made
>>bitboards the better choice for Cilkchess.
>>
>>>Well this is the key, no ? For the Crafty paradigm it works. For the
>>>knowledge paradigm, I think it gives problems. Your way promotes a
>>>certain sort of chess engine .....
>>
>>>But the question is how effectively, and does one way actually steer the
>>>designer down specific pathways ?
>>
>>It changes the way you look at things definitely. As I said earlier, we
>>are now adding a lot of knowledge because it is so tempting to do it
>>with
>>bitboards.
>
>Again, what ? tell us :)))))))))
>
In general, here's the "gist"... anything you do that takes two loops
(IE one loop to iterate over patterns, another inner loop to iterate
over
specific squares) I can do in one. Other things (like mobility) are
essentially free. IE, the very first evaluation I did in crafty, just
to get it running, was full mobility for all pieces.. And I don't mean
just counting square, but, rather, counting "safe" squares... And the
eval didn't register when I did profiles to speed things up...
>
>>
>>>One concern (repeated here) is that the bitmap doesn't inherently store
>>>the attacker significance. So if we want to find the smallest attacker
>>>we have to hunt around the bits first, and so for the next smallest etc.
>>>For qualitative work on attack/defence of a square this is going to be a
>>>drawback.
>>
>>I don't think bitmaps prevent you from doing any of this stuff fast.
>>Finding
>>the smallest attacker is extremely trivial with bitmaps.
>
>For offset, its likely to be just taking the least sgnificant bit. How
>much faster and how can you do this with bitboards ?
In Swap, I do it like this: I have a bitmap that gives *all* squares
that
currently attack the target square I am interested in. To find the
pawns
that attack square, just and this with the pawn bitmap. To find the
knights,
and with the knight bitmap. There are other approaches that might be
faster,
if this is a common thing to do. As always, redundancy can save time,
or
slow you down. It depends on how bad you need the redundant data. But
there's
nothing that inherently makes this good or bad...
>
>> Incrementally
>>updating and maintaining an attack board is certainly not free is it?
>
>Nope :(
>
>>There
>>is no reason they cannot be incrementally updated with bit boards
>>either.
>
>True.
>
>>
>>>But I still make the point; the design compromise made to be bitmapped
>>>ot offseted is going to have major consequences for the knowledge/speed
>>>decision.
>>
>>
>>We have learned that knowledge becomes more important with depth. Most
>>people already knew this but we proved it to ourselves with a long
>>autotest
>>study. I really don't see any reason why you cannot have a very
>>knowledge
>>intensive program with either approach. It seems to me that you simply
>>choose different compromises { and everything we do is really just some
>>compromise hack isn't it?}
>
>Yes.
>
>>
>>There always seems to be some clever way to do something with either
>>approach
>>and I'll bet the best possible bit board program would not be much
>>better,
>>if at all, than the best possible offset approach.
>
>Which is what Bob said as well a couple of posts back. This is what
>interested me, because we had been hearing so much about stuff really
>flying with 64 bitboards. Now it seems they both just walk at the same
>speed .... ?
with perfect programming, I think they should be 2x faster than offset
representations, *unless* an offset generator can somehow take advantage
of 64 bit words in a way that has not been done yet...
>
>> It has a lot more to
>>do
>>with the programmers imagination and skill.
>
>Agreed. Tell us some of these things imaginative ..... :)
>
>Chris Whittington
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.