1 module shogi.bitboard; 2 import std.algorithm, std.conv, std.range, std.format, std.traits; 3 import shogi.constants; 4 import core.simd; 5 6 version(LDC) { 7 import ldc.gccbuiltins_x86, ldc.intrinsics; 8 uint bsf(T)(in T src) { return cast(uint) llvm_cttz(src, true); } 9 uint popCnt(T)(in T x) { return cast(uint) llvm_ctpop(x); } 10 } else { 11 import core.bitop; 12 alias popCnt = _popcnt; 13 } 14 15 struct BitwiseRange(T, uint offset = 0) if (isIntegral !(T)) { 16 T a; 17 this(T b) { a = b; } 18 bool empty() @property { return !cast(bool) a; } 19 uint front() @property { return bsf(a) + offset; } 20 void popFront() { a &= a - 1; } 21 } 22 23 union Bitboard { 24 import core.simd; 25 ulong[2] b; 26 ulong2 a; 27 28 this(in Bitboard bb) @nogc { this = bb; } 29 this(in ulong2 b) @nogc { a = b; } 30 this(in ulong b0, in ulong b1) @nogc { b = [ b0, b1 ]; } 31 this(in string str) { 32 import std.format, std..string; 33 assert(str.replace("_", "").length == 81); 34 (s => (s = s.replace("_", "")[17..81]).formattedRead("%b", &b[0]))(str.dup); 35 (s => (s = s.replace("_", "")[0_..64]).formattedRead("%b", &b[1]))(str.dup); 36 } 37 38 // operators 39 Bitboard opBinary(string op)(in Bitboard bb) @nogc const { 40 return __ctfe ? mixin("Bitboard(b[0]" ~op ~"bb.b[0],b[1]" ~op ~"bb.b[1])") : mixin("Bitboard(a" ~op ~"bb.a)"); 41 } 42 Bitboard opUnary(string op)() @nogc const if (op == "~") { return Bitboard(~a); } 43 ref Bitboard opOpAssign(string op)(in Bitboard bb) @nogc if (op != "=") { return this = opBinary !op(bb); } 44 version(LDC) bool opCast(T)() @nogc const if (is(T == bool)) { return !__builtin_ia32_ptestz128(a, a); } 45 version(DigitalMars) bool opCast(T)() @nogc const if (is(T == bool)) { return cast(bool)(b[0] | b[1]); } 46 Bitboard opBin(string op)(in int i) @nogc const { return mixin("Bitboard(b[0]" ~op ~"i,b[1]" ~op ~"i)"); } 47 48 uint popCnt() @nogc const { return.popCnt(b[0]) +.popCnt(b[1] & ~0x7FFFFFFFFFFFUL); } 49 uint lsb() @nogc const { return b[0] ? b[0].bsf() : (b[1].bsf() + 17); } 50 51 auto computeHash(in Bitboard mask) @nogc const { return ((((b[0] & mask.b[0]) << 4) | (b[1] & mask.b[1])) * 0x102040810204081UL) >> 57; } 52 mixin(q{ 53 Bitboard ATTACKS_XX(in uint sq) @nogc const { return _ATTACKS_XX[(sq << 7) | computeHash(_MASK_XX[sq])]; } 54 }.generateReplace("XX", [ "BKY", "WKY", "1199", "9119", "RANK", "FILE" ])); 55 Bitboard ATTACKS_HI(in uint sq) @nogc const { return ATTACKS_RANK(sq) | ATTACKS_FILE(sq); } 56 Bitboard ATTACKS_KA(in uint sq) @nogc const { return ATTACKS_9119(sq) | ATTACKS_1199(sq); } 57 Bitboard ATTACKS_pHI(in uint sq) @nogc const { return ATTACKS_HI(sq) | ATTACKS_OU[sq]; } 58 Bitboard ATTACKS_pKA(in uint sq) @nogc const { return ATTACKS_KA(sq) | ATTACKS_OU[sq]; } 59 mixin(q{ alias ATTACKS_YYXX = ATTACKS_XX; }.generateReplace("YY", [ "B", "W" ]).generateReplace("XX", [ "KA", "HI", "pKA", "pHI" ])); 60 61 string toString() const { 62 string s; 63 foreach (i; 0..9) { 64 foreach_reverse(j; 0..10) { s ~= (j < 9) ? ((this & MASK_SQ[i * 9 + j]) ? "●" : "・") : "\n"; } 65 foreach_reverse(j; 0..10) { s ~= (j < 9 && i * 9 + j < 64_) ? ((b[0] & MASK_SQ[i * 9 + j].b[0]) ? "●" : "・") : " "; } 66 foreach_reverse(j; 0..10) { s ~= (j < 9 && i * 9 + j >= 17) ? ((b[1] & MASK_SQ[i * 9 + j].b[1]) ? "●" : "・") : " "; } 67 } 68 return s; 69 } 70 } 71 72 Bitboard[81] expand(in string str) { return expand(str, (i, j) => 9 * i + j, (i, j) => -j, ulong.max, ulong.max); } 73 Bitboard[81] expand(in string str, int delegate(int, int) dg1, int delegate(int, int) dg2, const ulong msk_b0, const ulong msk_b1) { 74 import std.range : replicate; 75 auto SIGNED_LEFT_SHIFT(in Bitboard a, in int shift) { return shift >= 0 ? a.opBin !"<<"(shift) : a.opBin !">>"(-shift); } 76 Bitboard[17] MASK_SHIFT = iota(17).map !(i => Bitboard(replicate("0000000011111111100000000"[16 - i..25 - i], 9))).array[0..17]; 77 78 return iota(81) 79 .map !(sq => SIGNED_LEFT_SHIFT(Bitboard(str), dg1(sq / 9 - 4, sq % 9 - 4)) & MASK_SHIFT[dg2(sq / 9 - 4, sq % 9 - 4) + 8]) 80 .map !(a => (a | Bitboard(a.b[1] << 17, a.b[0] >> 17)) & Bitboard(msk_b0, msk_b1)) 81 .array[0..81]; 82 } 83 84 Bitboard[81 * 128] genLongTable(int delegate(int, int) getSq, int delegate(int) getPos, int delegate(int, int) choice, in Bitboard[] MASK) { 85 import std.algorithm, std.range; 86 int genAttacksLine(in int occupied, in int pos) { 87 int a, b; // 0 88 for (int s = pos - 1; s >= 0 && !(a & occupied); s--) a |= 1 << s; 89 for (int s = pos + 1; s < 9_ && !(b & occupied); s++) b |= 1 << s; 90 return choice(a, b); 91 } 92 93 Bitboard genBB(in uint line, in uint sq) { 94 return reduce !((bb, sq) => bb | MASK_SQ[sq]) 95 (Bitboard(0, 0), line.BitwiseRange !uint.map !(a => getSq(sq, a)).filter !(a => 0 <= a && a < 81)); 96 } 97 98 Bitboard[81 * 128] list; 99 foreach (occupied_line; iota(128).map !(a => a << 1)) 100 foreach (sq; 0..81) 101 list[(sq << 7) | genBB(occupied_line, sq).computeHash(MASK[sq])] = genBB(genAttacksLine(occupied_line, getPos(sq)), sq); 102 103 return list; 104 } 105 106 enum NULLBITBOARD = Bitboard(0, 0); 107 108 immutable Bitboard[81] MASK_SQ = expand("000000000_000000000_000000000_000000000_000010000_000000000_000000000_000000000_000000000"); 109 unittest { 110 foreach (i; 0..81) { assert(MASK_SQ[i].popCnt == 1, "MASK_SQ[" ~i.text ~"]: 立っているビットは1つ"); } 111 foreach (i; 0..81) { assert(MASK_SQ[i].lsb == i, "MASK_SQ[" ~i.text ~"]: 配列のindexとビットの位置は等しい"); } 112 foreach (i; 0..81) { assert(MASK_SQ[i] == Bitboard((1UL << i) & ((i - 64L) >> 63), (1UL << (i - 17)) & ~((i - 17L) >> 63))); } 113 } 114 115 mixin(q{ 116 enum Bitboard MASK_NN = Bitboard("000000000".replicate(9 - NN) ~"111111111" ~"000000000".replicate(NN - 1)); 117 enum Bitboard MASK_1NN = Bitboard("000000000".replicate(9 - NN) ~"111111111".replicate(NN)); 118 static if (NN != 1) enum Bitboard MASK_NN9 = Bitboard("111111111".replicate(10 - NN) ~"000000000".replicate(NN - 1)); 119 }.generateReplace("NN", iota(9).map !(i => text(i + 1)).array)); 120 121 mixin([ 122 [ "PROMOTE_B", "13" ], [ "PROMOTE_W", "79" ], 123 [ "LEGAL_BFU", "29" ], [ "LEGAL_BKY", "29" ], [ "LEGAL_BKE", "39" ], 124 [ "LEGAL_WFU", "18" ], [ "LEGAL_WKY", "18" ], [ "LEGAL_WKE", "17" ], 125 [ "BKEp", "15" ], [ "WKEp", "59" ], 126 [ "BKE", "59" ], [ "WKE", "15" ], 127 [ "BGIp", "14" ], [ "WGIp", "69" ], 128 [ "BKY", "39" ], [ "WKY", "17" ], 129 [ "BKA", "49" ], [ "BpKA", "49" ], [ "BHI", "49" ], [ "BpHI", "49" ], 130 [ "WKA", "16" ], [ "WpKA", "16" ], [ "WHI", "16" ], [ "WpHI", "16" ] 131 ].map !(a => format("alias MASK_%s = MASK_%s;", a[0], a[1])) 132 .join); 133 134 mixin(q{ immutable Bitboard[81] ATTACKS_YYXX; }.generateReplace("XX", [ "FU", "KE", "GI", "KI" ]).generateReplace("YY", [ "B", "W" ])); 135 immutable Bitboard[81] ATTACKS_OU; 136 mixin(q{ alias ATTACKS_YYOU = ATTACKS_OU; }.generateReplace("YY", [ "B", "W" ])); 137 mixin(q{ alias ATTACKS_YYpXX = ATTACKS_YYKI; }.generateReplace("XX", [ "FU", "KY", "KE", "GI" ]).generateReplace("YY", [ "B", "W" ])); 138 139 immutable Bitboard[81] _MASK_1199; 140 immutable Bitboard[81] _MASK_9119; 141 immutable Bitboard[81] _MASK_FILE; 142 immutable Bitboard[81] _MASK_RANK; 143 mixin(q{ alias _MASK_YYKY = _MASK_FILE; }.generateReplace("YY", [ "B", "W" ])); 144 145 immutable Bitboard[81 * 128] _ATTACKS_BKY; 146 immutable Bitboard[81 * 128] _ATTACKS_WKY; 147 immutable Bitboard[81 * 128] _ATTACKS_1199; 148 immutable Bitboard[81 * 128] _ATTACKS_9119; 149 immutable Bitboard[81 * 128] _ATTACKS_FILE; 150 immutable Bitboard[81 * 128] _ATTACKS_RANK; 151 152 static this() { 153 ATTACKS_BFU = expand("000000000_000000000_000000000_000000000_000000000_000010000_000000000_000000000_000000000"); 154 ATTACKS_WFU = expand("000000000_000000000_000000000_000010000_000000000_000000000_000000000_000000000_000000000"); 155 ATTACKS_BKE = expand("000000000_000000000_000000000_000000000_000000000_000000000_000101000_000000000_000000000"); 156 ATTACKS_WKE = expand("000000000_000000000_000101000_000000000_000000000_000000000_000000000_000000000_000000000"); 157 ATTACKS_BGI = expand("000000000_000000000_000000000_000101000_000000000_000111000_000000000_000000000_000000000"); 158 ATTACKS_WGI = expand("000000000_000000000_000000000_000111000_000000000_000101000_000000000_000000000_000000000"); 159 ATTACKS_BKI = expand("000000000_000000000_000000000_000010000_000101000_000111000_000000000_000000000_000000000"); 160 ATTACKS_WKI = expand("000000000_000000000_000000000_000111000_000101000_000010000_000000000_000000000_000000000"); 161 ATTACKS_OU = expand("000000000_000000000_000000000_000111000_000101000_000111000_000000000_000000000_000000000"); 162 163 _MASK_1199 = expand("100000000_010000000_001000000_000100000_000010000_000001000_000000100_000000010_000000001", 164 (i, j) => -i + j, (i, j) => i - j, 0xFE7F3F9FC00UL, 0x3F9FCFE0000000UL); 165 _MASK_9119 = expand("000000001_000000010_000000100_000001000_000010000_000100000_001000000_010000000_100000000", 166 (i, j) => i + j, (i, j) => -i - j, 0xFE7F3F9FC00UL, 0x3F9FCFE0000000UL); 167 _MASK_FILE = expand("000010000_000010000_000010000_000010000_000010000_000010000_000010000_000010000_000010000", 168 (i, j) => j, (i, j) => 0, 0xFFFFFFE00UL, 0x7FFFFFFFF80000UL); 169 _MASK_RANK = expand("000000000_000000000_000000000_000000000_111111111_000000000_000000000_000000000_000000000", 170 (i, j) => 9 * i, (i, j) => 0, 0xFE7F3F9FCFEUL, 0x7F3F9FCFE0000000UL); 171 172 _ATTACKS_BKY = genLongTable((sq, n) => n * 9 + sq % 9, sq => sq / 9, (a, b) => a, _MASK_FILE); 173 _ATTACKS_WKY = genLongTable((sq, n) => n * 9 + sq % 9, sq => sq / 9, (a, b) => b, _MASK_FILE); 174 _ATTACKS_1199 = genLongTable((sq, n) => sq - 10 * (sq % 9 - n), sq => sq % 9, (a, b) => a | b, _MASK_1199); 175 _ATTACKS_9119 = genLongTable((sq, n) => sq + 8 * (sq % 9 - n), sq => sq % 9, (a, b) => a | b, _MASK_9119); 176 _ATTACKS_FILE = genLongTable((sq, n) => n * 9 + sq % 9, sq => sq / 9, (a, b) => a | b, _MASK_FILE); 177 _ATTACKS_RANK = genLongTable((sq, n) => sq / 9 * 9 + n, sq => sq % 9, (a, b) => a | b, _MASK_RANK); 178 }