Question regarding perft capture results

[algerbrex]

Hi,

I've been working on creating a chess engine, and right now I have the move generation function producing the correct number of nodes up to depth=4 from the starting position. However, when I added code to measure the number of captures and checks, both numbers were off a bit. So I did some investigating and at depth=2, I found the issue.

Both my engine and the perft tool I was testing against produced the exact same correct moves for the position at depth=2:

[d]rnbqkbnr/pppp1ppp/8/4p3/3P4/8/PPP1PPPP/RNBQKBNR w KQkq - 0 1

The only difference was that my perft function added d4xe5 to the total number of captures, while the tool I was testing against did not. So my perft function recorded 37 captures, but the tool recorded 36. This confused me. Would d4xe5 not be considered a capture, and thus added to the overall capture total? Why would it not be included?

Further, when I made the adjustment to filter out recording captures that occurred at depth=2 in my perft function, all the problems went away and I correctly produced the total number of checks and captures at depth=3 and depth=4. Can anyone provide any insight here as to what I'm doing wrong? Since my perft function is apparently the problem and not my engine, I've included the code for it below (written in golang):

Code: Select all

func Perft(board Board, depth int, divideAt int) PerftInfo {
	moves := ComputeAllLegalMoves(board)
	var nodes, captures, checks uint64
	movesToPerftInfo := make(map[Move]PerftInfo)

	if depth == 0 {
		return PerftInfo{Nodes: 1, Captures: 0, Checks: 0}
	}

	for _, move := range moves {
		if move.MoveType == Attack { //&& depth != 2 {
			captures++
		}

		MakeMove(&board, move)
		if IsCurrentPositionACheck(board) { //&& depth != 2 {
			checks++
		}
		perftInfo := Perft(board, depth-1, divideAt)
		movesToPerftInfo[move] = perftInfo
		nodes += perftInfo.Nodes
		captures += perftInfo.Captures
		checks += perftInfo.Checks
		UndoMove(&board, move)
	}

	if depth == divideAt {
		fmt.Println("------------------------------")
		for move, perftInfo := range movesToPerftInfo {
			fmt.Printf("%v: (nodes=%v, captures=%v, checks=%v)\n", move, perftInfo.Nodes, perftInfo.Captures, perftInfo.Checks)
		}
		fmt.Println("------------------------------")
	}
	return PerftInfo{Nodes: nodes, Captures: captures, Checks: checks}
}

[Joost Buijs]

The capture d4xe5 occurs at depth 3, if you calculate perft() for depth 2 you should not include it.
I didn't look at your code, maybe you interpret depth in a different way?

[algerbrex]

Huh, maybe I am understanding perft differently. I'll try to do a little more reading. Thanks.

[mvanthoor]

Huh, maybe I am understanding perft differently. I'll try to do a little more reading. Thanks.

d2-d4 (and all other moves by white) are depth 1.
e7-e5 (and all other moves by black) are depth 2.

So d4xe5 is played by white at depth 3, at the earliest. If you are including it in depth 2, you're including white moves during black's turn.

[algerbrex]

Huh, maybe I am understanding perft differently. I'll try to do a little more reading. Thanks.

d2-d4 (and all other moves by white) are depth 1.
e7-e5 (and all other moves by black) are depth 2.

So d4xe5 is played by white at depth 3, at the earliest. If you are including it in depth 2, you're including white moves during black's turn.

Well, see, here's where I'm confused. The position is showed in my question is the start position I use. And I went to a depth of 2. So at a depth of two from the position is showed, d4xe5 is a move for white, a capture move, so should it not be included along with the other captures move at a depth of 1?

[mvanthoor]

Well, see, here's where I'm confused. The position is showed in my question is the start position I use. And I went to a depth of 2. So at a depth of two from the position is showed, d4xe5 is a move for white, a capture move, so should it not be included along with the other captures move at a depth of 1?

If this position is the starting position for perft, then according to the FEN-string, white has the move. d4xe5 is a move on depth 1. It should thus be included in the results.

Use an engine with a known good perft, or something like QPert (by HG Muller) to verify.

My engine says:

Benchmarking perft 1-1:

8 r n b q k b n r
7 i i i i . i i i
6 . . . . . . . .
5 . . . . i . . .
4 . . . I . . . .
3 . . . . . . . .
2 I I I . I I I I
1 R N B Q K B N R

A B C D E F G H

Zobrist key: bc9b7354e69febc8
Active Color: White
Castling: KQkq
En Passant: -
Half-move clock: 0
Full-move number: 1

Perft 1: 29 (0 ms, inf leaves/sec, hash full: 0%)
Total time spent: 0 ms
Execution speed: inf leaves/second

29 moves on depth 1 for white:

16 pawn moves (including d4xe5)
5 knight moves
2 queen moves
5 bishop moves
1 king move
===
29 moves

[algerbrex]

Well, see, here's where I'm confused. The position is showed in my question is the start position I use. And I went to a depth of 2. So at a depth of two from the position is showed, d4xe5 is a move for white, a capture move, so should it not be included along with the other captures move at a depth of 1?

If this position is the starting position for perft, then according to the FEN-string, white has the move. d4xe5 is a move on depth 1. It should thus be included in the results.

Use an engine with a known good perft, or something like QPert (by HG Muller) to verify.

My engine says:

Benchmarking perft 1-1:

8 r n b q k b n r
7 i i i i . i i i
6 . . . . . . . .
5 . . . . i . . .
4 . . . I . . . .
3 . . . . . . . .
2 I I I . I I I I
1 R N B Q K B N R

A B C D E F G H

Zobrist key: bc9b7354e69febc8
Active Color: White
Castling: KQkq
En Passant: -
Half-move clock: 0
Full-move number: 1

Perft 1: 29 (0 ms, inf leaves/sec, hash full: 0%)
Total time spent: 0 ms
Execution speed: inf leaves/second

29 moves on depth 1 for white:

16 pawn moves (including d4xe5)
5 knight moves
2 queen moves
5 bishop moves
1 king move
===
29 moves

Ok, thank you for your help so far. I think I'm starting to see where I'm going wrong. I think I have the wrong idea of what perft is suppose to look like. I based my perft function off of this example code from the chess programming wiki:

typedef unsigned long long u64;

Code: Select all

u64 Perft(int depth)
{
  MOVE move_list[256];
  int n_moves, i;
  u64 nodes = 0;

  if (depth == 0) 
    return 1ULL;

  n_moves = GenerateLegalMoves(move_list);
  for (i = 0; i < n_moves; i++) {
    MakeMove(move_list[i]);
    nodes += Perft(depth - 1);
    UndoMove(move_list[i]);
  }
  return nodes;
}

And what I did is just insert a chunk of code to count if a move is an attack move. If so, I add it to the total count. So my engine gives the following output, starting at depth=2 and going down to depth=1:

Move [From: e2 To: e4 MoveType: Quiet]: (nodes=30, captures=1, checks=1, checkmates=0)
Move [From: b2 To: b4 MoveType: Quiet]: (nodes=30, captures=2, checks=1, checkmates=0)
Move [From: a2 To: a4 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: g1 To: f3 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: c1 To: d2 MoveType: Quiet]: (nodes=31, captures=1, checks=0, checkmates=0)
Move [From: d1 To: d2 MoveType: Quiet]: (nodes=31, captures=1, checks=0, checkmates=0)
Move [From: g2 To: g3 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: c2 To: c3 MoveType: Quiet]: (nodes=31, captures=1, checks=0, checkmates=0)
Move [From: h2 To: h3 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: h2 To: h4 MoveType: Quiet]: (nodes=31, captures=2, checks=1, checkmates=0)
Move [From: b2 To: b3 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: c1 To: f4 MoveType: Quiet]: (nodes=32, captures=2, checks=1, checkmates=0)
Move [From: e1 To: d2 MoveType: Quiet]: (nodes=31, captures=1, checks=2, checkmates=0)
Move [From: a2 To: a3 MoveType: Quiet]: (nodes=31, captures=2, checks=1, checkmates=0)
Move [From: c1 To: h6 MoveType: Quiet]: (nodes=30, captures=3, checks=1, checkmates=0)
Move [From: c1 To: e3 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: d4 To: d5 MoveType: Quiet]: (nodes=29, captures=0, checks=1, checkmates=0)
Move [From: f2 To: f3 MoveType: Quiet]: (nodes=31, captures=1, checks=2, checkmates=0)
Move [From: e2 To: e3 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: b1 To: c3 MoveType: Quiet]: (nodes=31, captures=1, checks=0, checkmates=0)
Move [From: c2 To: c4 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: g1 To: h3 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: c1 To: g5 MoveType: Quiet]: (nodes=28, captures=2, checks=1, checkmates=0)
Move [From: d1 To: d3 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: d4 To: e5 MoveType: Attack]: (nodes=29, captures=0, checks=1, checkmates=0)
Move [From: g2 To: g4 MoveType: Quiet]: (nodes=31, captures=1, checks=1, checkmates=0)
Move [From: f2 To: f4 MoveType: Quiet]: (nodes=32, captures=2, checks=2, checkmates=0)
Move [From: b1 To: a3 MoveType: Quiet]: (nodes=31, captures=2, checks=1, checkmates=0)
Move [From: b1 To: d2 MoveType: Quiet]: (nodes=31, captures=1, checks=0, checkmates=0)
------------------------------
Nodes: 891
Captures: 37
Checks: 27
Checkmates: 0

But your engine seems to be starting at a depth of 1, and counting upward towards a maximum depth. Why is that? And if my engine starts at depth=2, includes d4xe5, and then counts every capture at depth=1, should it not be 37?

[mvanthoor]

But your engine seems to be starting at a depth of 1, and counting upward towards a maximum depth. Why is that?

No, my engine also counts downward, but it uses something called iterative deepening. If I want to run perft for depth 5, the engine does:

1
2, 1
3, 2, 1
4, 3, 2, 1
5, 4, 3, 2, 1

I could do the last line directly, but iterative deepening allows you to use a transposition table (TT). It works as follows:

You run the depth to 1, and the perft function stores all the node counts for each position depth 1 in the TT.
When you run depth 2, you calculate your node count for depth 2 and store them in the TT, and get the ones for depth 1 from the TT.
When you run depth 3, you calculate the nodes for depth 3, and store them, and get the ones for depth 2 and one from the TT.
When you run depth 4... I'm sure you get the picture.

1 - Nodes/positions are identified in the transposition table using a Zobrist hash which is kept incrementally as the position changes. When your perft works perfectly, and you add a TT and it DOESN'T work, you have bugs in either the zobrist hashing, or the TT implementation. This us a way to make sure the basics of your TT are working, before you extend it to use it in games.
2 - Perft does huge amounts of duplicate work, because many positions can be reached through different move sequences. These are called transpositions, and perft calculates the node counts for all of them. If you store a node and its node-count in the TT, and perft encounters the same position again, it doesn't have to calculate the node count anymore. It will know it directly from the TT. (That's why it's called a transposition table: it stores positions, independently of how you reached them, and thus it alleviates the calculation of transpositions that reach the same position.) This makes perft MUCH faster.

You can find perft.rs in my source code (link in the sig) to see how this works.

And if my engine starts at depth=2, includes d4xe5, and then counts every capture at depth=1, should it not be 37?

I don't understand this question... I'll have to think about it. If I figure out what you mean, I'll let you know.

[diegopaiva]

But your engine seems to be starting at a depth of 1, and counting upward towards a maximum depth. Why is that?

No, my engine also counts downward, but it uses something called iterative deepening. If I want to run perft for depth 5, the engine does:

1
2, 1
3, 2, 1
4, 3, 2, 1
5, 4, 3, 2, 1

I could do the last line directly, but iterative deepening allows you to use a transposition table (TT). It works as follows:

You run the depth to 1, and the perft function stores all the node counts for each position depth 1 in the TT.
When you run depth 2, you calculate your node count for depth 2 and store them in the TT, and get the ones for depth 1 from the TT.
When you run depth 3, you calculate the nodes for depth 3, and store them, and get the ones for depth 2 and one from the TT.
When you run depth 4... I'm sure you get the picture.

1 - Nodes/positions are identified in the transposition table using a Zobrist hash which is kept incrementally as the position changes. When your perft works perfectly, and you add a TT and it DOESN'T work, you have bugs in either the zobrist hashing, or the TT implementation. This us a way to make sure the basics of your TT are working, before you extend it to use it in games.
2 - Perft does huge amounts of duplicate work, because many positions can be reached through different move sequences. These are called transpositions, and perft calculates the node counts for all of them. If you store a node and its node-count in the TT, and perft encounters the same position again, it doesn't have to calculate the node count anymore. It will know it directly from the TT. (That's why it's called a transposition table: it stores positions, independently of how you reached them, and thus it alleviates the calculation of transpositions that reach the same position.) This makes perft MUCH faster.

You can find perft.rs in my source code (link in the sig) to see how this works.

And if my engine starts at depth=2, includes d4xe5, and then counts every capture at depth=1, should it not be 37?

I don't understand this question... I'll have to think about it. If I figure out what you mean, I'll let you know.

Hey, I am a novice chess programmer and I am struggling to optimize my move generator. I implemented magic bitboards and created a function to test whether a move is legal, instead of making and unmaking moves. However, my perft(6) on the starting position still runs is something like 10 seconds, which is upsetting me.

Regarding your item (2), I did not even think about this. You said it makes perft much faster. Could this be the reason why my perft(6), e.g., is not very fast? Of course there are a lot of implementation details I am not taking in account here, but is there any rough estimate on how much speedup a TT provides in that case?

[mvanthoor]

Regarding your item (2), I did not even think about this. You said it makes perft much faster. Could this be the reason why my perft(6), e.g., is not very fast? Of course there are a lot of implementation details I am not taking in account here, but is there any rough estimate on how much speedup a TT provides in that case?

Hi,

You don't need a TT to run perft(6) in a resonable time. In my case it takes a bit over 3 seconds without a TT. (With no special perft tricks such as bulk counting.)

First try to make your perft correct; compare against the perft results in the chess programming wiki. You can also create a function that runs through a perft testing suite. Rustic has one, and has a feature to compile the suite into the engine:

https://github.com/mvanthoor/rustic/blo ... ra/epds.rs

First, get perft to run right, then optimize.

But, off the bat... make/unmake (where unmake can also be done if a move turns out to be illegal) is much faster than copying the board, making a move, en then throwing the board away. Is your code online somewhere?