Chess programming using bitboards
Joel Rivat
>For the attack bitboards. Stay away from them, they are a nightmare.
>Really. Complete Morgoth (that was the name, right?) and after you
>stretched it to the limit you have the options to be satisfied and
>give up chess programming (warning: it is addictive) or to write a
>whole new one. *Then* it makes sense to use bitboards because you
>will know exactly what you want.
I do not agree that attacks bitboards are a nightmare.
I would agree that incrementally updating attacks bitboards is a
nightmare, but in fact I think that it may be a better idea to
compute them at need. Then the attacks bitboards stuff consist only
of two functions AttacksFrom(square_t sq) and AttacksTo(square_t sq)
which can be strongly optimized.
You then loose the possibility to use the attacks bitboards too much,
but you win the copy the arrays (1024 bytes for both) during MakeMove,
and the update of the arrays...
In my program ChessGuru I have both implementations and choosing one
of them is just defining or undefining the macro INCREMENTAL_ATTACKS.
I do not want to make public any result now as my functions
AttacksFrom(square_t sq) and AttacksTo(square_t sq) are not optimal,
and a lot of the attacks bitboards use can be avoided,
but I can reveal that at least for ending positions the non incremental
method is much better, which did not surprise me.
For a beginner chess programmer who wants to use bitboards I suggest
the non incremental method, which also removes the nightmares.
If you plan a very huge use of the attacks bitboards you then can
switch to the incremental method "easily", the previous work being
helpful for debugging anyway...
The question if a beginner chess programmer should use bitboards is
much more difficult as some top level chess programs don't use them...
It depends if you prefer to manipulate squares (the loop approach)
or sets of squares (the bitboard approach) and if you will have a 64 bits
computers at your disposal in the near future or not...
Personnally I have choosed the bitboard approach because I have access
to a 64 bits computer and I find it boring to write a loop for
everything you do...
Joel Rivat
Peter Gillgasch
|> Peter W. Gillgasch (gil...@ira.uka.de) wrote:
|> >For the attack bitboards. Stay away from them, they are a nightmare.
|> >Really. Complete Morgoth (that was the name, right?) and after you
|> >stretched it to the limit you have the options to be satisfied and
|> >give up chess programming (warning: it is addictive) or to write a
|> >whole new one. *Then* it makes sense to use bitboards because you
|> >will know exactly what you want.
|>
|> I do not agree that attacks bitboards are a nightmare.
|> I would agree that incrementally updating attacks bitboards is a
|> nightmare,
That was what I wanted to say. Sorry for being unclear about this.
Using precomputed bitboards as optimization technique is of course
easy even for a beginner, but *only* if you are not interested in
portability. If you are it is still relatively easy, but a bit
more "advanced". Damned little endian boxes (^8
|> but in fact I think that it may be a better idea to
|> compute them at need. Then the attacks bitboards stuff consist only
|> of two functions AttacksFrom(square_t sq) and AttacksTo(square_t sq)
|> which can be strongly optimized.
Hm. That idea is cute, since it will allow you to use most of the
code developed for an incremental design. Of course it will be very
suboptimal in the beginning, but it is a relatively easy way to start
to look into this.
|> You then loose the possibility to use the attacks bitboards too much,
|> but you win the copy the arrays (1024 bytes for both) during MakeMove,
|> and the update of the arrays...
My tests on the DEC Alpha using a incremental design were quite disappointing.
Something like 20,000 nps on a 175 mhz machine. Compared with the results on
a 80 mhz PowerMacintosh it is not what I expected... The block move is
really expensive on that machine...
|> In my program ChessGuru I have both implementations and choosing one
|> of them is just defining or undefining the macro INCREMENTAL_ATTACKS.
|> I do not want to make public any result now as my functions
|> AttacksFrom(square_t sq) and AttacksTo(square_t sq) are not optimal,
|> and a lot of the attacks bitboards use can be avoided,
|> but I can reveal that at least for ending positions the non incremental
|> method is much better, which did not surprise me.
How is the performance of the incremental code on the alpha?
|> For a beginner chess programmer who wants to use bitboards I suggest
|> the non incremental method, which also removes the nightmares.
|> If you plan a very huge use of the attacks bitboards you then can
|> switch to the incremental method "easily", the previous work being
|> helpful for debugging anyway...
Good point.
|> The question if a beginner chess programmer should use bitboards is
|> much more difficult as some top level chess programs don't use them...
Actually I asked some teams at the WCCC about move generation and
bitboards. At that time I have already started to write "experimental"
code for the new engine, so I took the chance to ask some programmers
who are dealing with the problems of chess programming much longer than
I do - which was probably the most interesting thing for me in Hong Kong.
Most of the people that were willing to talk about this don't believe
in them. But some people were baffled by the question and changed
the subject of the conversation very quickly...
|> It depends if you prefer to manipulate squares (the loop approach)
|> or sets of squares (the bitboard approach) and if you will have a 64 bits
|> computers at your disposal in the near future or not...
Well, a 64 bit move generator design can be implemented on any 32 bit
machine easily and it could even be heavily optimized for those machines
(something that I didn't do yet). Of course something like the PPC620
would be really interesting to have (^8
|> Personnally I have choosed the bitboard approach because I have access
|> to a 64 bits computer and I find it boring to write a loop for
|> everything you do...
Personally I am switching to bitboards because in my case I felt
that I stretched the "loop" engine I designed to the limit. And
bitboards are really fun - but getting the incremental updating
stuff up to speed was a *long* way...
-- Peter
------------------------------------------------------------
Peter W. Gillgasch
Klosterweg 28/I-113 email gil...@ira.uka.de
76131 Karlsruhe/Germany Phone ++49/(0)721/6904255