Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: sliding attacks in three #define

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.