Symmetric move generation using bitboards

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
Lasse Hansen
Posts: 27
Joined: Wed May 28, 2008 11:07 am
Location: Porsgrunn, Norway

Symmetric move generation using bitboards

Post by Lasse Hansen » Sat Dec 20, 2014 8:20 am

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
Posts: 685
Joined: Tue May 22, 2007 9:13 am

Re: Symmetric move generation using bitboards

Post by Rein Halbersma » Sat Dec 20, 2014 9:45 am

Lasse Hansen wrote: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.

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: Symmetric move generation using bitboards

Post by SMIRF » Sat Dec 20, 2014 9:55 am

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.

User avatar
Lasse Hansen
Posts: 27
Joined: Wed May 28, 2008 11:07 am
Location: Porsgrunn, Norway

Re: Symmetric move generation using bitboards

Post by Lasse Hansen » Sat Dec 20, 2014 10:05 am

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
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Symmetric move generation using bitboards

Post by Gerd Isenberg » Sat Dec 20, 2014 10:09 am

Rein Halbersma wrote:
Lasse Hansen wrote: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
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Symmetric move generation using bitboards

Post by Gerd Isenberg » Sat Dec 20, 2014 10:10 am

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

Rein Halbersma
Posts: 685
Joined: Tue May 22, 2007 9:13 am

Re: Symmetric move generation using bitboards

Post by Rein Halbersma » Sat Dec 20, 2014 9:16 pm

Gerd Isenberg wrote:
Rein Halbersma wrote:
Lasse Hansen wrote: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
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Symmetric move generation using bitboards

Post by wgarvin » Sun Dec 21, 2014 1:37 am

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

Post Reply