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

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

着手可能位置取得処理の改善

改善前の着手可能位置取得処理はこんな感じ。

uint64_t GetMovableBitBoard(uint64_t black, uint64_t white) {
  uint64_t result = 0;
  uint64_t m = 1;
  uint64_t space_board = ~(black | white);

  for (auto i = 0; i < 64; ++i) {
    if ((m & space_board) &&
        (GetReversePattern(0x00ffffffffffff00, m, black, white,
                           LeftShift(8)) || // 下方向
         GetReversePattern(0x007e7e7e7e7e7e00, m, black, white,
                           LeftShift(7)) || // 左下方向
         GetReversePattern(0x7e7e7e7e7e7e7e7e, m, black, white,
                           RightShift(1)) || // 左方向
         GetReversePattern(0x007e7e7e7e7e7e00, m, black, white,
                           RightShift(9)) || // 左上方向
         GetReversePattern(0x00ffffffffffff00, m, black, white,
                           RightShift(8)) || // 上方向
         GetReversePattern(0x007e7e7e7e7e7e00, m, black, white,
                           RightShift(7)) || // 右上方向
         GetReversePattern(0x7e7e7e7e7e7e7e7e, m, black, white,
                           LeftShift(1)) || // 右方向
         GetReversePattern(0x007e7e7e7e7e7e00, m, black, white,
                           LeftShift(9)))) // 右下方向
    {
      result |= m;
    }

    m <<= 1;
  }

  return result;
}

やっていることとしては64箇所全てに対して1つずつ置けるかどうかを判断している、というもの。
これをこちらの記事を参考に、64箇所を一気に計算するように変更。

# 対象読者 「**ビットボード初心者がオセロをさくっと実装してみること**」に重点を置いてます "ビットボード"を知らない人は、まず以下あたりを読むと良いかもしれません (https:...

参考にして作り直した結果が下のコード。

uint64_t GetMovableBitBoard(uint64_t black, uint64_t white) {
  //左右端の番人
  uint64_t horizontalWatchBoard = white & 0x7e7e7e7e7e7e7e7e;
  //上下端の番人
  uint64_t verticalWatchBoard = white & 0x00ffffffffffff00;
  //全辺の番人
  uint64_t allSideWatchBoard = white & 0x007e7e7e7e7e7e00;
  //空きマスのみにビットが立っているボード
  uint64_t blankBoard = ~(black | white);

  // 8方向チェック (・一度に返せる石は最大6つ ・高速化のためにforを展開)
  //右
  uint64_t tmp = horizontalWatchBoard & (black << 1);
  tmp |= horizontalWatchBoard & (tmp << 1);
  tmp |= horizontalWatchBoard & (tmp << 1);
  tmp |= horizontalWatchBoard & (tmp << 1);
  tmp |= horizontalWatchBoard & (tmp << 1);
  tmp |= horizontalWatchBoard & (tmp << 1);
  uint64_t legalBoard = blankBoard & (tmp << 1);

  //左
  tmp = horizontalWatchBoard & (black >> 1);
  tmp |= horizontalWatchBoard & (tmp >> 1);
  tmp |= horizontalWatchBoard & (tmp >> 1);
  tmp |= horizontalWatchBoard & (tmp >> 1);
  tmp |= horizontalWatchBoard & (tmp >> 1);
  tmp |= horizontalWatchBoard & (tmp >> 1);
  legalBoard |= blankBoard & (tmp >> 1);

  //下
  tmp = verticalWatchBoard & (black << 8);
  tmp |= verticalWatchBoard & (tmp << 8);
  tmp |= verticalWatchBoard & (tmp << 8);
  tmp |= verticalWatchBoard & (tmp << 8);
  tmp |= verticalWatchBoard & (tmp << 8);
  tmp |= verticalWatchBoard & (tmp << 8);
  legalBoard |= blankBoard & (tmp << 8);

  //上
  tmp = verticalWatchBoard & (black >> 8);
  tmp |= verticalWatchBoard & (tmp >> 8);
  tmp |= verticalWatchBoard & (tmp >> 8);
  tmp |= verticalWatchBoard & (tmp >> 8);
  tmp |= verticalWatchBoard & (tmp >> 8);
  tmp |= verticalWatchBoard & (tmp >> 8);
  legalBoard |= blankBoard & (tmp >> 8);

  //左斜め下
  tmp = allSideWatchBoard & (black << 7);
  tmp |= allSideWatchBoard & (tmp << 7);
  tmp |= allSideWatchBoard & (tmp << 7);
  tmp |= allSideWatchBoard & (tmp << 7);
  tmp |= allSideWatchBoard & (tmp << 7);
  tmp |= allSideWatchBoard & (tmp << 7);
  legalBoard |= blankBoard & (tmp << 7);

  //右斜め下
  tmp = allSideWatchBoard & (black << 9);
  tmp |= allSideWatchBoard & (tmp << 9);
  tmp |= allSideWatchBoard & (tmp << 9);
  tmp |= allSideWatchBoard & (tmp << 9);
  tmp |= allSideWatchBoard & (tmp << 9);
  tmp |= allSideWatchBoard & (tmp << 9);
  legalBoard |= blankBoard & (tmp << 9);

  //左斜め上
  tmp = allSideWatchBoard & (black >> 9);
  tmp |= allSideWatchBoard & (tmp >> 9);
  tmp |= allSideWatchBoard & (tmp >> 9);
  tmp |= allSideWatchBoard & (tmp >> 9);
  tmp |= allSideWatchBoard & (tmp >> 9);
  tmp |= allSideWatchBoard & (tmp >> 9);
  legalBoard |= blankBoard & (tmp >> 9);

  //右斜め上
  tmp = allSideWatchBoard & (black >> 7);
  tmp |= allSideWatchBoard & (tmp >> 7);
  tmp |= allSideWatchBoard & (tmp >> 7);
  tmp |= allSideWatchBoard & (tmp >> 7);
  tmp |= allSideWatchBoard & (tmp >> 7);
  tmp |= allSideWatchBoard & (tmp >> 7);
  legalBoard |= blankBoard & (tmp >> 7);

  return legalBoard;
}

alphabetaでの重複処理の削除

前の記事でalphabeta関数の中身をお見せしていますが、同じ盤面で着手可能位置取得を2回行っていたのを1回に修正。
修正後のソースはこちら。

int alphabeta(uint64_t black, uint64_t white, int alpha, int beta,
              Benchmark *benchmark) {
  auto positions = board::GetMovableBitBoard(black, white);
  if (positions == 0) {
    if (board::GetMovableBitBoard(white, black) == 0) {
      // 双方が石を置けない
      ++benchmark->leaf;
      return board::GetScore(black, white);
    } else {
      // パス
      return -alphabeta(white, black, -beta, -alpha, benchmark);
    }
  }

  ++benchmark->internal;
  for (auto i = ntz(positions); positions; ++i) {
    auto position = uint64_t{1} << i;
    if (positions & position) {
      auto newblack = black;
      auto newwhite = white;
      board::Move(position, &newblack, &newwhite);
      alpha = std::max(
          alpha, -alphabeta(newwhite, newblack, -beta, -alpha, benchmark));

      if (alpha >= beta) {
        return alpha;
      }

      positions ^= position;
    }
  }

  return alpha;
}

単純に関数序盤での終局判定用の着手可能位置取得時に結果を覚えておいて、盤面展開時にも使用します、という対応。

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

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

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

約280秒→約94秒と大幅改善!

スポンサーリンク

フォローする

スポンサーリンク