Perft speed and depth questions

[chrisw]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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?