Author: Christophe Theron
Date: 18:53:17 04/10/04
Go up one level in this thread
On April 10, 2004 at 15:55:17, Tom Likens wrote: >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 Number 5 (or something close) was the reason why Tiger has made such a progress between 1997 and 1999. :) Number 2, seriously, is worth spending several months on it. Christophe
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.