Symmetric move generation using bitboards

[Lasse Hansen]

It is well known that bsf (bitscan forward) and bsr (bitscan reverse) dont behave
symmetrical for white/black move generation using bitboards.

This can be circumvented by the following:

Code: Select all

const int MirrorTable[2][64] = {
	{
		 0, 1, 2, 3, 4, 5, 6, 7,
		 8, 9,10,11,12,13,14,15,
		16,17,18,19,20,21,22,23,
		24,25,26,27,28,29,30,31,
		32,33,34,35,36,37,38,39,
		40,41,42,43,44,45,46,47,
		48,49,50,51,52,53,54,55,
		56,57,58,59,60,61,62,63,
	},{
		56,57,58,59,60,61,62,63,
		48,49,50,51,52,53,54,55,
		40,41,42,43,44,45,46,47,
		32,33,34,35,36,37,38,39,
		24,25,26,27,28,29,30,31,
		16,17,18,19,20,21,22,23,
		 8, 9,10,11,12,13,14,15,
		 0, 1, 2, 3, 4, 5, 6, 7,
	}
};

inline int FirstOneSym(int wtm, U64 A)
{
	int sqr[2];
	sqr[0] = FirstOne(A);
	sqr[1] = FirstOne(bswap(A));
	return MirrorTable[wtm][sqr[wtm]];
}
inline int LastOneSym(int wtm, U64 A)
{
	int sqr[2];
	sqr[0] = LastOne(A);
	sqr[1] = LastOne(bswap(A));
	return MirrorTable[wtm][sqr[wtm]];
}

One nice side effect is that the usual:

Code: Select all

fr = tr->wtm ? LastOne(Pcs) : FirstOne(Pcs);
to = tr->wtm ? FirstOne(Atk) : LastOne(Atk);

can be replaced with

Code: Select all

fr = LastOneSym(tr->wtm,Pcs);
to = FirstOneSym(tr->wtm,Atk);

which drops the condition.

My own tests show that this is slightly slower than the old code.

Regards, Lasse

[Rein Halbersma]

It is well known that bsf (bitscan forward) and bsr (bitscan reverse) dont behave
symmetrical for white/black move generation using bitboards.

What do you mean? Gcc intrinsics __builtin_ctz and __builtin_clz are symmetric.

[SMIRF]

To create a quite color independent set of chess routines you have to achieve an identical behavior for color-swapped positions. If routines would have different time consumptions e.g. when detecting check threats or performing moves or removes, symmetry will be broken. Thus when calculating something for the active player, there a view must be provided not being distinguishable from those having everything swapped: north/south, black/white and side-to-move.

Moreover this has to be true also for any used zobrist key while caching is used.

[Lasse Hansen]

I didnt mean the functions themselves, but the move generation for black/white side when one want to generate moves farthest away first.

In my movgen I take the piece closest to 'own' side and moves it as close as possible to the opponent side with:

Code: Select all

fr = tr->wtm ? LastOne(Pcs) : FirstOne(Pcs);
to = tr->wtm ? FirstOne(Atk) : LastOne(Atk);

For starting position this then gives:
Black first knight move is Ng8-f6
White first knight move is Nb1-c3
which is not symmetrical.

The new functions get this behavior symmetrical.
(assuming square mapping is A1, B1,. or H8, G8,... etc)

Regards, Lasse

[Gerd Isenberg]

It is well known that bsf (bitscan forward) and bsr (bitscan reverse) dont behave
symmetrical for white/black move generation using bitboards.

What do you mean? Gcc intrinsics __builtin_ctz and __builtin_clz are symmetric.

Lasse means:
Scanning White in a1..h1, a2 h2,,,..h8 order
Scanning Black in a8..h8, a7 h7,,,..h1 order

[Gerd Isenberg]

Nice. My proposal takes one extra register and xor inside the serialization bsf loop body. flipVertical = bswap.

[Rein Halbersma]

It is well known that bsf (bitscan forward) and bsr (bitscan reverse) dont behave
symmetrical for white/black move generation using bitboards.

What do you mean? Gcc intrinsics __builtin_ctz and __builtin_clz are symmetric.

Lasse means:
Scanning White in a1..h1, a2 h2,,,..h8 order
Scanning Black in a8..h8, a7 h7,,,..h1 order

ah my bad! I forgot that the inital position is not symmetric (I'm a draughts programmer, there everything is symmetric)

[wgarvin]

Is the table lookup really necessary? Can't you just xor it with 56 or something along those lines?

Edit: Gerd beat me to it. I should have read the replies first!

Edit: if you want to stick with the table, try it with a "const unsigned char" array instead of "const int" (so table uses up fewer lines of L1 cache).