From e6523e56b8cc110aa38d698a993cb04b430e67b0 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Wed, 12 Feb 2014 14:47:36 +0100 Subject: [PATCH] Move magic random to RKISS When initializing the magic numbers used to compute sliding attacks, we endless generate a random and test it as a possible magic. In the general case this takes a lot of iterations, but here, insteaad of picking a casual random, we rotate it a couple of times and generate a number that we know has a good probability to be a magic candidate. This is becuase the quantities by which we rotate the number are known in advance to produce quickly a good canidate. The patch, inspired by DON, just moves the shuffle to RKISS changing the boosters to take in account a left rotation instead of a right rotation as in the original. No functional change. --- src/bitboard.cpp | 21 ++++----------------- src/rkiss.h | 8 ++++++++ 2 files changed, 12 insertions(+), 17 deletions(-) diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 6784effd..b7eed922 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -246,20 +246,6 @@ namespace { } - Bitboard pick_random(RKISS& rk, int booster) { - - // Values s1 and s2 are used to rotate the candidate magic of a - // quantity known to be optimal to quickly find the magics. - int s1 = booster & 63, s2 = (booster >> 6) & 63; - - Bitboard m = rk.rand(); - m = (m >> s1) | (m << (64 - s1)); - m &= rk.rand(); - m = (m >> s2) | (m << (64 - s2)); - return m & rk.rand(); - } - - // 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 // chessprogramming.wikispaces.com/Magic+Bitboards. In particular, here we @@ -268,8 +254,9 @@ namespace { void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[], Bitboard masks[], unsigned shifts[], Square deltas[], Fn index) { - int MagicBoosters[][8] = { { 3191, 2184, 1310, 3618, 2091, 1308, 2452, 3996 }, - { 1059, 3608, 605, 3234, 3326, 38, 2029, 3043 } }; + int MagicBoosters[][8] = { { 969, 1976, 2850, 542, 2069, 2852, 1708, 164 }, + { 3101, 552, 3555, 926, 834, 4122, 2131, 1117 } }; + RKISS rk; Bitboard occupancy[4096], reference[4096], edges, b; int i, size, booster; @@ -309,7 +296,7 @@ namespace { // Find a magic for square 's' picking up an (almost) random number // until we find the one that passes the verification test. do { - do magics[s] = pick_random(rk, booster); + do magics[s] = rk.magic_rand(booster); while (popcount((magics[s] * masks[s]) >> 56) < 6); std::memset(attacks[s], 0, size * sizeof(Bitboard)); diff --git a/src/rkiss.h b/src/rkiss.h index b9b82cef..f3468db4 100644 --- a/src/rkiss.h +++ b/src/rkiss.h @@ -68,6 +68,14 @@ public: } template T rand() { return T(rand64()); } + + /// Special generator used to fast init magic numbers. Here the + /// trick is to rotate the randoms of a given quantity 's' known + /// to be optimal to quickly find a good magic candidate. + template T magic_rand(int s) { + return rotate_L(rotate_L(rand(), (s >> 0) & 0x3F) & rand() + , (s >> 6) & 0x3F) & rand(); + } }; #endif // #ifndef RKISS_H_INCLUDED -- 2.30.2