Author: Sune Fischer
Date: 11:02:31 01/26/02
Go up one level in this thread
On January 26, 2002 at 13:46:26, Russell Reagan wrote:
>I'm using 0x88 board representation in my program, and I thought it would be
>quicker to keep an array of white pieces and an array of black pieces for doing
>things like move generation. That way to generate legal moves for white, I would
>just have to loop through the white piece array (16 iterations max) instead of
>the entire board (64 iterations).
>
>The problem I've run into is updating the piece arrays. For example, if I have
>an array of pieces:
>
>int white_pieces[16] = {E1, D1, A1, H1, C1, F1, B1, G1,A2, B2, C2, D2, E2, F2,
>G2, H2};
>
>for the starting position. When white makes it's first move, how do I update
>this array? The only way I can see is to do a search through this array for the
>piece that was moved, and change it's square, and then if you're searching
>through this array every make move and unmake move, you're pretty much killing
>any gain in speed you got from reducing the 64 iterations to 16 iterations in
>generating the legal moves.
I keep info about the piece arrays in my board structure.
At my board I have a color and an index, the index is for the piece arrays.
In the piece array I have information about the type of piece and where it is on
the board.
It is double book keeping, but then I need no checks.
I also move around with the pieces in the piece array when one is captured, that
way I don't need to search 1-16 but only 1 to "number of pieces".
And I don't have to check for nullpieces (that would mean a bug, so I only do
that in debug mode).
When I did the last thing my movegen doubled its speed, avoid stupid check as
much as you can, better to design the structures so it can be avoided.
>One alternative that I thought of was to do something like the following:
>
>int white_king_square = E1;
>int white_queen_squares[9] = {D1,-1,-1,-1,-1,-1,-1,-1,-1};
>int white_rook_squares[10] = {A1,H1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
>etc...
I have:
struct BOARD{
char color[64];
char index[64];
...
};
struct ARMY{
char type[17];
char square[17];
...
};
>and keep track of each individual kind of piece in it's own array, reducing the
>amount of search required to change an index in the piece array, and possibly
>allowing for other little tricks in other areas of the program, such as if you
>wanted to find out if there were any pinned pieces statically, you could use the
>sliding piece arrays (queen, rook, bishop) to do that more efficiently, as well
>as detect attacks more quickly.
>
>The other idea I had was to keep a max and min value for the pieces on one side.
>For example, in the starting position, min would be A1 and max would be H2, so
>you would search from min to max and cut out 75% of the search for pieces in
>move generation. This would be better than searching the entire board, but not
>as quick as searching only the squares with pieces of the color you're looking
>for.
>
>If anyone has any comments or advise as to how I should implement the piece
>arrays to speed up looping through the board I would appreciate it.
>
>Thanks,
>Russell
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.