A performance comparison of two board representations

[MattieShoes]

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.

I've done that too, though I think I used lower order bits. Do you do some sort of conversion for hash then?

[hgm]

I am not sure what you are asking. Conversion of what, and for which purpose?

[bob]

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.

First, you need to dump the asm to see what is happening. In general, this is what you start out with:

int a[100][50];

x = a[j];

This is what the compiler produces:

int a[5000];

x = a[i * 50 + j]

So the conversion from 2d to 1d _must_ be done somewhere since there is no such animal in the real computer world, as far as memory addressing is concerned. You can do it yourself, or let the compiler do it. But you can do it faster, because when you generate moves for a slider, incrementing by a single constant (to take you down a diagonal) is faster than sticking in the multiply to converd a 2d reference to 1d.

[bob]

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?

That's why I had suggested you think about alternatives. You can try the classic 10x10 board to give you two border squares so that when a knight jumps off the edge, it will land on a square with a sentinel that says "not legal". Or you can use the 0x88 approach. If you haven't seen that, I can explain.

[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?

That's why I had suggested you think about alternatives. You can try the classic 10x10 board to give you two border squares so that when a knight jumps off the edge, it will land on a square with a sentinel that says "not legal". Or you can use the 0x88 approach. If you haven't seen that, I can explain.

Thanks, I'll probably try one of those options, hopefully in the not too distant future. there seems to be a fair bit of documentation on this stuff, and I'll report back if I have a problem. Thanks also to Matt, Russell, and HG for the helpful examples.

In the meantime, I tried a little experiment, using the int[64] array.

For the pieces that moved in a line I set up two static arrays, row[256][] & diag[256][], where each row represented movement in a particular direction, as follows...

Code: Select all

for&#40; int sq=0; sq<64; sq++ ) &#123;

	r1 = sq/8; c1 = sq%8; count = 0;	// movement along file towards 1st rank.
	for&#40; r2=r1+1; r2<8; r2++ ) temp&#91;count++&#93; = 8*r2 + c1;
	row&#91;4*sq+0&#93; = Arrays.copyOf&#40;temp,count&#41;;
		
	.
	.
	.
		
	r1 = sq/8; c1 = sq%8; count = 0;	// movement along top left to botton right diagonal
	r2 = r1; c2 = c1;
	while&#40; (++r2<8&#41; && (++c2<8&#41; ) temp&#91;count++&#93; = 8*r2 + c2;
	diag&#91;4*sq+0&#93; = Arrays.copyOf&#40;temp,count&#41;;
	.
	.
	.
&#125;

which meant that in moveGen I could replace all my code blocks, e.g. replace ...

Code: Select all

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

with

Code: Select all

for( int dst : Data.diag[4*src] ) {
	if( posn[dst] > 0 ) break;
	if( addMove(ply, gs, src, dst, 0) ) break;
}

I would have thought this would be a significant improvement, because in effect I was doing a good bunch of the necessary calculation during program initialization. But again early indications showed no real improvment, which was a bit of a surprise.