Project help required: Bitboard Fruit 2.1

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Sven
Posts: 3858
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Project help required: Bitboard Fruit 2.1

Post by Sven » Wed May 09, 2012 3:27 pm

ZirconiumX wrote:Yay!

The SQUARE_TO_64() macro saved it, thanks Sven!

Matthew:out
Ok, good to know that. And what about the possible board corruption I reported in the other mail regarding square_clear() vs. square_set()?

Sven

User avatar
lucasart
Posts: 3109
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Project help required: Bitboard Fruit 2.1

Post by lucasart » Thu May 10, 2012 10:51 am

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
Here's the magic code from Umko slightely rewritten, and reduced to its barebone:
* 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&#58;//www.gnu.org/licenses/>.
 * 
 * Credits&#58; All magic bitboard code is a &#40;almost&#41; 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&#40;);
extern bool MagicInitialized;

/* Squares attacked by a bishop/rook for a given board occupancy */
extern uint64_t bishop_attack&#40;unsigned sq, uint64_t occ&#41;;
extern uint64_t rook_attack&#40;unsigned sq, uint64_t occ&#41;;
magic.c

Code: Select all

/*
 * DoubleCheck, a UCI chess playing engine. Copyright &#40;C&#41; 2011 Lucas Braesch.
 *
 * DoubleCheck is free software&#58; 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 &#40;at your option&#41; 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&#58;//www.gnu.org/licenses/>.
 *
 * Credits&#58; All magic bitboard code is a &#40;almost&#41; 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&#91;64&#93; = &#123;
	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
&#125;;

const uint64_t magic_bb_r_magics&#91;64&#93; = &#123;
	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
&#125;;

const uint64_t magic_bb_r_mask&#91;64&#93; = &#123;
	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
&#125;;

const unsigned magic_bb_b_shift&#91;64&#93; = &#123;
	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
&#125;;

const uint64_t magic_bb_b_magics&#91;64&#93; = &#123;
	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
&#125;;

const uint64_t magic_bb_b_mask&#91;64&#93; = &#123;
	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
&#125;;

uint64_t magic_bb_r_db&#91;0x19000&#93;;
uint64_t magic_bb_b_db&#91;0x1480&#93;;

const uint64_t* magic_bb_b_indices&#91;64&#93; = &#123;
	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
&#125;;

const uint64_t* magic_bb_r_indices&#91;64&#93; = &#123;
	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
&#125;;

static uint64_t init_magic_bb_r&#40;unsigned sq, uint64_t occ&#41;;
static uint64_t init_magic_bb_occ&#40;const unsigned *sq, unsigned numSq, uint64_t linocc&#41;;
static uint64_t init_magic_bb_b&#40;unsigned sq, uint64_t occ&#41;;

void init_magics&#40;)
&#123;
	const unsigned init_magic_bitpos64_db&#91;64&#93; = &#123;
		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
	&#125;;

	uint64_t* const magic_bb_b_indices2&#91;64&#93; = &#123;
		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
	&#125;;

	uint64_t* const magic_bb_r_indices2&#91;64&#93; = &#123;
		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
	&#125;;

	for&#40;unsigned i = 0; i < 64; i++) &#123;
		unsigned sq&#91;64&#93;;
		unsigned numSq = 0;
		uint64_t temp = magic_bb_b_mask&#91;i&#93;;
		while&#40;temp&#41; &#123;
			uint64_t bit = temp & -temp;
			sq&#91;numSq++&#93; = init_magic_bitpos64_db&#91;&#40;bit * 0x07EDD5E59A4E28C2ull&#41; >> 58&#93;;
			temp ^= bit;
		&#125;
		for&#40;temp = 0; temp < &#40;1ULL << numSq&#41;; temp++) &#123;
			uint64_t tempocc = init_magic_bb_occ&#40;sq, numSq, temp&#41;;
			*&#40;magic_bb_b_indices2&#91;i&#93; + (&#40;tempocc * magic_bb_b_magics&#91;i&#93;) >> magic_bb_b_shift&#91;i&#93;)) =
				init_magic_bb_b&#40;i,tempocc&#41;;
		&#125;
	&#125;

	for&#40;unsigned i = 0; i < 64; i++) &#123;
		unsigned sq&#91;64&#93;;
		unsigned numSq = 0;
		uint64_t temp = magic_bb_r_mask&#91;i&#93;;
		while&#40;temp&#41; &#123;
			uint64_t bit = temp & -temp;
			sq&#91;numSq++&#93; = init_magic_bitpos64_db&#91;&#40;bit * 0x07EDD5E59A4E28C2ull&#41; >> 58&#93;;
			temp ^= bit;
		&#125;
		for&#40;temp = 0; temp < &#40;1ULL << numSq&#41;; temp++) &#123;
			uint64_t tempocc = init_magic_bb_occ&#40;sq, numSq, temp&#41;;
			*&#40;magic_bb_r_indices2&#91;i&#93; + (&#40;tempocc * magic_bb_r_magics&#91;i&#93;) >> magic_bb_r_shift&#91;i&#93;)) =
				init_magic_bb_r&#40;i, tempocc&#41;;
		&#125;
	&#125;
	
	MagicInitialized = true;
&#125;

static uint64_t init_magic_bb_r&#40;unsigned sq, uint64_t occ&#41;
&#123;
	uint64_t ret = 0;
	uint64_t bit;
	uint64_t rowbits = 0xFFULL << &#40;sq & ~7&#41;;

	bit = 1ULL << sq;
	do &#123;
		bit <<= 8;
		ret |= bit;
	&#125; while &#40;bit && !&#40;bit & occ&#41;);
	
	bit = 1ULL << sq;
	do &#123;
		bit >>= 8;
		ret |= bit;
	&#125; while&#40;bit && !&#40;bit & occ&#41;);
	
	bit = 1ULL << sq;
	do &#123;
		bit<<=1;
		if&#40;bit&rowbits&#41;
			ret |= bit;
		else
			break;
	&#125; while (!&#40;bit & occ&#41;);
	
	bit = 1ULL << sq;
	do &#123;
		bit >>= 1;
		if &#40;bit & rowbits&#41;
			ret |= bit;
		else
			break;
	&#125; while (!&#40;bit & occ&#41;);
	return ret;
&#125;

static uint64_t init_magic_bb_b&#40;unsigned sq, uint64_t occ&#41;
&#123;
	uint64_t ret = 0;
	uint64_t bit, bit2;
	uint64_t rowbits = 0xFFULL << &#40;sq & ~7&#41;;

	bit = 1ULL << sq;
	bit2 = bit;
	do &#123;
		bit <<= 8-1;
		bit2 >>= 1;
		if &#40;bit2 & rowbits&#41;
			ret |= bit;
		else
			break;
	&#125; while&#40;bit && !&#40;bit & occ&#41;);
	
	bit = 1ULL << sq;
	bit2 = bit;
	do &#123;
		bit <<= 8+1;
		bit2 <<= 1;
		if &#40;bit2 & rowbits&#41;
			ret |= bit;
		else
			break;
	&#125; while &#40;bit && !&#40;bit & occ&#41;);
	
	bit = 1ULL << sq;
	bit2 = bit;
	do &#123;
		bit >>= 8-1;
		bit2 <<= 1;
		if &#40;bit2 & rowbits&#41;
			ret |= bit;
		else
			break;
	&#125; while&#40;bit && !&#40;bit & occ&#41;);
	
	bit = 1ULL << sq;
	bit2 = bit;
	do &#123;
		bit >>= 8+1;
		bit2 >>= 1;
		if &#40;bit2 & rowbits&#41;
			ret |= bit;
		else
			break;
	&#125; while &#40;bit && !&#40;bit & occ&#41;);
	
	return ret;
&#125;

static uint64_t init_magic_bb_occ&#40;const unsigned* sq, unsigned numSq, uint64_t linocc&#41;
&#123;
	uint64_t ret = 0;
	for&#40;unsigned i = 0; i < numSq; i++)
		if &#40;linocc & &#40;1ULL << i&#41;)
			ret |= 1ULL << sq&#91;i&#93;;
	return ret;
&#125;

uint64_t bishop_attack&#40;unsigned sq, uint64_t occ&#41;
/* returns the set of squares attacked by a bishop on sq, for a given occupancy bitboard */
&#123;
	assert&#40;MagicInitialized && sq < 64&#41;;
	return *&#40;magic_bb_b_indices&#91;sq&#93;
		+ ((&#40;occ & magic_bb_b_mask&#91;sq&#93;) * magic_bb_b_magics&#91;sq&#93;) >> magic_bb_b_shift&#91;sq&#93;));
&#125;

uint64_t rook_attack&#40;unsigned sq, uint64_t occ&#41;
/* returns the set of squares attacked by a rook on sq, for a given occupancy bitboard */
&#123;
	assert&#40;MagicInitialized && sq < 64&#41;;
	return *&#40;magic_bb_r_indices&#91;sq&#93;
		+ ((&#40;occ & magic_bb_r_mask&#91;sq&#93;) * magic_bb_r_magics&#91;sq&#93;) >> magic_bb_r_shift&#91;sq&#93;));
&#125;

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Project help required: Bitboard Fruit 2.1

Post by ZirconiumX » Thu May 10, 2012 1:32 pm

@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:
  • 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?)
Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

User avatar
hgm
Posts: 24651
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Project help required: Bitboard Fruit 2.1

Post by hgm » Thu May 10, 2012 2:47 pm

Chess is to computing as Drosophila Melanogaster is to biology.
A pest? :roll:

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Project help required: Bitboard Fruit 2.1

Post by ZirconiumX » Thu May 10, 2012 3:06 pm

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
Some believe in the almighty dollar.

I believe in the almighty printf statement.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Project help required: Bitboard Fruit 2.1

Post by ZirconiumX » Thu May 10, 2012 3:11 pm

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
Some believe in the almighty dollar.

I believe in the almighty printf statement.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Project help required: Bitboard Fruit 2.1

Post by ZirconiumX » Thu May 10, 2012 3:14 pm

Ten quick tests aborted early becuase the bitboard version lost. Badly. (-3 =0 +0)

I am really confused.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

User avatar
hgm
Posts: 24651
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Project help required: Bitboard Fruit 2.1

Post by hgm » Thu May 10, 2012 3:25 pm

ZirconiumX wrote:The FruitFly is useful to biology because it is easy to get a colony of them for testing.
Ah yes, of course. They are easy to clone! :lol:

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: 4598
Joined: Tue Feb 28, 2012 10:56 pm

Re: Project help required: Bitboard Fruit 2.1

Post by syzygy » Thu May 10, 2012 6:42 pm

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.
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.

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: 3858
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Project help required: Bitboard Fruit 2.1

Post by Sven » Thu May 10, 2012 11:06 pm

ZirconiumX wrote:Ten quick tests aborted early becuase the bitboard version lost. Badly. (-3 =0 +0)

I am really confused.
Again, I suggest to implement a "perft" function (original Fruit does not have it yet) and find the move generator bugs.

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&#40;board_t * board, int depth, int height&#41;
&#123;
   int trans_move;
   uint64 nLeaves;
   int move;
   attack_t attack&#91;1&#93;;
   sort_t sort&#91;1&#93;;
   undo_t undo&#91;1&#93;;

   ASSERT&#40;board!=NULL&#41;;
   ASSERT&#40;depth_is_ok&#40;depth&#41;);
   ASSERT&#40;board_is_legal&#40;board&#41;);

   // init
   SearchCurrent->node_nb++;
   SearchInfo->check_nb--;

   if &#40;depth == 0&#41; return 1;

   // more init
   attack_set&#40;attack,board&#41;;

   // move generation
   trans_move = MoveNone;
   sort_init&#40;sort,board,attack,depth,height,trans_move&#41;;

   // move loop
   nLeaves = 0;
   while (&#40;move=sort_next&#40;sort&#41;) != MoveNone&#41; &#123;

      // recursive search
      move_do&#40;board,move,undo&#41;;
      nLeaves += perft&#40;board, depth - 1, height + 1&#41;;
      move_undo&#40;board,move,undo&#41;;
   &#125;

   return nLeaves;
&#125;

uint64 perft_root&#40;list_t * list, board_t * board, int depth, int height&#41;
&#123;
   uint64 nLeaves;
   int move;
   int i;
   attack_t attack&#91;1&#93;;
   undo_t undo&#91;1&#93;;

   ASSERT&#40;list_is_ok&#40;list&#41;);
   ASSERT&#40;board!=NULL&#41;;
   ASSERT&#40;depth_is_ok&#40;depth&#41;);
   ASSERT&#40;list==SearchRoot->list&#41;;
   ASSERT&#40;board==SearchCurrent->board&#41;;
   ASSERT&#40;board_is_legal&#40;board&#41;);

   // init
   SearchCurrent->node_nb++;
   SearchInfo->check_nb--;

   if &#40;depth == 0&#41; return 1;

   // more init
   attack_set&#40;attack,board&#41;;

   // move loop
   nLeaves = 0;
   for &#40;i = 0; i < LIST_SIZE&#40;list&#41;; i++) &#123;
      move = LIST_MOVE&#40;list,i&#41;;

      // recursive search
      move_do&#40;board,move,undo&#41;;
      nLeaves += perft&#40;board, depth - 1, height + 1&#41;;
      move_undo&#40;board,move,undo&#41;;
   &#125;

   return nLeaves;
&#125;

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&#40;list_t * list, board_t * board, int depth, int height&#41;;

#endif // !defined PERFT_H

// end of perft.h

Code: Select all

// protocol.cpp

// ...
#include "perft.h"
#include "move_gen.h"
#include "sort.h"
// ...

// loop_step&#40;)
// ...
   &#125; else if &#40;string_start_with&#40;string,"perft ")) &#123;

      const char * ptr = strtok&#40;string," "); // skip "perft"
      ptr = strtok&#40;NULL," ");
      int depth = atoi&#40;ptr&#41;;
      SearchCurrent->node_nb = 0;
      send&#40;"starting perft&#40;%d&#41;", depth&#41;;

      // SearchInput
      gen_legal_moves&#40;SearchInput->list,SearchInput->board&#41;;
      // SearchRoot
      list_copy&#40;SearchRoot->list,SearchInput->list&#41;;
      // SearchCurrent
      board_copy&#40;SearchCurrent->board,SearchInput->board&#41;;
      my_timer_reset&#40;SearchCurrent->timer&#41;;
      my_timer_start&#40;SearchCurrent->timer&#41;;
      sort_init&#40;);
      // standard sort
      list_note&#40;SearchRoot->list&#41;;
      list_sort&#40;SearchRoot->list&#41;;
      uint64 nLeaves = perft_root&#40;SearchRoot->list,SearchCurrent->board, depth, 0&#41;;
      my_timer_stop&#40;SearchCurrent->timer&#41;;
      search_update_current&#40;);

      send&#40;"perft&#40;%d&#41;=%I64u, %I64u nodes, time=%.3f",
          depth, nLeaves, SearchCurrent->node_nb, my_timer_elapsed_real&#40;SearchCurrent->timer&#41;);
   &#125;
It is possible that I did something wrong. But with the implementation above I get:

Code: Select all

perft&#40;2&#41;=320 .....
perft&#40;3&#41;=4758 .....
perft&#40;4&#41;=71813 .....
perft&#40;5&#41;=1011120 .....
perft&#40;6&#41;=14463120 .....
for the start position which is clearly wrong (way too low).

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

Post Reply