Author: Robert Hyatt
Date: 14:50:54 02/10/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: TYPE doesn't have to be a branch. On the athlon, and all intel processors with the P6 core the "CMOV" instruction will do this. You put x in one reg, -x in another reg, then cmov the right one to the target reg with no branch penalty at all. Doesn't work on K6 nor on older pentiums, even with mmx stuff. > >#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. > >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 There are pros and cons for all implementations. The pros for bitmaps don't become apparent until they are run on a 'native' architecture (64 bit machines). When all is said and done, it is likely that both approaches are going to end up pretty much equal, except for the 'data width' problem. IE an 0x88 program moves squares around a lot, and since the contents is < 255, 7/8ths of the data movement is wasted on a 64 bit machine. On a bitmap approach, the entire 64 bits means something, although it has a lot of zeros which could also be considered 'wasted' in a sense. But it sure is convenient to access all pawns with 1 64 bit value, as memory references become very rare in the pawn structure analysis. The big down-side is that you have to commit a _lot_ of time to get familiar with the 'bitmap approach' to things. That doesn't happen quickly or easily. from experience... but it does happen... also from experience.
This page took 0.01 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.