## Perft speed and depth questions

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
chrisw
Posts: 3851
Joined: Tue Apr 03, 2012 2:28 pm

### Re: Perft speed and depth questions

ajaxuk wrote:
Thu Jun 11, 2020 5:19 pm
Hi all

I have just started the long journey of programming a Chess engine in c++. I'm not a programmer although I have enough knowledge to wite ugly but working code!

After several days of frustration I think I have a working move generator plus makemove and unmake move,so I can check against the 6 positions on https://www.chessprogramming.org/Perft_Results. So far I have checked up to depths 7,6, 8,6, 5 and 6 respectively with no errors. Can I reasonably assume that most if not all edge cases will have been covered by these depths?

The next is on the topic of speed and whether what I have written so far will be reasonably quick enough to not be the limiting factor later on for thhe rest of the engine. I have done some reading on the subject and my perft function is the most basic flavour with no bulk_counting, hashing or any other tweaks. Perft function below:

Code: Select all

``````uint64		Board::Perft(int depth)
{
MoveList moves;
int nMoves, i;
uint64 nodes = 0;

if (depth == 0) return 1;

nMoves = genMoves(moves);

for (i = 0; i < nMoves; i++)
{
if (makeMove(moves.move[i]))
{
nodes += Perft(depth - 1);
undoMove(moves.move[i]);
}
else
{
if (depth==1) nodes += 1;
}
}
return nodes;
}``````

running on my PC (i7-6850 3.6Ghz) for x86 in Visual Studio I can get Position 1 at depth 7 completed in 228 seconds or 14 million nodes per second.

I can't recall where, but I think I read that the top engines are generating in the region of 200 million nodes per second.

It's a very subjective question but is 14 million a reasonable starting point to continue developing the rest of the engine?

Thanks for any pointers in the right directions
Plenty of PERFT suites here:

https://github.com/ChrisWhittington/Chess-EPDs

mvanthoor
Posts: 586
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

### Re: Perft speed and depth questions

alessandro wrote:
Thu Jun 18, 2020 6:47 am
As already pointed out, the first thing is ensure a correct implementation. Optimization and anything else comes after it. What will you implements is related to your final goal.
I love it when people write chess engines in another language that isn't C or C++. Ada was one of the languages I considered when I was looking for a language for Rustic. As "Ada" is named after "Ada Lovelace", I considered "Lovely" as a name for the engine, had I written it in Ada

The one thing I'm curious about... Ada seems to be in development for quite some time now. It's speed is also fast enough (expectation is that it would run at around 23 million leaves/second on my CPU in perft), and it has some advanced functions. However, on the CCRL 40/15 and 40/2 lists, versions 3.4 and 3.6 are 1685 and 1954. An engine such as VICE has a rating of over 2000, even though it's not really advanced. Basically, it implements, alpha/beta, quiescence search, a transposition table, and killer moves. Evaluation is only PSQT and material count, and nothing more, if I remember correctly. Also, VICE is not particularly fast or optimized. Therefore I'd expect that any engine implementing similar functions that is as fast or faster, to be at least 2000 ELO.

Is AdaChess experimental? What I mean is: are you implementing "non-standard" features/your own idea's, or implementing standard features in a different way, to see if they work, or work better?

mvanthoor
Posts: 586
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

### Re: Perft speed and depth questions

PS: This is perftsuite.epd (converted to a Rust array), with some additions I found around these forums. I have a function that runs perft through this array, position by position, and it quits as soon as a number doesn't match.

Code: Select all

``````// This is the table with all the tests from perftsuite.epd.
pub const LARGE_PERFT_SUITE: [&str; 172] = [
"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 ;D1 20 ;D2 400 ;D3 8902 ;D4 197281 ;D5 4865609 ;D6 119060324",
"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR b KQkq - 0 1 ;D1 20 ;D2 400 ;D3 8902 ;D4 197281 ;D5 4865609 ;D6 119060324",
"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 ;D1 48 ;D2 2039 ;D3 97862 ;D4 4085603 ;D5 193690690 ;D6 8031647685",
"8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1 ;D1 14 ;D2 191 ;D3 2812 ;D4 43238 ;D5 674624 ;D6 11030083",
"r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1 ;D1 6 ;D2 264 ;D3 9467 ;D4 422333 ;D5 15833292 ;D6 706045033",
"r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10 ;D1 46 ;D2 2079 ;D3 89890 ;D4 3894594 ;D5 164075551 ;D6 6923051137",
"4k3/8/8/8/8/8/8/4K2R w K - 0 1 ;D1 15 ;D2 66 ;D3 1197 ;D4 7059 ;D5 133987 ;D6 764643",
"4k3/8/8/8/8/8/8/R3K3 w Q - 0 1 ;D1 16 ;D2 71 ;D3 1287 ;D4 7626 ;D5 145232 ;D6 846648",
"4k2r/8/8/8/8/8/8/4K3 w k - 0 1 ;D1 5 ;D2 75 ;D3 459 ;D4 8290 ;D5 47635 ;D6 899442",
"r3k3/8/8/8/8/8/8/4K3 w q - 0 1 ;D1 5 ;D2 80 ;D3 493 ;D4 8897 ;D5 52710 ;D6 1001523",
"4k3/8/8/8/8/8/8/R3K2R w KQ - 0 1 ;D1 26 ;D2 112 ;D3 3189 ;D4 17945 ;D5 532933 ;D6 2788982",
"r3k2r/8/8/8/8/8/8/4K3 w kq - 0 1 ;D1 5 ;D2 130 ;D3 782 ;D4 22180 ;D5 118882 ;D6 3517770",
"8/8/8/8/8/8/6k1/4K2R w K - 0 1 ;D1 12 ;D2 38 ;D3 564 ;D4 2219 ;D5 37735 ;D6 185867",
"8/8/8/8/8/8/1k6/R3K3 w Q - 0 1 ;D1 15 ;D2 65 ;D3 1018 ;D4 4573 ;D5 80619 ;D6 413018",
"4k2r/6K1/8/8/8/8/8/8 w k - 0 1 ;D1 3 ;D2 32 ;D3 134 ;D4 2073 ;D5 10485 ;D6 179869",
"r3k3/1K6/8/8/8/8/8/8 w q - 0 1 ;D1 4 ;D2 49 ;D3 243 ;D4 3991 ;D5 20780 ;D6 367724",
"r3k2r/8/8/8/8/8/8/R3K2R w KQkq - 0 1 ;D1 26 ;D2 568 ;D3 13744 ;D4 314346 ;D5 7594526 ;D6 179862938",
"r3k2r/8/8/8/8/8/8/1R2K2R w Kkq - 0 1 ;D1 25 ;D2 567 ;D3 14095 ;D4 328965 ;D5 8153719 ;D6 195629489",
"r3k2r/8/8/8/8/8/8/2R1K2R w Kkq - 0 1 ;D1 25 ;D2 548 ;D3 13502 ;D4 312835 ;D5 7736373 ;D6 184411439",
"r3k2r/8/8/8/8/8/8/R3K1R1 w Qkq - 0 1 ;D1 25 ;D2 547 ;D3 13579 ;D4 316214 ;D5 7878456 ;D6 189224276",
"1r2k2r/8/8/8/8/8/8/R3K2R w KQk - 0 1 ;D1 26 ;D2 583 ;D3 14252 ;D4 334705 ;D5 8198901 ;D6 198328929",
"2r1k2r/8/8/8/8/8/8/R3K2R w KQk - 0 1 ;D1 25 ;D2 560 ;D3 13592 ;D4 317324 ;D5 7710115 ;D6 185959088",
"r3k1r1/8/8/8/8/8/8/R3K2R w KQq - 0 1 ;D1 25 ;D2 560 ;D3 13607 ;D4 320792 ;D5 7848606 ;D6 190755813",
"4k3/8/8/8/8/8/8/4K2R b K - 0 1 ;D1 5 ;D2 75 ;D3 459 ;D4 8290 ;D5 47635 ;D6 899442",
"4k3/8/8/8/8/8/8/R3K3 b Q - 0 1 ;D1 5 ;D2 80 ;D3 493 ;D4 8897 ;D5 52710 ;D6 1001523",
"4k2r/8/8/8/8/8/8/4K3 b k - 0 1 ;D1 15 ;D2 66 ;D3 1197 ;D4 7059 ;D5 133987 ;D6 764643",
"r3k3/8/8/8/8/8/8/4K3 b q - 0 1 ;D1 16 ;D2 71 ;D3 1287 ;D4 7626 ;D5 145232 ;D6 846648",
"4k3/8/8/8/8/8/8/R3K2R b KQ - 0 1 ;D1 5 ;D2 130 ;D3 782 ;D4 22180 ;D5 118882 ;D6 3517770",
"r3k2r/8/8/8/8/8/8/4K3 b kq - 0 1 ;D1 26 ;D2 112 ;D3 3189 ;D4 17945 ;D5 532933 ;D6 2788982",
"8/8/8/8/8/8/6k1/4K2R b K - 0 1 ;D1 3 ;D2 32 ;D3 134 ;D4 2073 ;D5 10485 ;D6 179869",
"8/8/8/8/8/8/1k6/R3K3 b Q - 0 1 ;D1 4 ;D2 49 ;D3 243 ;D4 3991 ;D5 20780 ;D6 367724",
"4k2r/6K1/8/8/8/8/8/8 b k - 0 1 ;D1 12 ;D2 38 ;D3 564 ;D4 2219 ;D5 37735 ;D6 185867",
"r3k3/1K6/8/8/8/8/8/8 b q - 0 1 ;D1 15 ;D2 65 ;D3 1018 ;D4 4573 ;D5 80619 ;D6 413018",
"r3k2r/8/8/8/8/8/8/R3K2R b KQkq - 0 1 ;D1 26 ;D2 568 ;D3 13744 ;D4 314346 ;D5 7594526 ;D6 179862938",
"r3k2r/8/8/8/8/8/8/1R2K2R b Kkq - 0 1 ;D1 26 ;D2 583 ;D3 14252 ;D4 334705 ;D5 8198901 ;D6 198328929",
"r3k2r/8/8/8/8/8/8/2R1K2R b Kkq - 0 1 ;D1 25 ;D2 560 ;D3 13592 ;D4 317324 ;D5 7710115 ;D6 185959088",
"r3k2r/8/8/8/8/8/8/R3K1R1 b Qkq - 0 1 ;D1 25 ;D2 560 ;D3 13607 ;D4 320792 ;D5 7848606 ;D6 190755813",
"1r2k2r/8/8/8/8/8/8/R3K2R b KQk - 0 1 ;D1 25 ;D2 567 ;D3 14095 ;D4 328965 ;D5 8153719 ;D6 195629489",
"2r1k2r/8/8/8/8/8/8/R3K2R b KQk - 0 1 ;D1 25 ;D2 548 ;D3 13502 ;D4 312835 ;D5 7736373 ;D6 184411439",
"r3k1r1/8/8/8/8/8/8/R3K2R b KQq - 0 1 ;D1 25 ;D2 547 ;D3 13579 ;D4 316214 ;D5 7878456 ;D6 189224276",
"8/1n4N1/2k5/8/8/5K2/1N4n1/8 w - - 0 1 ;D1 14 ;D2 195 ;D3 2760 ;D4 38675 ;D5 570726 ;D6 8107539",
"8/1k6/8/5N2/8/4n3/8/2K5 w - - 0 1 ;D1 11 ;D2 156 ;D3 1636 ;D4 20534 ;D5 223507 ;D6 2594412",
"8/8/4k3/3Nn3/3nN3/4K3/8/8 w - - 0 1 ;D1 19 ;D2 289 ;D3 4442 ;D4 73584 ;D5 1198299 ;D6 19870403",
"K7/8/2n5/1n6/8/8/8/k6N w - - 0 1 ;D1 3 ;D2 51 ;D3 345 ;D4 5301 ;D5 38348 ;D6 588695",
"k7/8/2N5/1N6/8/8/8/K6n w - - 0 1 ;D1 17 ;D2 54 ;D3 835 ;D4 5910 ;D5 92250 ;D6 688780",
"8/1n4N1/2k5/8/8/5K2/1N4n1/8 b - - 0 1 ;D1 15 ;D2 193 ;D3 2816 ;D4 40039 ;D5 582642 ;D6 8503277",
"8/1k6/8/5N2/8/4n3/8/2K5 b - - 0 1 ;D1 16 ;D2 180 ;D3 2290 ;D4 24640 ;D5 288141 ;D6 3147566",
"8/8/3K4/3Nn3/3nN3/4k3/8/8 b - - 0 1 ;D1 4 ;D2 68 ;D3 1118 ;D4 16199 ;D5 281190 ;D6 4405103",
"K7/8/2n5/1n6/8/8/8/k6N b - - 0 1 ;D1 17 ;D2 54 ;D3 835 ;D4 5910 ;D5 92250 ;D6 688780",
"k7/8/2N5/1N6/8/8/8/K6n b - - 0 1 ;D1 3 ;D2 51 ;D3 345 ;D4 5301 ;D5 38348 ;D6 588695",
"B6b/8/8/8/2K5/4k3/8/b6B w - - 0 1 ;D1 17 ;D2 278 ;D3 4607 ;D4 76778 ;D5 1320507 ;D6 22823890",
"8/8/1B6/7b/7k/8/2B1b3/7K w - - 0 1 ;D1 21 ;D2 316 ;D3 5744 ;D4 93338 ;D5 1713368 ;D6 28861171",
"k7/B7/1B6/1B6/8/8/8/K6b w - - 0 1 ;D1 21 ;D2 144 ;D3 3242 ;D4 32955 ;D5 787524 ;D6 7881673",
"K7/b7/1b6/1b6/8/8/8/k6B w - - 0 1 ;D1 7 ;D2 143 ;D3 1416 ;D4 31787 ;D5 310862 ;D6 7382896",
"B6b/8/8/8/2K5/5k2/8/b6B b - - 0 1 ;D1 6 ;D2 106 ;D3 1829 ;D4 31151 ;D5 530585 ;D6 9250746",
"8/8/1B6/7b/7k/8/2B1b3/7K b - - 0 1 ;D1 17 ;D2 309 ;D3 5133 ;D4 93603 ;D5 1591064 ;D6 29027891",
"k7/B7/1B6/1B6/8/8/8/K6b b - - 0 1 ;D1 7 ;D2 143 ;D3 1416 ;D4 31787 ;D5 310862 ;D6 7382896",
"K7/b7/1b6/1b6/8/8/8/k6B b - - 0 1 ;D1 21 ;D2 144 ;D3 3242 ;D4 32955 ;D5 787524 ;D6 7881673",
"7k/RR6/8/8/8/8/rr6/7K w - - 0 1 ;D1 19 ;D2 275 ;D3 5300 ;D4 104342 ;D5 2161211 ;D6 44956585",
"R6r/8/8/2K5/5k2/8/8/r6R w - - 0 1 ;D1 36 ;D2 1027 ;D3 29215 ;D4 771461 ;D5 20506480 ;D6 525169084",
"7k/RR6/8/8/8/8/rr6/7K b - - 0 1 ;D1 19 ;D2 275 ;D3 5300 ;D4 104342 ;D5 2161211 ;D6 44956585",
"R6r/8/8/2K5/5k2/8/8/r6R b - - 0 1 ;D1 36 ;D2 1027 ;D3 29227 ;D4 771368 ;D5 20521342 ;D6 524966748",
"6kq/8/8/8/8/8/8/7K w - - 0 1 ;D1 2 ;D2 36 ;D3 143 ;D4 3637 ;D5 14893 ;D6 391507",
"6KQ/8/8/8/8/8/8/7k b - - 0 1 ;D1 2 ;D2 36 ;D3 143 ;D4 3637 ;D5 14893 ;D6 391507",
"K7/8/8/3Q4/4q3/8/8/7k w - - 0 1 ;D1 6 ;D2 35 ;D3 495 ;D4 8349 ;D5 166741 ;D6 3370175",
"6qk/8/8/8/8/8/8/7K b - - 0 1 ;D1 22 ;D2 43 ;D3 1015 ;D4 4167 ;D5 105749 ;D6 419369",
"6KQ/8/8/8/8/8/8/7k b - - 0 1 ;D1 2 ;D2 36 ;D3 143 ;D4 3637 ;D5 14893 ;D6 391507",
"K7/8/8/3Q4/4q3/8/8/7k b - - 0 1 ;D1 6 ;D2 35 ;D3 495 ;D4 8349 ;D5 166741 ;D6 3370175",
"8/8/8/8/8/K7/P7/k7 w - - 0 1 ;D1 3 ;D2 7 ;D3 43 ;D4 199 ;D5 1347 ;D6 6249",
"8/8/8/8/8/7K/7P/7k w - - 0 1 ;D1 3 ;D2 7 ;D3 43 ;D4 199 ;D5 1347 ;D6 6249",
"K7/p7/k7/8/8/8/8/8 w - - 0 1 ;D1 1 ;D2 3 ;D3 12 ;D4 80 ;D5 342 ;D6 2343",
"7K/7p/7k/8/8/8/8/8 w - - 0 1 ;D1 1 ;D2 3 ;D3 12 ;D4 80 ;D5 342 ;D6 2343",
"8/2k1p3/3pP3/3P2K1/8/8/8/8 w - - 0 1 ;D1 7 ;D2 35 ;D3 210 ;D4 1091 ;D5 7028 ;D6 34834",
"8/8/8/8/8/K7/P7/k7 b - - 0 1 ;D1 1 ;D2 3 ;D3 12 ;D4 80 ;D5 342 ;D6 2343",
"8/8/8/8/8/7K/7P/7k b - - 0 1 ;D1 1 ;D2 3 ;D3 12 ;D4 80 ;D5 342 ;D6 2343",
"K7/p7/k7/8/8/8/8/8 b - - 0 1 ;D1 3 ;D2 7 ;D3 43 ;D4 199 ;D5 1347 ;D6 6249",
"7K/7p/7k/8/8/8/8/8 b - - 0 1 ;D1 3 ;D2 7 ;D3 43 ;D4 199 ;D5 1347 ;D6 6249",
"8/2k1p3/3pP3/3P2K1/8/8/8/8 b - - 0 1 ;D1 5 ;D2 35 ;D3 182 ;D4 1091 ;D5 5408 ;D6 34822",
"8/8/8/8/8/4k3/4P3/4K3 w - - 0 1 ;D1 2 ;D2 8 ;D3 44 ;D4 282 ;D5 1814 ;D6 11848",
"4k3/4p3/4K3/8/8/8/8/8 b - - 0 1 ;D1 2 ;D2 8 ;D3 44 ;D4 282 ;D5 1814 ;D6 11848",
"8/8/7k/7p/7P/7K/8/8 w - - 0 1 ;D1 3 ;D2 9 ;D3 57 ;D4 360 ;D5 1969 ;D6 10724",
"8/8/k7/p7/P7/K7/8/8 w - - 0 1 ;D1 3 ;D2 9 ;D3 57 ;D4 360 ;D5 1969 ;D6 10724",
"8/8/3k4/3p4/3P4/3K4/8/8 w - - 0 1 ;D1 5 ;D2 25 ;D3 180 ;D4 1294 ;D5 8296 ;D6 53138",
"8/3k4/3p4/8/3P4/3K4/8/8 w - - 0 1 ;D1 8 ;D2 61 ;D3 483 ;D4 3213 ;D5 23599 ;D6 157093",
"8/8/3k4/3p4/8/3P4/3K4/8 w - - 0 1 ;D1 8 ;D2 61 ;D3 411 ;D4 3213 ;D5 21637 ;D6 158065",
"k7/8/3p4/8/3P4/8/8/7K w - - 0 1 ;D1 4 ;D2 15 ;D3 90 ;D4 534 ;D5 3450 ;D6 20960",
"8/8/7k/7p/7P/7K/8/8 b - - 0 1 ;D1 3 ;D2 9 ;D3 57 ;D4 360 ;D5 1969 ;D6 10724",
"8/8/k7/p7/P7/K7/8/8 b - - 0 1 ;D1 3 ;D2 9 ;D3 57 ;D4 360 ;D5 1969 ;D6 10724",
"8/8/3k4/3p4/3P4/3K4/8/8 b - - 0 1 ;D1 5 ;D2 25 ;D3 180 ;D4 1294 ;D5 8296 ;D6 53138",
"8/3k4/3p4/8/3P4/3K4/8/8 b - - 0 1 ;D1 8 ;D2 61 ;D3 411 ;D4 3213 ;D5 21637 ;D6 158065",
"8/8/3k4/3p4/8/3P4/3K4/8 b - - 0 1 ;D1 8 ;D2 61 ;D3 483 ;D4 3213 ;D5 23599 ;D6 157093",
"k7/8/3p4/8/3P4/8/8/7K b - - 0 1 ;D1 4 ;D2 15 ;D3 89 ;D4 537 ;D5 3309 ;D6 21104",
"7k/3p4/8/8/3P4/8/8/K7 w - - 0 1 ;D1 4 ;D2 19 ;D3 117 ;D4 720 ;D5 4661 ;D6 32191",
"7k/8/8/3p4/8/8/3P4/K7 w - - 0 1 ;D1 5 ;D2 19 ;D3 116 ;D4 716 ;D5 4786 ;D6 30980",
"k7/8/8/7p/6P1/8/8/K7 w - - 0 1 ;D1 5 ;D2 22 ;D3 139 ;D4 877 ;D5 6112 ;D6 41874",
"k7/8/7p/8/8/6P1/8/K7 w - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4354 ;D6 29679",
"k7/8/8/6p1/7P/8/8/K7 w - - 0 1 ;D1 5 ;D2 22 ;D3 139 ;D4 877 ;D5 6112 ;D6 41874",
"k7/8/6p1/8/8/7P/8/K7 w - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4354 ;D6 29679",
"k7/8/8/3p4/4p3/8/8/7K w - - 0 1 ;D1 3 ;D2 15 ;D3 84 ;D4 573 ;D5 3013 ;D6 22886",
"k7/8/3p4/8/8/4P3/8/7K w - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4271 ;D6 28662",
"7k/3p4/8/8/3P4/8/8/K7 b - - 0 1 ;D1 5 ;D2 19 ;D3 117 ;D4 720 ;D5 5014 ;D6 32167",
"7k/8/8/3p4/8/8/3P4/K7 b - - 0 1 ;D1 4 ;D2 19 ;D3 117 ;D4 712 ;D5 4658 ;D6 30749",
"k7/8/8/7p/6P1/8/8/K7 b - - 0 1 ;D1 5 ;D2 22 ;D3 139 ;D4 877 ;D5 6112 ;D6 41874",
"k7/8/7p/8/8/6P1/8/K7 b - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4354 ;D6 29679",
"k7/8/8/6p1/7P/8/8/K7 b - - 0 1 ;D1 5 ;D2 22 ;D3 139 ;D4 877 ;D5 6112 ;D6 41874",
"k7/8/6p1/8/8/7P/8/K7 b - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4354 ;D6 29679",
"k7/8/8/3p4/4p3/8/8/7K b - - 0 1 ;D1 5 ;D2 15 ;D3 102 ;D4 569 ;D5 4337 ;D6 22579",
"k7/8/3p4/8/8/4P3/8/7K b - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4271 ;D6 28662",
"7k/8/8/p7/1P6/8/8/7K w - - 0 1 ;D1 5 ;D2 22 ;D3 139 ;D4 877 ;D5 6112 ;D6 41874",
"7k/8/8/p7/1P6/8/8/7K b - - 0 1 ;D1 5 ;D2 22 ;D3 139 ;D4 877 ;D5 6112 ;D6 41874",
"7k/8/8/1p6/P7/8/8/7K w - - 0 1 ;D1 5 ;D2 22 ;D3 139 ;D4 877 ;D5 6112 ;D6 41874",
"7k/8/8/1p6/P7/8/8/7K b - - 0 1 ;D1 5 ;D2 22 ;D3 139 ;D4 877 ;D5 6112 ;D6 41874",
"7k/8/p7/8/8/1P6/8/7K w - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4354 ;D6 29679",
"7k/8/p7/8/8/1P6/8/7K b - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4354 ;D6 29679",
"7k/8/1p6/8/8/P7/8/7K w - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4354 ;D6 29679",
"7k/8/1p6/8/8/P7/8/7K b - - 0 1 ;D1 4 ;D2 16 ;D3 101 ;D4 637 ;D5 4354 ;D6 29679",
"k7/7p/8/8/8/8/6P1/K7 w - - 0 1 ;D1 5 ;D2 25 ;D3 161 ;D4 1035 ;D5 7574 ;D6 55338",
"k7/7p/8/8/8/8/6P1/K7 b - - 0 1 ;D1 5 ;D2 25 ;D3 161 ;D4 1035 ;D5 7574 ;D6 55338",
"k7/6p1/8/8/8/8/7P/K7 w - - 0 1 ;D1 5 ;D2 25 ;D3 161 ;D4 1035 ;D5 7574 ;D6 55338",
"k7/6p1/8/8/8/8/7P/K7 b - - 0 1 ;D1 5 ;D2 25 ;D3 161 ;D4 1035 ;D5 7574 ;D6 55338",
"8/Pk6/8/8/8/8/6Kp/8 w - - 0 1 ;D1 11 ;D2 97 ;D3 887 ;D4 8048 ;D5 90606 ;D6 1030499",
"8/Pk6/8/8/8/8/6Kp/8 b - - 0 1 ;D1 11 ;D2 97 ;D3 887 ;D4 8048 ;D5 90606 ;D6 1030499",
"3k4/3pp3/8/8/8/8/3PP3/3K4 w - - 0 1 ;D1 7 ;D2 49 ;D3 378 ;D4 2902 ;D5 24122 ;D6 199002",
"3k4/3pp3/8/8/8/8/3PP3/3K4 b - - 0 1 ;D1 7 ;D2 49 ;D3 378 ;D4 2902 ;D5 24122 ;D6 199002",
"8/PPPk4/8/8/8/8/4Kppp/8 w - - 0 1 ;D1 18 ;D2 270 ;D3 4699 ;D4 79355 ;D5 1533145 ;D6 28859283",
"8/PPPk4/8/8/8/8/4Kppp/8 b - - 0 1 ;D1 18 ;D2 270 ;D3 4699 ;D4 79355 ;D5 1533145 ;D6 28859283",
"n1n5/1Pk5/8/8/8/8/5Kp1/5N1N w - - 0 1 ;D1 24 ;D2 421 ;D3 7421 ;D4 124608 ;D5 2193768 ;D6 37665329",
"n1n5/1Pk5/8/8/8/8/5Kp1/5N1N b - - 0 1 ;D1 24 ;D2 421 ;D3 7421 ;D4 124608 ;D5 2193768 ;D6 37665329",
"n1n5/PPPk4/8/8/8/8/4Kppp/5N1N w - - 0 1 ;D1 24 ;D2 496 ;D3 9483 ;D4 182838 ;D5 3605103 ;D6 71179139",
"n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - - 0 1 ;D1 24 ;D2 496 ;D3 9483 ;D4 182838 ;D5 3605103 ;D6 71179139",

// Specials
"3k4/3p4/8/K1P4r/8/8/8/8 b - - 0 1 ;D6 1134888",
"r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1 ;D4 1274206",
"8/8/8/8/k1p4R/8/3P4/3K4 w - - 0 1 ;D6 1134888",
"8/8/1k6/2b5/2pP4/8/5K2/8 b - d3 0 1 ;D6 1440467",
"8/5k2/8/2Pp4/2B5/1K6/8/8 w - d6 0 1 ;D6 1440467",
"8/8/4k3/8/2p5/8/B2P2K1/8 w - - 0 1 ;D6 1015133",
"8/b2p2k1/8/2P5/8/4K3/8/8 b - - 0 1 ;D6 1015133",
"5k2/8/8/8/8/8/8/4K2R w K - 0 1 ;D6 661072",
"4k2r/8/8/8/8/8/8/5K2 b k - 0 1 ;D6 661072",
"3k4/8/8/8/8/8/8/R3K3 w Q - 0 1 ;D6 803711",
"r3k3/8/8/8/8/8/8/3K4 b q - 0 1 ;D6 803711",

// en passant capture checks opponent
"8/8/1k6/2b5/2pP4/8/5K2/8 b - d3 0 1 ;D6 1440467",
"8/5k2/8/2Pp4/2B5/1K6/8/8 w - d6 0 1 ;D6 1440467",

// avoid illegal ep(thanks to Steve Maughan)
"3k4/3p4/8/K1P4r/8/8/8/8 b - - 0 1 ;D6 1134888",
"8/8/8/8/k1p4R/8/3P4/3K4 w - - 0 1 ;D6 1134888",

// avoid illegal ep #2
"8/8/4k3/8/2p5/8/B2P2K1/8 w - - 0 1 ;D6 1015133",
"8/b2p2k1/8/2P5/8/4K3/8/8 b - - 0 1 ;D6 1015133",

// short castling gives check
"5k2/8/8/8/8/8/8/4K2R w K - 0 1 ;D6 661072",
"4k2r/8/8/8/8/8/8/5K2 b k - 0 1 ;D6 661072",

// long castling gives check
"3k4/8/8/8/8/8/8/R3K3 w Q - 0 1 ;D6 803711",
"r3k3/8/8/8/8/8/8/3K4 b q - 0 1 ;D6 803711",

// castling(including losing cr due to rook capture)
"r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1 ;D4 1274206",
"r3k2r/7b/8/8/8/8/1B4BQ/R3K2R b KQkq - 0 1 ;D4 1274206",

// castling prevented
"r3k2r/8/3Q4/8/8/5q2/8/R3K2R b KQkq - 0 1 ;D4 1720476",
"r3k2r/8/5Q2/8/8/3q4/8/R3K2R w KQkq - 0 1 ;D4 1720476",
//  promote out of check
"2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1 ;D6 3821001",
"3K4/8/8/8/8/8/4p3/2k2R2 b - - 0 1 ;D6 3821001",

// "# discovered check
"8/8/1P2K3/8/2n5/1q6/8/5k2 b - - 0 1 ;D5 1004658",
"5K2/8/1Q6/2N5/8/1p2k3/8/8 w - - 0 1 ;D5 1004658",

// "# promote to give check
"4k3/1P6/8/8/8/8/K7/8 w - - 0 1 ;D6 217342",
"8/k7/8/8/8/8/1p6/4K3 b - - 0 1 ;D6 217342",

// "# underpromote to check
"8/P1k5/K7/8/8/8/8/8 w - - 0 1 ;D6 92683",
"8/8/8/8/8/k7/p1K5/8 b - - 0 1 ;D6 92683",

// "# self stalemate
"K1k5/8/P7/8/8/8/8/8 w - - 0 1 ;D6 2217",
"8/8/8/8/8/p7/8/k1K5 b - - 0 1 ;D6 2217",

// stalemate/checkmate:
"8/k1P5/8/1K6/8/8/8/8 w - - 0 1 ;D7 567584",
"8/8/8/8/1k6/8/K1p5/8 b - - 0 1 ;D7 567584",

// double check
"8/8/2k5/5q2/5n2/8/5K2/8 b - - 0 1 ;D4 23527",

// short castling impossible although the rook never moved away from its corner
"1k6/1b6/8/8/7R/8/8/4K2R b K - 0 1 ;D5 1063513",
"4k2r/8/8/7r/8/8/1B6/1K6 w k - 0 1 ;D5 1063513",

// long castling impossible although the rook never moved away from its corner
"1k6/8/8/8/R7/1n6/8/R3K3 b Q - 0 1 ;D5 346695",
"r3k3/8/1N6/r7/8/8/8/1K6 w q - 0 1 ;D5 346695",
];
``````

ajaxuk
Posts: 13
Joined: Tue Jun 09, 2020 4:44 pm
Full name: Mark Buisseret

### Re: Perft speed and depth questions

I think I am comfortable with the legality of my supposedly 100% legal move generator (famous last words) I also have implemnted Zobrist hashing and a very rudimentary hash table.

Alas, I cannot get the correct answer for the initial positon and depth 5 onwards while implementing a perftHash function. Could someone cast a glance over it and see if anything wrong is glaringly obvious...

Code: Select all

``````uint64		Board::PerftHash(int depth)
{
MoveList moves;
int nMoves, i;
uint64 nodes = 0, _leaves = 0;

if (depth == 0) return 1;
else
{
if (pHsh.find(zob.getKEY(), depth, _leaves))
return _leaves;
nMoves = genMoves(moves);
}

for (i = 0; i < nMoves; i++)
{
makeMove(moves.move[i]);
nodes += PerftHash(depth - 1);
undoMove(moves.move[i]);
}
pHsh.insert(zob.getKEY(), depth, nodes);

return nodes;
}
``````
The hash table size is 2^20 and at depth 5 the performance of the table is as follows:
Writes: 96933
Hits: 60708
Misses: 96933
Collisions: 5344

The answer returned is 4,865,606 instead of 4,865,609...

I don't really understand why there are so many collisions, if I increase the size from 2^20 to 16*2^20 then collisions reduce to around 300 but the anwer doesn't change.

My PHash class:

Code: Select all

``````	PHash(size_t size):
_size(size),_hits(0),_misses(0),_writes(0),_collisions(0)
{
table = (Record *)calloc(size, sizeof(Record));
}

struct Record
{
uint64 key;
int depth;
uint64 perft;
};

``````
and the main methods find and insert are as follows:

Code: Select all

``````	void PHash::insert(const uint64 &key, int depth, uint64 perft)
{
_writes++;
Record &r = table[key & _size-1];			// HGM
if (r.key != 0 && r.key != key)
{
_collisions++;
}
r.key = key;
r.depth = depth;
r.perft = perft;

}

bool PHash::find(const uint64 &key, int &depth, uint64 &perft)
{
Record &r = table[key & _size - 1];
if (r.key == key && r.depth==depth)
{
_hits++;
perft = r.perft;
return true;
}
else
{
_misses++;
return false;
}
}
``````

As I mentioned, it's very simple.

odomobo
Posts: 79
Joined: Thu Jul 05, 2018 11:09 pm
Location: Chicago, IL
Full name: Josh Odom

### Re: Perft speed and depth questions

The code seems fine to me. If you change the find function to just return false (which should effectively disable hashing), do you still get the wrong value? If you get the right value, then I think your hash function must be missing a parameter, for example, en passant or castling rights.

The number of collisions seems in the right ballpark to me. By the end, the table has about 90% occupancy, so 10% of inserts at that time should be collisions.

ajaxuk
Posts: 13
Joined: Tue Jun 09, 2020 4:44 pm
Full name: Mark Buisseret

### Re: Perft speed and depth questions

odomobo wrote:
Thu Jun 18, 2020 5:40 pm
The code seems fine to me. If you change the find function to just return false (which should effectively disable hashing), do you still get the wrong value? If you get the right value, then I think your hash function must be missing a parameter, for example, en passant or castling rights.

The number of collisions seems in the right ballpark to me. By the end, the table has about 90% occupancy, so 10% of inserts at that time should be collisions.
Thanks odomobo, i did as you suggested and the correct answer is returned. I will go over the hashing function again!

ajaxuk
Posts: 13
Joined: Tue Jun 09, 2020 4:44 pm
Full name: Mark Buisseret

### Re: Perft speed and depth questions

ajaxuk wrote:
Thu Jun 18, 2020 5:59 pm
odomobo wrote:
Thu Jun 18, 2020 5:40 pm
The code seems fine to me. If you change the find function to just return false (which should effectively disable hashing), do you still get the wrong value? If you get the right value, then I think your hash function must be missing a parameter, for example, en passant or castling rights.

The number of collisions seems in the right ballpark to me. By the end, the table has about 90% occupancy, so 10% of inserts at that time should be collisions.
Thanks odomobo, i did as you suggested and the correct answer is returned. I will go over the hashing function again!
...found it qquickly after you pointed me in the right direction. For some reason I only initialised the first 4 en passant keys in my loop instead of 8...

It now works Thank you!

mvanthoor
Posts: 586
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

### Re: Perft speed and depth questions

Keep checking that zobrist key anytime you change anything in that function. It's very finicky.

If you found my earlier topic about hashing, look into the following:

- buckets (multiple spots at the same hash index)
- the amount of data that can be retrieved with one memory read (64 bytes, if I remember correctly). If a memory read needs to hit the memory twice, the hash table is slower. In short, all the buckets at one index need to fit within 64 bytes. If they don't, memory alignment causes the CPU to fetch a bucket in 2 steps, which is obviously slower.

Both things are discussed in that topic.

How much speedup did the hash table bring in your case?

Perft is great to also test if zobrist and the hash table are working correctly

bob
Posts: 20922
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

### Re: Perft speed and depth questions

minor addition... each "bucket needs to have the low order 6 bits of the address as 000000, which makes each bucket lie on an address that starts a 64 bit block of memory that gets read in in one cache fill cycle. If it spans a 64 bit address break, it will take two cache fill cycles which is bad for speed and also kicks out an extra cache entry that might be useful.

ajaxuk
Posts: 13
Joined: Tue Jun 09, 2020 4:44 pm
Full name: Mark Buisseret

### Re: Perft speed and depth questions

mvanthoor wrote:
Thu Jun 18, 2020 8:19 pm
Keep checking that zobrist key anytime you change anything in that function. It's very finicky.

If you found my earlier topic about hashing, look into the following:

- buckets (multiple spots at the same hash index)
- the amount of data that can be retrieved with one memory read (64 bytes, if I remember correctly). If a memory read needs to hit the memory twice, the hash table is slower. In short, all the buckets at one index need to fit within 64 bytes. If they don't, memory alignment causes the CPU to fetch a bucket in 2 steps, which is obviously slower.

Both things are discussed in that topic.

How much speedup did the hash table bring in your case?

Perft is great to also test if zobrist and the hash table are working correctly
Well, its a basic implementation of hash tables and no buckets as of yet. Also, I am a little surprised at how much slower everything is running now I have included incremental hashing of posiitons.

Relative times in seconds are below for Perft(7) of initial posiion run on my laptop (bit of a coach potatoe..)

Vanila Perft = 235 seconds
Perft + Bulk Counting = 94 seconds
Perft + Hash table = 65 seconds
Perft + Hash Table + Bulk Counting = 31 seconds

So my current implementation of the Hash table sped up by approx. 3.5 times.

I think I will put buckets on the todo list and move onto the next stage.

What would be the next step? I assume it will be to start evaluating or scoring a Board position in isolation?