Check detection and move generation using bitboards

[Lasse Hansen]

Here is an alternative way to detect checks based on last move,
and to use this in move generation. Since I dont see it in Crafty,
I guess its not done by others yet. I get a pretty good speedup
when doing perft, based on this.

The basic idea is to look at the king from a queens view, plus
knights view when needed.

One nice thing is that when not in check, all queen, rook, bishop
and knight moves are legal by default, pinned or not.

Also, to help generate check evasions, the CheckDetect function generates
what I call CheckAtk, a bitmap of all squares to reach for to intersect
or capture the check giving piece, when not in double check.

Here's some sample code, hopefully self explanatory.

Cheers!, Lasse

Code: Select all

int CheckDetect(U32 ply) 
// Determines if wtm is in check or double check. 
// Sets KingVulnAtk[wtm]
// Sets CheckAtk = all sqrs that evades single check if reached by a piece
// Returns 0: Not in check 1: Single check 2: Double check
{
	U32 M = Game_MoveList[Game_Ply+ply-1];
	if (!M || SPECIAL(M)) return CheckDetectSlow(ply);
	U64 Atk = 0, KVA;
	int fr, to, ksqr;

	ksqr = FirstOne(Pieces[wtm][King]); 
	fr = FROM(M); to = TO(M);

	KVA = PosInfo[ply].KingVulnAtk[wtm] = RookAttacks(ksqr) | BishopAttacks(ksqr);
	PosInfo[ply].InCheck = 0;
	PosInfo[ply].CheckAtk = 0;

	if ((SetBit(fr) | SetBit(to)) & (KVA | KnightAttacks[ksqr])) {
		// Discovered check
		if (SetBit(fr) & KVA & MaskRook[ksqr]) { 
			Atk = (SetBit(fr) | RookAttacks(fr)) & MaskRook[ksqr];
			if (Atk & (Pieces[!wtm][Queen] | Pieces[!wtm][Rook])) { 
				PosInfo[ply].CheckAtk = Atk;
				PosInfo[ply].InCheck++;
				goto DirectCheck;
			}
		}
		if (SetBit(fr) & KVA & MaskBishop[ksqr]) {
			Atk = (SetBit(fr) | BishopAttacks(fr)) & MaskBishop[ksqr];
			if (Atk & (Pieces[!wtm][Queen] | Pieces[!wtm][Bishop])) {
				PosInfo[ply].CheckAtk = Atk;
				PosInfo[ply].InCheck++;
			}
		}
DirectCheck:
		if (SetBit(to) & KVA & MaskRook[ksqr]) {
			Atk = (SetBit(to) | RookAttacks(to)) & KVA & MaskRook[ksqr];
			if (Atk & (Pieces[!wtm][Queen] | Pieces[!wtm][Rook])) {
				PosInfo[ply].CheckAtk |= Atk;
				PosInfo[ply].InCheck++;
				return PosInfo[ply].InCheck;
			}
		}
		if (SetBit(to) & KVA & MaskBishop[ksqr]) {
			Atk = (SetBit(to) | BishopAttacks(to)) & KVA & MaskBishop[ksqr];
			if (Atk & (Pieces[!wtm][Queen] | Pieces[!wtm][Bishop])) {
				PosInfo[ply].CheckAtk |= Atk;
				PosInfo[ply].InCheck++;
				return PosInfo[ply].InCheck;
			}
		}
		Atk = SetBit(to) & KnightAttacks[ksqr] & Pieces[!wtm][Knight];
		if (Atk) {
			PosInfo[ply].CheckAtk |= Atk; 
			PosInfo[ply].InCheck++;
			return PosInfo[ply].InCheck;
		}
		Atk = SetBit(to) & PawnAttacks[wtm][ksqr] & Pieces[!wtm][Pawn];
		if (Atk) {
			PosInfo[ply].CheckAtk |= Atk; 
			PosInfo[ply].InCheck++;
			return PosInfo[ply].InCheck;
		}
	}
	return PosInfo[ply].InCheck;
}

int Movgen(U32 ply, U64 Trg)
// Generates q-legal (QRBN legal) moves to MoveList when InCheck == 0
// returns (-1) if king is attacked, else the number of moves
{
	U64 Atk, Pcs, B;
	int fr, to;
	U32 *M;
	U32 ksqr = FirstOne(Pieces[wtm][King]);
	
	if (ply>0) PosInfo[ply].FirstMove = PosInfo[ply-1].LastMove;
	M = PosInfo[ply].LastMove = PosInfo[ply].FirstMove;
	
	Pcs = Pieces[wtm][Queen];
	while (Pcs) {
		fr = wtm ? FirstOne(Pcs) : LastOne(Pcs);
		Atk = RookAttacks(fr) | BishopAttacks(fr);
		if (Atk & Pieces[!wtm][King]) return -1;
		Atk ^= Atk & Pieces[wtm][ALL];
		Pcs ^= SetBit(fr);

		B = SetBit(fr) & MaskRook[ksqr] & PosInfo[ply].KingVulnAtk[wtm];
		if (B) { // Possible rook pin
			B = Atk & MaskRook[fr] & MaskRook[ksqr];
			if (B & (Pieces[!wtm][Rook] | Pieces[!wtm][Queen])) {
				Atk = B;
				goto RollQueen;
			}
		}
		B = SetBit(fr) & MaskBishop[ksqr] & PosInfo[ply].KingVulnAtk[wtm];
		if (B) { // Possible bishop pin
			B = Atk & MaskBishop[fr] & MaskBishop[ksqr];
			if (B & (Pieces[!wtm][Bishop] | Pieces[!wtm][Queen])) {
				Atk = B;
				goto RollQueen;
			}
		}
	RollQueen:		
		Atk &= Trg;
		fr = &#40;fr<<6&#41;+((&#40;wtm<<3&#41;+Queen&#41;<<12&#41;;
		while &#40;Atk&#41; &#123;
			to = wtm ? FirstOne&#40;Atk&#41; &#58; LastOne&#40;Atk&#41;;
			*M++=fr+to+&#40;Board&#91;to&#93;<<16&#41;;
			Atk ^= SetBit&#40;to&#41;;
		&#125;
	&#125;
	PosInfo&#91;ply&#93;.LastMove = M;
	return &#40;M-PosInfo&#91;ply&#93;.FirstMove&#41;;
&#125;

[Evert]

Here is an alternative way to detect checks based on last move,
and to use this in move generation. Since I dont see it in Crafty,
I guess its not done by others yet. I get a pretty good speedup
when doing perft, based on this.

The basic idea is to look at the king from a queens view, plus
knights view when needed.

This is called a "superpiece" (a piece that moves like any piece in the game). I've used something like this for ages, both in Jazz and in Sjaak.
If a move does not disturb the lines of a superpiece on the location of the king, then it cannot be a checking move (or a check evasion, for that matter; I use that too since I only do pseudo-legal move generation when in check).
In Sjaak I use the superpiece to find possible checkers. In Jazz, I actually don't use it explicitly because I found that was faster to do a piece-type-by-piece-type test and take an early exit if I can (EDIT: specifically, I test for the knight first because it's easy and fast and I can take an immediate exit if the superpiece can take an enemy knight). This didn't actually test as faster using standard perft from the opening position, but it did test as slighly faster when using test positions or perft from other positions than the starting position. That's because the opening position is not representative of the type of position you encounter during the search.

I really like the concept though, so I keep trying to find new uses for it.
I'll have a look at your implementation and see if there's something I can adopt for my own.

[Lasse Hansen]

Some perft results from my Core i7 2600K @ 3.4GHz (BIOS normal mode):
Since all QRBN moves are legal when not in check, I use popcount at leaf
nodes instead of rolling out moves to movelist. I also compare with not
using popcount. These results are withouth hashing, single core.

Normal chess start position:

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

With popcount:

Code: Select all

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 49.32MN/s
perft 5=4865609 t=0.04s 115.85MN/s
perft 6=119060324 t=0.92s 128.85MN/s
perft 7=3195901860 t=22.97s 139.15MN/s

Without using popcount:

Code: Select all

perft 1=20 t=0.00s 0.00MN/s
perft 2=400 t=0.00s 0.00MN/s
perft 3=8902 t=0.00s 8.90MN/s
perft 4=197281 t=0.01s 32.88MN/s
perft 5=4865609 t=0.06s 76.03MN/s
perft 6=119060324 t=1.47s 80.99MN/s
perft 7=3195901860 t=36.93s 86.55MN/s

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

With popcount:

Code: Select all

perft 1=48 t=0.00s 0.00MN/s
perft 2=2039 t=0.00s 0.00MN/s
perft 3=97862 t=0.00s 0.00MN/s
perft 4=4085603 t=0.03s 163.42MN/s
perft 5=193690690 t=0.68s 284.00MN/s
perft 6=8031647685 t=33.79s 237.69MN/s
perft 7=374190009323 t=1377.11s 271.72MN/s

Without popcount:

Code: Select all

perft 1=48 t=0.00s 0.00MN/s
perft 2=2039 t=0.00s 0.00MN/s
perft 3=97862 t=0.00s 48.93MN/s
perft 4=4085603 t=0.04s 95.01MN/s
perft 5=193690690 t=1.54s 126.10MN/s
perft 6=8031647685 t=70.04s 114.67MN/s

[bob]

Here is an alternative way to detect checks based on last move,
and to use this in move generation. Since I dont see it in Crafty,
I guess its not done by others yet. I get a pretty good speedup
when doing perft, based on this.

The basic idea is to look at the king from a queens view, plus
knights view when needed.

This is old, first mentioned in Belle (ken called this a "super-piece" since you pretend that the piece on the target square can move to any square that any piece could reach... Crafty does this, but you have to look at "Attacks()" (in attacks.c). You find this exact idea.

One nice thing is that when not in check, all queen, rook, bishop
and knight moves are legal by default, pinned or not.

Also, to help generate check evasions, the CheckDetect function generates
what I call CheckAtk, a bitmap of all squares to reach for to intersect
or capture the check giving piece, when not in double check.

Here's some sample code, hopefully self explanatory.

Cheers!, Lasse

Code: Select all

int CheckDetect(U32 ply) 
// Determines if wtm is in check or double check. 
// Sets KingVulnAtk[wtm]
// Sets CheckAtk = all sqrs that evades single check if reached by a piece
// Returns 0: Not in check 1: Single check 2: Double check
{
	U32 M = Game_MoveList[Game_Ply+ply-1];
	if (!M || SPECIAL(M)) return CheckDetectSlow(ply);
	U64 Atk = 0, KVA;
	int fr, to, ksqr;

	ksqr = FirstOne(Pieces[wtm][King]); 
	fr = FROM(M); to = TO(M);

	KVA = PosInfo[ply].KingVulnAtk[wtm] = RookAttacks(ksqr) | BishopAttacks(ksqr);
	PosInfo[ply].InCheck = 0;
	PosInfo[ply].CheckAtk = 0;

	if ((SetBit(fr) | SetBit(to)) & (KVA | KnightAttacks[ksqr])) {
		// Discovered check
		if (SetBit(fr) & KVA & MaskRook[ksqr]) { 
			Atk = (SetBit(fr) | RookAttacks(fr)) & MaskRook[ksqr];
			if (Atk & (Pieces[!wtm][Queen] | Pieces[!wtm][Rook])) { 
				PosInfo[ply].CheckAtk = Atk;
				PosInfo[ply].InCheck++;
				goto DirectCheck;
			}
		}
		if (SetBit(fr) & KVA & MaskBishop[ksqr]) {
			Atk = (SetBit(fr) | BishopAttacks(fr)) & MaskBishop[ksqr];
			if (Atk & (Pieces[!wtm][Queen] | Pieces[!wtm][Bishop])) {
				PosInfo[ply].CheckAtk = Atk;
				PosInfo[ply].InCheck++;
			}
		}
DirectCheck:
		if (SetBit(to) & KVA & MaskRook[ksqr]) {
			Atk = (SetBit(to) | RookAttacks(to)) & KVA & MaskRook[ksqr];
			if (Atk & (Pieces[!wtm][Queen] | Pieces[!wtm][Rook])) {
				PosInfo[ply].CheckAtk |= Atk;
				PosInfo[ply].InCheck++;
				return PosInfo[ply].InCheck;
			}
		}
		if (SetBit(to) & KVA & MaskBishop[ksqr]) {
			Atk = (SetBit(to) | BishopAttacks(to)) & KVA & MaskBishop[ksqr];
			if (Atk & (Pieces[!wtm][Queen] | Pieces[!wtm][Bishop])) {
				PosInfo[ply].CheckAtk |= Atk;
				PosInfo[ply].InCheck++;
				return PosInfo[ply].InCheck;
			}
		}
		Atk = SetBit(to) & KnightAttacks[ksqr] & Pieces[!wtm][Knight];
		if (Atk) {
			PosInfo[ply].CheckAtk |= Atk; 
			PosInfo[ply].InCheck++;
			return PosInfo[ply].InCheck;
		}
		Atk = SetBit(to) & PawnAttacks[wtm][ksqr] & Pieces[!wtm][Pawn];
		if (Atk) {
			PosInfo[ply].CheckAtk |= Atk; 
			PosInfo[ply].InCheck++;
			return PosInfo[ply].InCheck;
		}
	}
	return PosInfo[ply].InCheck;
}

int Movgen(U32 ply, U64 Trg)
// Generates q-legal (QRBN legal) moves to MoveList when InCheck == 0
// returns (-1) if king is attacked, else the number of moves
{
	U64 Atk, Pcs, B;
	int fr, to;
	U32 *M;
	U32 ksqr = FirstOne(Pieces[wtm][King]);
	
	if (ply>0) PosInfo[ply].FirstMove = PosInfo[ply-1].LastMove;
	M = PosInfo[ply].LastMove = PosInfo[ply].FirstMove;
	
	Pcs = Pieces[wtm][Queen];
	while (Pcs) {
		fr = wtm ? FirstOne(Pcs) : LastOne(Pcs);
		Atk = RookAttacks(fr) | BishopAttacks(fr);
		if (Atk & Pieces[!wtm][King]) return -1;
		Atk ^= Atk & Pieces[wtm][ALL];
		Pcs ^= SetBit(fr);

		B = SetBit(fr) & MaskRook[ksqr] & PosInfo[ply].KingVulnAtk[wtm];
		if (B) { // Possible rook pin
			B = Atk & MaskRook[fr] & MaskRook[ksqr];
			if (B & (Pieces[!wtm][Rook] | Pieces[!wtm][Queen])) {
				Atk = B;
				goto RollQueen;
			}
		}
		B = SetBit(fr) & MaskBishop[ksqr] & PosInfo[ply].KingVulnAtk[wtm];
		if (B) { // Possible bishop pin
			B = Atk & MaskBishop[fr] & MaskBishop[ksqr];
			if (B & (Pieces[!wtm][Bishop] | Pieces[!wtm][Queen])) {
				Atk = B;
				goto RollQueen;
			}
		}
	RollQueen:		
		Atk &= Trg;
		fr = &#40;fr<<6&#41;+((&#40;wtm<<3&#41;+Queen&#41;<<12&#41;;
		while &#40;Atk&#41; &#123;
			to = wtm ? FirstOne&#40;Atk&#41; &#58; LastOne&#40;Atk&#41;;
			*M++=fr+to+&#40;Board&#91;to&#93;<<16&#41;;
			Atk ^= SetBit&#40;to&#41;;
		&#125;
	&#125;
	PosInfo&#91;ply&#93;.LastMove = M;
	return &#40;M-PosInfo&#91;ply&#93;.FirstMove&#41;;
&#125;

Crafty's "GenerateCheckEvasions" is similar in idea...

[bob]

Some perft results from my Core i7 2600K @ 3.4GHz (BIOS normal mode):
Since all QRBN moves are legal when not in check, I use popcount at leaf
nodes instead of rolling out moves to movelist. I also compare with not
using popcount. These results are withouth hashing, single core.

Normal chess start position:

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

With popcount:

Code: Select all

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 49.32MN/s
perft 5=4865609 t=0.04s 115.85MN/s
perft 6=119060324 t=0.92s 128.85MN/s
perft 7=3195901860 t=22.97s 139.15MN/s

Without using popcount:

Code: Select all

perft 1=20 t=0.00s 0.00MN/s
perft 2=400 t=0.00s 0.00MN/s
perft 3=8902 t=0.00s 8.90MN/s
perft 4=197281 t=0.01s 32.88MN/s
perft 5=4865609 t=0.06s 76.03MN/s
perft 6=119060324 t=1.47s 80.99MN/s
perft 7=3195901860 t=36.93s 86.55MN/s

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

With popcount:

Code: Select all

perft 1=48 t=0.00s 0.00MN/s
perft 2=2039 t=0.00s 0.00MN/s
perft 3=97862 t=0.00s 0.00MN/s
perft 4=4085603 t=0.03s 163.42MN/s
perft 5=193690690 t=0.68s 284.00MN/s
perft 6=8031647685 t=33.79s 237.69MN/s
perft 7=374190009323 t=1377.11s 271.72MN/s

Without popcount:

Code: Select all

perft 1=48 t=0.00s 0.00MN/s
perft 2=2039 t=0.00s 0.00MN/s
perft 3=97862 t=0.00s 48.93MN/s
perft 4=4085603 t=0.04s 95.01MN/s
perft 5=193690690 t=1.54s 126.10MN/s
perft 6=8031647685 t=70.04s 114.67MN/s

How can you be sure all those "last ply" moves are legal? Perft does not count illegal moves...

[Ajedrecista]

Hello:

Some perft results from my Core i7 2600K @ 3.4GHz (BIOS normal mode):
Since all QRBN moves are legal when not in check, I use popcount at leaf
nodes instead of rolling out moves to movelist. I also compare with not
using popcount. These results are withouth hashing, single core.

Normal chess start position:

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

With popcount:

Code: Select all

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 49.32MN/s
perft 5=4865609 t=0.04s 115.85MN/s
perft 6=119060324 t=0.92s 128.85MN/s
perft 7=3195901860 t=22.97s 139.15MN/s

Without using popcount:

Code: Select all

perft 1=20 t=0.00s 0.00MN/s
perft 2=400 t=0.00s 0.00MN/s
perft 3=8902 t=0.00s 8.90MN/s
perft 4=197281 t=0.01s 32.88MN/s
perft 5=4865609 t=0.06s 76.03MN/s
perft 6=119060324 t=1.47s 80.99MN/s
perft 7=3195901860 t=36.93s 86.55MN/s

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

With popcount:

Code: Select all

perft 1=48 t=0.00s 0.00MN/s
perft 2=2039 t=0.00s 0.00MN/s
perft 3=97862 t=0.00s 0.00MN/s
perft 4=4085603 t=0.03s 163.42MN/s
perft 5=193690690 t=0.68s 284.00MN/s
perft 6=8031647685 t=33.79s 237.69MN/s
perft 7=374190009323 t=1377.11s 271.72MN/s

Without popcount:

Code: Select all

perft 1=48 t=0.00s 0.00MN/s
perft 2=2039 t=0.00s 0.00MN/s
perft 3=97862 t=0.00s 48.93MN/s
perft 4=4085603 t=0.04s 95.01MN/s
perft 5=193690690 t=1.54s 126.10MN/s
perft 6=8031647685 t=70.04s 114.67MN/s

How can you be sure all those "last ply" moves are legal? Perft does not count illegal moves...

I have run Perft(1) to Perft(7) of the following position:

[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - -

I have used JetChess 1.0.0.0 (a single core, w32 perft counter) with 64 MB of hash for Perft(1) to Perft(5), and 1 GB of hash for Perft(6) and Perft(7). My computer is an Intel Pentium D930 (2999 MHz), so nothing of the outer space.

Code: Select all

Total:               48

48 (move pathes after 1 half move).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Qf3-g4          43
  2  Qf3-h5          43
  3  Qf3-f4          43
  4  Qf3-f5          45
  5  Qf3*f6          39
  6  Qf3-g3          43
  7  Qf3*h3          43
  8  Qf3-e3          43
  9  Qf3-d3          42
 10  Ra1-b1          43
 11  Ra1-c1          43
 12  Ra1-d1          43
 13  Rh1-g1          43
 14  Rh1-f1          43
 15  Bd2-e3          43
 16  Bd2-f4          43
 17  Bd2-g5          42
 18  Bd2-h6          41
 19  Bd2-c1          43
 20  Be2-d3          42
 21  Be2-c4          41
 22  Be2-b5          39
 23  Be2*a6          36
 24  Be2-f1          44
 25  Be2-d1          44
 26  Nc3-a4          42
 27  Nc3-b5          39
 28  Nc3-b1          42
 29  Nc3-d1          42
 30  Ne5-c6          41
 31  Ne5*d7          45
 32  Ne5*f7          44
 33  Ne5*g6          42
 34  Ne5-c4          42
 35  Ne5-d3          43
 36  Ne5-g4          44
 37   a2-a3          44
 38   a2-a4          44
 39   b2-b3          42
 40   g2-g3          42
 41   g2-g4          42
 42   g2*h3          43
 43   d5-d6          41
 44   d5*e6          46
 45     0-0          43
 46   0-0-0          43
 47  Ke1-f1          43
 48  Ke1-d1          43

Total:             2039

2,039 (move pathes after 2 half moves).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Qf3-g4        2169
  2  Qf3-h5        2267
  3  Qf3-f4        2132
  4  Qf3-f5        2396
  5  Qf3*f6        2111
  6  Qf3-g3        2214
  7  Qf3*h3        2360
  8  Qf3-e3        2174
  9  Qf3-d3        2005
 10  Ra1-b1        1969
 11  Ra1-c1        1968
 12  Ra1-d1        1885
 13  Rh1-g1        2013
 14  Rh1-f1        1929
 15  Bd2-e3        2136
 16  Bd2-f4        2000
 17  Bd2-g5        2134
 18  Bd2-h6        2019
 19  Bd2-c1        1963
 20  Be2-d3        2050
 21  Be2-c4        2082
 22  Be2-b5        2057
 23  Be2*a6        1907
 24  Be2-f1        2060
 25  Be2-d1        1733
 26  Nc3-a4        2203
 27  Nc3-b5        2138
 28  Nc3-b1        2038
 29  Nc3-d1        2040
 30  Ne5-c6        2027
 31  Ne5*d7        2124
 32  Ne5*f7        2080
 33  Ne5*g6        1997
 34  Ne5-c4        1880
 35  Ne5-d3        1803
 36  Ne5-g4        1878
 37   a2-a3        2186
 38   a2-a4        2149
 39   b2-b3        1964
 40   g2-g3        1882
 41   g2-g4        1843
 42   g2*h3        1970
 43   d5-d6        1991
 44   d5*e6        2241
 45     0-0        2059
 46   0-0-0        1887
 47  Ke1-f1        1855
 48  Ke1-d1        1894

Total:            97862

97,862 (move pathes after 3 half moves).

Time: 1 ms (0:00:00.001).

Code: Select all

  1  Qf3-g4       92037
  2  Qf3-h5       95034
  3  Qf3-f4       90488
  4  Qf3-f5      104992
  5  Qf3*f6       77838
  6  Qf3-g3       94461
  7  Qf3*h3       98524
  8  Qf3-e3       92505
  9  Qf3-d3       83727
 10  Ra1-b1       83348
 11  Ra1-c1       83263
 12  Ra1-d1       79695
 13  Rh1-g1       84876
 14  Rh1-f1       81563
 15  Bd2-e3       90274
 16  Bd2-f4       84869
 17  Bd2-g5       87951
 18  Bd2-h6       82323
 19  Bd2-c1       83037
 20  Be2-d3       85119
 21  Be2-c4       84835
 22  Be2-b5       79739
 23  Be2*a6       69334
 24  Be2-f1       88728
 25  Be2-d1       74963
 26  Nc3-a4       91447
 27  Nc3-b5       81498
 28  Nc3-b1       84773
 29  Nc3-d1       84782
 30  Ne5-c6       83885
 31  Ne5*d7       93913
 32  Ne5*f7       88799
 33  Ne5*g6       83866
 34  Ne5-c4       77752
 35  Ne5-d3       77431
 36  Ne5-g4       79912
 37   a2-a3       94405
 38   a2-a4       90978
 39   b2-b3       81066
 40   g2-g3       77468
 41   g2-g4       75677
 42   g2*h3       82759
 43   d5-d6       79551
 44   d5*e6       97464
 45     0-0       86975
 46   0-0-0       79803
 47  Ke1-f1       77887
 48  Ke1-d1       79989

Total:          4085603

4,085,603 (move pathes after 4 half moves).

Time: 78 ms (0:00:00.078).

Code: Select all

  1  Qf3-g4     4514010
  2  Qf3-h5     4743335
  3  Qf3-f4     4327936
  4  Qf3-f5     5271134
  5  Qf3*f6     3975992
  6  Qf3-g3     4669768
  7  Qf3*h3     5067173
  8  Qf3-e3     4477772
  9  Qf3-d3     3949570
 10  Ra1-b1     3827454
 11  Ra1-c1     3814203
 12  Ra1-d1     3568344
 13  Rh1-g1     3989454
 14  Rh1-f1     3685756
 15  Bd2-e3     4407041
 16  Bd2-f4     3941257
 17  Bd2-g5     4370915
 18  Bd2-h6     3967365
 19  Bd2-c1     3793390
 20  Be2-d3     4066966
 21  Be2-c4     4182989
 22  Be2-b5     4032348
 23  Be2*a6     3553501
 24  Be2-f1     4095479
 25  Be2-d1     3074219
 26  Nc3-a4     4628497
 27  Nc3-b5     4317482
 28  Nc3-b1     3996171
 29  Nc3-d1     3995761
 30  Ne5-c6     4083458
 31  Ne5*d7     4404043
 32  Ne5*f7     4164923
 33  Ne5*g6     3949417
 34  Ne5-c4     3494887
 35  Ne5-d3     3288812
 36  Ne5-g4     3415992
 37   a2-a3     4627439
 38   a2-a4     4387586
 39   b2-b3     3768824
 40   g2-g3     3472039
 41   g2-g4     3338154
 42   g2*h3     3819456
 43   d5-d6     3835265
 44   d5*e6     4727437
 45     0-0     4119629
 46   0-0-0     3551583
 47  Ke1-f1     3377351
 48  Ke1-d1     3559113

Total:        193690690

193,690,690 (move pathes after 5 half moves).

Time: 1.384 s (0:00:01.384).

Code: Select all

  1  Qf3-g4   189789456
  2  Qf3-h5   197839051
  3  Qf3-f4   181938761
  4  Qf3-f5   226135507
  5  Qf3*f6   146338070
  6  Qf3-g3   198078522
  7  Qf3*h3   210100865
  8  Qf3-e3   189120807
  9  Qf3-d3   164583144
 10  Ra1-b1   160413321
 11  Ra1-c1   159720218
 12  Ra1-d1   149265033
 13  Rh1-g1   166086672
 14  Rh1-f1   154273720
 15  Bd2-e3   184114087
 16  Bd2-f4   165805784
 17  Bd2-g5   177883051
 18  Bd2-h6   161319567
 19  Bd2-c1   158801466
 20  Be2-d3   167737155
 21  Be2-c4   170094798
 22  Be2-b5   158033152
 23  Be2*a6   130642863
 24  Be2-f1   174218453
 25  Be2-d1   131348645
 26  Nc3-a4   191260040
 27  Nc3-b5   166970874
 28  Nc3-b1   165673862
 29  Nc3-d1   165415976
 30  Ne5-c6   169836097
 31  Ne5*d7   193856446
 32  Ne5*f7   176070755
 33  Ne5*g6   165477768
 34  Ne5-c4   145182844
 35  Ne5-d3   140737072
 36  Ne5-g4   144264874
 37   a2-a3   197413067
 38   a2-a4   183872225
 39   b2-b3   153953689
 40   g2-g3   141076301
 41   g2-g4   135208177
 42   g2*h3   158328615
 43   d5-d6   151133066
 44   d5*e6   203255191
 45     0-0   172063416
 46   0-0-0   148701308
 47  Ke1-f1   139601450
 48  Ke1-d1   148612404

Total:       8031647685

8,031,647,685 (move pathes after 6 half moves).

Time: 35.798 s (0:00:35.798).

Code: Select all

  1  Qf3-g4   9047498461
  2  Qf3-h5   9445639220
  3  Qf3-f4   8487829062
  4  Qf3-f5  10870589675
  5  Qf3*f6   7136487960
  6  Qf3-g3   9484342196
  7  Qf3*h3  10314822739
  8  Qf3-e3   8885152041
  9  Qf3-d3   7637864872
 10  Ra1-b1   7312345541
 11  Ra1-c1   7249929466
 12  Ra1-d1   6710600976
 13  Rh1-g1   7743466513
 14  Rh1-f1   6941145758
 15  Bd2-e3   8831533611
 16  Bd2-f4   7644341581
 17  Bd2-g5   8614847947
 18  Bd2-h6   7594325672
 19  Bd2-c1   7188695081
 20  Be2-d3   7843129110
 21  Be2-c4   8143385765
 22  Be2-b5   7708742487
 23  Be2*a6   6480008058
 24  Be2-f1   7893751276
 25  Be2-d1   5464336094
 26  Nc3-a4   9346560191
 27  Nc3-b5   8536331785
 28  Nc3-b1   7574150349
 29  Nc3-d1   7560735010
 30  Ne5-c6   8102096729
 31  Ne5*d7   8964657917
 32  Ne5*f7   8146033781
 33  Ne5*g6   7679730505
 34  Ne5-c4   6485370632
 35  Ne5-d3   6010078078
 36  Ne5-g4   6143255313
 37   a2-a3   9491604100
 38   a2-a4   8711431200
 39   b2-b3   7059227732
 40   g2-g3   6261927843
 41   g2-g4   5928350487
 42   g2*h3   7265571564
 43   d5-d6   7180089264
 44   d5*e6   9741806126
 45     0-0   8038310789
 46   0-0-0   6631088095
 47  Ke1-f1   6050797903
 48  Ke1-d1   6605992768

Total:      374190009323

374,190,009,323 (move pathes after 7 half moves).

Time: 862.823 s (0:14:22.823).

I had to change the order of castles in the FEN string, from:

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

To:

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

If not, perft values were different; this position is well known for perft purposes and I was confused when JetChess gave wrong results until I noticed that the key was in FEN string. So, these numbers I post (which match with the ones that Lasse obtained) should be correct. Of course perft values of starting position are fine.

Regards from Spain.

Ajedrecista.

[bob]

Couple of things.

1. I assume you only generate legal moves? If so, that incurs a cost that can be avoided much of the time, if you wait until the last second to verify that a move is legal, as in a CUT node, you will only verify the first move, as opposed to doing them all when you generate them.

2. KQ or QK should make ZERO difference to perft. Those are simply two letters that say that white can castle king-side (K) and/or queenside (Q). KQ or QK should work identically.

[Ajedrecista]

Hello Mr. Hyatt:

Couple of things.

1. I assume you only generate legal moves? If so, that incurs a cost that can be avoided much of the time, if you wait until the last second to verify that a move is legal, as in a CUT node, you will only verify the first move, as opposed to doing them all when you generate them.

2. KQ or QK should make ZERO difference to perft. Those are simply two letters that say that white can castle king-side (K) and/or queenside (Q). KQ or QK should work identically.

Jetchess is not my programme, so really I do not know how it internally works. It can be downloaded from its web. Please try it. It comes with an easy interface (very easy indeed, because I know how to use it!).

I post the example of switching KQkq to QKqk from Perft(1) to Perft(3):

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - - (the string that gives correct results):

Code: Select all

Total:               48

48 (move pathes after 1 half move).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Qf3-g4          43
  2  Qf3-h5          43
  3  Qf3-f4          43
  4  Qf3-f5          45
  5  Qf3*f6          39
  6  Qf3-g3          43
  7  Qf3*h3          43
  8  Qf3-e3          43
  9  Qf3-d3          42
 10  Ra1-b1          43
 11  Ra1-c1          43
 12  Ra1-d1          43
 13  Rh1-g1          43
 14  Rh1-f1          43
 15  Bd2-e3          43
 16  Bd2-f4          43
 17  Bd2-g5          42
 18  Bd2-h6          41
 19  Bd2-c1          43
 20  Be2-d3          42
 21  Be2-c4          41
 22  Be2-b5          39
 23  Be2*a6          36
 24  Be2-f1          44
 25  Be2-d1          44
 26  Nc3-a4          42
 27  Nc3-b5          39
 28  Nc3-b1          42
 29  Nc3-d1          42
 30  Ne5-c6          41
 31  Ne5*d7          45
 32  Ne5*f7          44
 33  Ne5*g6          42
 34  Ne5-c4          42
 35  Ne5-d3          43
 36  Ne5-g4          44
 37   a2-a3          44
 38   a2-a4          44
 39   b2-b3          42
 40   g2-g3          42
 41   g2-g4          42
 42   g2*h3          43
 43   d5-d6          41
 44   d5*e6          46
 45     0-0          43
 46   0-0-0          43
 47  Ke1-f1          43
 48  Ke1-d1          43

Total:             2039

2,039 (move pathes after 2 half moves).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Qf3-g4        2169
  2  Qf3-h5        2267
  3  Qf3-f4        2132
  4  Qf3-f5        2396
  5  Qf3*f6        2111
  6  Qf3-g3        2214
  7  Qf3*h3        2360
  8  Qf3-e3        2174
  9  Qf3-d3        2005
 10  Ra1-b1        1969
 11  Ra1-c1        1968
 12  Ra1-d1        1885
 13  Rh1-g1        2013
 14  Rh1-f1        1929
 15  Bd2-e3        2136
 16  Bd2-f4        2000
 17  Bd2-g5        2134
 18  Bd2-h6        2019
 19  Bd2-c1        1963
 20  Be2-d3        2050
 21  Be2-c4        2082
 22  Be2-b5        2057
 23  Be2*a6        1907
 24  Be2-f1        2060
 25  Be2-d1        1733
 26  Nc3-a4        2203
 27  Nc3-b5        2138
 28  Nc3-b1        2038
 29  Nc3-d1        2040
 30  Ne5-c6        2027
 31  Ne5*d7        2124
 32  Ne5*f7        2080
 33  Ne5*g6        1997
 34  Ne5-c4        1880
 35  Ne5-d3        1803
 36  Ne5-g4        1878
 37   a2-a3        2186
 38   a2-a4        2149
 39   b2-b3        1964
 40   g2-g3        1882
 41   g2-g4        1843
 42   g2*h3        1970
 43   d5-d6        1991
 44   d5*e6        2241
 45     0-0        2059
 46   0-0-0        1887
 47  Ke1-f1        1855
 48  Ke1-d1        1894

Total:            97862

97,862 (move pathes after 3 half moves).

Time: 1 ms (0:00:00.001).

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w QKqk - - (the string that gives wrong results):

Code: Select all

Total:               47

47 (move pathes after 1 half move).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Qf3-g4          42
  2  Qf3-h5          42
  3  Qf3-f4          42
  4  Qf3-f5          44
  5  Qf3*f6          38
  6  Qf3-g3          42
  7  Qf3*h3          42
  8  Qf3-e3          42
  9  Qf3-d3          41
 10  Ra1-b1          42
 11  Ra1-c1          42
 12  Ra1-d1          42
 13  Rh1-g1          42
 14  Rh1-f1          42
 15  Bd2-e3          42
 16  Bd2-f4          42
 17  Bd2-g5          41
 18  Bd2-h6          40
 19  Bd2-c1          42
 20  Be2-d3          41
 21  Be2-c4          40
 22  Be2-b5          38
 23  Be2*a6          36
 24  Be2-f1          43
 25  Be2-d1          43
 26  Nc3-a4          41
 27  Nc3-b5          38
 28  Nc3-b1          41
 29  Nc3-d1          41
 30  Ne5-c6          41
 31  Ne5*d7          44
 32  Ne5*f7          44
 33  Ne5*g6          41
 34  Ne5-c4          41
 35  Ne5-d3          42
 36  Ne5-g4          43
 37   a2-a3          43
 38   a2-a4          43
 39   b2-b3          41
 40   g2-g3          41
 41   g2-g4          41
 42   g2*h3          42
 43   d5-d6          40
 44   d5*e6          45
 45     0-0          42
 46  Ke1-f1          42
 47  Ke1-d1          42

Total:             1952

1,952 (move pathes after 2 half moves).

Time: 0 ms (0:00:00.000).

Code: Select all

  1  Qf3-g4        2077
  2  Qf3-h5        2172
  3  Qf3-f4        2041
  4  Qf3-f5        2299
  5  Qf3*f6        2019
  6  Qf3-g3        2121
  7  Qf3*h3        2263
  8  Qf3-e3        2082
  9  Qf3-d3        1916
 10  Ra1-b1        1923
 11  Ra1-c1        1922
 12  Ra1-d1        1841
 13  Rh1-g1        1925
 14  Rh1-f1        1843
 15  Bd2-e3        2045
 16  Bd2-f4        1912
 17  Bd2-g5        2043
 18  Bd2-h6        1931
 19  Bd2-c1        1917
 20  Be2-d3        1960
 21  Be2-c4        1991
 22  Be2-b5        1966
 23  Be2*a6        1871
 24  Be2-f1        1971
 25  Be2-d1        1694
 26  Nc3-a4        2110
 27  Nc3-b5        2045
 28  Nc3-b1        1989
 29  Nc3-d1        1991
 30  Ne5-c6        1987
 31  Ne5*d7        2033
 32  Ne5*f7        2037
 33  Ne5*g6        1909
 34  Ne5-c4        1794
 35  Ne5-d3        1719
 36  Ne5-g4        1793
 37   a2-a3        2094
 38   a2-a4        2058
 39   b2-b3        1877
 40   g2-g3        1797
 41   g2-g4        1759
 42   g2*h3        1883
 43   d5-d6        1903
 44   d5*e6        2148
 45     0-0        2011
 46  Ke1-f1        1810
 47  Ke1-d1        1849

Total:            92341

92,341 (move pathes after 3 half moves).

Time: 1 ms (0:00:00.001).

Perft values for higher plies also differ, as expected. Hash = 64 MB for all these examples. White castle queenside (O-O-O) disappears and also node counts for other moves vary (I suppose that also black castle queenside disappears, but this is only a guess).

I will try to answer you, but please bear in mind that I am not a programmer and my chess/programming knowledge is VERY limited.

1.- AFAIK this programme only generates legal moves; otherwise (i.e. generating illegal moves) those perft values would be senseless. I have checked lots of positions on this subforum with this programme (just check my profile), and I always agree (well, the results given by JetChess agree) with no less than Steven Edwards and Paul Byrne results, people that know a lot of things about generating moves and calculating perft values (as you). I will not answer the rest of the first question because simply I have no idea (Jetchess author is Thomas Zipproth, not me). I am unable of answer you in a better way. Sorry.

2.- I fully agree with you: they should work identically, but the fact is just the opposite. I have been using JetChess for three or four months (more less), and this was the very first time I realize about that issue (luckily I always put K before Q, so everything should be fine). It is surely a bug. I will check the order of castle rights in future tests for ensuring the validity of the results.

Regards from Spain.

Ajedrecista.

[sje]

A reminder:

A FEN record always has EXACTLY SIX fields. No program is obligated to interpret an invalid FEN record, and no program should generate an invalid FEN record.

Also, the ordering of the castling availability is KQkq.

A sample:

Code: Select all

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

[Sven]

One nice thing is that when not in check, all queen, rook, bishop and knight moves are legal by default, pinned or not.

Could you explain this, please? To my understanding, moving a pinned knight is always illegal, as well as for instance moving a rook pinned by a bishop or a bishop pinned by a rook, etc. So maybe I did not get your point in that sentence above.

Sven