Stockfish DD – bitcount.h | やねうら王公式サイト

今回はStockfishのbitcount.hです。これは、2進数的に見て1になっているbitの数を数えるというものです。いわゆるpopcountですね。SSE4.1以降であればx86/x64ではpopcnt命令が使えますので簡単なのですが、そうではない環境ではビット演算のテクニックを用いて求めることになります。

popcountは、王に利きのある敵駒のbitboardを得たときにpopcountしてそれが2以上であれば両王手なので次の合法手としては王が逃げる指し手のみを生成するときに使えます。Stockfishのmore_than_one( )という関数がそれです。というか、この使い道以外は将棋ではほとんどないような…。

そう言えば、私は棋譜からの学習のときに評価因子に正規分布っぽい乱数を加算するのに、popcount(rand() & 7) とかやってますが(二項分布≒正規分布なので)…まあ、こんなところはたいした問題ではないですね。

/*
  Stockfish, a UCI chess playing engine derived from Glaurung 2.1
  Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
  Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad

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


  Stockfish 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/>.
*/

#ifndef BITCOUNT_H_INCLUDED
#define BITCOUNT_H_INCLUDED

#include <cassert>
#include "types.h"

// popcountするときの対象bit数と、最大数えるbit数
enum BitCountType {
  CNT_64,       // 64bitに対して1であるbitを最大64個のbitまで数える
  CNT_64_MAX15, // 64bitに対して1であるbitを最大15個のbitまで数える
  CNT_32,       // 32bitに対して1であるbitを最大32個のbitまで数える
  CNT_32_MAX15, // 32bitに対して1であるbitを最大15個のbitまで数える
  CNT_HW_POPCNT // ハードウェアのPOPCNT命令を用いる
};

/// Determine at compile time the best popcount<> specialization according if
/// platform is 32 or 64 bits, to the maximum number of nonzero bits to count
/// and if hardware popcnt instruction is available.

// ハードウェア命令が使えるなら、非0であるbitを最大個数(なるべく最大のbitだけ)数えるために
// プラットフォームが32か64bitなのかによって、コンパイル時にベストなpopcount<>の特殊化されたものを選択する。

// ※　popcount<Full>()と書けば64bitまるごとに対して、1であるbit数を返す。
const BitCountType Full  = HasPopCnt ? CNT_HW_POPCNT : Is64Bit ? CNT_64 : CNT_32;
const BitCountType Max15 = HasPopCnt ? CNT_HW_POPCNT : Is64Bit ? CNT_64_MAX15 : CNT_32_MAX15;


/// popcount() counts the number of nonzero bits in a bitboard
// popcount()はbitboardに対して非0のbitの数を数える。
template<BitCountType> inline int popcount(Bitboard);

template<>
inline int popcount<CNT_64>(Bitboard b) {
  b -=  (b >> 1) & 0x5555555555555555ULL;
  b  = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);
  b  = ((b >> 4) + b) & 0x0F0F0F0F0F0F0F0FULL;
  return (b * 0x0101010101010101ULL) >> 56;
}

template<>
inline int popcount<CNT_64_MAX15>(Bitboard b) {
  b -=  (b >> 1) & 0x5555555555555555ULL;
  b  = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);
  return (b * 0x1111111111111111ULL) >> 60;
}

template<>
inline int popcount<CNT_32>(Bitboard b) {
  unsigned w = unsigned(b >> 32), v = unsigned(b);
  v -=  (v >> 1) & 0x55555555; // 0-2 in 2 bits
  w -=  (w >> 1) & 0x55555555;
  v  = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits
  w  = ((w >> 2) & 0x33333333) + (w & 0x33333333);
  v  = ((v >> 4) + v + (w >> 4) + w) & 0x0F0F0F0F;
  return (v * 0x01010101) >> 24;
}

template<>
inline int popcount<CNT_32_MAX15>(Bitboard b) {
  unsigned w = unsigned(b >> 32), v = unsigned(b);
  v -=  (v >> 1) & 0x55555555; // 0-2 in 2 bits
  w -=  (w >> 1) & 0x55555555;
  v  = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits
  w  = ((w >> 2) & 0x33333333) + (w & 0x33333333);
  return ((v + w) * 0x11111111) >> 28;
}

template<>
inline int popcount<CNT_HW_POPCNT>(Bitboard b) {

#ifndef USE_POPCNT
  // ToDo : →　HasPopCntでなかったのか？なぜにシンボルが変わっているのだ…。

  assert(false);
  return b != 0; // Avoid 'b not used' warning

#elif defined(_MSC_VER) && defined(__INTEL_COMPILER)

  return _mm_popcnt_u64(b);

#elif defined(_MSC_VER)

  return (int)__popcnt64(b);

#else

  __asm__("popcnt %1, %0" : "=r" (b) : "r" (b));
  return b;

#endif
}

#endif // #ifndef BITCOUNT_H_INCLUDED

100

101

102

103

104

105

106

107

108

109

110

111

112

113

Stockfish, a UCI chess playing engine derived from Glaurung 2.1

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

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

#ifndef BITCOUNT_H_INCLUDED

#define BITCOUNT_H_INCLUDED

#include

#include "types.h"

// popcountするときの対象bit数と、最大数えるbit数

enum BitCountType {

CNT_64, // 64bitに対して1であるbitを最大64個のbitまで数える

CNT_64_MAX15, // 64bitに対して1であるbitを最大15個のbitまで数える

CNT_32, // 32bitに対して1であるbitを最大32個のbitまで数える

CNT_32_MAX15, // 32bitに対して1であるbitを最大15個のbitまで数える

CNT_HW_POPCNT // ハードウェアのPOPCNT命令を用いる

};

/// Determine at compile time the best popcount<> specialization according if

/// platform is 32 or 64 bits, to the maximum number of nonzero bits to count

/// and if hardware popcnt instruction is available.

// ハードウェア命令が使えるなら、非0であるbitを最大個数(なるべく最大のbitだけ)数えるために

// プラットフォームが32か64bitなのかによって、コンパイル時にベストなpopcount<>の特殊化されたものを選択する。

// ※　popcount()と書けば64bitまるごとに対して、1であるbit数を返す。

const BitCountType Full = HasPopCnt ? CNT_HW_POPCNT : Is64Bit ? CNT_64 : CNT_32;

const BitCountType Max15 = HasPopCnt ? CNT_HW_POPCNT : Is64Bit ? CNT_64_MAX15 : CNT_32_MAX15;

/// popcount() counts the number of nonzero bits in a bitboard

// popcount()はbitboardに対して非0のbitの数を数える。

template inline int popcount(Bitboard);

template<>

inline int popcount(Bitboard b) {

b -= (b >> 1) & 0x5555555555555555ULL;

b = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);

b = ((b >> 4) + b) & 0x0F0F0F0F0F0F0F0FULL;

return (b * 0x0101010101010101ULL) >> 56;

}

template<>

inline int popcount(Bitboard b) {

b -= (b >> 1) & 0x5555555555555555ULL;

b = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);

return (b * 0x1111111111111111ULL) >> 60;

}

template<>

inline int popcount(Bitboard b) {

unsigned w = unsigned(b >> 32), v = unsigned(b);

v -= (v >> 1) & 0x55555555; // 0-2 in 2 bits

w -= (w >> 1) & 0x55555555;

v = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits

w = ((w >> 2) & 0x33333333) + (w & 0x33333333);

v = ((v >> 4) + v + (w >> 4) + w) & 0x0F0F0F0F;

return (v * 0x01010101) >> 24;

}

template<>

inline int popcount(Bitboard b) {

unsigned w = unsigned(b >> 32), v = unsigned(b);

v -= (v >> 1) & 0x55555555; // 0-2 in 2 bits

w -= (w >> 1) & 0x55555555;

v = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits

w = ((w >> 2) & 0x33333333) + (w & 0x33333333);

return ((v + w) * 0x11111111) >> 28;

}

template<>

inline int popcount(Bitboard b) {

#ifndef USE_POPCNT

// ToDo : →　HasPopCntでなかったのか？なぜにシンボルが変わっているのだ…。

assert(false);

return b != 0; // Avoid 'b not used' warning

#elif defined(_MSC_VER) && defined(__INTEL_COMPILER)

return _mm_popcnt_u64(b);

#elif defined(_MSC_VER)

return (int)__popcnt64(b);

#else

__asm__("popcnt %1, %0" : "=r" (b) : "r" (b));

return b;

#endif

}

#endif // #ifndef BITCOUNT_H_INCLUDED

「Stockfish DD – bitcount.h」への4件のフィードバック

かず@なのは 2014年12月30日 10:54 より:

なのはminiではpopcountせずに x & (x-1)が0より大かで両王手を判定しています。

返信 ↓
- やねうらお 2014年12月30日 11:50 より:
  
  はい、そうですね。両王手のみだったら、最下位ビットを消すビット演算のテクニック(x & (x-1))が使えますね。将棋盤面は128bitでないと収まらないので、これに対してこの処理を行なうのは結構嫌ですね。x-1のところが綺麗に書けないので…。
  
  なのはの場合、GPSっぽくどこから利きがあるか各升ごとに持っていたと思うので、ある升への利きは32bit変数に収まるので問題ないということですね。GPS風に持つと盤面のupdateするときのコストが高いのが私は嫌なんですが、利きを持っていると判定が速く済む部分もあるので全体的には相殺するんでしょう。もしかすると速かったり？うーん。比較実験してみたい気分になってきたぞ…。
  
  返信 ↓
  - dasapon 2014年12月30日 13:18 より:
    
    両王手に限って言えば,王手している駒のbitboardのそれぞれの変数の論理和を取ってやることで速くできないでしょうか?
    
    両王手のときには玉を攻撃している二つの駒が異なる筋にいることが保障されているので,論理和を取っても立っているbitの数は変わらないと思います. それで本当に速くなるのかはよくわかりませんが……
    
    返信 ↓
    - やねうらお 2014年12月30日 18:46 より:
      
      王手している駒のbitboardのそれぞれの変数の論理和を取って
      
      取ってます。ある地点sqに対して利いている手番turn側の駒のbitboardを得る関数
      Bitboard attackers_to(Square sq,Turn turn) const;
      みたいな関数がありまして、これを用いているので実際のコードとしては、
      if ( more_than_one( attackers_to(sq,~us))) { // 両王手
      のようなコードになっちょります。
      
      返信 ↓

やねうら王公式サイト

コンピューター将棋やねうら王公式サイト

Stockfish DD – bitcount.h

「Stockfish DD – bitcount.h」への4件のフィードバック

コメントを残すコメントをキャンセル

「Stockfish DD – bitcount.h」への4件のフィードバック

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル