Quote:Original post by AfroFire
Ah, interesting - Why wouldn't they use bitboards? I always figured a bitboard would be the fastest way to do checks?

Some things are faster with bitboards and some aren't. If you want to program a "bean counter", you can probably get a very fast one using bitboards, but a lot of the chess knowledge that should go in an evaluation function won't be particularly easy to write using a bitboard representation. Adding attack information to your representation can probably speed things up more.

Quote:Original post by alvaro
I should mention that a lot of the top chess programs don't use a bitboard representation.

Really?
Rybka is a bitboard engine (at least according to the author) and it's currently pretty much undisputed that it's the strongest engine available.
Crafty is probably the top engine for which the source is available (hmm... maybe not these days, but it was when I was looking for a strong engine) - it's also bitboard.

Can you name a few strong non-bitboard engines? (Ideally with the source available).
I'd be very interested to see code.

Quote:Original post by alun

Quote:Original post by alvaro
I should mention that a lot of the top chess programs don't use a bitboard representation.

Really?
Rybka is a bitboard engine (at least according to the author) and it's currently pretty much undisputed that it's the strongest engine available.
Crafty is probably the top engine for which the source is available (hmm... maybe not these days, but it was when I was looking for a strong engine) - it's also bitboard.

Can you name a few strong non-bitboard engines? (Ideally with the source available).
I'd be very interested to see code.

Fruit and Sjeng don't use bitboards (at least the versions whose code was publicly available didn't: Fruit used 16x16 and Sjeng 12x12). Neither does Diep (he made his move generator public some time ago, and I've talked to the author), and neither did Rebel (this last one is a little old). I don't have hard proof, but I think Fritz, Junior and Shredder don't use them either.

It is possible that now that 64-bit processors are becoming the norm, more and more chess programs will jump into the bitboard bandwagon, but one can write a very strong program using other representations. Bitboards are *not* the key to a strong chess program. Good algorithms, a good evaluation function, good testing procedures and absence of bugs are the key.

[Edited by - alvaro on April 29, 2007 12:02:39 AM]

Bitboards are not inherently faster than other well optimized methods. Especialy not on the x86 line of CPU's (no fast Log2, BSF and BSR instructions are not fast)

Things like move generation and attack and pin detection are trivialy very efficient with bitboards, but other things that engines need are not automatically efficient at all such as actualy evaluating a board position.

Quote:Original post by AfroFire
Timkin? What do you mean a larger hyper word?

I simply meant a manually defined data type that is comprised of 2 or more primitive word types concatenated to form a longer word; and for which the basic bitwise operations are overloaded so that the longer word can be used in the same way you would use a primitive word.

Timkin

Bitboards are used for performance reasons, precisely because processors natively support the right number of bits.
It probably doesn't make sense if you have to have another structure to make it work.

Quote:Original post by alun
Bitboards are used for performance reasons, precisely because processors natively support the right number of bits.
It probably doesn't make sense if you have to have another structure to make it work.

Certainly performance would not be as optimal. However, since overloaded operators for hyper-words are typically implemented in terms of native operations, the decline in performance is small (and can be measured by the number of primitive operations required to implement a hyper-word operation). From my experience it's a lot less of a performance drop than using non-bit representations for large state spaces. The worst case scenario is typically bit-shifting, where you need to preserve information that flows out of one word and into the next.

Anyway, I'm certainly not stating that this is the way that the OP should go. I merely indicated that one shouldn't let perceived hardware limitations (in this case native word length) dictate software solutions.

Quote:Original post by alvaro
I should mention that a lot of the top chess programs don't use a bitboard representation. The algorithms you use are way more important than the board representation. If you don't want to loop through a lot of empty squares trying to find your pieces when you are generating moves, keep a list of pieces.

Most state-of-the-art chess AI now uses bitboards, and if they don't, they should ;) It's simply more efficient. Harder to read and debug? Yes... but a much more efficient use of pipelining/caching/registers. Just a more efficient use of computer architecture overall. Several years ago they weren't as widely used, but that is largely untrue today with 64 bit machines.

Quote:Original post by alvaro
The algorithms you use are way more important than the board representation.

I disagree - I think they are both vitally important. If I'm using an array[][] and I have to do a multiply + add to access any position and I'm doing lots of for loops with conditional branches, I'm going to get much less done than someone else using a bitboard who can execute multiple queries simultaneously thanks to pipelining.

Quote:Original post by alvaro
If you don't want to loop through a lot of empty squares trying to find your pieces when you are generating moves, keep a list of pieces.

Bitboards are used precisely because there is no looping to find where pieces are, where collisions are, etc. They are highly optimized for generating moves, far more efficient than the offset method.

Here are some interesting papers by Bob Hyatt (Crafty)
http://www.cis.uab.edu/hyatt/boardrep.html
http://www.cis.uab.edu/hyatt/pubs.html

The articles were written a few years ago before 64 bit machines were widely available, so the preference for bitboards has increased even more since then.

As for the Op post... I don't know. A simple array will probably do the job. Bitboards are so convenient for 'regular' chess because a 64-bit unsigned integer perfectly accommodates an 8x8 chessboard. If you are doing 22x22 or something odd like that, it's probably more work than its worth to use a more complex bitboard setup (unless this is a very hardcore project). It's complex enough for an 8x8 chessboard...

EDIT: Also, Sjeng does use bitboards... as of 5 years ago. I also would not be surprised if REBEL doesn't use them since it stopped being developed in 2004.

[Edited by - kosmon_x on April 30, 2007 6:23:00 PM]