Author: Robert Hyatt
Date: 18:54:06 01/17/99
Go up one level in this thread
On January 17, 1999 at 18:35:15, Vincent Diepeveen wrote:
>On January 17, 1999 at 00:22:38, Robert Hyatt wrote:
>
>>On January 16, 1999 at 14:37:49, Vincent Diepeveen wrote:
>>
>>>On January 15, 1999 at 22:09:04, Robert Hyatt wrote:
>>>
>>>>On January 15, 1999 at 21:26:17, Vincent Diepeveen wrote:
>>>>
>>>>>On January 13, 1999 at 07:19:54, Ernst A. Heinz wrote:
>>>>>
>>>>>>On January 13, 1999 at 06:13:30, Vincent Diepeveen wrote:
>>>>>>>
>>>>>>> [...]
>>>>>>
>>>>>>Vincent,
>>>>>>
>>>>>>As usual you spread your own fallible impressions and interpretations
>>>>>>in a style that suggests they are proven facts. But indeed they are *not*.
>>>>>
>>>>>I have not seen a single function using bitboards making attacktables
>>>>>for every square indeed.
>>>>>In crafty there is only this: a function that gives
>>>>>soemthing for a single square.
>>>>>
>>>>>I thought a long time about it.
>>>>
>>>>Vincent this is simply wrong, and your reasoning is badly flawed. In early
>>>>versions of crafty I did _full_ attack bitmaps, so that at any point I had
>>>>the bitmaps for the squares attacked from a specific square, and bitmaps for
>>>>every square showing which squares were attacking _it_. I kept these
>>>>incrementally updated.
>>>
>>>I talk in numbers Bob, not in "i have done something in the past".
>>>You generate a bunch of different bitboards. Cool with me.
>>>
>>>A) You miss number of attackers
>>>B) you miss where the attacker comes from
>>
>>Questions: (1) have you read chess skill in man and machine? (2) Have you
>>read the comments in main.c (crafty)? If the answer to either question is
>>yes, then your question makes no sense. In 1976 chess 4.0 had both of the
>>things you ask for. They kept an array of bitmaps called attacks_from[sq] that
>>had 1 bits set for each square the piece on sq attacks (this is like what I do
>>except I compute it on the fly faster than they incrementally updated this).
>
>We are not talking about doing things incrementally here or on the fly.
>
>Just bare speed of it.
>
Then as I said, _they_ (chess 4.x, Slate, Atkin) did it in the 1970's on a 14
MIP computer. I did it in crafty. So it is obviously doable. I don't do it
now because I don't use that kind of data very often.
>>They also kept an array of bitmaps called attacks_to[sq] that had a one bit
>>set for each square that attacks sq. If you PopCnt(attacks_to[sq]) you get
>>the number of attackers for that square. If you want black or white attackers
>>you first AND to exclude opposing pieces. So bitmaps give you A and B if you
>>want them. Chess 4.x had them. Early crafty versions had them. So I fail to
>>see why you keep saying this can't be done? IE just because I don't do it
>>doesn't mean I can't do it. It means I don't _want_ to do it at present.
>
>You can do it but only very very very slow. I'm sure you would do it if
>it was fast in your datastructure. Gives you a big bunch of powerful info.
then you assume wrong. Taking that out sped me up by 10%. Putting it back
in would cost the same thing again. But at present I don't do it because I
don't _need_ it. I only do what I need. And when I need it I do it.
>
>So saying now "I don't wanna do it and therefore shut up" has nothing
>to do with this.
By the same token, your saying "I need it so why don't you do it? Because it
is too slow for you to do" is pure baloney...
>
>It's like we want to fly therefore i design a new wing, as
>a new engines got developed you say: "i'm not interested in that
>engine, my wing is perfect".
Maybe you have this _turned around_? IE I am quite happy with _my_ wing
at present. I am not telling _you_ that you need a new wing. So please stop
telling me that _I_ need one. I should be the judge of that?
>
>Where i adapt and say: "i want to use that new engine for my airplane
>so i design a new wing that works"
That's not quite how I'd put it. More like "I'm using this brick for a wing
and it is the best way to do it because that is the way I am doing it." Do
what you want. Let others do the same. In the end, the best approach 'wins'.
>
>>
>>
>>>
>>>Main thing is that i miss are numbers. Things can get
>>>measured you know.
>>
>>
>>both chess 4.x and crafty (early versions) had this. I would think it could
>>be measured since we both did it.
>>
>>
>>
>>
>>>
>>>>I later decided that the 'latter' bitboard wasn't being used much and I got
>>>>rid of it as it did have a cost. But that cost was some 10% overall speed,
>>>>which I could instantly get back if I wanted to use such bitmaps.
>>>
>>>>your bad logic seems to be "if it isn't in Crafty now, it isn't practical
>>>>or it can't be done." On the contrary, if it isn't done in crafty now, it
>>>>is because I don't need (or don't want) the information at present. Nothing
>>>>says others don't / can't do it...
>>>
>>>This has to do with how your tables look like. You need to
>>>add all your bitmaps before you can do something useful with it.
>>>That is a mainpoint. Please don't get personal, i am not insulting you
>>>personal. I'm just talking about
>>
>>
>>So, why can't I add to my bitmaps if I need to? I don't see why that is
>>a problem. I assume you have added to your data structures over the past
>>couple of years? I can modify mine just as easily...
>
>It shows that bitboards are not useful in many aspects if you plan
>to expand and improve evaluation (which i consider weakest chain of
>programs) and it was already clear, although you are very good
>in writing info around functions, that it is not an easy way of working
>with datastructure.
>
>This 'way of working is tough with bitboards' is of course an opinion,
>which we probably disagree in, although it took years for you and ernst
>just to be able to work with it as you wrote in previous msg which shows my
>point, where the simple way of representing things everyone can work at once
>with.
So what? Parallel programming is orders of magnitude more difficult than
learning bitboards. I'm doing just fine with it. How is yours coming? I'd
say I have had _no_ problems adapting to new programming issues and ideas.
>
>Now apart from this opinion we have bare speed facts.
>
>Suppose everyone would have a computer C where a datastructure X is way
>way faster for your program than a datastructure Y.
>
>Now without further info i would simply use data structure X, no questions about
>it.
>
yes, but we don't have that situation.
>
>
>>>a) how difficult bitboards are to work with
>>>b) that you need 64 bits machines for it which are very expensive
>>> unless you want to buy an outdated 21164 533Mhz chip, with say a 1 gig
>>> harddisk in it (this advertisement here i see in this magazine offers
>>> it for the prize of 6000 dutch guilder (3500 dollar) a 1 GIG harddisk in
>>> it!! and 64 MB RAM).
>>>
>>>c) that after the big effort of a and b it is not possible to do everything
>>> quickly with it and that it is definitely not faster.
>>
>>Maybe it isn't faster for _you_ to do things faster. My speed isn't bad. When
>
>It isn't bad, that's sure.
>
>>I run on a 64 bit machine my program goes twice as fast. What does _yours_ get
>>when you do so? If you want to write for 32 bit machines (past and present)
>>that's fine. I choose to write for the future. And the future _is_ 64 bits.
>>Just wait 5 years and see if you can find a 32 bit machine left.
>
>Wait 5 years and you need a better evaluation.
>Try evaluating with bitboards then. Bitboards is then past.
I'll make a wager with you. That I am still using bitboards in 5 years, and
that I'll still win more games than I lose when we play. I see _no_ sort of
asymptotic limit. Quite the contrary I see lots of speed coming with 64 bit
machines.
>
>If i would use 64 bits my program goes way faster than it is now,
>assuming that within 5 years there are some very good 64 bits compilers,
>which is not a bad assumption. There is still no good PII/PRO
>compiler right now.
>
>And about the speed difference, our speed difference is currently more
>than a factor 2 at a 32 bits machine when you would do the same in evaluation.
>
>It makes no sense slowing down a program more than 2 times in order to
>get it 2 times faster at a 64 bits machine, that's how i see it.
>
>>>>>>The "problems" (rumors?) you allude to in the post only show that you have
>>>>>>*not* understood what bitboards are capable of and how to handle them
>>>>>>effciently. You are of course free to criticize Bob's coding style and his
>>>>>>design decisions in "Crafty". However, only inexperienced and narrow-minded
>>>>>>people draw general conclusions from just a single example (i.e. the source
>>>>>
>>>>>Now comon comon, who is narrowminded here.
>>>>>I've investigated bitboards just as close as you did.
>>>>>
>>>>>Note that i don't have a 64 bits processor, and even if i did, then still
>>>>>i never might sell a 64 bits program, where never is defined as next
>>>>>few years.
>>>>>
>>>>
>>>>I doubt you have 'investigated bitboards just as close as you did' (you talking
>>>>to Ernst here). It took me a _long_ time to become competent with them. It
>>>
>>>We don't doubt your insight in bitboards Bob. Please don't doubt my insight
>>>either. That's a bad way of writing emails.
>>
>>I know my programming skills. And I know it took me several months to become
>>'bitmap-friendly'. I doubt you are better than I am. No reason to doubt you
>>are not as good, of course, but better? I doubt it. Which means you haven't
>>'studied' them until you have _done_ them. And I'm not talking about a simple
>>pawn structure bitmap. We had a single bitmap in cray blitz to detect in check
>>stuff. That is _not_ the same thing.
>
>The time you needed to become 'bitmap' friendly says enough about
>friendlyness of developping a program using bitmaps only.
So? The time needed to become a "parallel searcher" is even longer... But
it is still worthwhile. Difficult or not. I don't worry about 'easy'. I
worry about 'viable'
.
>
>My bitmap is different from crafty bitmap. dunno how you have implemented
>it cray blitz. Don't have the source of it. Would love to have that source
>code: diep@xs4all.nl. you told you spreaded it at the cray computer mailing
>list. I'm not at that list, please email it to: diep@xs4all.nl
>
>>>Don't forget i use a single bitboard for speeding up my pawn structure
>>>evaluation. I take the best of all worlds. That's why
>>>in the rest or the program i don't use bitboards.
>
>
>>Remember, the man who is blind can't appreciate art. Maybe you just don't
>
>Don't compare datastructure with art too much.
I wasn't. You haven't tried bitmaps to the point where you feel comfortable
with them. So of course you are going to see problems where I only see
solutions.
>
>If you say: my datastructure is
>a very original one, i invented it myselve, and i don't care whether it's
>faster or slower, then i respect you completely.
I didn't invent them, they are 30 years old.
>
>If you say: "my datastructure is a very good one to represent a chessboard,
>just wait till within 5 years you also have a 64 bits machine then it rocks,"
>then i completely disagree with you!
>
>I also wonder: when a 64 bits machine is really that fast to you, why
>buy a quad Xeon for a big bunch of money instead of a quad 21164 533Mhz alpha,
>which is only 300 dollar a processor x 4 = 1200 dollar for processors
>where quad Xeon is a big multiple of it.
Do the math. There are no quad alphas available, except thru Digital, and
I can't buy them for $10,000.00... not even close. I have _run_ on multiple
alphas. With any luck, you'll be on the wrong end of one in Paderborn.
>
>>understand them well enough yet. They are an alternative data structure,
>>nothing more or less. Anything you can do I can do. Anything I can do, you
>>can do. No more, no less.
>
>Not at the same speed, and also you need way more time and need
>way more time writing code, when developing things using bitboards!
>
absolutely not. The learning curve is the only difference. Once used to
them, coding is _not_ hard... in fact it is often easier, because pattern
matching is easier/faster.
>>>>did _not" come by just taking a casual look. I had to start writing code and
>>>>spend a year figuring out how to do everything I wanted to do efficiently. An
>>>>example: I teach a programming language course and cover some esoteric things
>>>>like APL, prolog, etc. And when I assign a program in (say) APL to students,
>>>>I get "C" programs back. Syntactically APL. But algorithmically C. That is
>>>>what happens with bitboards for a good while, _until_ the writer becomes used to
>>>>'thinking bitboards'. (or thinking parallel search or whatever). These topics
>>>>are _not_ something you spend a day or two thinking about and then say "been
>>>>there, done that, it's no good..."
>>>
>>>I'm not busy one day with my program either. We don't doubt your experience,
>>>that still however doesn't give the objective reader clear numbers about
>>>WHETHER you can do it.
>>>
>>>It is very simple. Just dig up your old code and test it at your Xeon.
>>>matter of a few minutes to run the old code imho and with your deep insight
>>>easy to initialize the demanded arrays, then please count speed of it,
>>
>>
>>what 'old code'? incremental versions of crafty? why?
>
>>>leave the code in crafty as a 'testroutine' and we know.
>>>
>>>>
>>>>>>code of "Crafty"). There are many ways to do things differently with bitboards
>>>>>>and rotated bitboards than in "Crafty". Overall, your post mainly elaborates
>>>>>>on some of Bob's design decisions which you deem non-optimal.
>>>>>>
>>>>>>The only real disadvantage of bitboards at the moment is the obvious penalty
>>>>>>of 64-bit integers on 32-bit CPUs which comes hand in hand with unfortunately
>>>>>>limited compilers and programming environments.
>>>>>
>>>>>I'm waiting for your implementation of attacktables using bitboards.
>>>>>
>>>>>I'll even be friendly to you allowing it to do at a 64 bits machine,
>>>>>which next 5 years is probably out of wallet of 99% of the people,
>>>>>but then please don't use macros, but write it all out. Macros confuse people,
>>>>>giving them the idea that it is simple using bitboards, where actually
>>>>>every macro is a kind of hacked thing in bitboards imho. Please post again
>>>>>how you count the number of bits in a bitboard?
>>>>>
>>>>
>>>>
>>>>well known:
>>>>
>>>> int c;
>>>> while (bitboard) {
>>>> c++;
>>>> bitboard=bitboard&(bitboard-1);
>>>> }
>>>> return(c);
>>>
>>>>is best for small numbers of bits.
>>>
>>>>Or on intel machines, even better is this piece of code:
>>>
>>>>PopCnt:
>>>> movl 4(%esp), %ecx
>>>> xorl %eax, %eax
>>>> testl %ecx, %ecx
>>>> jz l1
>>>>l0:
>>>> leal -1(%ecx), %edx
>>>> incl %eax
>>>> andl %edx, %ecx
>>>> jnz l0
>>>>l1:
>>>> movl 8(%esp), %ecx
>>>> testl %ecx, %ecx
>>>> jz l3
>>>>l2:
>>>> leal -1(%ecx), %edx
>>>> incl %eax
>>>> andl %edx, %ecx
>>>> jnz l2
>>>>l3:
>>>> ret
>>>>
>>>>that is _very_ fast...
>>>
>>>
>>>>>At a PII-450 diep generates 250k attacktables a second in the position
>>>>>after openingsposition+1.e4,e5 2.d4,d5
>>>>>
>>>>>I'm only using C code. Not a single assembler instruction is in my code,
>>>>>as far as i know your bitboards are written in C? In that case
>>>>>there is no unfair comparision.
>>>>>
>>>>>An attacktable is a table in my program of
>>>>>int attacktable [2][64];
>>>>>First i clean the attacktable, then i store for every piece all attacks.
>>>>>
>>>>>that includes
>>>>> a) piece that attacks (what square it is from)
>>>>> b) number of attackers (clear i guess)
>>>>> c) kind of piece (pawn,knight,bishop ...)
>>>>>
>>>>>I need this to evaluate in my program, as it evaluates also 'relationships'
>>>>>between pieces and mobility is also depending upon it.
>>>>>
>>>>>My mobility goes like this: i loop over all squares of a piece, including
>>>>>xray squares and then find out how important control over such a square is
>>>>>depending on all kind of chessknowlege where info from attacktable is
>>>>>used using lookup of attacktable[c][sq] where sq are all squares that
>>>>>need to be considered. And as i use this 'attacktable' info a lot,
>>>>>i therefore store it in this a simple way in [2][64] array.
>>>>>Every time i use something out of my attacktable i definitely not
>>>>>am gonna add all values of the different bitboards *just* to get the
>>>>>number of attackers. That would slow down my program *considerable*.
>>>>>
>>>>>Now a problem using attacktables with mobility is:
>>>>>if you do all squares at once (otherwise bitboards not rewarding),
>>>>>that is kind of tough, considering that values are different
>>>>>for every square. So where i simply count a+b+c, where probably
>>>>>a != b != c then you run into problems, as for a range of -50 to +50
>>>>>you need to do 101 bitboard counts.
>>>>>
>>>>
>>>>
>>>>I've already pointed out that this is false. Here's how to do this _fast_ on
>>>>the cray:
>>>
>>>>first compute the bitmap for the squares a piece on "sq" attacks. This produces
>>>>a set of zeros and ones. Then take a static const array sqval[64] where you
>>>>have filled in the value of attacking each square. IE values for e4 d5 and
>>>>so forth, and _every_ value can be different.
>>>
>>>>ON the cray, we use the vector load instruction, but from this sqval[] array
>>>>we only load the values with 1's set in the according bitmap. We sum these
>>>>and we are done, and it takes roughly 20 clock cycles to get the first value
>>>
>>>The problem is that according bitmaps. If value can range from -50 to 50
>>>then you need to do this 101 times, because you need a bitcount for
>>>every value.
>>
>>NO NO NO. on the cray, I load the attack bitmap. One instruction. I then
>>do a vector load to grab the values for mobility (different value for each
>>square if you want.) I then sum those values. I do the *whole* thing in
>>under 50 clock cycles. *whole thing*. No loops of any kind either... And I
>>do this while I am doing other things as well... so I don't even notice the
>>'expense'...
>
>Please don't confuse the cray-many-million-dollar-computer with nowadays
>hardware.
_You_ are the one that keeps saying "this can not be done with bitmaps." I
simply showed that not only 'can' it be done with bitmaps, but on hardware that
_really_ supports bitmaps it can be done so much faster than what you are doing
that it isn't even funny to think about.
>
>
>>>>from the sq array, and assuming you have 20 squares you attack, the entire
>>>>thing will complete in about 50 clock ticks _total_.
>>>>Not very inefficient. So things you think are hard are actually trivial on the
>>>>right hardware...
>>>
>>>A rude way of mobility can be done quickly. NO doubt. Please don't talk
>>>about the cray. We're talking general audience here. General audience
>>>doesn't have a cray nor alpha 533 and also will not buy it.
>>>
>>>In that respect crafty does a good job as it can be compiled at all
>>>platforms.
>>>
>>>>>I have given you exact data here.
>>>>>2 challenges are posted, from which one is very clear.
>>>>>The second one, mobility is simply impossible, unless you use the same
>>>>>code i use, so you get every square out of the bitboard and then run
>>>>>through the evaluation code, which means that the loop used over the squares
>>>>>is different, but not the evaluation code
>>>>
>>>>better rethink that 'impossible' as I just did it and I did it many times
>>>>faster than you can. On the cray of course. Or on the intel i860/960...
>>>>which are commodity micros.
>>>
>>>I fear you didn't get the point, or simply are hiding it.
>>>
>>>I have a big range of values here and a big bunch of chessknowledge
>>>which decides which square gets what value, and that chessknowledge
>>>is based on piece relationships and attackers and a lot of other things.
>>>
>>>Please don't compare that with a rude "how many moves can i make" count.
>
>>read the above. Generate the array of scores for each square. I can
>>extract and add them faster than you can.
>
>At the cray computer perhaps dear sir,
>we were talking rotated bitboards as you use at the PII.
>
>Please reanswer it for PII.
we weren't talking about the PII. We were talking about bitmaps period. I
believe you will find that 64 bit machines 5 years from now have the same
sort of vector capabilities as crays do now. There are already machines that
do.
>
>>>I don't doubt we all generate that quickly. Actually in DIEP i generate
>>>15 million move generations a second after 1.e4,e5 2.d4,d5 at a PII-450
>
>
>>>>>Assuming in all cases lossless code,
>>>
>>>This was my point. Your code is lossy to mine.
>>
>>
>>
>>what is 'lossy' code? concept makes no sense to me in this context.
>
>he he he he he,
>I thought you gave lessons as a professor in things like that...
>
I do. I teach about "lossless and lossy joins in database theory." But
that implies 'losing something'. I lose _nothing_.
>>
>>>
>>>>>Greetings,
>>>>>Vincent
>>>>>
>>>>>>=Ernst=
>>>>>
>>>>>Please guys don't moderate Ernst too tough, if you do, then i dunno
>>>>>what Heinz thinks of himselve.
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.