強いオセロプログラムの内部動作

Gunnar Andersson

予備知識

以下に述べるより高度な技法を理解するには、最適化理論と線形回帰について、 若干の知識が必要である。これらは大学の応用数学レベルに相当する。

強いオセロプログラムを作る上で、もっとも難しいのはデバッグである。 探索アルゴリズムの性質上、バグはかなり長い期間潜伏した後に、 プログラマーの意表を突いて表面化することがある。 私ができる唯一のアドバイスは、すべての新しいモジュールを完全にテストしなさい、 ということである。

探索

• 基礎

  今日のすべての強いプログラムは、多くの手を先読みすることにより最善手を決定する。 「私がこう打てば相手はこう打ち、私はこう打つ・・ この局面の形勢はどうだろう？」というように。 明らかに、わずか数手先でも局面の数は急速に増加する。 中盤においては多くの場合、それぞれのプレイヤーは約10ヶ所から着手を選べるので、 ９手先読みする（プログラマーの用語では深さ９の探索）だけでも、 十億通り (10^9) の局面を調べなければならない。 幸いにして、最善手を選択するためには、これらすべての局面を評価する必要はないことが （数学的に）証明されている。 その代わりにαβ探索 (alpha-beta pruning) と呼ばれる手法（Andy Walker による優れた解説が ここ にある）を使うことができ、評価する局面数を大きく減らすことができる。 強いオセロプログラム（およびチェスやチェッカーなど、他のボードゲームのプログラム） のすべてが、このアルゴリズムのバリエーションを用いている。 よいオセロプログラムなら、αβを使わなければ十億局面になる９手読みを、 100,000〜1,000,000局面程度で済ませられるであろう。 αβにはいくつかのバリエーションが存在し、中でも Alexander Reinefeld により発見された nega-scout 法が広く使われているが、基本的な部分はαβ法と変わらない。

• 評価の順序

  αβ探索においては、その局面での良い手を先に探索するようにすることが重要である。 このために、いくつかの手法が使用できる。 １つは、それぞれの手に対し「キラー応手」を保存しておく方法である。 たとえば私は、相手がg2にＸ打ちしてきたときには、間違いなく最初にh1を調べ、 隅が取れないか、取れるならその手を打つべきかどうかを読むだろう。 別の有用な手法として、浅い探索をしてみるというのがある。 たとえば深さ12の探索をする前に、深さ２の探索で最善と思われる手を探すということで、 この場合後者にかかる時間は前者に比べて無視できる。

• 選択的探索（前向き枝刈り）

  今日における最強のオセロプログラムはすべて、何らかの形で選択的探索を行っている。 その考え方は非常に単純で、人間のプレイヤーの思考に近い。 ほとんどの局面で、明らかな悪手が多数存在し、 それらは悪手であることが確認できるだけ読めば十分である。 これは通常次のように実装される。深さ12の探索（12手読み） を行うとき、プログラムは深さ４まではすべての可能な手を評価した上で、 本当に悪いと思われる手を排除する。 残った手を深さ12まで探索する。 「本当に悪い」の基準は、深さ４の探索からどの程度正確に深さ12の探索の結果を予測できるか を統計的に分析することにより、数式化できる。 この手続きは Multi Prob-Cut （Michael Buro の考案）と呼ばれ、 上記の例は「カットペア 4/12」になる。 もちろん他のカットペアを使うこともでき、 多くのプログラムは複数のカットペアを使っている。

• 探索アルゴリズムの選択

  αβ探索はどのようなゲームプレイプログラムにも使え、 ごくわずかな工夫で多くの利益が得られる。 MPC (Multi Prob-Cut) のような選択的探索アルゴリズムは、 優れた局面評価関数があってはじめて有効に働く。 その理由は、誤った選択が致命的な結果につながる場合があるからである。 また、ゲーム中での異なる局面での評価を比較することになるため、 局面評価の方法などの他の条件にも依存する。 トップクラスのプログラムは、MPC により探索をかなり深くすることができる。 MPC を使わなければ15〜16手以上先を読むのは難しいが、 MPC を使うと20〜27手読みも到達可能である。

• 置換表 (Transposition table)

  数手先で同じ局面が生じることがしばしばある。 たとえば虎定石の初手から f5-d6-c3-d3-c4 と f5-d6-c4-d3-c3 の手順は、同じ局面になる。 これは置換 (transposition) と呼ばれる。 同じ局面を複数回探索するのを防ぐため、プログラムは探索中に遭遇した局面のすべて （あるいは大部分）を置換表（通常はハッシュ表のデータ構造を用いる）に保存する。 オセロの中盤においては、深い読みでは20%〜50%（概算）の時間を節約できる。 終盤においては、置換が生じる確率はさらに高くなり、節約できる時間も大きくなる。

局面評価

• 石の位置による評価

  この評価関数の基本となる考え方は、石の位置によりその価値が異なる、 すなわち隅は価値があり、隅の隣は良くない、というようなことである。 対称形を除いて考えると、盤上には10種類の異なる位置があり、 それぞれの位置について黒石、白石と空きの３通りについて値が与えられる。 より洗練されたアプローチとしては、ゲームの進行に伴って、 それぞれの位置の評価を変化させる方法がある。 たとえば隅の価値は序盤および中盤初期においては、終盤よりも高い。

  この種の評価関数を用いたプログラムは、（私の経験では例外なく） どうしても弱くなってしまう。 その代わり、この評価関数をプログラムするのは非常に簡単である。 また、多くのプログラマーにとって、 この方法でも作者本人よりも強いプログラムが作れることが多い。

• 着手可能数（手の広さ）による評価

  これはより洗練されたアプローチであり、 盤面の非常に局所的な評価である位置による評価の代わりに、 盤面をより大局的に見ようとするものである。 多くの人間のプレイヤーを観察すると、手の広さ（可能な手の数）を最大にし、 壁石（空きに接した石）を最小にするように努力していることがわかる。 これらの値、あるいはその良い近似値は、 効率よくコーディングすれば十分速く求めることができ、 プログラムの強さの向上に大きく寄与する。

  着手可能数に基づく評価関数を利用するプログラムの多くは、 辺と隅の形についての何らかの知識を持っていて、 また中盤初期までは自分の石数を減らすように努める。 これもまた人間のプレイヤーが用いる戦略の１つである。

• パターンに基づく評価

  上に述べたように、ある程度の強さのプログラムでは、 辺と隅の形について何らかの知識を用いている。 着手可能数の最大化と壁石の最小化は大域的な性質であるが、 局所的な配置に分解・帰着させ、足し合わせることができる。 同じことが自石の最小化についても言える。

  これを一般化すると、次のように言える。 評価関数では、局所的な配置（パターン）のみを使えばよい。 通常の実装では、それぞれの縦列、横列、斜めと隅周辺の配置を別々に評価し、 その評価値を合計する。 これがうまくいくようにするには、多数の異なるパターンを評価しなければならない。 隅だけでも3321通りの配置があり、すべての配置を数えると、数万通りになる。 さらに悪いことに、異なる配置の相対的な価値関係は、ゲームの進行に伴い大きく変化する。 当然、これらすべての配置の評価値は、自動的に決定されるようにすべきである。 これは強いプレイヤー間の棋譜の大きなデータベースを用意し、 それらすべてのゲームに現れるそれぞれの局面の各配置を統計的に分析することにより実現できる。 具体的な実装はプログラムによって異なり、またここで扱うべき範囲を越えてしまう。 詳しくはこのページの最後に紹介している Michael Buro による論文などを参照されたい。

  異なる配置を数値化して比較するために、 その評価関数がどのような値を予想しようとするのかを決める必要がある。 最も一般的な選択肢は、最終石差を予想するものである。 私の理解では、Hannibal は勝勢の側に石差に応じたボーナスを加えた、 加重石差を用いている。

定石の知識

他のいくつかのプログラムはそれぞれの局面の変化は保存せず、 変化をその場で計算する。 この方法の主な利点は、（非常に時間がかかる）変化の計算を行っておく必要がないことである。 しかしそれと引き換えにいくつかの欠点がある。 この種の定石集は棋譜データベース中の悪手の影響を受けやすく、 それにより定石を外れて必敗形になってしまうことがある。

終盤

中盤で有効な探索アルゴリズム（MPC のバリエーションなど）は、 終盤においても同様に有効である。 しかし、探索の目的は異なる。 プログラムにとって、終盤はどちらが勝つかが計算できる段階、 すなわち最終手までの勝敗に関わるすべての変化を読み切れる時点からはじまる。 トップクラスのプログラムでは、これは通常残り24〜30手の時点である。 プログラムはどちらの勝ちかがわかると、 次は最善手（スコアが最良になる手）を探しはじめる。 完全読みは通常（引き分け局面の場合を除き）勝敗を判断するよりはるかに困難で、 残り23〜28手から始まるのが普通である。

終盤の探索性能は評価の順序にかかっており、 中盤と異なる順序付けの方針を用いることはその労に見合う。 その理由を以下に述べる：評価される変化の多くには、 １手以上の悪手が含まれており、その悪手を咎める手を探すときには、 必ずしも最善手である必要はなく、十分な反駁手のいずれかを見つければよい。 プログラムができるだけ早く読み切りを行えるようにしたいので、 （思考時間が）最も速くなる反駁手を探すことは意味がある。 これは打った後に相手の着手可能数が少なくなる手を、 中盤より優先して探索することにより実現できる。 この手法は一般に、速さ優先探索 (Fastest-First heuristic) と呼ばれる。

ソースコード例

基本的な終盤ソルバー

私がコンピュータオセロに取り組み始めたとき、Warren Smith が作成し、 Jean-Christophe Weill が改良した終盤ソルバーをダウンロードした。 それを私自身が改良した結果がここにある。 Richard Delorme による、より洗練された終盤ソルバーが ここにある。

ビットボードによるトリック

Zebraの終盤ソルバーは 非常に高速で、おそらく最速かもしれない。この理由の一つに、オセロ盤を黒石と白石それぞれ２ワード、 計４ワードの32ビットで表していることがある。 この表現を用いることにより、非常に高速な着手生成関数を書くことができる。 この手法は速さ優先探索による順序付けにおいても有効で、 ここ に示すＣ＋アセンブラの関数により、一方のプレイヤーの着手可能数を AMD Athlon で200クロック以内で求めることができる。他のプラットフォームでは 測定していないが、私の予想ではPentium IIIでおおよそ同程度、Pentium IVでは 300〜400クロックではないかと思う。

このコードの使用法は次の通り: いくつかの定数を初期化するためinit_mmx() をコールし（一度呼べばよい）、その後bitboard_mobility()を呼ぶと、 着手可能な手を得られる。 このコードは GCC のasm拡張を用いたＣのソースになっている。 これを Microsoft Visual C++ でコンパイルできるコードに直すのは、難しくはないが 退屈な作業になるだろう。

このコードで使われている主なトリックは、１方向（たとえば上方向）に 石を返すすべての手を同時に求めることである。 これにはいくつかの方法があるが、このコードは Richard Delorme により最初に 提案され、私が若干改善したもののバリエーションである。 石を返す方向は８あるが、そのうち６方向をMMXレジスタで、残りの２方向を 整数レジスタで処理している。

現在 AMD Athlon はこのコードを平均１クロックあたりおよそ２命令 - 200クロック で400命令処理する。 CPU を最大限に使えば、１クロックあたり３命令を処理できるはずである。 この用途でこの理論的最適値を達成するのは不可能かもしれないが、 命令のペアリングやレジスタストールを考慮すれば、このコードを改善する 余地はありそうに思える - 私はアセンブラに関しては初心者で、不必要な ストールを生じさせているかもしれないので。 Pentium III, Pentium IV と Athlon にしかないpsadbw命令を 使えば、わずかながら速くなるかもしれない。 他にコードを改善できるところがあれば、私に知らせて欲しい。

[訳注] 訳者がさらに最適化を進めたコードがここ にあります。 このコードはGunner氏にも送ってあり、Zebraの最新バージョンで使われています。

他の情報源

Annotated bibliography of Othello programming.

この分野での研究論文を紹介している。 本ページの内容のほとんどは、 ここで紹介されている論文中に見つけることができる。

FTP archive at NEC

いくつかの文献とともに、IOS でプレイされたすべての棋譜（約500,000） とコンピュータプログラムのLogistelloとKittyの対戦の棋譜（約100,000） を含む棋譜データベースがある。 これらの棋譜データベースは強い評価関数を作るのに役立つ。

Machine learning in games

ゲームプログラミングのすべての側面をカバーする、Jay Scott による充実したウェブサイトである。 ボードゲームに限らず、ロボットサッカーや人工知能アドベンチャーゲームなど、 多種のゲームが含まれている。 多くの技法が紹介され、インターネットの他の文献へのリンクもある、 推奨サイトである。

Michael Buro's publications

ブレークスルーとなった Michael Buro の論文がダウンロードできる。 強いオセロプログラムを作りたいのなら、これらの論文を読むことを強く推奨する。

Original: Last modified July 16, 2004 by Gunnar Andersson
著者は現在一般に入手可能なプログラムの中で最強のものの１つである、WZebraの作者。

訳：奥原 俊彦
Booby Reversi Home