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

最近、Pythonで遊んでいましたが、久しぶりにC++でコードを書きたくなり(笑)、題材としてリバーシ(オセロ)の終盤読みを実装してみました。

終盤読みのネタとしては「The FFO endgame test suite」を使用。

何も考えずに作ってみた

まず最初に何も考えずに作ってみたのがこちら

MacBook Air (13-inch, Mid 2011)で#40を解いてみた際の時間はこんな感じ。

  • score: 最終的な石差。
  • internal: 中間ノードの数。
  • leaf: 末端ノードの数。
  • total: internal+leaf
  • time: 読み切るのに必要な秒数。
  • knps: 1秒あたりの処理ノード数。(k単位)
score internal leaf total time(sec) knps
38 299,002,385 113,304,014 412,306,399 320.853 1,285.03

320秒かかっているということ。ここから時間を削っていきたいと思います。

最初の改善

αβ法を使っているのですが、最初の実装はこんな感じ。

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

  ++benchmark->internal;
  auto positions = board::GetMovableBitBoard(black, white);
  for (auto i = 0; i < 64; ++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;
      }
    }
  }

  return alpha;
}

board::GetMovableBitBoardの戻り値は置くことができる場所を1にした64bits整数。1が立っている位置はあまり多くないのに64回回しているのは無駄…ということで、ループ回数を減らす対応。

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

  ++benchmark->internal;
  auto positions = board::GetMovableBitBoard(black, white);
  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

40秒短縮!

続きの記事

前回に引き続きリバーシの終盤読み。前回時点で約280秒と酷い状況ですが、引き続き改善していきたいと思います。 着手可能位置取得処理...
スポンサーリンク

フォローする

スポンサーリンク