On bitboard legal move generation

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

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

On bitboard legal move generation

Post by Lasse Hansen » Mon Feb 09, 2015 2:11 pm

While trying to get my move generators symmetrical I also looked a bit deeper.
(Yes, CPW and Gerd's method of bit removal is much faster than my crap,
I did'nt even see that ^56 removes the lookup table, DOOH!!)
I only generate legal moves now, and I found some ways to improve the speed.
(I have searched CPW and TalkChess, but could not find anything about the stuff I do here)

I included the results for my staged move generators as well, since this counts in Sillycon (my engine).

These results are from my i7 2600K @ 3.4GHz (no turbo boost, no hashing, single core)

Popcounting at leaf nodes.

Code: Select all

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w QKqk - -

Perft  1=48 t=0.00s 0.00MN/s
Perft  2=2039 t=0.00s 0.00MN/s
Perft  3=97862 t=0.00s 97.86MN/s
Perft  4=4085603 t=0.02s 226.98MN/s
Perft  5=193690690 t=0.50s 389.72MN/s
Perft  6=8031647685 t=24.72s 324.93MN/s
Perft  7=374190009323 t=985.89s 379.54MN/s

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w QKqk - -

Perft  1=20 t=0.00s 0.00MN/s
Perft  2=400 t=0.00s 0.00MN/s
Perft  3=8902 t=0.00s 0.00MN/s
Perft  4=197281 t=0.00s 65.76MN/s
Perft  5=4865609 t=0.03s 152.05MN/s
Perft  6=119060324 t=0.60s 199.77MN/s
Perft  7=3195901860 t=14.90s 214.45MN/s
Perft  8=84998978956 t=395.18s 215.09MN/s
Symmetrical, staged move generation as in my engine. (Captures + queen
promotions, noncaptures separately)

Code: Select all

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w QKqk - -

Perft2  1=48 t=0.00s 0.00MN/s
Perft2  2=2039 t=0.00s 0.00MN/s
Perft2  3=97862 t=0.00s 48.93MN/s
Perft2  4=4085603 t=0.04s 116.73MN/s
Perft2  5=193690690 t=1.16s 166.97MN/s
Perft2  6=8031647685 t=53.45s 150.25MN/s

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w QKqk - -

Perft2  1=20 t=0.00s 0.00MN/s
Perft2  2=400 t=0.00s 0.00MN/s
Perft2  3=8902 t=0.00s 0.00MN/s
Perft2  4=197281 t=0.01s 39.46MN/s
Perft2  5=4865609 t=0.05s 99.30MN/s
Perft2  6=119060324 t=1.02s 116.50MN/s
Perft2  7=3195901860 t=27.55s 116.00MN/s
Downloaded executeable version of qperft for comparison

Code: Select all

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w QKqk - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft( 1)=           20 ( 0.000 sec)
perft( 2)=          400 ( 0.000 sec)
perft( 3)=         8902 ( 0.000 sec)
perft( 4)=       197281 ( 0.002 sec)
perft( 5)=      4865609 ( 0.038 sec)
perft( 6)=    119060324 ( 0.853 sec)
perft( 7)=   3195901860 (21.731 sec)

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w QKqk - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft( 1)=           48 ( 0.000 sec)
perft( 2)=         2039 ( 0.000 sec)
perft( 3)=        97862 ( 0.001 sec)
perft( 4)=      4085603 ( 0.029 sec)
perft( 5)=    193690690 ( 1.131 sec)
perft( 6)=   8031647685 (50.765 sec)
These functions are just simplifications to see if the king is attacked.
One might call it Very Lazy make/unmake functions.
One trick I used for IsQRBPMoveIllegal was to avoid using tr->Pieces[0..1][0]
for storing piece info, and by that, if the captured piece is empty (=zero), no disturbance.

Code: Select all

bool IsQRBPMoveIllegal(TTree *tr, int fr, int to, int ksqr)
// Assumes not in check. Detects if QRBP is pinned (not en-passant)
{
	int CaptPcs = tr->Board[to] & 7;
	tr->Pieces[!tr->wtm][CaptPcs] &= ClrBit(to);
	U64 mask = SetBit(fr) | SetBit(to);
	tr->Pieces[tr->wtm][ALL] ^= mask; 
	U64 Pinned = RookAttacks(ksqr,ALLPCS) & ALL_QR(!tr->wtm);
	Pinned |= BishopAttacks(ksqr,ALLPCS) & ALL_QB(!tr->wtm);
	tr->Pieces[tr->wtm][ALL] ^= mask;
	tr->Pieces[!tr->wtm][CaptPcs] |= SetBit(to);
	return Pinned > 0;
}

bool IsKnightMoveIllegal(TTree *tr, int fr, int ksqr)
// Assumes not in check. Determines if N is pinned
{
	tr->Pieces[tr->wtm][ALL] ^= SetBit(fr); 
	U64 Pinned = RookAttacks(ksqr,ALLPCS) & ALL_QR(!tr->wtm);
	Pinned |= BishopAttacks(ksqr,ALLPCS) & ALL_QB(!tr->wtm);
	tr->Pieces[tr->wtm][ALL] ^= SetBit(fr);
	return Pinned > 0;
}

bool IsKingMoveIllegal(TTree *tr, int fr, int to)
// Assumed not in check, no castling
{
	U64 mask = SetBit(fr) | SetBit(to);
	tr->Pieces[tr->wtm][ALL] ^= mask; // No need to remove captured piece
	bool Attacked = IsAttacked(tr,to,tr->wtm);
	tr->Pieces[tr->wtm][ALL] ^= mask;
	return Attacked;
}
The symmetrical move generation code for (noncapturing) pawns and king

Code: Select all

// All 1-step and 2-step pawn moves
Atk = &#40;tr->Pieces&#91;tr->wtm&#93;&#91;Pawn&#93;<<8&#41;>>&#40;tr->wtm<<4&#41;;
if &#40;Atk &= ~ALLPCS&#41; &#123;
	Atk = Atk ^ (&#40;Atk ^ bswap&#40;Atk&#41;) & m1&#41;;
	do &#123; 
		to = FirstOne&#40;Atk&#41; ^ o1;
		fr = to - 8 + &#40;tr->wtm<<4&#41;;
		if &#40;SetBit&#40;fr&#41; & KVA && IsQRBPMoveIllegal&#40;tr, fr, to, ksqr&#41;) continue;					
		if &#40;SetBit&#40;to&#41; & &#40;RANK_A8H8 | RANK_A1H1&#41;) &#123; // UnderPromotions
			*M=&#40;fr<<6&#41;+to+&#40;Pawn<<12&#41;+&#40;tr->wtm<<15&#41;+&#40;tr->wtm<<23&#41;; // Colour of prompiece added
			*&#40;M+1&#41; = *M | &#40;Bishop<<20&#41;; // Promote to RBN 
			*&#40;M+2&#41; = *M | &#40;Knight<<20&#41;;
			*M |= &#40;Rook<<20&#41;; M += 3;
			continue;
		&#125; 
		if &#40;SetBit&#40;fr&#41; & RANK_2&#40;tr->wtm&#41;) &#123; // Double pawn push
			int to2 = fr+16-32*tr->wtm;
			if &#40;tr->Board&#91;to2&#93;==Empty&#41; *M++=&#40;fr<<6&#41;+to2+&#40;Pawn<<12&#41;+&#40;tr->wtm<<15&#41;;
		&#125;
		*M++=&#40;fr<<6&#41;+to+&#40;Pawn<<12&#41;+&#40;tr->wtm<<15&#41;; // Normal pawn push
	&#125; while &#40;Atk &= Atk - 1ull&#41;;		
&#125;


// King
fr = ksqr;
if &#40;Atk = KingAttacks&#91;fr&#93; & ~ALLPCS&#41; &#123;
	Atk = Atk ^ (&#40;Atk ^ bswap&#40;Atk&#41;) & m1&#41;;
	fr = &#40;fr<<6&#41; + &#40;King<<12&#41; + &#40;tr->wtm<<15&#41;;
	do &#123;
		to = FirstOne&#40;Atk&#41; ^ o1;
		if &#40;IsKingMoveIllegal&#40;tr, ksqr, to&#41;) continue;
		*M++ = fr+to;
	&#125; while &#40;Atk &= Atk - 1ull&#41;;
&#125;

Some pawn moves at leaves &#40;PopCount version&#41;

// En-passant
TMove Mtemp&#91;2&#93;; // Also used for MovgenCastling&#40;)
int EpSqr = tr->Game_EpSqr&#91;tr->Game_Ply+ply&#93;;
if &#40;EpSqr&#41; &#123;
	U64 Atk = KingAttacks&#91;EpSqr&#93; & RANK_5&#40;tr->wtm&#41;;
	if &#40;Atk & KVA&#41; nSafeMoves += MovgenEnPassant&#40;tr, ply, Mtemp&#41; - Mtemp;
	else nSafeMoves += PopCount&#40;Atk & tr->Pieces&#91;tr->wtm&#93;&#91;Pawn&#93;);
&#125;
// All 1-step and 2-step moves
Pcs = tr->Pieces&#91;tr->wtm&#93;&#91;Pawn&#93; & ~KVA;  // Pawns outside pin range
Atk = ~ALLPCS & (&#40;Pcs<<8&#41;>>&#40;tr->wtm<<4&#41;);
nSafeMoves += PopCount&#40;Atk&#41;;			// Safe 1-step moves
nSafeMoves += 3*PopCount&#40;Atk & &#40;RANK_A8H8 | RANK_A1H1&#41;); // Promotions
Atk &= RANK_3&#40;tr->wtm&#41;;
Atk = ~ALLPCS & (&#40;Atk<<8&#41;>>&#40;tr->wtm<<4&#41;);
nSafeMoves += PopCount&#40;Atk&#41;;			// Safe 2-step moves
Pcs = tr->Pieces&#91;tr->wtm&#93;&#91;Pawn&#93; & KVA;  // Pawns inside pin range
Atk = ~ALLPCS & (&#40;Pcs<<8&#41;>>&#40;tr->wtm<<4&#41;);
if &#40;Atk&#41; &#123;
	do &#123; 
		to = FirstOne&#40;Atk&#41;;
		fr = to - 8 + &#40;tr->wtm<<4&#41;;
		if &#40;SetBit&#40;fr&#41; & KVA && IsQRBPMoveIllegal&#40;tr, fr, to, ksqr&#41;) continue;					
		if &#40;SetBit&#40;to&#41; & &#40;RANK_A8H8 | RANK_A1H1&#41;) &#123; // Promotions
			nSafeMoves += 4;
			continue;
		&#125;
		nSafeMoves += 1;					// Single pawn push
		if &#40;SetBit&#40;fr&#41; & RANK_2&#40;tr->wtm&#41;) &#123; // Double pawn push
			int to2 = fr+16-32*tr->wtm;
			if &#40;tr->Board&#91;to2&#93;==Empty&#41; nSafeMoves += 1;
		&#125;
	&#125; while &#40;Atk &= Atk - 1ull&#41;;		
&#125;
Before generating moves, I have an InCheck function that makes KVA and some other stuff.

Code: Select all

KVA =  RookAttacks&#40;ksqr,ALLPCS&#41; | BishopAttacks&#40;ksqr,ALLPCS&#41;;
Regards, Lasse

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

Re: On bitboard legal move generation

Post by SMIRF » Mon Feb 09, 2015 3:33 pm

Does your legal move generator also add information to each move, whether it is threatening a single or double check?

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

Re: On bitboard legal move generation

Post by Lasse Hansen » Mon Feb 09, 2015 3:48 pm

No, but in advance of the move generator, I run a check detection function, that generates KVA bitboard (king vulnerability attacks = seeing king as superpiece), and if king is in check, double check or not. Also, the function generates a bitmap of all squares that the check evasion function needs to generate all interventions from friendly pieces to evade the check.

Hrvoje Horvatic
Posts: 14
Joined: Mon Nov 10, 2014 12:53 pm

Re: On bitboard legal move generation

Post by Hrvoje Horvatic » Mon Feb 09, 2015 9:53 pm

Lasse,

that's fast, damn fast... I'm impressed...

Let me get this straight: you managed to beat QPerft with almost double nps count? No additional tricks? no hash table, no special SSE instructions, no copy-make tricks?

I just don't believe bitboards can go that fast... :twisted: specially if you use bswap to rotate board...

It's too late today, I will look at the code tommorow, I just noticed you use helper bitboards for pins and king attacks (kva), so you generate only legal moves, but this still doesn't explain such fantastic result... HGM in QPerft also utilizes pin information (ie. generates only legal moves), so I just can't believe that bitboards can beat what HGM has done...

Hrvoje Horvatic
Posts: 14
Joined: Mon Nov 10, 2014 12:53 pm

Re: On bitboard legal move generation

Post by Hrvoje Horvatic » Mon Feb 09, 2015 9:59 pm

Also, very weird thing is that if you do staged move generation (caps and non-caps separately) you lose a lot of speed... it is normal to lose 10% or maybe even a little more (depends on the quality of implementation), but you halved your nps! that's weird...

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

Re: On bitboard legal move generation

Post by Lasse Hansen » Mon Feb 09, 2015 10:42 pm

The staged move generation does not use PopCount at leaf nodes, that will explain the reduction in speed, and with the staged move gen I also have to scan through the pieces a second time to roll out the moves. I dont think I am using any additional tricks. The bswap is just used for generating symmetrical moves, not for speed.

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

Re: On bitboard legal move generation

Post by SMIRF » Mon Feb 16, 2015 5:25 pm

Here are the results of a simple perft of my new legal 8x8- and 10x8-random chess achromatic / symmetric legal move generator (no hashing, no turbo boost, on i7-4690S at 2.95 GHz):

Code: Select all

XFEN 00&#58; rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
   +-*--b--c--d--*--f--g--*-+
 8 |&#91;r&#93;&#91;n&#93;&#91;b&#93;&#91;q&#93;&#91;k&#93;&#91;b&#93;&#91;n&#93;&#91;r&#93;|  Compiled on Feb 16 2015
 7 |&#91;p&#93;&#91;p&#93;&#91;p&#93;&#91;p&#93;&#91;p&#93;&#91;p&#93;&#91;p&#93;&#91;p&#93;|  MS Vis.Studio C/C++ 64-Bit Vers. 18.0
 6 |   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;|
 5 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   |  Break, when time >= 10.0 sec
 4 |   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;|
 3 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   |  &#40;run without any hashing&#41;
 2 |<P><P><P><P><P><P><P><P>|
 1 |<R><N><B><Q><K><B><N><R>|
&#40;w&#41;+-*--b--c--d--*--f--g--*-+

Ply&#58;          Moves      Sec
 1&#58;              20     0.00
 2&#58;             400     0.00
 3&#58;            8902     0.00
 4&#58;          197281     0.00
 5&#58;         4865609     0.04
 6&#58;       119060324     0.89
 7&#58;      3195901860    23.11


XFEN 01&#58; r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 25
   +-*--b--c--d--*--f--g--*-+
 8 |&#91;r&#93;&#58;&#58;&#58;   &#58;&#58;&#58;&#91;k&#93;&#58;&#58;&#58;   &#91;r&#93;|  Compiled on Feb 16 2015
 7 |&#91;p&#93;   &#91;p&#93;&#91;p&#93;&#91;q&#93;&#91;p&#93;&#91;b&#93;   |  MS Vis.Studio C/C++ 64-Bit Vers. 18.0
 6 |&#91;b&#93;&#91;n&#93;   &#58;&#58;&#58;&#91;p&#93;&#91;n&#93;&#91;p&#93;&#58;&#58;&#58;|
 5 |&#58;&#58;&#58;   &#58;&#58;&#58;<P><N>   &#58;&#58;&#58;   |  Break, when time >= 10.0 sec
 4 |   &#91;p&#93;   &#58;&#58;&#58;<P>&#58;&#58;&#58;   &#58;&#58;&#58;|
 3 |&#58;&#58;&#58;   <N>   &#58;&#58;&#58;<Q>&#58;&#58;&#58;&#91;p&#93;|  &#40;run without any hashing&#41;
 2 |<P><P><P><B><B><P><P><P>|
 1 |<R>   &#58;&#58;&#58;   <K>   &#58;&#58;&#58;<R>|
&#40;w&#41;+-*--b--c--d--*--f--g--*-+

Ply&#58;          Moves      Sec
 1&#58;              48     0.00
 2&#58;            2039     0.00
 3&#58;           97862     0.00
 4&#58;         4085603     0.03
 5&#58;       193690690     1.19
 6&#58;      8031647685    53.60


XFEN 02&#58; 8/PPP4k/8/8/8/8/4Kppp/8 w - - 0 1
   +-a--b--c--d--e--f--g--h-+
 8 |   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;|  Compiled on Feb 16 2015
 7 |<P><P><P>   &#58;&#58;&#58;   &#58;&#58;&#58;&#91;k&#93;|  MS Vis.Studio C/C++ 64-Bit Vers. 18.0
 6 |   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;|
 5 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   |  Break, when time >= 10.0 sec
 4 |   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;|
 3 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   |  &#40;run without any hashing&#41;
 2 |   &#58;&#58;&#58;   &#58;&#58;&#58;<K>&#91;p&#93;&#91;p&#93;&#91;p&#93;|
 1 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   |
&#40;w&#41;+-a--b--c--d--e--f--g--h-+

Ply&#58;          Moves      Sec
 1&#58;              18     0.00
 2&#58;             290     0.00
 3&#58;            5044     0.00
 4&#58;           89363     0.00
 5&#58;         1745545     0.01
 6&#58;        34336777     0.25
 7&#58;       749660761     5.71
 8&#58;     16303466487   116.51

Post Reply