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

Gunnar Andersson


予備知識 / 探索 / 局面評価 / 定石の知識 / 終盤 / ソースコード例 / 他の情報源

予備知識

ある程度の強さのオセロプログラムを構築するためには、 多少のプログラミング経験が必要である。 使用するアルゴリズムやデータ構造の多くは、人工知能の解説書、 アルゴリズムの解説書やウェブ上で見つけられる。 優秀な高校生、コンピュータ科学専攻の大学生なら、 それらのアルゴリズムを理解し、強いプログラムを作ることが可能であろう。

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

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

探索

局面評価

これはプログラムにとってきわめて重要な部分であり、 ここが弱ければ、そのプログラムがいかに優れた探索アルゴリズムを使っていたとしても、 その効果はほとんど現れないだろう。 ここでは評価関数を作るための3種類の異なる方法論を紹介する。 これらは Zebra の知識の進化の過程を示すもので、 また私は多くのオセロプログラムがこれらのいずれかに分類されると考えている。

定石の知識

強いプログラムはすべて、定石集(データベース)を使っていて、 試合を重ねるごとに自動的に更新している。 トップクラスのプログラムの多くは何らかの形で IOS/GGS の棋譜をベースにしているので、 それぞれの定石集はかなりの部分が重複している。 棋譜からどのような情報を得るかにより、相違点が生じる。 トップクラスのプログラムすべてが用いているアプローチとして、 棋譜データベースの全試合の全局面を調べ、 データベースの棋譜で打たれていない最善変化を求める方法がある。 この方法は各局面で深い探索を実行しなければならないので、 時間がかかるが、定石集をその場で更新するのは比較的容易である。 一試合終わるごとに、すべての新しい局面(および時にはいくつかの古い局面) について、最善の変化が探索される。 その結果求められた、局面と(実際にプレイされた手と、変化の両方の)着手の組を使うと、 両者にとっての最善進行は単純なミニマックス探索により求められる。

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

終盤

終局に近付くにつれて両プレイヤーが打てる手は少なくなっていくので、 プログラムはゲームの終盤になるとずっと深く探索することができる。 このため終盤においては、プログラムはどんな人間プレイヤーよりはるかに強い。 コンピュータ同士の終盤戦では、 20手以上残っている段階で両者ともゲームの結果を読み切ってしまうので、 しばしば観戦している人間に超能力的な印象を与える。 コンピュータプログラムにとっての終盤は、多くの人間にとってはまだ中盤後半である、 20〜30ヶ所空きから始まる。

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

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

ソースコード例

基本的な終盤ソルバー

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

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

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

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

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

現在 AMD Athlon はこのコードを平均1クロックあたりおよそ2命令 - 200クロック で400命令処理する。 CPU を最大限に使えば、1クロックあたり3命令を処理できるはずである。 この用途でこの理論的最適値を達成するのは不可能かもしれないが、 命令のペアリングやレジスタストールを考慮すれば、このコードを改善する 余地はありそうに思える - 私はアセンブラに関しては初心者で、不必要な ストールを生じさせているかもしれないので。 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
著者は現在一般に入手可能なプログラムの中で最強のものの1つである、WZebraの作者。

訳:奥原 俊彦

Booby Reversi Home