Ok, good to know that. And what about the possible board corruption I reported in the other mail regarding square_clear() vs. square_set()?ZirconiumX wrote:Yay!
The SQUARE_TO_64() macro saved it, thanks Sven!
Matthew:out
Sven
Project help required: Bitboard Fruit 2.1
Moderators: hgm, Rebel, chrisw
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Project help required: Bitboard Fruit 2.1
Sven
-
lucasart
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Project help required: Bitboard Fruit 2.1
Here's the magic code from Umko slightely rewritten, and reduced to its barebone:ZirconiumX wrote:I am basically trying to get a Fruit that runs (approx) ~1.5x current speed. I was not using board->bitboards[0] because I hoped to use the PieceNone256 constant to indicate empty squares.
@Sven
Thank you for your help in this, I shall correct the corrections and report back.
@Lucas
A basic barebones of Magic is under way. I currently have the Interface done, and ermmm not much else ATM.
Matthew:out
* portable: fully ICO C99 compliant, ciompiler & OS & architecture independant
* dependable: no dependancy, just #include magic.h and you're good to go (call init_magics() first, then bishop_attack() and rook_attack() as you please).
magic.h
Code: Select all
/*
* DoubleCheck, a UCI chess playing engine. Copyright (C) 2011 Lucas Braesch.
*
* DoubleCheck is free software: you can redistribute it and/or modify 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.
*
* DoubleCheck is distributed in the hope that it will be useful, 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.
*
* You should have received a copy of the GNU General Public License along with this program. If not,
* see <http://www.gnu.org/licenses/>.
*
* Credits: All magic bitboard code is a (almost) verbatim copy of Umko, by Borko Boskovic. Many
* thanks to Borko for providing a good implementation of magics to the free software community.
*/
#pragma once
#include <inttypes.h>
#include <stdbool.h>
/* Precalculate magic bitboards */
void init_magics();
extern bool MagicInitialized;
/* Squares attacked by a bishop/rook for a given board occupancy */
extern uint64_t bishop_attack(unsigned sq, uint64_t occ);
extern uint64_t rook_attack(unsigned sq, uint64_t occ);Code: Select all
/*
* DoubleCheck, a UCI chess playing engine. Copyright (C) 2011 Lucas Braesch.
*
* DoubleCheck is free software: you can redistribute it and/or modify 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.
*
* DoubleCheck is distributed in the hope that it will be useful, 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.
*
* You should have received a copy of the GNU General Public License along with this program. If not,
* see <http://www.gnu.org/licenses/>.
*
* Credits: All magic bitboard code is a (almost) verbatim copy of Umko, by Borko Boskovic. Many
* thanks to Borko for providing a good implementation of magics to the free software community.
*/
#include "magic.h"
#include <assert.h>
bool MagicInitialized = false;
const unsigned magic_bb_r_shift[64] = {
52, 53, 53, 53, 53, 53, 53, 52,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 53, 53, 53, 53, 53
};
const uint64_t magic_bb_r_magics[64] = {
0x0080001020400080ull, 0x0040001000200040ull, 0x0080081000200080ull, 0x0080040800100080ull,
0x0080020400080080ull, 0x0080010200040080ull, 0x0080008001000200ull, 0x0080002040800100ull,
0x0000800020400080ull, 0x0000400020005000ull, 0x0000801000200080ull, 0x0000800800100080ull,
0x0000800400080080ull, 0x0000800200040080ull, 0x0000800100020080ull, 0x0000800040800100ull,
0x0000208000400080ull, 0x0000404000201000ull, 0x0000808010002000ull, 0x0000808008001000ull,
0x0000808004000800ull, 0x0000808002000400ull, 0x0000010100020004ull, 0x0000020000408104ull,
0x0000208080004000ull, 0x0000200040005000ull, 0x0000100080200080ull, 0x0000080080100080ull,
0x0000040080080080ull, 0x0000020080040080ull, 0x0000010080800200ull, 0x0000800080004100ull,
0x0000204000800080ull, 0x0000200040401000ull, 0x0000100080802000ull, 0x0000080080801000ull,
0x0000040080800800ull, 0x0000020080800400ull, 0x0000020001010004ull, 0x0000800040800100ull,
0x0000204000808000ull, 0x0000200040008080ull, 0x0000100020008080ull, 0x0000080010008080ull,
0x0000040008008080ull, 0x0000020004008080ull, 0x0000010002008080ull, 0x0000004081020004ull,
0x0000204000800080ull, 0x0000200040008080ull, 0x0000100020008080ull, 0x0000080010008080ull,
0x0000040008008080ull, 0x0000020004008080ull, 0x0000800100020080ull, 0x0000800041000080ull,
0x00FFFCDDFCED714Aull, 0x007FFCDDFCED714Aull, 0x003FFFCDFFD88096ull, 0x0000040810002101ull,
0x0001000204080011ull, 0x0001000204000801ull, 0x0001000082000401ull, 0x0001FFFAABFAD1A2ull
};
const uint64_t magic_bb_r_mask[64] = {
0x000101010101017Eull, 0x000202020202027Cull, 0x000404040404047Aull, 0x0008080808080876ull,
0x001010101010106Eull, 0x002020202020205Eull, 0x004040404040403Eull, 0x008080808080807Eull,
0x0001010101017E00ull, 0x0002020202027C00ull, 0x0004040404047A00ull, 0x0008080808087600ull,
0x0010101010106E00ull, 0x0020202020205E00ull, 0x0040404040403E00ull, 0x0080808080807E00ull,
0x00010101017E0100ull, 0x00020202027C0200ull, 0x00040404047A0400ull, 0x0008080808760800ull,
0x00101010106E1000ull, 0x00202020205E2000ull, 0x00404040403E4000ull, 0x00808080807E8000ull,
0x000101017E010100ull, 0x000202027C020200ull, 0x000404047A040400ull, 0x0008080876080800ull,
0x001010106E101000ull, 0x002020205E202000ull, 0x004040403E404000ull, 0x008080807E808000ull,
0x0001017E01010100ull, 0x0002027C02020200ull, 0x0004047A04040400ull, 0x0008087608080800ull,
0x0010106E10101000ull, 0x0020205E20202000ull, 0x0040403E40404000ull, 0x0080807E80808000ull,
0x00017E0101010100ull, 0x00027C0202020200ull, 0x00047A0404040400ull, 0x0008760808080800ull,
0x00106E1010101000ull, 0x00205E2020202000ull, 0x00403E4040404000ull, 0x00807E8080808000ull,
0x007E010101010100ull, 0x007C020202020200ull, 0x007A040404040400ull, 0x0076080808080800ull,
0x006E101010101000ull, 0x005E202020202000ull, 0x003E404040404000ull, 0x007E808080808000ull,
0x7E01010101010100ull, 0x7C02020202020200ull, 0x7A04040404040400ull, 0x7608080808080800ull,
0x6E10101010101000ull, 0x5E20202020202000ull, 0x3E40404040404000ull, 0x7E80808080808000ull
};
const unsigned magic_bb_b_shift[64] = {
58, 59, 59, 59, 59, 59, 59, 58,
59, 59, 59, 59, 59, 59, 59, 59,
59, 59, 57, 57, 57, 57, 59, 59,
59, 59, 57, 55, 55, 57, 59, 59,
59, 59, 57, 55, 55, 57, 59, 59,
59, 59, 57, 57, 57, 57, 59, 59,
59, 59, 59, 59, 59, 59, 59, 59,
58, 59, 59, 59, 59, 59, 59, 58
};
const uint64_t magic_bb_b_magics[64] = {
0x0002020202020200ull, 0x0002020202020000ull, 0x0004010202000000ull, 0x0004040080000000ull,
0x0001104000000000ull, 0x0000821040000000ull, 0x0000410410400000ull, 0x0000104104104000ull,
0x0000040404040400ull, 0x0000020202020200ull, 0x0000040102020000ull, 0x0000040400800000ull,
0x0000011040000000ull, 0x0000008210400000ull, 0x0000004104104000ull, 0x0000002082082000ull,
0x0004000808080800ull, 0x0002000404040400ull, 0x0001000202020200ull, 0x0000800802004000ull,
0x0000800400A00000ull, 0x0000200100884000ull, 0x0000400082082000ull, 0x0000200041041000ull,
0x0002080010101000ull, 0x0001040008080800ull, 0x0000208004010400ull, 0x0000404004010200ull,
0x0000840000802000ull, 0x0000404002011000ull, 0x0000808001041000ull, 0x0000404000820800ull,
0x0001041000202000ull, 0x0000820800101000ull, 0x0000104400080800ull, 0x0000020080080080ull,
0x0000404040040100ull, 0x0000808100020100ull, 0x0001010100020800ull, 0x0000808080010400ull,
0x0000820820004000ull, 0x0000410410002000ull, 0x0000082088001000ull, 0x0000002011000800ull,
0x0000080100400400ull, 0x0001010101000200ull, 0x0002020202000400ull, 0x0001010101000200ull,
0x0000410410400000ull, 0x0000208208200000ull, 0x0000002084100000ull, 0x0000000020880000ull,
0x0000001002020000ull, 0x0000040408020000ull, 0x0004040404040000ull, 0x0002020202020000ull,
0x0000104104104000ull, 0x0000002082082000ull, 0x0000000020841000ull, 0x0000000000208800ull,
0x0000000010020200ull, 0x0000000404080200ull, 0x0000040404040400ull, 0x0002020202020200ull
};
const uint64_t magic_bb_b_mask[64] = {
0x0040201008040200ull, 0x0000402010080400ull, 0x0000004020100A00ull, 0x0000000040221400ull,
0x0000000002442800ull, 0x0000000204085000ull, 0x0000020408102000ull, 0x0002040810204000ull,
0x0020100804020000ull, 0x0040201008040000ull, 0x00004020100A0000ull, 0x0000004022140000ull,
0x0000000244280000ull, 0x0000020408500000ull, 0x0002040810200000ull, 0x0004081020400000ull,
0x0010080402000200ull, 0x0020100804000400ull, 0x004020100A000A00ull, 0x0000402214001400ull,
0x0000024428002800ull, 0x0002040850005000ull, 0x0004081020002000ull, 0x0008102040004000ull,
0x0008040200020400ull, 0x0010080400040800ull, 0x0020100A000A1000ull, 0x0040221400142200ull,
0x0002442800284400ull, 0x0004085000500800ull, 0x0008102000201000ull, 0x0010204000402000ull,
0x0004020002040800ull, 0x0008040004081000ull, 0x00100A000A102000ull, 0x0022140014224000ull,
0x0044280028440200ull, 0x0008500050080400ull, 0x0010200020100800ull, 0x0020400040201000ull,
0x0002000204081000ull, 0x0004000408102000ull, 0x000A000A10204000ull, 0x0014001422400000ull,
0x0028002844020000ull, 0x0050005008040200ull, 0x0020002010080400ull, 0x0040004020100800ull,
0x0000020408102000ull, 0x0000040810204000ull, 0x00000A1020400000ull, 0x0000142240000000ull,
0x0000284402000000ull, 0x0000500804020000ull, 0x0000201008040200ull, 0x0000402010080400ull,
0x0002040810204000ull, 0x0004081020400000ull, 0x000A102040000000ull, 0x0014224000000000ull,
0x0028440200000000ull, 0x0050080402000000ull, 0x0020100804020000ull, 0x0040201008040200ull
};
uint64_t magic_bb_r_db[0x19000];
uint64_t magic_bb_b_db[0x1480];
const uint64_t* magic_bb_b_indices[64] = {
magic_bb_b_db+4992, magic_bb_b_db+2624, magic_bb_b_db+256, magic_bb_b_db+896,
magic_bb_b_db+1280, magic_bb_b_db+1664, magic_bb_b_db+4800, magic_bb_b_db+5120,
magic_bb_b_db+2560, magic_bb_b_db+2656, magic_bb_b_db+288, magic_bb_b_db+928,
magic_bb_b_db+1312, magic_bb_b_db+1696, magic_bb_b_db+4832, magic_bb_b_db+4928,
magic_bb_b_db+0, magic_bb_b_db+128, magic_bb_b_db+320, magic_bb_b_db+960,
magic_bb_b_db+1344, magic_bb_b_db+1728, magic_bb_b_db+2304, magic_bb_b_db+2432,
magic_bb_b_db+32, magic_bb_b_db+160, magic_bb_b_db+448, magic_bb_b_db+2752,
magic_bb_b_db+3776, magic_bb_b_db+1856, magic_bb_b_db+2336, magic_bb_b_db+2464,
magic_bb_b_db+64, magic_bb_b_db+192, magic_bb_b_db+576, magic_bb_b_db+3264,
magic_bb_b_db+4288, magic_bb_b_db+1984, magic_bb_b_db+2368, magic_bb_b_db+2496,
magic_bb_b_db+96, magic_bb_b_db+224, magic_bb_b_db+704, magic_bb_b_db+1088,
magic_bb_b_db+1472, magic_bb_b_db+2112, magic_bb_b_db+2400, magic_bb_b_db+2528,
magic_bb_b_db+2592, magic_bb_b_db+2688, magic_bb_b_db+832, magic_bb_b_db+1216,
magic_bb_b_db+1600, magic_bb_b_db+2240, magic_bb_b_db+4864, magic_bb_b_db+4960,
magic_bb_b_db+5056, magic_bb_b_db+2720, magic_bb_b_db+864, magic_bb_b_db+1248,
magic_bb_b_db+1632, magic_bb_b_db+2272, magic_bb_b_db+4896, magic_bb_b_db+5184
};
const uint64_t* magic_bb_r_indices[64] = {
magic_bb_r_db+86016, magic_bb_r_db+73728, magic_bb_r_db+36864, magic_bb_r_db+43008,
magic_bb_r_db+47104, magic_bb_r_db+51200, magic_bb_r_db+77824, magic_bb_r_db+94208,
magic_bb_r_db+69632, magic_bb_r_db+32768, magic_bb_r_db+38912, magic_bb_r_db+10240,
magic_bb_r_db+14336, magic_bb_r_db+53248, magic_bb_r_db+57344, magic_bb_r_db+81920,
magic_bb_r_db+24576, magic_bb_r_db+33792, magic_bb_r_db+6144, magic_bb_r_db+11264,
magic_bb_r_db+15360, magic_bb_r_db+18432, magic_bb_r_db+58368, magic_bb_r_db+61440,
magic_bb_r_db+26624, magic_bb_r_db+4096, magic_bb_r_db+7168, magic_bb_r_db+0,
magic_bb_r_db+2048, magic_bb_r_db+19456, magic_bb_r_db+22528, magic_bb_r_db+63488,
magic_bb_r_db+28672, magic_bb_r_db+5120, magic_bb_r_db+8192, magic_bb_r_db+1024,
magic_bb_r_db+3072, magic_bb_r_db+20480, magic_bb_r_db+23552, magic_bb_r_db+65536,
magic_bb_r_db+30720, magic_bb_r_db+34816, magic_bb_r_db+9216, magic_bb_r_db+12288,
magic_bb_r_db+16384, magic_bb_r_db+21504, magic_bb_r_db+59392, magic_bb_r_db+67584,
magic_bb_r_db+71680, magic_bb_r_db+35840, magic_bb_r_db+39936, magic_bb_r_db+13312,
magic_bb_r_db+17408, magic_bb_r_db+54272, magic_bb_r_db+60416, magic_bb_r_db+83968,
magic_bb_r_db+90112, magic_bb_r_db+75776, magic_bb_r_db+40960, magic_bb_r_db+45056,
magic_bb_r_db+49152, magic_bb_r_db+55296, magic_bb_r_db+79872, magic_bb_r_db+98304
};
static uint64_t init_magic_bb_r(unsigned sq, uint64_t occ);
static uint64_t init_magic_bb_occ(const unsigned *sq, unsigned numSq, uint64_t linocc);
static uint64_t init_magic_bb_b(unsigned sq, uint64_t occ);
void init_magics()
{
const unsigned init_magic_bitpos64_db[64] = {
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5
};
uint64_t* const magic_bb_b_indices2[64] = {
magic_bb_b_db+4992, magic_bb_b_db+2624, magic_bb_b_db+256,
magic_bb_b_db+896, magic_bb_b_db+1280, magic_bb_b_db+1664,
magic_bb_b_db+4800, magic_bb_b_db+5120, magic_bb_b_db+2560,
magic_bb_b_db+2656, magic_bb_b_db+288, magic_bb_b_db+928,
magic_bb_b_db+1312, magic_bb_b_db+1696, magic_bb_b_db+4832,
magic_bb_b_db+4928, magic_bb_b_db+0, magic_bb_b_db+128,
magic_bb_b_db+320, magic_bb_b_db+960, magic_bb_b_db+1344,
magic_bb_b_db+1728, magic_bb_b_db+2304, magic_bb_b_db+2432,
magic_bb_b_db+32, magic_bb_b_db+160, magic_bb_b_db+448,
magic_bb_b_db+2752, magic_bb_b_db+3776, magic_bb_b_db+1856,
magic_bb_b_db+2336, magic_bb_b_db+2464, magic_bb_b_db+64,
magic_bb_b_db+192, magic_bb_b_db+576, magic_bb_b_db+3264,
magic_bb_b_db+4288, magic_bb_b_db+1984, magic_bb_b_db+2368,
magic_bb_b_db+2496, magic_bb_b_db+96, magic_bb_b_db+224,
magic_bb_b_db+704, magic_bb_b_db+1088, magic_bb_b_db+1472,
magic_bb_b_db+2112, magic_bb_b_db+2400, magic_bb_b_db+2528,
magic_bb_b_db+2592, magic_bb_b_db+2688, magic_bb_b_db+832,
magic_bb_b_db+1216, magic_bb_b_db+1600, magic_bb_b_db+2240,
magic_bb_b_db+4864, magic_bb_b_db+4960, magic_bb_b_db+5056,
magic_bb_b_db+2720, magic_bb_b_db+864, magic_bb_b_db+1248,
magic_bb_b_db+1632, magic_bb_b_db+2272, magic_bb_b_db+4896,
magic_bb_b_db+5184
};
uint64_t* const magic_bb_r_indices2[64] = {
magic_bb_r_db+86016, magic_bb_r_db+73728, magic_bb_r_db+36864,
magic_bb_r_db+43008, magic_bb_r_db+47104, magic_bb_r_db+51200,
magic_bb_r_db+77824, magic_bb_r_db+94208, magic_bb_r_db+69632,
magic_bb_r_db+32768, magic_bb_r_db+38912, magic_bb_r_db+10240,
magic_bb_r_db+14336, magic_bb_r_db+53248, magic_bb_r_db+57344,
magic_bb_r_db+81920, magic_bb_r_db+24576, magic_bb_r_db+33792,
magic_bb_r_db+6144, magic_bb_r_db+11264, magic_bb_r_db+15360,
magic_bb_r_db+18432, magic_bb_r_db+58368, magic_bb_r_db+61440,
magic_bb_r_db+26624, magic_bb_r_db+4096, magic_bb_r_db+7168,
magic_bb_r_db+0, magic_bb_r_db+2048, magic_bb_r_db+19456,
magic_bb_r_db+22528, magic_bb_r_db+63488, magic_bb_r_db+28672,
magic_bb_r_db+5120, magic_bb_r_db+8192, magic_bb_r_db+1024,
magic_bb_r_db+3072, magic_bb_r_db+20480, magic_bb_r_db+23552,
magic_bb_r_db+65536, magic_bb_r_db+30720, magic_bb_r_db+34816,
magic_bb_r_db+9216, magic_bb_r_db+12288, magic_bb_r_db+16384,
magic_bb_r_db+21504, magic_bb_r_db+59392, magic_bb_r_db+67584,
magic_bb_r_db+71680, magic_bb_r_db+35840, magic_bb_r_db+39936,
magic_bb_r_db+13312, magic_bb_r_db+17408, magic_bb_r_db+54272,
magic_bb_r_db+60416, magic_bb_r_db+83968, magic_bb_r_db+90112,
magic_bb_r_db+75776, magic_bb_r_db+40960, magic_bb_r_db+45056,
magic_bb_r_db+49152, magic_bb_r_db+55296, magic_bb_r_db+79872,
magic_bb_r_db+98304
};
for(unsigned i = 0; i < 64; i++) {
unsigned sq[64];
unsigned numSq = 0;
uint64_t temp = magic_bb_b_mask[i];
while(temp) {
uint64_t bit = temp & -temp;
sq[numSq++] = init_magic_bitpos64_db[(bit * 0x07EDD5E59A4E28C2ull) >> 58];
temp ^= bit;
}
for(temp = 0; temp < (1ULL << numSq); temp++) {
uint64_t tempocc = init_magic_bb_occ(sq, numSq, temp);
*(magic_bb_b_indices2[i] + ((tempocc * magic_bb_b_magics[i]) >> magic_bb_b_shift[i])) =
init_magic_bb_b(i,tempocc);
}
}
for(unsigned i = 0; i < 64; i++) {
unsigned sq[64];
unsigned numSq = 0;
uint64_t temp = magic_bb_r_mask[i];
while(temp) {
uint64_t bit = temp & -temp;
sq[numSq++] = init_magic_bitpos64_db[(bit * 0x07EDD5E59A4E28C2ull) >> 58];
temp ^= bit;
}
for(temp = 0; temp < (1ULL << numSq); temp++) {
uint64_t tempocc = init_magic_bb_occ(sq, numSq, temp);
*(magic_bb_r_indices2[i] + ((tempocc * magic_bb_r_magics[i]) >> magic_bb_r_shift[i])) =
init_magic_bb_r(i, tempocc);
}
}
MagicInitialized = true;
}
static uint64_t init_magic_bb_r(unsigned sq, uint64_t occ)
{
uint64_t ret = 0;
uint64_t bit;
uint64_t rowbits = 0xFFULL << (sq & ~7);
bit = 1ULL << sq;
do {
bit <<= 8;
ret |= bit;
} while (bit && !(bit & occ));
bit = 1ULL << sq;
do {
bit >>= 8;
ret |= bit;
} while(bit && !(bit & occ));
bit = 1ULL << sq;
do {
bit<<=1;
if(bit&rowbits)
ret |= bit;
else
break;
} while (!(bit & occ));
bit = 1ULL << sq;
do {
bit >>= 1;
if (bit & rowbits)
ret |= bit;
else
break;
} while (!(bit & occ));
return ret;
}
static uint64_t init_magic_bb_b(unsigned sq, uint64_t occ)
{
uint64_t ret = 0;
uint64_t bit, bit2;
uint64_t rowbits = 0xFFULL << (sq & ~7);
bit = 1ULL << sq;
bit2 = bit;
do {
bit <<= 8-1;
bit2 >>= 1;
if (bit2 & rowbits)
ret |= bit;
else
break;
} while(bit && !(bit & occ));
bit = 1ULL << sq;
bit2 = bit;
do {
bit <<= 8+1;
bit2 <<= 1;
if (bit2 & rowbits)
ret |= bit;
else
break;
} while (bit && !(bit & occ));
bit = 1ULL << sq;
bit2 = bit;
do {
bit >>= 8-1;
bit2 <<= 1;
if (bit2 & rowbits)
ret |= bit;
else
break;
} while(bit && !(bit & occ));
bit = 1ULL << sq;
bit2 = bit;
do {
bit >>= 8+1;
bit2 >>= 1;
if (bit2 & rowbits)
ret |= bit;
else
break;
} while (bit && !(bit & occ));
return ret;
}
static uint64_t init_magic_bb_occ(const unsigned* sq, unsigned numSq, uint64_t linocc)
{
uint64_t ret = 0;
for(unsigned i = 0; i < numSq; i++)
if (linocc & (1ULL << i))
ret |= 1ULL << sq[i];
return ret;
}
uint64_t bishop_attack(unsigned sq, uint64_t occ)
/* returns the set of squares attacked by a bishop on sq, for a given occupancy bitboard */
{
assert(MagicInitialized && sq < 64);
return *(magic_bb_b_indices[sq]
+ (((occ & magic_bb_b_mask[sq]) * magic_bb_b_magics[sq]) >> magic_bb_b_shift[sq]));
}
uint64_t rook_attack(unsigned sq, uint64_t occ)
/* returns the set of squares attacked by a rook on sq, for a given occupancy bitboard */
{
assert(MagicInitialized && sq < 64);
return *(magic_bb_r_indices[sq]
+ (((occ & magic_bb_r_mask[sq]) * magic_bb_r_magics[sq]) >> magic_bb_r_shift[sq]));
}-
ZirconiumX
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Project help required: Bitboard Fruit 2.1
@Sven
Fixed. Have also shrunk the bitboards[] array to a managable 10 (2 colours, 6 pieces, empty, occupied).
@Lucas
Will add the assert()'s, and the initialized quick escape (though the magics are on top priority, initialized in main.cpp before UCI is even started)
So, list of optimization:
Fixed. Have also shrunk the bitboards[] array to a managable 10 (2 colours, 6 pieces, empty, occupied).
@Lucas
Will add the assert()'s, and the initialized quick escape (though the magics are on top priority, initialized in main.cpp before UCI is even started)
So, list of optimization:
- Move Generator - should give Fruit a shot in the arm or two. (+50 Elo?)
- Looped Eval() - basically taking what fruit does already and providing a binary equivalent (+20 Elo?)
- Loopless Eval() (+10 Elo?)
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
hgm
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Project help required: Bitboard Fruit 2.1
A pest?Chess is to computing as Drosophila Melanogaster is to biology.
-
ZirconiumX
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Project help required: Bitboard Fruit 2.1
OK - new version to be found exactly where you found the old one (first page, first post)
I have tested this version, and despite the new piece move generator (pawns are the same) it seems a) slower and b) wrong. By wrong I mean the eval is somehow all messed up (even when I refreshed the eval) and does not produce the same results (i.e. PV) as mailbox fruit.
Let me demonstrate:
Mailbox:
Score : +0.10
Depth : 13/1
Time : 00:00:30
Nodes : 5050000
N/sec : 167218
1. Nf3 Nc6 2. Nc3 Nf6 3. d4 d5 4. Ne5 Bf5 5. Nxc6 bxc6 6. Bf4 Rb8 7. b3
Bitboard (ish):
Score : +0.26
Depth : 16/1
Time : 00:00:30
Nodes : 5230000
N/sec : 172892
1. Nc3 b5 2. a3 c5 3. b4 d5 4. d4 c4 5. e4 dxe4 6. f3 exf3 7. Nxf3 a6 8. a4 e6 9. axb5 Bxb4
Now I think you would agree that either the MG is at fault (which it probably isn't) or the Eval of Fruit can't handle that speed, and the the PV of the Bitboard version is ugly.
Now I am going to run 10 quick tests between bitboard and mailbox, and will report back.
Matthew:out
I have tested this version, and despite the new piece move generator (pawns are the same) it seems a) slower and b) wrong. By wrong I mean the eval is somehow all messed up (even when I refreshed the eval) and does not produce the same results (i.e. PV) as mailbox fruit.
Let me demonstrate:
Mailbox:
Score : +0.10
Depth : 13/1
Time : 00:00:30
Nodes : 5050000
N/sec : 167218
1. Nf3 Nc6 2. Nc3 Nf6 3. d4 d5 4. Ne5 Bf5 5. Nxc6 bxc6 6. Bf4 Rb8 7. b3
Bitboard (ish):
Score : +0.26
Depth : 16/1
Time : 00:00:30
Nodes : 5230000
N/sec : 172892
1. Nc3 b5 2. a3 c5 3. b4 d5 4. d4 c4 5. e4 dxe4 6. f3 exf3 7. Nxf3 a6 8. a4 e6 9. axb5 Bxb4
Now I think you would agree that either the MG is at fault (which it probably isn't) or the Eval of Fruit can't handle that speed, and the the PV of the Bitboard version is ugly.
Now I am going to run 10 quick tests between bitboard and mailbox, and will report back.
Matthew:out
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
ZirconiumX
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Project help required: Bitboard Fruit 2.1
Ha Ha.
The FruitFly is useful to biology because it is easy to get a colony of them for testing.
Chess is useful to computing because it is easy to get an open source program, clone it and call it your own. (Ahem!)
Matthew:out
The FruitFly is useful to biology because it is easy to get a colony of them for testing.
Chess is useful to computing because it is easy to get an open source program, clone it and call it your own. (Ahem!)
Matthew:out
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
ZirconiumX
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Project help required: Bitboard Fruit 2.1
Ten quick tests aborted early becuase the bitboard version lost. Badly. (-3 =0 +0)
I am really confused.
Matthew:out
I am really confused.
Matthew:out
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
hgm
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Project help required: Bitboard Fruit 2.1
Ah yes, of course. They are easy to clone!ZirconiumX wrote:The FruitFly is useful to biology because it is easy to get a colony of them for testing.
But seriously: why do you expect them to be verydifferent? For not too different programs, 0-3 is no reason to abort a test. This can easily be bad luck. (0-30 would be another matter, of course.)
I noticed that for the two PVs you printed, the depth is different (13 vs 16). So that the PVs are different then does not have to be an error. But of course it is a bit suspect that the depth is so different with so nearly-equal node counts.
-
syzygy
- Posts: 5565
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Project help required: Bitboard Fruit 2.1
If the only thing you have changed is the MG, then certainly the MG is at fault, buf of course it cannot be excluded that you inadvertently introduced changes/bugs in other parts of the code.ZirconiumX wrote:Now I think you would agree that either the MG is at fault (which it probably isn't) or the Eval of Fruit can't handle that speed, and the the PV of the Bitboard version is ugly.
Note that a program won't suddenly search 3 plies deeper in about the same number of nodes if you only replace the MG by another (correct) MG.
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Project help required: Bitboard Fruit 2.1
Again, I suggest to implement a "perft" function (original Fruit does not have it yet) and find the move generator bugs.ZirconiumX wrote:Ten quick tests aborted early becuase the bitboard version lost. Badly. (-3 =0 +0)
I am really confused.
This is an example of a "perft" implementation for Fruit which I wrote:
Code: Select all
// perft.cpp
#include "attack.h"
#include "board.h"
#include "colour.h"
#include "list.h"
#include "move.h"
#include "move_check.h"
#include "move_do.h"
#include "piece.h"
#include "search.h"
#include "sort.h"
#include "util.h"
uint64 perft(board_t * board, int depth, int height)
{
int trans_move;
uint64 nLeaves;
int move;
attack_t attack[1];
sort_t sort[1];
undo_t undo[1];
ASSERT(board!=NULL);
ASSERT(depth_is_ok(depth));
ASSERT(board_is_legal(board));
// init
SearchCurrent->node_nb++;
SearchInfo->check_nb--;
if (depth == 0) return 1;
// more init
attack_set(attack,board);
// move generation
trans_move = MoveNone;
sort_init(sort,board,attack,depth,height,trans_move);
// move loop
nLeaves = 0;
while ((move=sort_next(sort)) != MoveNone) {
// recursive search
move_do(board,move,undo);
nLeaves += perft(board, depth - 1, height + 1);
move_undo(board,move,undo);
}
return nLeaves;
}
uint64 perft_root(list_t * list, board_t * board, int depth, int height)
{
uint64 nLeaves;
int move;
int i;
attack_t attack[1];
undo_t undo[1];
ASSERT(list_is_ok(list));
ASSERT(board!=NULL);
ASSERT(depth_is_ok(depth));
ASSERT(list==SearchRoot->list);
ASSERT(board==SearchCurrent->board);
ASSERT(board_is_legal(board));
// init
SearchCurrent->node_nb++;
SearchInfo->check_nb--;
if (depth == 0) return 1;
// more init
attack_set(attack,board);
// move loop
nLeaves = 0;
for (i = 0; i < LIST_SIZE(list); i++) {
move = LIST_MOVE(list,i);
// recursive search
move_do(board,move,undo);
nLeaves += perft(board, depth - 1, height + 1);
move_undo(board,move,undo);
}
return nLeaves;
}Code: Select all
// perft.h
#ifndef PERFT_H
#define PERFT_H
// includes
#include "util.h"
// forward declarations
struct board_t;
// functions
extern uint64 perft_root(list_t * list, board_t * board, int depth, int height);
#endif // !defined PERFT_H
// end of perft.hCode: Select all
// protocol.cpp
// ...
#include "perft.h"
#include "move_gen.h"
#include "sort.h"
// ...
// loop_step()
// ...
} else if (string_start_with(string,"perft ")) {
const char * ptr = strtok(string," "); // skip "perft"
ptr = strtok(NULL," ");
int depth = atoi(ptr);
SearchCurrent->node_nb = 0;
send("starting perft(%d)", depth);
// SearchInput
gen_legal_moves(SearchInput->list,SearchInput->board);
// SearchRoot
list_copy(SearchRoot->list,SearchInput->list);
// SearchCurrent
board_copy(SearchCurrent->board,SearchInput->board);
my_timer_reset(SearchCurrent->timer);
my_timer_start(SearchCurrent->timer);
sort_init();
// standard sort
list_note(SearchRoot->list);
list_sort(SearchRoot->list);
uint64 nLeaves = perft_root(SearchRoot->list,SearchCurrent->board, depth, 0);
my_timer_stop(SearchCurrent->timer);
search_update_current();
send("perft(%d)=%I64u, %I64u nodes, time=%.3f",
depth, nLeaves, SearchCurrent->node_nb, my_timer_elapsed_real(SearchCurrent->timer));
}Code: Select all
perft(2)=320 .....
perft(3)=4758 .....
perft(4)=71813 .....
perft(5)=1011120 .....
perft(6)=14463120 .....I used the same "perft" for the original Fruit, it produces the correct numbers for the start position. So there must be a problem in your move generator changes or your make/unmake move changes.
Sven