OK I am playing with a comparison of the following two board structures, and corresponding moveGen. I know my choices are probably kind of primitive, but this is the best I can come up with for now. Also, my program is written in Sun java
1. int[64]
- a linear transformations to row and column co-ordinates are done in order to make moveGen more intuitive. ( for me )
2. int[8][8]
- no linear transformation is needed. this reduces the amount of calculations needs to determine possibleMoves
In both cases, the actual values in the position array cells are the material values also( +ve white, -ve black), so these values do double duty. So to calculate the material balance I just sum the positional array.
Anyways, my tests have not been exhaustive, but the initial indication is that there is extra overhead associated with indexing a two dimensional array as opposed to indexing a one dimensional array, and this extra overhead nullifies the advantage of fewer calculations in moveGen.
Does this sound like a reasonable conclusion? Thanks.
A performance comparison of two board representations
Moderators: hgm, Rebel, chrisw
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: A performance comparison of two board representations
What computer do you know of that has memory organized as a matrix? +you+ might not need to do the linear transformation, but the compiler has to produce instructions that do so. This can be done pretty efficiently, but will consume an extra register if you want to go the route [board + eax + 8 * ebx]Fguy64 wrote:OK I am playing with a comparison of the following two board structures, and corresponding moveGen. I know my choices are probably kind of primitive, but this is the best I can come up with for now. Also, my program is written in Sun java
1. int[64]
- a linear transformations to row and column co-ordinates are done in order to make moveGen more intuitive. ( for me )
2. int[8][8]
- no linear transformation is needed. this reduces the amount of calculations needs to determine possibleMoves
where eax has the file, and ebx has the rank.
There are better representations, however, as you are currently left with some ugly conditionals to keep pieces from jumping off one side of the board and onto the other side, thanks to the edges.
In both cases, the actual values in the position array cells are the material values also( +ve white, -ve black), so these values do double duty. So to calculate the material balance I just sum the positional array.
Anyways, my tests have not been exhaustive, but the initial indication is that there is extra overhead associated with indexing a two dimensional array as opposed to indexing a one dimensional array, and this extra overhead nullifies the advantage of fewer calculations in moveGen.
Does this sound like a reasonable conclusion? Thanks.
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: A performance comparison of two board representations
Thanks Bob. I'm not trying to make a choice between board designs, as much as I am just trying to explain the results I'm getting, altough I am interested in any strategy that would improve performance for the two board structures I have on my plate. I know I have a lot of learning to do to deal properly with the issues you describe.
As an example, this is the sort of thing I am talking about. Here are the two methods for a white rook moving forward along a file...
int[8][8], r1 & c1 given
int[64], src given.
So the question still remains. It looks like in the first case there is much less calculating, yet it is not faster. Your remark "what computer do you know of that organizes memory in a matrix" leads me to believe that in fact the overhead associated with the 2D indexing of the first case is enough to counteract the benefit of fewer calulations of the moveGen routine.
As an example, this is the sort of thing I am talking about. Here are the two methods for a white rook moving forward along a file...
int[8][8], r1 & c1 given
Code: Select all
for( r2 = r1-1; r2<8 0; r2++ ) {
if( posn[r2][c1] > 0 ) break;
if( addMove(ply, gs, r1, c1, r2, c1, 0) ) break; // addMove returns true for a capture.
}
Code: Select all
r = src/8; c = src%8;
while( ++r < 8 ) {
dest = 8*r + c;
if( posn[dest] > 0 ) break;
if( addMove(ply, gs, src, dest, 0) ) break;
}
-
- Posts: 151
- Joined: Thu Nov 12, 2009 6:31 pm
Re: A performance comparison of two board representations
There is no need to decompose & recompose a coordinate. You can merely write :Fguy64 wrote:
int[64], src given.Code: Select all
r = src/8; c = src%8; while( ++r < 8 ) { dest = 8*r + c; if( posn[dest] > 0 ) break; if( addMove(ply, gs, src, dest, 0) ) break; }
Code: Select all
const int UP = 8;
for (dest = src + UP; dest <= 64; dest += UP) {
if( posn[dest] > 0 ) break;
if( addMove(ply, gs, src, dest, 0) ) break;
}
You can fasten this code even more by using sentinel values surrounding the board to get a code similar to:
Code: Select all
const int UP = 8;
for (dest = src + UP; posn[dest] <= 0; dest += UP) {
if( addMove(ply, gs, src, dest, 0) ) break;
}
Richard
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: A performance comparison of two board representations
OK Richard I see what you mean. It seems to work very nicely for rook movements along a file, as a matter of fact since my last post I had already done what you suggest, But things aren't so cut and dry for movement along a rank, or for diagonal movements, as there does not seem to be a nice neat little stop condition on the loop that works for all cases. At least not with my simplistic board representation. Agreed?
-
- Posts: 718
- Joined: Fri Mar 20, 2009 8:59 pm
Re: A performance comparison of two board representations
You could use a 10x8 or 10x10 or 12x10 or 12x12 or 8x16 board. The last one is known as "0x88" and the fake squares make for some nice binary math tricks...
In binary, it looks like xRRRxFFF, and all squares relatively near to the board will have one of those x'es flipped. 10001000 is 0x88 in hex, hence the name.
if(index & 0x88) //square is illegal
index>>4 //rank
index&7 //file
There's some trick for finding out square color too, but I'm too sleepy to think about it.
Anyway, it detects leaving the board in any direction. It also allows for a compact attack vector -- can a piece on square X attack square Y? With an 64 element board, you have to use vector[X][Y], 4096 elements long. With 0x88, you can construct one that's something like vector[Y-X] so the array size is something like 240 elements.
If you're examining array based systems, 16x8 (0x88) is probably the one to use. Fruit used 12x12 quite successfully too if I remember right.
In binary, it looks like xRRRxFFF, and all squares relatively near to the board will have one of those x'es flipped. 10001000 is 0x88 in hex, hence the name.
if(index & 0x88) //square is illegal
index>>4 //rank
index&7 //file
There's some trick for finding out square color too, but I'm too sleepy to think about it.
Anyway, it detects leaving the board in any direction. It also allows for a compact attack vector -- can a piece on square X attack square Y? With an 64 element board, you have to use vector[X][Y], 4096 elements long. With 0x88, you can construct one that's something like vector[Y-X] so the array size is something like 240 elements.
If you're examining array based systems, 16x8 (0x88) is probably the one to use. Fruit used 12x12 quite successfully too if I remember right.
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: A performance comparison of two board representations
duly noted Matt. I'm aware that there are array representations that deal with the issues I've raised. It's on my todo list, When I do my next re-write I'll be looking at some of this stuff.
-
- Posts: 102
- Joined: Sun Sep 09, 2007 6:32 am
Re: A performance comparison of two board representations
Fruit uses a 16x16 board. A 12x16 board is probably better. You can use a 12x15 board too.MattieShoes wrote:You could use a 10x8 or 10x10 or 12x10 or 12x12 or 8x16 board. The last one is known as "0x88" and the fake squares make for some nice binary math tricks...
In binary, it looks like xRRRxFFF, and all squares relatively near to the board will have one of those x'es flipped. 10001000 is 0x88 in hex, hence the name.
if(index & 0x88) //square is illegal
index>>4 //rank
index&7 //file
There's some trick for finding out square color too, but I'm too sleepy to think about it.
Anyway, it detects leaving the board in any direction. It also allows for a compact attack vector -- can a piece on square X attack square Y? With an 64 element board, you have to use vector[X][Y], 4096 elements long. With 0x88, you can construct one that's something like vector[Y-X] so the array size is something like 240 elements.
If you're examining array based systems, 16x8 (0x88) is probably the one to use. Fruit used 12x12 quite successfully too if I remember right.
See http://chessprogramming.wikispaces.com/15%2A12+Board
-
- Posts: 102
- Joined: Sun Sep 09, 2007 6:32 am
Re: A performance comparison of two board representations
With a 12x16 board like this:Fguy64 wrote:But things aren't so cut and dry for movement along a rank, or for diagonal movements, as there does not seem to be a nice neat little stop condition on the loop that works for all cases. At least not with my simplistic board representation. Agreed?
Code: Select all
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
Code: Select all
to = from + direction;
while (board[to] == empty) {
generate_non_capture(from,to);
to += direction;
}
if (board[to] == enemy_piece) {
generate_capture(from,to)
}
You can do this kind of board scanning with lots of different board sizes (10x10, 12x12, 12x15, 12x16, 16x16, etc). There are other advantages to using the larger board sizes such as 12x15 or 12x16. Primarily the unique square relationships, but that's not what you were asking about
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: A performance comparison of two board representations
In Joker I use separate bits in the piece encoding to indicate if a piece is white or black. So I can make 'pieces' that hve both bits set, and that would pass the test for either color. Those I use as 'border guards' around the board. So that the test that weeds out captures of own pieces in the move generator also automatically weeds out off-board moves.
So there is no extra overhead at all in testing if you are off board.
Code: Select all
#define WHITE 32
#define BLACK 64
if(board[toSquare] & myColor) continue;