vsOtha アルゴリズム解説 - 人生きつね色

本文書では、vsOthaのアルゴリズムの概要を解説します。今のところは、vsOthaの実装についての説明が多いようです。とりあえず粗く書きました。今後更新するかもしれません。

また、Seal softwareさんによる Thellのアルゴリズム解説には、オセロ/リバーシのアルゴリズム全般に関する優れた説明がありますので、そちらもご覧ください。

ボードの実装

探索アルゴリズム

置換表

ゲーム木中には、どっちから打っても同じ場合など、同じ局面が複数回登場することがあります。そこで、既に探索した局面を、置換表というテーブル(実体は大抵ハッシュ)に登録しておき、再度出現した場合には探索を省略することで高速化を図ることができます。

Thellの解説にもあるように、置換表は単体での使用よりも、むしろ反復深化との組み合わせにより大きな効果を発揮します。

vsOthaでは、置換表をChained Hashを用いて実装しています。キーが衝突してもリストにつないですべて保持しています。また、要素数の上限を設けてメモリ使用量を制限しています。

第二置換表

メインの置換表は、重複盤面のカットと反復深化の実現という二つの目的を持っていましたが、この第二置換表は重複盤面のカットのみに使用されます。

メインの置換表は、探索盤面全てを登録し、リストも使うため、それなりのコストがかかります。第二置換表では、ハッシュを用いて実装してありますが、衝突した場合には単純に古い要素を消して上書きします。このため、メインの置換表に比べて高速に動作し、メインの置換表ではコストが大きすぎて適用できないゲーム木下部において動作します。

高速化のためのパラメータ調整

Move Ordering、置換表、反復深化法は共に、探索ノード数を少なくする効果がありますが、その反面それなりのコストがかかり、 NPS(Node Per Second; 1秒あたりに探索するノード数)を下げてしまいます。

ゲーム木の下の方(葉に近い方)ではこれらの手法の効果は少なくなります (単純αβ法で探索してもかかる時間が少なくなるので、これらの手法による高速化効果も限られてくるため)。しかし、これらの手法によるコストはほとんど変わりません。そのため、ゲーム木の下の方では、これらの手法を用いずに、単純αβ法で探索する方が (ノード数は増えますが)時間は短縮されます。

どこまでこれらの手法を用いるかは、実験的に決定しました。これらのパラメータは実装によって異なります。

vsOtha 13.09現在、終盤探索時には、置換表登録は高さ(height)10以上、 Move Orderingは高さ8以上のノードに対してのみ行っています。反復深化は高さ10のノードに到達するまで行い、 PVSはMove Orderingと同じ高さ8以上のノードに対して行っています。また、第二置換表は高さ6の盤面のみを登録します。まとめると下図のようになります。

また、中盤探索時には、置換表登録は高さ3以上、Move Orderingも高さ3以上となっています。反復深化は最後まで行います。

評価関数

終局盤面の評価

終局盤面の評価値は、基本的には黒にとっての石差 × 1000 としています。但し、全滅時は +64000 (白全滅負け) あるいは -64000 (黒全滅負け) とします。

狸ルーチン

いわゆる「古典的ルーチン」で、石差、隅にある石、Xにある石、着手可能数を元に算出します。実装は routine_general.cpp にあります。

狐ルーチン

概要

狐ルーチンは、 Michael Buro氏の論文 "Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello" を元に実装されています(但し完全に論文に従ってはいません)。実装は routine_fox.h/.cpp などです。

原論文(線形結合)とは異なり、狐ルーチンは3層パーセプトロン型ニューラルネットワークを使用して実装されています。これは、単に線形結合での実装に失敗したからです。中間層のユニット数は8にしています(コード上では変更可能となっている)。出力関数はロジスティック関数 f(x) = 1 / ( 1 + exp( - x / 8 ) ) を用いています。

ニューラルネットワークの入力(入力層ユニットの値)としては、以下のものを用いています。これらが、狐ルーチンが利用する盤面の特徴(feature)であると言えます。

注: ニューラルネット自体についてはここでは説明しません。他のWebページあるいは書籍等を当たってください。

パターン

概要

一番下の「パターン」について解説します(これ以外は明らかだと思います)。まず、hor/vert2パターンを例にして解説します。

hor/vert2パターンでは、緑のマスが8個あります。実際の盤面では、この8個のマスはそれぞれが黒か白か空きかのいずれかです。よって、これら8個のマスの状態は、左から順に「黒黒黒黒黒黒黒黒」や「黒黒黒黒黒黒黒白」や「空空空空空空空空」など、計3⁸ = 6561 通りあることになります。

線形結合の場合は、この6561通りのそれぞれにスコアを割り当てます。 hor/vert2以外のパターンに関しても同様にスコアを振り当てます。そして、与えられた盤面で出現しているパターンのスコアの総和を取ることで、その盤面の評価値とします。

狐ルーチンでは線形結合ではなくニューラルネットワークを使用していますが、やりたいこととしては同じようなことです。

対称性

hor/vert2の6561通りのうちには、「黒黒黒黒黒黒白白」と「白白黒黒黒黒黒黒」などのように、対称的なパターンも含まれています。「オセロの盤面の評価値(有利不利)は、盤面を回転させたり、左右反転させても変わらない」ということから、回転させたり左右反転させたりすると同じになるパターンは同じもの、と見なします。よって、これらの対称なパターンは、同一のパターンとして考えます。そのため、実質的なパターン数は約半分(3000強)になります。

実装上は、黒 = 0、白 = 1、空き = 2 として、「黒黒黒黒黒黒白白」を「00000011」という風に8桁の3進数の整数(インデックス)と見なし、そのインデックスでパターンを管理しています。そして、あるパターンAのインデックスを算出する時に、 Aとその対象形のインデックスをそれぞれ算出し、値の小さい方をAの正式なインデックスとして採用します。これにより、「黒黒黒黒黒黒白白」も「白白黒黒黒黒黒黒」も、インデックスは同じ00000011(3進数)となります。インデックス11000000(3進数)とそれに対応するデータ領域は使われません。

(この方式だとメモリの無駄が出る(約半分が無駄)ので、 vsOthaでは実際には無駄が出ないように詰めたりしているのだがとりあえず省略)

また、下図のように、緑のマスの位置を回転しても、同じと考えられます。よって、実質的にはhor/vert2の出現パターンは4つ取れることになります。 (diag8は2つ、corner2x5は裏返しも含めて8つ)

ニューラルネットワークとの組み合わせ

狐ルーチンのニューラルネットワークでは、hor/vert2の場合、 3000強通りのパターンそれぞれに対応する入力ユニットをひとつずつ持っています。

具体的には、「黒黒黒黒黒黒黒黒」に対応するユニット、「黒黒黒黒黒黒黒白」に対応するユニット、などのユニットがあります。

そして、出現したパターンに対応するユニットの値は「1」(複数出現したらその出現回数)、出現しなかったパターンに対応するユニットの値は「0」とします。

ニューラルネットの概観は下図のようになります。この図では、hor/vert2の「黒黒黒黒黒黒黒黒」が一回出現していることを表しています。 hor/vert2以外のパターンも(図には描かれていませんが)同様になっています。

学習

学習には、IOSの棋譜約30万件を使いました。棋譜を使うと、盤面とその最終石差の組を作れるので、それを元に学習を行います。

但し、この棋譜には間違いも含まれています。序盤の間違いなどは訂正が不可能あるいは困難ですが、終盤の間違い(結構多くあります)は完全読みにより訂正可能です。狐ルーチンの学習においては、最大最終20手分の完全読みを行って、棋譜を訂正して使いました。このことにより、評価関数の精度・強さ共に向上しました。

ステージ分け

また、狐ルーチンは、オセロ60手を4手ごとに15ステージに分割して、それぞれのステージごとに個別に学習を行っています。

スムージングやパターンの補填は、ニューラルネットワークなので単純にはできないのでやっていません。