Author: Tom Likens
Date: 12:55:17 04/10/04
Go up one level in this thread
On April 09, 2004 at 23:44:03, Christophe Theron wrote: >On April 09, 2004 at 16:07:25, Sune Fischer wrote: > >>On April 09, 2004 at 15:26:34, Christophe Theron wrote: >> >>>On April 09, 2004 at 14:27:48, Sune Fischer wrote: >>> >>>> >>>>>Clearly, nothing beats the ugliness of bitboards. >>>> >>>>This may not be the best example to judge by. >>>> >>>>-S. >>>>> Christophe >>> >>> >>> >>>In the contrary, I think it's fairly typical of bitboard code. >>> >>>Elegance is supposed to be the strong point of bitboards. >>> >>>The only thing I find elegant is the pseudo-great starting idea "64 squares <-> >>>64 bits". >>> >>>Passed this point everything becomes unreadable and ugly. >> >>I know what you mean by that of course. >>There are some macros for rotated which is very ugly and initializing the lookup >>tables isn't pretty either. >> >>When that is over and done with however, you never need to look at it again. >> >>The question is what do you get in return. >>What you get in return is a piece list which is very easy to work with. >>You get fast checks for a lot of simple stuff, ie. is the king in the corner >>could be something like (white_king & (H1|G1|H2|G2)) is there white rooks on >>7th: (white_rooks & rank7) etc. >>So a lot of little things are easy. > > > >Yes I have heard this over and over again but would you believe that in Chess >Tiger testing for a piece on a corner, on a border (horizontal or vertical), in >the center, in the two center rows (4 and 5) and in the two center files (e and >f) is just a single arithmetic operation with no memory reference? I mean I'm >beating bitboards easily on these ones. > >And I have more examples like these. > >I also need only one arithmetic operation to test if I have a passer, advanced >passer, open files and so on. OK, this is because I update this information in >make move, and pawn structures hashing make this basically FREE - less than 0.1% >of execution time. But again, bitboards would not provide any advantage here. > >The useful little things are extremely easy in Chess Tiger as, with much less >L1/L2 performance hit than with bitboards. > >When you think about it, 8 bitboards use as much L1/L2 cache as the whole board >representation. And a bitboard program needs to handle so many bitboards!... > > > > > >>For the attacks I don't know if they is faster, they use a table so they are >>loopless and branch pridictionless, so it might be faster if cache is big >>enough. > > > >Using bitboards for attacks seems to be the most efficient when you want to >compute all attacks at once. > >Unfortunately that's exactly the kind of things I find counter productive. I >compute an attack of one piece on a given square only when I need it. Most of >the time I won't need all attacks of all pieces to all squares. > > > > > >>Another possibility is to do a hybrid approach to get the best of both worlds. >>This might be faster but for now I'm not interested in complicating my program. >> >>>I also see it often used to pre-compute attack tables and such, which is in my >>>opinion contrary to one of the most important things I have learned in computer >>>chess: do not compute anything in advance if you are not certain that you will >>>use it. >> >>Actually I'm on the same side as you in this, altough I'm not 100% convinced we >>are right :) >> >>Attack tables, if you need them at every node because you do a complicated eval >>every node, might actually save time. >>Of course we can then discuss if a full eval at every node shouldn't be avoided >>in the first place, but "evaluation based search" seems to be a hit with for >>some people. >>I think it sounds interesting too, I just wouldn't know what to do with it :) >> >>>This is not an intrinsic problem of bitboards, it's just that use of >>>bitboards often go along with this misuse of computing resources, is it just by >>>chance? >> >>Asside from the attack lookup table I don't think you need that much else. >> >>Crafty has a lot of stuff for detecting outposts and such, but a filler could do >>this just as well on the fly. It's just a matter of tuning which is faster in >>your program. > > > >It's almost irrelevant given the little time it takes. > >The problem is that bitboards promise very good execution times for complex >evaluations terms. And that I basically never need to do such complex >calculations... > > > > >>>Bitboards are a great tool allowing you to compute very complex things in a >>>blink. The problem is that in a chess program you rarely need to do these >>>complex computations if you know what you are doing, and so you end up with ugly >>>and unreadable code and waste of resources (in particular of L1 and L2 caches). >> >>If you want to program to run within 64k I would not recommend bitboards. >>But this limit is from the early 90ties, today we have 256k minimum and soon >>512k to 1024k and growing larger with each generation of CPUs. >> >>>That being said, I do not want to be too harsh: it is probably possible to write >>>a top-level chess program using bitboards, a program that would be not very far >>>behind the programs using more portable approaches like 0x88 and derivatives. >>> >>>Somebody will write one some day. >> >>I think it has already been done. >>Ruffian is said to be a bitboarder but since I'm not sure about that I will >>mention Crafty instead. >> >>Crafty isn't quite a "top" engine you might say, but I don't think that has got >>anything to do with bitboards, I think that is because >>1. it is open source >>2. its selective search isn't very advanced. > > > >Has a bitboard program ever topped the SSDF list? > >Naturally that's not a proof. We are going to be told anyway to wait for 64 bits >computers to be widely in use. > >And you know what? That's not going to change anything. Actually it's going to >take excessively powerful computers with loads of L1 and L2 cache for bitboard >programs to catch up. Just to catch up. If they ever catch up. > > > > Christophe I'm not sure where I come down on the bitboards vs. non-bitboard architectures. My engine is a bitboard engine, but that doesn't necessarily mean that the next one will be bitboard based. I don't believe though, that because no bitboarder has topped the SSDF list that this really constitutes any kind of proof. My strong suspicion is that if all the top commercial programmers converted over to bitboards tomorrow (yourself included) that *eventually* their new engines would again rise to the top of the SSDF. I'm beginning to suspect that creating a strong (i.e. world-class) engine involves a helluva lot more than just the basic data representation, but instead involves... 1. 24/7 dedication 2. A *real* way to measure progress 3. A selective search strategy that works 99.99999% of the time 4. Attention to about 2^64 minor details 5. A failed marriage (okay, maybe this is extreme but you see the point) regards, --tom
This page took 0.03 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.