Author: Dan Homan
Date: 06:19:04 02/11/00
Go up one level in this thread
On February 10, 2000 at 17:34:52, Tom Kerrigan wrote:
>There seems to be a huge pro-bitboard movement underway... But for those of us
>not jumping on the bandwagon, I have some thoughts.
>
>Let's say you have an array to represent the board:
>int board[64];
>
>If you make white pieces positive (i.e., pawn = 1, knight = 2) and black pieces
>negative, you can use the following macros:
>
>#define COLOR(x) (x < 0)
>#define TYPE(x) (x < 0 ? -x: x)
>
>I don't like the TYPE macro because it has a branch. So let's say you set bit #4
>if the piece is black. Then you can use these macros:
>
>#define COLOR(x) (x >> 3)
>#define TYPE(x) (x & 7)
>
>This seems pretty good, but I still have a minor complaint: a pawn = 1, so all
>the arrays that are indexed by piece type have to have an unused element at the
>beginning.
>
>You can set the pawn = 0, but then the empty square value has to be non-zero. On
>some proessors, this increases the time it takes to see if a square is empty.
>
>If you're using the 0x88 trick, you get two boards to play with, so the color of
>the piece on square x can be board[x] and the piece type can be board[x+8]. I
>think this is a pretty good solution, but it involves some extra memory
>accesses, not only when you're examining the board, but also when you're moving
>pieces around.
>
>If you have a piece struct, your board can be pointers to the structs:
>piece_struct *board[64];
>
>Then the color of the piece on square x is board[x]->color and the piece type is
>board[x]->type. I think this solution is pretty cool, but it involves some extra
>memory accesses. Plus, every time you want to check the piece type of square x,
>you have to make sure that board[x] isn't NULL. That's not cool.
I do essentially this in EXchess. I tried both of the above methods, and using
a struct seems to be faster (by a few percent). I use
struct square {
char type; // type of piece (0 - 6)
char side; // side which owns square (1 = white)
}
struct position {
square sq[64]; // array of board squares
....
}
I use char's for "type" and "side" rather than shorts (which I could union
together to an "int") because I do a memory position copy rather than
an "undo-move".
I also have piece lists in my position structure. Piece lists, of course,
are a great help in both move generation and evaluation - making quite
a nice speed-up, despite the larger memory copy which is necessary (for me)
on each move.
It just recently occurred to me that anything I am doing with piece lists
I can do with bitboards but faster and more efficiently. I am beginning
to wonder if there is any reason not to have bitboards (even if one doesn't
want to use them fully - ie rotated bitboard move generation).
- Dan
>
>So... each method has its minor advantages and disadvantages. I can't really
>decide which I like more. What do other programmers do? Is there some really
>elegant solution that I'm missing? I hope so. :)
>
>-Tom
This page took 0 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.