リバーシ(終盤読み) その3


前回に引き続きリバーシの終盤読み。前回時点で約280秒→約94秒と改善しましたが、継続して改善してみます。

ビット数カウント、NTZカウントの組み込み関数化

盤面をビットボードで実装している関係でビット数カウント、NTZ (下位ビットから続く0の数)を数える、ということが必要になってくるのですが、これを組み込み関数化することで速度改善を図ります。

もともとのビット数カウント、NTZはこちら。

int CountBits(uint64_t bits) {
  static const int BITS_COUNT_TABLE[256] = {
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
      2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
      2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
      4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
      3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
      4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  };

  const unsigned char *p = reinterpret_cast<const unsigned char *>(&bits);
  return BITS_COUNT_TABLE[p[0]] + BITS_COUNT_TABLE[p[1]] +
         BITS_COUNT_TABLE[p[2]] + BITS_COUNT_TABLE[p[3]] +
         BITS_COUNT_TABLE[p[4]] + BITS_COUNT_TABLE[p[5]] +
         BITS_COUNT_TABLE[p[6]] + BITS_COUNT_TABLE[p[7]];
}

int ntz(uint64_t x) { return CountBits((~x) & (x - 1)); }

これを以下に変更。(このタイミングで関数名とか変えていたり、ヘッダ側に移動していたりするのでそのまま入れ替えできないですが)

#include <x86intrin.h>

inline int CountBits(uint64_t bits) { return _popcnt64(bits); }

inline int CountNTZ(uint64_t bits) { return _tzcnt_u64(bits); }

あとは組み込み関数が使えるようにCMake側で「add_compile_options(-march=native)」を追加。

関数のテンプレート化

頻繁に呼び出している反転用のビットパターンの取得用の関数をテンプレート化することで速度改善を図りました。

元々はこちら。

uint64_t GetReversePattern(uint64_t mask, uint64_t m, uint64_t black,
                           uint64_t white,
                           std::function&lt;uint64_t(uint64_t)&gt; func) {
…
}

それをこういう形に。当然呼び出し側もそれに合わせて変えてます。

template &lt;uint64_t mask, typename F&gt;
uint64_t GetReversePattern(uint64_t m, uint64_t black, uint64_t white, F func) {
…
}

この時点での処理速度等…

この時点での処理速度等ですが、以下です。

score internal leaf total time(sec) knps
この記事の対応前 38 299,002,385 113,304,014 412,306,399 93.848 4,393.34
この記事の対応後 38 299,002,385 113,304,014 412,306,399 52.535 7,848.22

ようやく1分切ってきました。

スポンサーリンク

フォローする

スポンサーリンク