リバーシ(終盤読み) その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秒かかっているということ。ここから時間を削っていきたいと思います。

最初の改善

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

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

上位下位のゼロの連続を除外してループ回数を減らしてみました。

結果…

score internal leaf total time(sec) knps
38 299,002,385 113,304,014 412,306,399 279.929 1,472.90

40秒短縮!

続きの記事

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

フォローする

スポンサーリンク