参考文献

Thellの開発並びに「リバーシのアルゴリズム」執筆にあたって参考にした資料を紹介します。リバーシプログラミングをお考えの方はぜひ一読してみることをおすすめします。

リバーシプログラミング・初心者向け

Programming Tea Shop: Visual C++でオセロを作ってみよう
Minimax探索及びalpha-beta法の解説があります。GUIとの組み合わせについても丁寧に解説されています。

-鶯教-コンピュータ・リバーシ講座
コンピュータリバーシ及びリバーシの全般的な戦術についてのページです。コンピュータリバーシについてひととおりのことを知ることができます。

リバーシプログラミング・中級者向け

オセロプログラムの作り方
ゲーム木探索の基礎から評価関数の重み最適化、リバーシプログラムTurtleを題材にしたソースコード解説まで幅広く扱っているサイトです。Thell 3.0の評価関数パターンはこのTurtleのものを流用しました。

強いオセロプログラムの内部動作
Zebraの作者、Gunnar Anderssonが書いた記事の翻訳です。よく読むと、強く、速いオセロプログラムを作るためのノウハウがびっしりと書かれています。また、原文には、Zebraの終盤解析ルーチンのコードなども追加されており、参考になります。

リバーシプログラミング・上級者向け

LOGISTELLO's Homepage
リバーシプログラミングにおいて、統計ベースの評価関数の基礎を築いたMichael Buro氏のサイトです。オセロプログラムに関する多くの論文が役に立つでしょう。Buro氏の方法に基づく統計ベース評価関数は今となっては新奇性には欠けますが、よい評価関数を作る確実な方法であることは間違いありません。
最強のプログラムとして長年君臨したLOGISTELLOのソースコードなども公開されていますが、Buro氏本人が「どのファイルが実際使われているのかもよくわからん(I hardly can tell which file is actually used anymore.)」と述べているように、ソースを読むことは困難です。

Keyano
LOGISTELLOに匹敵するプログラム、Keyanoのページです。"Keyano unplugged"という論文に内部構造について記載されており、探索、評価関数、定石など多くの分野にわたって実装の詳細が書かれています。

The FFO endgame test suite
Zebraの作者Gunner Andersson氏による、終盤読み切りのテストケースです。一番簡単と思われる#40でも20石空きであり、相当ハードなテストです。Thell3の評価関数ができあがった後、探索速度を向上させるためにこのテストを利用しました。

識別のための線形手法と汎化性
パターン認識について述べたページですが、参考資料として線形重回帰分析というページがあり、最急降下法で重み係数を段階的に変化させることによって回帰係数を求めるという手法について解説されています。これを読んでからBuro氏の論文を読むと理解が早まるでしょう。

探索アルゴリズム

ゲーム木の探索問題
Rei Suzukiさんによるゲーム木探索のアルゴリズム解説です。一般的な木探索の話からNegaScout/MTD(f)といったアルゴリズムまで解説されています。

NegaScout - A Minimax Algorithm faster than AlphaBeta
NegaScout考案者のAlexander Reinefeld氏によるNegaScoutの紹介と擬似コード。Scoutを提案した論文である"A. Reinefeld. An improvement to the Scout tree search algorithm. ICCA Journal, 6(4):pp.4-14, 1983."を読むこともできます。

Principal Variation Search - An enhancement to alpha-beta
Thell 3.0で採用しているPVS探索の実装に関して参考にしたページです。

MTD(f), a minimax algorithm faster than alpha-beta
alpha-beta法の改良の1つであるMTD(f)についてのページ。MTD(f)の他、置換表付alpha-betaの実装についても書かれています。また、彼のPh.D ThesisであるResearch Re: search & Re-searchは様々なゲーム木探索の手法について詳しく述べたもので、一読の価値があります。

定石

オセロ序盤理論
 Let's Othello内の序盤理論に関するページです。定石のうち代表的なものについて紹介されています。

定石＆終盤30手最善手順
代表的な定石の進行について、終盤30手をソフトを使って完全に読み切ったというすばらしいデータベースです。

コミュニティ

コンピュータリバーシ研究会
コンピュータリバーシについて様々な記事を書いていらっしゃる石川さんが運営するサイトです。「ゲームと人工知能」メーリングリストには私も参加しています。

ソフトウェア設計手法

オブジェクト指向における再利用のためのデザインパターン(改訂版)
Erich Gamma, Ralph Johnson, Richard Helm, John Vlissidesの4人、通称Gang of Four(GoF)によって書かれたデザインパターンのバイブルです。

戻る