-> There are no more than three legal pinned pawns moves in a position, one in each direction.
-> For pinned sliders, '&' the slider attack masks with LineBetween[sq][own_king_square] for completely legal move set.
-> A pinned knight can't legally move
My aim wasn't to build the fastest perft program out there, and there is still lot of speed-up possible in this program, although I have never myself seen a program that beats it (but I believe there are many). My aim was merely to experiment with ideas I had, and to write a base for my completely original engine which would not use any copyrighted code (such as Pradu's). Also, I had an idea to pre-store moves inside MoveLists, and to index MoveLists using magic bitboards. I knew this would screw cache, and not pay off too much, but as I said, my aim was to experiment. I came to know that Gerd Isenberg had similar ideas in the past, but that didn't stop me. I used this code to find the magics (not really, the following code is a rather heavily evolved one)
Code: Select all
inline bool is_good_mlist_magic(bitboard_t magic, bitboard_t Atk,
std::vector<bool>& used, count_t shift)
{
const size_t MaxSize = 1 << (64 - shift);
assert(used.size() >= MaxSize);
for (size_t i = 0; i < MaxSize; ++i)
used[i] = false;
bitboard_t subset = 0;
do {
uint32_t h = uint32_t((magic * subset) >> shift);
assert(h < MaxSize);
if (used[h] == true) return false;
used[h] = true;
} while (subset = (subset - Atk) & Atk); // Transverse all subsets
return true;
}
// Finds a magic which would hash all subsets of 'atk' uniquely into 64-'shift' bits.
inline bitboard_t find_mlist_magic(count_t shift, bitboard_t atk)
{
bitboard_t m;
std::vector<bool> temp(1 << (64-shift)); // Feel free to use an array
for (;;) {
m = Random::rand64_few_bits();
if (is_good_mlist_magic(m, atk, temp, shift)) break;
}
return m;
}
1. The start position (a position featuring sparsely populated slider attack masks). Yaka with movelists performed 1.26x faster than qperft, and without movelists performed 2.86x faster.
Code: Select all
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft( 1)= 20 ( 0.000 sec)
perft( 2)= 400 ( 0.000 sec)
perft( 3)= 8902 ( 0.000 sec)
perft( 4)= 197281 ( 0.000 sec)
perft( 5)= 4865609 ( 0.047 sec)
perft( 6)= 119060324 ( 1.156 sec)
perft( 7)= 3195901860 (31.080 sec)
Yaka 0.0 x64 by Syed Fahad
perft 7
b1a3: 120142144
...truncated...
h2h4: 138495290
Took 24626 ms for 3195901860 nodes, 129777 knps
Yaka (no movelists) 0.0 x64 by Syed Fahad
perft 7
b1a3: 120142144
...truncated...
h2h4: 138495290
Took 10874 ms for 3195901860 nodes, 293903 knps
Code: Select all
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft( 1)= 48 ( 0.000 sec)
perft( 2)= 2039 ( 0.000 sec)
perft( 3)= 97862 ( 0.000 sec)
perft( 4)= 4085603 ( 0.047 sec)
perft( 5)= 193690690 ( 1.437 sec)
perft( 6)= 8031647685 (65.519 sec)
Yaka 0.0 x64 by Syed Fahad
position kiwipete
perft 6
f3d3: 164583144
...truncated...
g2g4: 135208177
Took 46955 ms for 8031647685 nodes, 171049 knps
Yaka (no movelists) 0.0 x64 by Syed Fahad
position kiwipete
perft 6
a1b1: 160413321
...truncated...
g2g4: 135208177
Took 22354 ms for 8031647685 nodes, 359293 knps
Here, Yaka performed 1.24x faster, and without movelists it performed only 1.97x faster.
Code: Select all
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft( 1)= 14 ( 0.000 sec)
perft( 2)= 191 ( 0.000 sec)
perft( 3)= 2812 ( 0.000 sec)
perft( 4)= 43238 ( 0.016 sec)
perft( 5)= 674624 ( 0.000 sec)
perft( 6)= 11030083 ( 0.172 sec)
perft( 7)= 178633661 ( 2.078 sec)
perft( 8)= 3009794393 (40.283 sec)
Yaka 0.0 x64 by Syed Fahad
position fen 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1
perft 8
b4b1: 334237659
...truncated...
g2g4: 229481475
Took 32560 ms for 3007928693 nodes, 92381 knps
Yaka (no movelists) 0.0 x64 by Syed Fahad
position fen 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1
perft 8
b4b1: 334237659
...truncated...
g2g4: 229481475
Took 20476 ms for 3007928693 nodes, 146900 knps
In this position, Yaka with movelists performed 1.42x faster, and without movelists it's 3.31x faster!
Code: Select all
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft( 1)= 6 ( 0.000 sec)
perft( 2)= 264 ( 0.000 sec)
perft( 3)= 9467 ( 0.000 sec)
perft( 4)= 422333 ( 0.000 sec)
perft( 5)= 15833292 ( 0.141 sec)
perft( 6)= 706045033 ( 7.641 sec)
perft( 7)= 27209691363 (260.328 sec)
Yaka 0.0 x64 by Syed Fahad
position fen r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1
perft 7
g1h1: 5992804777
f1f2: 4558995210
b4c5: 3227348274
f3d4: 5092346265
c4c5: 3409832969
d2d4: 4928363868
Took 182889 ms for 27209691363 nodes, 148777 knps
Yaka (no movelists) 0.0 x64 by Syed Fahad
position fen r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1
perft 7
g1h1: 5992804777
f1f2: 4558995210
b4c5: 3227348274
f3d4: 5092346265
c4c5: 3409832969
d2d4: 4928363868
Took 78677 ms for 27209691363 nodes, 345840 knps
In this position, Yaka with movelists is only 1.19x faster, but Yaka without movelists is 2.69x faster.
Code: Select all
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft( 1)= 42 ( 0.000 sec)
perft( 2)= 1352 ( 0.000 sec)
perft( 3)= 53392 ( 0.001 sec)
perft( 4)= 1761505 ( 0.017 sec)
perft( 5)= 70202861 ( 0.629 sec)
perft( 6)= 2362704901 (20.089 sec)
Yaka 0.0 x64 by Syed Fahad
position fen rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6
perft 6
d1d2: 61274029
...truncated...
h2h4: 59632702
Took 16981 ms for 2362704901 nodes, 139138 knps
Yaka (no movelists) 0.0 x64 by Syed Fahad
position fen rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6
perft 6
d1d2: 61274029
...truncated...
h2h4: 59632702
Took 7470 ms for 2362704901 nodes, 316292 knps
=====================================================
To download these versions and test yourself: https://sites.google.com/site/sydfhd/projects/yaka