Pradu wrote:Tord Romstad wrote:This is a moot point, I think. Having a single line with
- Code: Select all
if(!move_is_legal(board, move)) continue;
at the beginning of the move loop in the search function doesn't really make the code any harder to read and maintain.'
Well I don't have something like this in the move loop, my alpha beta looks something like
int ab(board b, move m, int depth, int a, int b, ....)
So at the beginning of the function you make a test if the move is legal or not which kind of looks ackward.
But you don't have to do it at the beginning of your function, it seems cleaner (and faster) to do it before ab() is called. Somewhere in your program, you must have some loop or function which picks a move from a move list, extracts a move from a pair of bitboards, or something similar. Just modify this function to do legality checking before it returns a move to search, and you are done.
Also there is some difficulty in figuring out whether you are in stalemate or mate because you have to keep a counter of the number of illegal moves.
This is true, but counting the number of legal moves is useful in any case, because it is nice to have for splitting and reduction decisions.
My point was that bitboard and mailbox representations excel at different operations, and that it is probably a good idea to structure the low-level parts of the program in ways that exploit the advantages of the chosen representation. Bitboards are generally fast for computing more complicated information (like finding all pinned pieces at once, generating a legal move list, or finding all the squares a given piece attacks), but tend to be rather slow for more simple, atomic tasks (like testing whether a single piece is pinned, testing whether a single move is legal, or testing whether a given piece attacks a given square). With a mailbox representation, it is precisely the opposite.
Nothing preventing you from combining both approaches
. Bitboards are usually accompanied by some sort of array boards so using bitboards is clearly superior because you have the same abilities you had to array boards with the additional capabilities of bitboards.
It is not that clear, and it depends to a big extent on the program. Combining mailbox and bitboards is very expensive. The board data structure becomes bigger and more complicated, which makes copying boards at splitpoints and doing/undoing moves much slower. Bitboard are also somewhat less efficient with board arrays bigger than 64 entries, because you will either have to expand the size of various mask arrays, or do some extra arithmetics or an additional table lookup in order to convert square indices down to the 0-63 range.
In some programs, using both bitboards and a mailbox board might be worth the price, but in mine it is not. Pure mailbox and pure bitboard is faster than any hybrid solution, for the old Glaurung as well as the new.
Bitboards without arrayboards will be slow, and I suspect any that pure bitboard programs are not-optimal and will have some difficult code to read.
Not necessarily - look at the fabulous OliThink 5 alpha, for instance. Blazingly fast, and one of the most elegant and readable chess programs ever written. It's a pity Oliver never finished it. Does anyone know what he's doing now?
An example of this would be figuring out what kind of piece was captured from a move. With pure bitboards you have to do some &ing to figure out which bitboard the piece was taken from. With array boards one can use to-square's data from the array.
Intuitively this seems plausible, but when I experimented with this recently it seemed that using a board[] array hardly helped at all (the speedup with the array was about 3%), and I removed it in order to make things simpler.
I think some kind of light-weight piece list data structure would give a bigger boost to performance than a board[] array. Bitscanning is one of the most frequent and expensive operations in a bitboard program, and piece lists would help to reduce its usage.
Tord
