2008-08-31 23:59:13 -06:00
|
|
|
/*
|
2008-10-19 10:56:28 -06:00
|
|
|
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
|
2021-01-08 09:04:23 -07:00
|
|
|
Copyright (C) 2004-2021 The Stockfish developers (see AUTHORS file)
|
2008-08-31 23:59:13 -06:00
|
|
|
|
2008-10-19 10:56:28 -06:00
|
|
|
Stockfish is free software: you can redistribute it and/or modify
|
2008-08-31 23:59:13 -06:00
|
|
|
it under the terms of the GNU General Public License as published by
|
|
|
|
the Free Software Foundation, either version 3 of the License, or
|
|
|
|
(at your option) any later version.
|
2008-09-18 08:09:19 -06:00
|
|
|
|
2008-10-19 10:56:28 -06:00
|
|
|
Stockfish is distributed in the hope that it will be useful,
|
2008-08-31 23:59:13 -06:00
|
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
|
GNU General Public License for more details.
|
2008-09-18 08:09:19 -06:00
|
|
|
|
2008-08-31 23:59:13 -06:00
|
|
|
You should have received a copy of the GNU General Public License
|
|
|
|
along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
|
|
*/
|
|
|
|
|
2019-03-31 02:48:27 -06:00
|
|
|
#include <algorithm>
|
2019-03-31 04:02:19 -06:00
|
|
|
#include <bitset>
|
2008-08-31 23:59:13 -06:00
|
|
|
|
|
|
|
#include "bitboard.h"
|
Simpler PRNG and faster magics search
This patch replaces RKISS by a simpler and faster PRNG, xorshift64* proposed
by S. Vigna (2014). It is extremely simple, has a large enough period for
Stockfish's needs (2^64), requires no warming-up (allowing such code to be
removed), and offers slightly better randomness than MT19937.
Paper: http://xorshift.di.unimi.it/
Reference source code (public domain):
http://xorshift.di.unimi.it/xorshift64star.c
The patch also simplifies how init_magics() searches for magics:
- Old logic: seed the PRNG always with the same seed,
then use optimized bit rotations to tailor the RNG sequence per rank.
- New logic: seed the PRNG with an optimized seed per rank.
This has two advantages:
1. Less code and less computation to perform during magics search (not ROTL).
2. More choices for random sequence tuning. The old logic only let us choose
from 4096 bit rotation pairs. With the new one, we can look for the best seeds
among 2^64 values. Indeed, the set of seeds[][] provided in the patch reduces
the effort needed to find the magics:
64-bit SF:
Old logic -> 5,783,789 rand64() calls needed to find the magics
New logic -> 4,420,086 calls
32-bit SF:
Old logic -> 2,175,518 calls
New logic -> 1,895,955 calls
In the 64-bit case, init_magics() take 25 ms less to complete (Intel Core i5).
Finally, when playing with strength handicap, non-determinism is achieved
by setting the seed of the static RNG only once. Afterwards, there is no need
to skip output values.
The bench only changes because the Zobrist keys are now different (since they
are random numbers straight out of the PRNG).
The RNG seed has been carefully chosen so that the
resulting Zobrist keys are particularly well-behaved:
1. All triplets of XORed keys are unique, implying that it
would take at least 7 keys to find a 64-bit collision
(test suggested by ceebo)
2. All pairs of XORed keys are unique modulo 2^32
3. The cardinality of { (key1 ^ key2) >> 48 } is as close
as possible to the maximum (65536)
Point 2 aims at ensuring a good distribution among the bits
that determine an TT entry's cluster, likewise point 3
among the bits that form the TT entry's key16 inside a
cluster.
Details:
Bitset card(key1^key2)
------ ---------------
RKISS
key16 64894 = 99.020% of theoretical maximum
low18 180117 = 99.293%
low32 305362 = 99.997%
Xorshift64*, old seed
key16 64918 = 99.057%
low18 179994 = 99.225%
low32 305350 = 99.993%
Xorshift64*, new seed
key16 65027 = 99.223%
low18 181118 = 99.845%
low32 305371 = 100.000%
Bench: 9324905
Resolves #148
2014-12-07 17:10:57 -07:00
|
|
|
#include "misc.h"
|
2008-08-31 23:59:13 -06:00
|
|
|
|
2021-02-26 02:02:13 -07:00
|
|
|
namespace Stockfish {
|
|
|
|
|
2016-04-08 11:52:15 -06:00
|
|
|
uint8_t PopCnt16[1 << 16];
|
2019-02-08 02:36:03 -07:00
|
|
|
uint8_t SquareDistance[SQUARE_NB][SQUARE_NB];
|
2015-01-03 08:39:17 -07:00
|
|
|
|
2019-03-31 04:02:19 -06:00
|
|
|
Bitboard SquareBB[SQUARE_NB];
|
2013-11-08 19:06:47 -07:00
|
|
|
Bitboard LineBB[SQUARE_NB][SQUARE_NB];
|
Change definition of between_bb()
We remark that in current master, most of our use cases for between_bb() can be
optimized if the second parameter of the function is added to the segment. So we
change the definition of between_bb(s1, s2) such that it excludes s1 but includes s2.
We also use a precomputed array for between_bb() for another small speed gain
(see https://tests.stockfishchess.org/tests/view/604d09f72433018de7a389fb).
Passed STC:
LLR: 2.96 (-2.94,2.94) {-0.25,1.25}
Total: 18736 W: 1746 L: 1607 D: 15383
Ptnml(0-2): 61, 1226, 6644, 1387, 50
https://tests.stockfishchess.org/tests/view/60428c84ddcba5f0627bb6e4
Yellow LTC:
LTC:
LLR: -3.00 (-2.94,2.94) {0.25,1.25}
Total: 39144 W: 1431 L: 1413 D: 36300
Ptnml(0-2): 13, 1176, 17184, 1178, 21
https://tests.stockfishchess.org/tests/view/605128702433018de7a38ca1
Closes https://github.com/official-stockfish/Stockfish/pull/3397
---------
Verified for correctness by running perft on the following position:
./stockfish
position fen 4rrk1/1p1nq3/p7/2p1P1pp/3P2bp/3Q1Bn1/PPPB4/1K2R1NR w - - 40 21
go perft 6
Nodes searched: 6136386434
--------
No functional change
2021-03-15 13:06:42 -06:00
|
|
|
Bitboard BetweenBB[SQUARE_NB][SQUARE_NB];
|
2012-10-21 02:41:23 -06:00
|
|
|
Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB];
|
2017-04-28 21:33:30 -06:00
|
|
|
Bitboard PawnAttacks[COLOR_NB][SQUARE_NB];
|
2019-02-08 02:36:03 -07:00
|
|
|
|
2017-06-04 03:03:23 -06:00
|
|
|
Magic RookMagics[SQUARE_NB];
|
|
|
|
Magic BishopMagics[SQUARE_NB];
|
|
|
|
|
2011-06-06 01:58:59 -06:00
|
|
|
namespace {
|
|
|
|
|
2015-01-03 08:39:17 -07:00
|
|
|
Bitboard RookTable[0x19000]; // To store rook attacks
|
|
|
|
Bitboard BishopTable[0x1480]; // To store bishop attacks
|
2011-06-06 01:58:59 -06:00
|
|
|
|
2020-06-21 07:21:46 -06:00
|
|
|
void init_magics(PieceType pt, Bitboard table[], Magic magics[]);
|
2020-07-11 08:59:33 -06:00
|
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
/// safe_destination() returns the bitboard of target square for the given step
|
|
|
|
/// from the given square. If the step is off the board, returns empty bitboard.
|
|
|
|
|
|
|
|
inline Bitboard safe_destination(Square s, int step) {
|
|
|
|
Square to = Square(s + step);
|
|
|
|
return is_ok(to) && distance(s, to) <= 2 ? square_bb(to) : Bitboard(0);
|
2008-09-23 16:32:53 -06:00
|
|
|
}
|
2008-08-31 23:59:13 -06:00
|
|
|
|
2012-04-01 03:46:38 -06:00
|
|
|
|
2015-01-03 08:39:17 -07:00
|
|
|
/// Bitboards::pretty() returns an ASCII representation of a bitboard suitable
|
|
|
|
/// to be printed to standard output. Useful for debugging.
|
2012-04-01 03:46:38 -06:00
|
|
|
|
2021-01-30 01:50:04 -07:00
|
|
|
std::string Bitboards::pretty(Bitboard b) {
|
2012-04-01 03:46:38 -06:00
|
|
|
|
2014-03-01 05:05:55 -07:00
|
|
|
std::string s = "+---+---+---+---+---+---+---+---+\n";
|
2012-08-29 05:28:59 -06:00
|
|
|
|
2014-04-06 02:50:27 -06:00
|
|
|
for (Rank r = RANK_8; r >= RANK_1; --r)
|
2012-04-01 03:46:38 -06:00
|
|
|
{
|
2014-04-06 02:50:27 -06:00
|
|
|
for (File f = FILE_A; f <= FILE_H; ++f)
|
2015-06-28 02:24:10 -06:00
|
|
|
s += b & make_square(f, r) ? "| X " : "| ";
|
2012-04-01 03:46:38 -06:00
|
|
|
|
2020-06-07 15:48:38 -06:00
|
|
|
s += "| " + std::to_string(1 + r) + "\n+---+---+---+---+---+---+---+---+\n";
|
2012-04-01 03:46:38 -06:00
|
|
|
}
|
2020-06-07 15:48:38 -06:00
|
|
|
s += " a b c d e f g h\n";
|
2014-03-01 05:05:55 -07:00
|
|
|
|
|
|
|
return s;
|
2012-04-01 03:46:38 -06:00
|
|
|
}
|
|
|
|
|
|
|
|
|
2013-12-07 04:09:33 -07:00
|
|
|
/// Bitboards::init() initializes various bitboard tables. It is called at
|
|
|
|
/// startup and relies on global objects to be already zero-initialized.
|
2011-01-03 03:50:41 -07:00
|
|
|
|
2012-04-01 03:46:38 -06:00
|
|
|
void Bitboards::init() {
|
2011-01-03 03:50:41 -07:00
|
|
|
|
2016-04-08 11:52:15 -06:00
|
|
|
for (unsigned i = 0; i < (1 << 16); ++i)
|
2020-05-23 05:26:13 -06:00
|
|
|
PopCnt16[i] = uint8_t(std::bitset<16>(i).count());
|
2016-04-08 11:52:15 -06:00
|
|
|
|
2013-09-15 01:02:09 -06:00
|
|
|
for (Square s = SQ_A1; s <= SQ_H8; ++s)
|
2018-06-16 20:26:25 -06:00
|
|
|
SquareBB[s] = (1ULL << s);
|
2013-12-07 03:33:31 -07:00
|
|
|
|
2013-09-15 01:02:09 -06:00
|
|
|
for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
|
|
|
|
for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2)
|
2020-01-03 11:33:18 -07:00
|
|
|
SquareDistance[s1][s2] = std::max(distance<File>(s1, s2), distance<Rank>(s1, s2));
|
|
|
|
|
2020-06-21 07:21:46 -06:00
|
|
|
init_magics(ROOK, RookTable, RookMagics);
|
|
|
|
init_magics(BISHOP, BishopTable, BishopMagics);
|
2020-01-03 11:33:18 -07:00
|
|
|
|
2020-03-30 14:45:35 -06:00
|
|
|
for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
|
2020-01-03 11:33:18 -07:00
|
|
|
{
|
2020-03-30 14:45:35 -06:00
|
|
|
PawnAttacks[WHITE][s1] = pawn_attacks_bb<WHITE>(square_bb(s1));
|
|
|
|
PawnAttacks[BLACK][s1] = pawn_attacks_bb<BLACK>(square_bb(s1));
|
|
|
|
|
2020-01-03 11:33:18 -07:00
|
|
|
for (int step : {-9, -8, -7, -1, 1, 7, 8, 9} )
|
2020-04-12 12:30:08 -06:00
|
|
|
PseudoAttacks[KING][s1] |= safe_destination(s1, step);
|
2020-01-03 11:33:18 -07:00
|
|
|
|
|
|
|
for (int step : {-17, -15, -10, -6, 6, 10, 15, 17} )
|
2020-04-12 12:30:08 -06:00
|
|
|
PseudoAttacks[KNIGHT][s1] |= safe_destination(s1, step);
|
2012-01-15 00:24:50 -07:00
|
|
|
|
2013-11-30 02:27:23 -07:00
|
|
|
PseudoAttacks[QUEEN][s1] = PseudoAttacks[BISHOP][s1] = attacks_bb<BISHOP>(s1, 0);
|
|
|
|
PseudoAttacks[QUEEN][s1] |= PseudoAttacks[ ROOK][s1] = attacks_bb< ROOK>(s1, 0);
|
2011-03-10 06:39:53 -07:00
|
|
|
|
2017-04-28 21:33:30 -06:00
|
|
|
for (PieceType pt : { BISHOP, ROOK })
|
2015-05-09 03:09:06 -06:00
|
|
|
for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2)
|
Change definition of between_bb()
We remark that in current master, most of our use cases for between_bb() can be
optimized if the second parameter of the function is added to the segment. So we
change the definition of between_bb(s1, s2) such that it excludes s1 but includes s2.
We also use a precomputed array for between_bb() for another small speed gain
(see https://tests.stockfishchess.org/tests/view/604d09f72433018de7a389fb).
Passed STC:
LLR: 2.96 (-2.94,2.94) {-0.25,1.25}
Total: 18736 W: 1746 L: 1607 D: 15383
Ptnml(0-2): 61, 1226, 6644, 1387, 50
https://tests.stockfishchess.org/tests/view/60428c84ddcba5f0627bb6e4
Yellow LTC:
LTC:
LLR: -3.00 (-2.94,2.94) {0.25,1.25}
Total: 39144 W: 1431 L: 1413 D: 36300
Ptnml(0-2): 13, 1176, 17184, 1178, 21
https://tests.stockfishchess.org/tests/view/605128702433018de7a38ca1
Closes https://github.com/official-stockfish/Stockfish/pull/3397
---------
Verified for correctness by running perft on the following position:
./stockfish
position fen 4rrk1/1p1nq3/p7/2p1P1pp/3P2bp/3Q1Bn1/PPPB4/1K2R1NR w - - 40 21
go perft 6
Nodes searched: 6136386434
--------
No functional change
2021-03-15 13:06:42 -06:00
|
|
|
{
|
2019-02-08 02:36:03 -07:00
|
|
|
if (PseudoAttacks[pt][s1] & s2)
|
Change definition of between_bb()
We remark that in current master, most of our use cases for between_bb() can be
optimized if the second parameter of the function is added to the segment. So we
change the definition of between_bb(s1, s2) such that it excludes s1 but includes s2.
We also use a precomputed array for between_bb() for another small speed gain
(see https://tests.stockfishchess.org/tests/view/604d09f72433018de7a389fb).
Passed STC:
LLR: 2.96 (-2.94,2.94) {-0.25,1.25}
Total: 18736 W: 1746 L: 1607 D: 15383
Ptnml(0-2): 61, 1226, 6644, 1387, 50
https://tests.stockfishchess.org/tests/view/60428c84ddcba5f0627bb6e4
Yellow LTC:
LTC:
LLR: -3.00 (-2.94,2.94) {0.25,1.25}
Total: 39144 W: 1431 L: 1413 D: 36300
Ptnml(0-2): 13, 1176, 17184, 1178, 21
https://tests.stockfishchess.org/tests/view/605128702433018de7a38ca1
Closes https://github.com/official-stockfish/Stockfish/pull/3397
---------
Verified for correctness by running perft on the following position:
./stockfish
position fen 4rrk1/1p1nq3/p7/2p1P1pp/3P2bp/3Q1Bn1/PPPB4/1K2R1NR w - - 40 21
go perft 6
Nodes searched: 6136386434
--------
No functional change
2021-03-15 13:06:42 -06:00
|
|
|
{
|
|
|
|
LineBB[s1][s2] = (attacks_bb(pt, s1, 0) & attacks_bb(pt, s2, 0)) | s1 | s2;
|
|
|
|
BetweenBB[s1][s2] = (attacks_bb(pt, s1, square_bb(s2)) & attacks_bb(pt, s2, square_bb(s1)));
|
|
|
|
}
|
|
|
|
BetweenBB[s1][s2] |= s2;
|
|
|
|
}
|
2013-11-30 02:27:23 -07:00
|
|
|
}
|
2011-06-04 03:16:44 -06:00
|
|
|
}
|
2009-07-24 04:16:18 -06:00
|
|
|
|
2011-06-04 03:16:44 -06:00
|
|
|
namespace {
|
|
|
|
|
2020-06-21 07:21:46 -06:00
|
|
|
Bitboard sliding_attack(PieceType pt, Square sq, Bitboard occupied) {
|
2011-06-05 02:04:57 -06:00
|
|
|
|
2020-04-12 12:30:08 -06:00
|
|
|
Bitboard attacks = 0;
|
2020-06-21 07:21:46 -06:00
|
|
|
Direction RookDirections[4] = {NORTH, SOUTH, EAST, WEST};
|
|
|
|
Direction BishopDirections[4] = {NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST};
|
2010-04-18 00:57:34 -06:00
|
|
|
|
2020-07-11 08:59:33 -06:00
|
|
|
for (Direction d : (pt == ROOK ? RookDirections : BishopDirections))
|
2020-04-12 12:30:08 -06:00
|
|
|
{
|
|
|
|
Square s = sq;
|
2021-03-24 14:55:49 -06:00
|
|
|
while (safe_destination(s, d) && !(occupied & s))
|
2020-06-21 07:21:46 -06:00
|
|
|
attacks |= (s += d);
|
2020-04-12 12:30:08 -06:00
|
|
|
}
|
2012-01-15 00:24:50 -07:00
|
|
|
|
2020-04-12 12:30:08 -06:00
|
|
|
return attacks;
|
2008-08-31 23:59:13 -06:00
|
|
|
}
|
|
|
|
|
2011-12-03 03:43:07 -07:00
|
|
|
|
2012-01-15 00:24:50 -07:00
|
|
|
// init_magics() computes all rook and bishop attacks at startup. Magic
|
|
|
|
// bitboards are used to look up attacks of sliding pieces. As a reference see
|
2019-01-01 06:10:26 -07:00
|
|
|
// www.chessprogramming.org/Magic_Bitboards. In particular, here we use the so
|
|
|
|
// called "fancy" approach.
|
2011-10-31 08:37:46 -06:00
|
|
|
|
2020-06-21 07:21:46 -06:00
|
|
|
void init_magics(PieceType pt, Bitboard table[], Magic magics[]) {
|
2011-06-07 07:12:07 -06:00
|
|
|
|
2017-06-30 23:58:38 -06:00
|
|
|
// Optimal PRNG seeds to pick the correct magics in the shortest time
|
Simpler PRNG and faster magics search
This patch replaces RKISS by a simpler and faster PRNG, xorshift64* proposed
by S. Vigna (2014). It is extremely simple, has a large enough period for
Stockfish's needs (2^64), requires no warming-up (allowing such code to be
removed), and offers slightly better randomness than MT19937.
Paper: http://xorshift.di.unimi.it/
Reference source code (public domain):
http://xorshift.di.unimi.it/xorshift64star.c
The patch also simplifies how init_magics() searches for magics:
- Old logic: seed the PRNG always with the same seed,
then use optimized bit rotations to tailor the RNG sequence per rank.
- New logic: seed the PRNG with an optimized seed per rank.
This has two advantages:
1. Less code and less computation to perform during magics search (not ROTL).
2. More choices for random sequence tuning. The old logic only let us choose
from 4096 bit rotation pairs. With the new one, we can look for the best seeds
among 2^64 values. Indeed, the set of seeds[][] provided in the patch reduces
the effort needed to find the magics:
64-bit SF:
Old logic -> 5,783,789 rand64() calls needed to find the magics
New logic -> 4,420,086 calls
32-bit SF:
Old logic -> 2,175,518 calls
New logic -> 1,895,955 calls
In the 64-bit case, init_magics() take 25 ms less to complete (Intel Core i5).
Finally, when playing with strength handicap, non-determinism is achieved
by setting the seed of the static RNG only once. Afterwards, there is no need
to skip output values.
The bench only changes because the Zobrist keys are now different (since they
are random numbers straight out of the PRNG).
The RNG seed has been carefully chosen so that the
resulting Zobrist keys are particularly well-behaved:
1. All triplets of XORed keys are unique, implying that it
would take at least 7 keys to find a 64-bit collision
(test suggested by ceebo)
2. All pairs of XORed keys are unique modulo 2^32
3. The cardinality of { (key1 ^ key2) >> 48 } is as close
as possible to the maximum (65536)
Point 2 aims at ensuring a good distribution among the bits
that determine an TT entry's cluster, likewise point 3
among the bits that form the TT entry's key16 inside a
cluster.
Details:
Bitset card(key1^key2)
------ ---------------
RKISS
key16 64894 = 99.020% of theoretical maximum
low18 180117 = 99.293%
low32 305362 = 99.997%
Xorshift64*, old seed
key16 64918 = 99.057%
low18 179994 = 99.225%
low32 305350 = 99.993%
Xorshift64*, new seed
key16 65027 = 99.223%
low18 181118 = 99.845%
low32 305371 = 100.000%
Bench: 9324905
Resolves #148
2014-12-07 17:10:57 -07:00
|
|
|
int seeds[][RANK_NB] = { { 8977, 44560, 54343, 38998, 5731, 95205, 104912, 17020 },
|
|
|
|
{ 728, 10316, 55013, 32803, 12281, 15100, 16645, 255 } };
|
2014-12-08 00:23:09 -07:00
|
|
|
|
2011-06-21 11:48:14 -06:00
|
|
|
Bitboard occupancy[4096], reference[4096], edges, b;
|
2017-06-04 03:03:23 -06:00
|
|
|
int epoch[4096] = {}, cnt = 0, size = 0;
|
2008-08-31 23:59:13 -06:00
|
|
|
|
2013-09-15 01:02:09 -06:00
|
|
|
for (Square s = SQ_A1; s <= SQ_H8; ++s)
|
2010-04-18 00:57:34 -06:00
|
|
|
{
|
2011-10-31 08:37:46 -06:00
|
|
|
// Board edges are not considered in the relevant occupancies
|
2011-06-21 11:48:14 -06:00
|
|
|
edges = ((Rank1BB | Rank8BB) & ~rank_bb(s)) | ((FileABB | FileHBB) & ~file_bb(s));
|
2011-06-05 05:09:55 -06:00
|
|
|
|
2011-10-31 08:37:46 -06:00
|
|
|
// Given a square 's', the mask is the bitboard of sliding attacks from
|
|
|
|
// 's' computed on an empty board. The index must be big enough to contain
|
|
|
|
// all the attacks for each possible subset of the mask and so is 2 power
|
|
|
|
// the number of 1s of the mask. Hence we deduce the size of the shift to
|
|
|
|
// apply to the 64 or 32 bits word to get the index.
|
2017-06-04 03:03:23 -06:00
|
|
|
Magic& m = magics[s];
|
2020-06-21 07:21:46 -06:00
|
|
|
m.mask = sliding_attack(pt, s, 0) & ~edges;
|
2017-06-04 03:03:23 -06:00
|
|
|
m.shift = (Is64Bit ? 64 : 32) - popcount(m.mask);
|
|
|
|
|
|
|
|
// Set the offset for the attacks table of the square. We have individual
|
|
|
|
// table sizes for each square with "Fancy Magic Bitboards".
|
|
|
|
m.attacks = s == SQ_A1 ? table : magics[s - 1].attacks + size;
|
2009-03-24 03:30:27 -06:00
|
|
|
|
2011-10-31 08:37:46 -06:00
|
|
|
// Use Carry-Rippler trick to enumerate all subsets of masks[s] and
|
2012-01-15 00:24:50 -07:00
|
|
|
// store the corresponding sliding attack bitboard in reference[].
|
2011-11-01 02:07:23 -06:00
|
|
|
b = size = 0;
|
2011-06-14 11:40:52 -06:00
|
|
|
do {
|
2011-11-01 02:07:23 -06:00
|
|
|
occupancy[size] = b;
|
2020-06-21 07:21:46 -06:00
|
|
|
reference[size] = sliding_attack(pt, s, b);
|
2014-04-07 08:27:14 -06:00
|
|
|
|
|
|
|
if (HasPext)
|
2017-06-04 03:03:23 -06:00
|
|
|
m.attacks[pext(b, m.mask)] = reference[size];
|
2014-04-07 08:27:14 -06:00
|
|
|
|
|
|
|
size++;
|
2017-06-04 03:03:23 -06:00
|
|
|
b = (b - m.mask) & m.mask;
|
2011-06-14 11:40:52 -06:00
|
|
|
} while (b);
|
|
|
|
|
2014-04-07 08:27:14 -06:00
|
|
|
if (HasPext)
|
|
|
|
continue;
|
|
|
|
|
Simpler PRNG and faster magics search
This patch replaces RKISS by a simpler and faster PRNG, xorshift64* proposed
by S. Vigna (2014). It is extremely simple, has a large enough period for
Stockfish's needs (2^64), requires no warming-up (allowing such code to be
removed), and offers slightly better randomness than MT19937.
Paper: http://xorshift.di.unimi.it/
Reference source code (public domain):
http://xorshift.di.unimi.it/xorshift64star.c
The patch also simplifies how init_magics() searches for magics:
- Old logic: seed the PRNG always with the same seed,
then use optimized bit rotations to tailor the RNG sequence per rank.
- New logic: seed the PRNG with an optimized seed per rank.
This has two advantages:
1. Less code and less computation to perform during magics search (not ROTL).
2. More choices for random sequence tuning. The old logic only let us choose
from 4096 bit rotation pairs. With the new one, we can look for the best seeds
among 2^64 values. Indeed, the set of seeds[][] provided in the patch reduces
the effort needed to find the magics:
64-bit SF:
Old logic -> 5,783,789 rand64() calls needed to find the magics
New logic -> 4,420,086 calls
32-bit SF:
Old logic -> 2,175,518 calls
New logic -> 1,895,955 calls
In the 64-bit case, init_magics() take 25 ms less to complete (Intel Core i5).
Finally, when playing with strength handicap, non-determinism is achieved
by setting the seed of the static RNG only once. Afterwards, there is no need
to skip output values.
The bench only changes because the Zobrist keys are now different (since they
are random numbers straight out of the PRNG).
The RNG seed has been carefully chosen so that the
resulting Zobrist keys are particularly well-behaved:
1. All triplets of XORed keys are unique, implying that it
would take at least 7 keys to find a 64-bit collision
(test suggested by ceebo)
2. All pairs of XORed keys are unique modulo 2^32
3. The cardinality of { (key1 ^ key2) >> 48 } is as close
as possible to the maximum (65536)
Point 2 aims at ensuring a good distribution among the bits
that determine an TT entry's cluster, likewise point 3
among the bits that form the TT entry's key16 inside a
cluster.
Details:
Bitset card(key1^key2)
------ ---------------
RKISS
key16 64894 = 99.020% of theoretical maximum
low18 180117 = 99.293%
low32 305362 = 99.997%
Xorshift64*, old seed
key16 64918 = 99.057%
low18 179994 = 99.225%
low32 305350 = 99.993%
Xorshift64*, new seed
key16 65027 = 99.223%
low18 181118 = 99.845%
low32 305371 = 100.000%
Bench: 9324905
Resolves #148
2014-12-07 17:10:57 -07:00
|
|
|
PRNG rng(seeds[Is64Bit][rank_of(s)]);
|
2011-06-05 02:04:57 -06:00
|
|
|
|
2011-10-31 08:37:46 -06:00
|
|
|
// Find a magic for square 's' picking up an (almost) random number
|
|
|
|
// until we find the one that passes the verification test.
|
2017-06-04 03:03:23 -06:00
|
|
|
for (int i = 0; i < size; )
|
|
|
|
{
|
|
|
|
for (m.magic = 0; popcount((m.magic * m.mask) >> 56) < 6; )
|
|
|
|
m.magic = rng.sparse_rand<Bitboard>();
|
2012-06-10 04:11:28 -06:00
|
|
|
|
2011-10-31 08:37:46 -06:00
|
|
|
// A good magic must map every possible occupancy to an index that
|
|
|
|
// looks up the correct sliding attack in the attacks[s] database.
|
|
|
|
// Note that we build up the database for square 's' as a side
|
2017-06-04 03:03:23 -06:00
|
|
|
// effect of verifying the magic. Keep track of the attempt count
|
|
|
|
// and save it in epoch[], little speed-up trick to avoid resetting
|
|
|
|
// m.attacks[] after every failed attempt.
|
|
|
|
for (++cnt, i = 0; i < size; ++i)
|
2011-06-07 07:12:07 -06:00
|
|
|
{
|
2017-06-28 18:11:17 -06:00
|
|
|
unsigned idx = m.index(occupancy[i]);
|
2015-03-22 04:27:32 -06:00
|
|
|
|
2017-06-04 03:03:23 -06:00
|
|
|
if (epoch[idx] < cnt)
|
2015-03-22 04:27:32 -06:00
|
|
|
{
|
2017-06-04 03:03:23 -06:00
|
|
|
epoch[idx] = cnt;
|
|
|
|
m.attacks[idx] = reference[i];
|
2015-03-22 04:27:32 -06:00
|
|
|
}
|
2017-06-04 03:03:23 -06:00
|
|
|
else if (m.attacks[idx] != reference[i])
|
2011-06-07 07:12:07 -06:00
|
|
|
break;
|
|
|
|
}
|
2017-06-04 03:03:23 -06:00
|
|
|
}
|
2008-08-31 23:59:13 -06:00
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
2021-02-26 02:02:13 -07:00
|
|
|
|
|
|
|
} // namespace Stockfish
|