A performance comparison of two board representations

[Fguy64]

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.

[bob]

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

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]
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.

[Fguy64]

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

Code: Select all

for&#40; r2 = r1-1; r2<8 0; r2++ ) &#123;
	if&#40; posn&#91;r2&#93;&#91;c1&#93; > 0 ) break;
	if&#40; addMove&#40;ply, gs, r1, c1, r2, c1, 0&#41; ) break;	// addMove returns true for a capture.
&#125;

int[64], src given.

Code: Select all

r = src/8; c = src%8;
while&#40; ++r < 8 ) &#123;
	dest = 8*r + c;
	if&#40; posn&#91;dest&#93; > 0 ) break;
	if&#40; addMove&#40;ply, gs, src, dest, 0&#41; ) break;
&#125;

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.

[abulmo]

int[64], src given.

Code: Select all

r = src/8; c = src%8;
while&#40; ++r < 8 ) &#123;
	dest = 8*r + c;
	if&#40; posn&#91;dest&#93; > 0 ) break;
	if&#40; addMove&#40;ply, gs, src, dest, 0&#41; ) break;
&#125;

There is no need to decompose & recompose a coordinate. You can merely write :

Code: Select all

const int UP = 8; 
for &#40;dest = src + UP; dest <= 64; dest += UP&#41; &#123;
	if&#40; posn&#91;dest&#93; > 0 ) break;
	if&#40; addMove&#40;ply, gs, src, dest, 0&#41; ) break;
&#125;

Using a constant like UP makes clear the way you want to go through the chessboard.

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 &#40;dest = src + UP; posn&#91;dest&#93; <= 0; dest += UP&#41; &#123;
	if&#40; addMove&#40;ply, gs, src, dest, 0&#41; ) break;
&#125;

[Fguy64]

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?

[MattieShoes]

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.

[Fguy64]

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.

[rreagan]

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.

Fruit uses a 16x16 board. A 12x16 board is probably better. You can use a 12x15 board too.

See http://chessprogramming.wikispaces.com/15%2A12+Board

[rreagan]

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?

With a 12x16 board like this:

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

You just scan until you hit something that is not an empty square. Let's say you are generating captures. You scan in one direction until you find a square that is not empty. If the contents of that square contains an enemy piece, you generate a capture move. Otherwise the contents of the non-empty square is either a friendly piece, or you ran off the board, so you stop scanning.

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)
}

Read Christophe Theron's post. He explains it well: http://www.stmintz.com/ccc/index.php?id=114377

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

[hgm]

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.

Code: Select all

#define WHITE 32
#define BLACK 64
if(board[toSquare] & myColor) continue;

So there is no extra overhead at all in testing if you are off board.