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.