Hash entry/bucket memory usage optimization

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.
Post Reply
User avatar
mvanthoor
Posts: 1245
Joined: Wed Jul 03, 2019 2:42 pm
Location: Netherlands
Full name: Marcel Vanthoor
Contact:

Hash entry/bucket memory usage optimization

Post by mvanthoor » Mon Mar 30, 2020 11:27 pm

Hello again :) Thanks for the assistance in the other topic with regard to getting the hash table working.

I've now been trying to optimize the memory usage of the entries. Before, an entry looked like this:

zobrist_key: u64
leaf_nodes: u64
depth: u8

17 bytes, which Rusts pads to 24 (next multiple of 8), so it would only fit 3 buckets in 64 bytes.

Because leaf_nodes runs into the billions in higher perfts, I think I need the entire 64-bit. So, to get the entry at, or under 16 bits, I need to take out the depth or make the zobrist_key field smaller. I tried this:

verification: u8
leaf_nodes: u64
depth: u8

(10 bytes, which Rust pads to 16; fits 4 buckets in 64-bits.)

Then, I took out the lowest significant bit of the zobrist key to put in "verification", shifted the zobrist key right 8 bits (keeping 56 out of 64), and used those 56 bits to calculate the index. Then, when probing the hash, I also used those 56 bits, and the one byte and depth as verification.

It didn't work; the numbers where off.

Then I did exactly the same thing, but using 32-bit verification (so taking half the zobrist key). Strangely enough, it seemed to work with 3 buckets, but not with 1, 2 or 4.

Now I have this:

verification: u64
leaf_nodes: u64

In this scenario, I folded the depth into the verification:

Code: Select all

const UNSET_HIGHEST_BYTE: u64 = 0x00_FF_FF_FF_FF_FF_FF_FF;

let verification = (zk & UNSET_HIGHEST_BYTE) | ((depth as u64) << 56);
So this takes 7 out of the 8 zobrist bytes, and the depth, in one variable for verification of the entry in a bucket.

This seems to work. I ran perft(8) for the starting position with no errors. The entire perftsuite.epd checked out, and I tested many positions from the Perft Results page on the chess programming wiki. All without errors.

Perft 7 for the starting position also became faster:
Before optimization: 27.20 seconds
After optimization: 23.26 seconds
Running with 32MB hash table (both before and after optimization; after optimization obviously has more entries because it uses less memory per entry. I'm running all my tests with a 32MB table at perft 7 from the starting position.)

Code: Select all

Entry memory usage: 16
Bucket memory usage: 64
Benchmarking perft 1-7:
Starting position

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . . . . .
3   . . . . . . . .
2   I 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:        819aa694337673fb
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (7 ms, 28183000 leaves/sec)
Perft 5: 4865609 (107 ms, 45472981 leaves/sec)
Perft 6: 119060324 (1385 ms, 85964132 leaves/sec)
Perft 7: 3195901860 (23258 ms, 137410863 leaves/sec)
Total time spent: 24757 ms
Execution speed: 134104875 leaves/second
Finished.
So memory layout optimization gained 14.4% speedup of the hash table.

(edit: with the current implementation, even a 1 MB hash table of only 65.536 entries is useful: it speeds up perft 7 from 113.2 seconds to 70.6 seconds. That's a 37.6% speedup... for only a 1 MB hash. When I started out with this a few days ago, I needed a a 24 GB hash table to achieve what now can be done with 32 MB; and everything under 1 GB wasn't even remotely useful, let alone 1 MB.)

Hash vs no hash speed for perft 7 is now 23.26 seconds vs 113.20 seconds. So the hash table speeds up Perft by 79.5% I know that Perft / movegen speed isn't the most important thing in a chess program, but this perft function allows me to see if things are working correctly.

Can I be certain that this way of verifying that I got the correct entry within the bucket holds up on higher depths?

If so, I can generalize this has table (leaf_nodes -> data, etc)... and use the same code when doing the search. In that case, my hash table is already done before I even finish the engine.

Or, does this not work eventually and is there another/better way of making the entries 16 bytes maximum that I'm not finding?
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL

mar
Posts: 2494
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Hash entry/bucket memory usage optimization

Post by mar » Tue Mar 31, 2020 2:15 am

mvanthoor wrote:
Mon Mar 30, 2020 11:27 pm
Can I be certain that this way of verifying that I got the correct entry within the bucket holds up on higher depths?

If so, I can generalize this has table (leaf_nodes -> data, etc)... and use the same code when doing the search. In that case, my hash table is already done before I even finish the engine.

Or, does this not work eventually and is there another/better way of making the entries 16 bytes maximum that I'm not finding?
Well, you'd have to reach high depths to verify promotions, for example (first promotion from startpos 9 plies I think?)
I prefer a custom set of artificial positions that test most of the movegen gotchas that can be validated instantly at much lower depths.

As for "hashtable is already done", I don't think so. Hashtable for the engine (=search) needs to store more info (at least search bound, score, depth) + probing is a bit more complicated as well
Martin Sedlak

mar
Posts: 2494
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Hash entry/bucket memory usage optimization

Post by mar » Tue Mar 31, 2020 6:29 am

(and move, of course)
Martin Sedlak

User avatar
mvanthoor
Posts: 1245
Joined: Wed Jul 03, 2019 2:42 pm
Location: Netherlands
Full name: Marcel Vanthoor
Contact:

Re: Hash entry/bucket memory usage optimization

Post by mvanthoor » Tue Mar 31, 2020 7:25 am

mar wrote:
Tue Mar 31, 2020 2:15 am
I prefer a custom set of artificial positions that test most of the movegen gotchas that can be validated instantly at much lower depths.
As said: I ran the entire perftsuite.epd file (in which I've included all the positions on this page: https://www.chessprogramming.org/Perft_Results), and they all check out fine.
As for "hashtable is already done", I don't think so. Hashtable for the engine (=search) needs to store more info (at least search bound, score, depth) + probing is a bit more complicated as well
Obviously I need to store other information for search instead of the number of leaf nodes found :P
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL

chrisw
Posts: 4008
Joined: Tue Apr 03, 2012 2:28 pm

Re: Hash entry/bucket memory usage optimization

Post by chrisw » Tue Mar 31, 2020 10:05 pm

mvanthoor wrote:
Tue Mar 31, 2020 7:25 am
mar wrote:
Tue Mar 31, 2020 2:15 am
I prefer a custom set of artificial positions that test most of the movegen gotchas that can be validated instantly at much lower depths.
As said: I ran the entire perftsuite.epd file (in which I've included all the positions on this page: https://www.chessprogramming.org/Perft_Results), and they all check out fine.
As for "hashtable is already done", I don't think so. Hashtable for the engine (=search) needs to store more info (at least search bound, score, depth) + probing is a bit more complicated as well
Obviously I need to store other information for search instead of the number of leaf nodes found :P
I collected up this little lot some time ago (possibly some are duplicated on the wiki).

It is necessary to test for the rare things that pop up, and I think this suite has the suitable candidates for that. Some of the commenting is just my internal notes, some may come with the epds, not sure which is which now.

Also seem to recollect doing an inverse position switch, which can also pick up problems.

Code: Select all


char perft_epd[][256] =
{
	"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",
	"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/p7/8/8/1P6/8/7K w - - 0 1; D1 4; D2 16; D3 101; D4 637; D5 4354; D6 29679",
	"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/1p6/8/8/P7/8/7K w - - 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/6p1/8/8/8/8/7P/K7 w - - 0 1; D1 5; D2 25; D3 161; D4 1035; D5 7574; D6 55338",
	"3k4/3pp3/8/8/8/8/3PP3/3K4 w - - 0 1; D1 7; D2 49; D3 378; D4 2902; D5 24122; D6 199002",
	"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/p7/8/8/1P6/8/7K b - - 0 1; D1 4; D2 16; D3 101; D4 637; D5 4354; D6 29679",
	"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/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 b - - 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",
	"3k4/3pp3/8/8/8/8/3PP3/3K4 b - - 0 1; D1 7; D2 49; D3 378; D4 2902; D5 24122; D6 199002",
	"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",
	"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",
	"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",
	"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/Pk6/8/8/8/8/6Kp/8 w - - 0 1; D1 11; D2 97; D3 887; D4 8048; D5 90606; D6 1030499",
	"n1n5/1Pk5/8/8/8/8/5Kp1/5N1N w - - 0 1; D1 24; D2 421; D3 7421; D4 124608; D5 2193768; D6 37665329",
	"8/PPPk4/8/8/8/8/4Kppp/8 w - - 0 1; D1 18; D2 270; D3 4699; D4 79355; D5 1533145; D6 28859283",
	"n1n5/PPPk4/8/8/8/8/4Kppp/5N1N w - - 0 1; D1 24; D2 496; D3 9483; D4 182838; D5 3605103; D6 71179139",
	"8/Pk6/8/8/8/8/6Kp/8 b - - 0 1; D1 11; D2 97; D3 887; D4 8048; D5 90606; D6 1030499",
	"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",
	"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",
	"8/p7/8/1P6/K1k3p1/6P1/7P/8 w - - 0 1; D8 8103790",
	"r3k2r/p6p/8/B7/1pp1p3/3b4/P6P/R3K2R w KQkq - 0 1; D6 77054993",
	"8/5p2/8/2k3P1/p3K3/8/1P6/8 b - - 0 1; D8 64451405",
	"r3k2r/pb3p2/5npp/n2p4/1p1PPB2/6P1/P2N1PBP/R3K2R b KQkq - 0 1; D6 867640754",
	"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1; D1 20; D2 400; D3 8902; D4 197281; D5 4865609; D6 119060324",
	"n1n5/1Pk5/8/8/8/8/5Kp1/5N1N b - - 0 1; D1 24; D2 421; D3 7421; D4 124608; D5 2193768; D6 37665329",
	"8/PPPk4/8/8/8/8/4Kppp/8 b - - 0 1; D1 18; D2 270; D3 4699; D4 79355; D5 1533145; D6 28859283",
	"n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - - 0 1; D1 24; D2 496; D3 9483; D4 182838; D5 3605103; D6 71179139",
	"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",
	"rnbqkbnr/pppp1pp1/8/3Pp2p/3Q4/8/PPP1PPPP/RNB1KBNR w KQkq e6 0 1; D1 44; D2 1307; D3 51845; D4 1549650; D5 59257777; D6 1801085024",
	"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1; D1 48; D2 2039; D3 97862; D4 4085603; D5 193690690; D6 8031647685",
};


User avatar
mvanthoor
Posts: 1245
Joined: Wed Jul 03, 2019 2:42 pm
Location: Netherlands
Full name: Marcel Vanthoor
Contact:

Re: Hash entry/bucket memory usage optimization

Post by mvanthoor » Thu Apr 02, 2020 7:27 pm

Thanks for the extra tests chrisw. I added them to my perft suite. (I assume the very large chunk is the well-known perftsuite.epd, as I've sampled a few and I already had them all.) All of the extra tests such as "double check", "castling gives check" etc run just fine.
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL

chrisw
Posts: 4008
Joined: Tue Apr 03, 2012 2:28 pm

Re: Hash entry/bucket memory usage optimization

Post by chrisw » Thu Apr 02, 2020 7:39 pm

mvanthoor wrote:
Thu Apr 02, 2020 7:27 pm
Thanks for the extra tests chrisw. I added them to my perft suite. (I assume the very large chunk is the well-known perftsuite.epd, as I've sampled a few and I already had them all.) All of the extra tests such as "double check", "castling gives check" etc run just fine.
Those extra tests are really to test out check_generators and/or special move generators. Some programmers have special partial move generators for some situations, so checking everything adds up needs some destruction testing. En passant discovery and check by castles for example.

User avatar
mvanthoor
Posts: 1245
Joined: Wed Jul 03, 2019 2:42 pm
Location: Netherlands
Full name: Marcel Vanthoor
Contact:

Re: Hash entry/bucket memory usage optimization

Post by mvanthoor » Fri Apr 03, 2020 1:54 pm

Yes. At some point I'll be implementing such enhancements in the move generator, but that will be somewhere down the line :)
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL

Post Reply