オセロプログラム FOREST を開発した方の記事、Developing an Artificial Intelligence for Othello/Reversi の日本語訳です。
FOREST 作者に許可をいただいて公開しています。
執筆時期がやや昔であり、最新の情報を踏まえると異なる見解があるかもしれませんが、オセロ AI 開発全貌を知るにはとても良い記事だと思いました。
Logistello や Edax の偉大さとそれを支える技術、昨今の Neural networks による試みまでを、ざっくり(/時に深く)説明してくれています。
FOREST 作者が指摘してくれている(See: sensuikan1973/othello-complete-analysis/issues/1#issuecomment-716798458)ように、最近の進捗が反映されてない点には留意してください。今後最新情報踏まえて更新予定あるようなのでメッチャ楽しみですね。
以下翻訳。
前置き
詳細に入る前に、いくつかの基本概念と用語について話しておきましょう。
我々は何を AI と呼ぶのか? そして、AI を作るためにどんなアルゴリズムや手法を使えるのか?
- AI は、推論や学習の観点から、人間の脳の能力を模倣できるプログラムあるいはアルゴリズムだと一般的に認識されています。
ゲームをプレイする際、AI は、少なくとも人間に対して適度に優れた対戦相手であることが求められます。
実際に過去数年間で、ドラフツやオセロ,チェス ,囲碁などの特定のゲーム(e.g. 完全情報ゲーム)について、AI が人間のプレイヤーを打ち負かせることが分かってきました。 - AI を作るために、多くのアルゴリズムや手法が利用可能です。
単純なルールベースのものから高度な機械学習まで色々あります。
以下が、最も単純なものから最も複雑で強力なものまでの、現時点のマイリストです。
decision rules(決定ルール), game and position libraries(ゲームと配置のライブラリ), αβツリー探索, モンテカルロツリー探索, 遺伝的アルゴリズム, 線形回帰, ロジスティック回帰, ランダムフォレスト, 深層学習/Neural networks, 敵対的生成ネットワーク, 強化学習。
上記のリストには、明示的なプログラミング(つまりゲームの知識をアルゴリズムとして表現すること)が必要なものを含んでいます。
その他のアルゴリズムは、既知のゲームデータや結果から学習(教師あり学習)したり、最良の戦術や戦略自体を発見するための学習(教師なし学習)をしたりする能力を有している点に注意して下さい。
実際、多くの優れたプログラムでは、これらのアルゴリズムや手法のいくつかを組み合わせています。
以降の段落では、FOREST で使用している主な手法を、何が最も効果的で何が上手く機能しないかについてのアドバイスとともに、列挙しました。
詳細に入る
評価関数
特定局面の評価値を推定する関数のことです。
オセロゲームの従来の評価関数は、事前の戦略知識に基づいています。
例えば、プレイヤーの石数, 合法手の数, 石の配置の境界, 端や隅あるいは対角線などの特定パターン集です。
通常、評価は最終スコアの見積もり、すなわち 2 プレイヤー間の最終石差(-64 ~ +64)として表現されます。
オセロプログラミングの初期の頃、評価関数は経験的に求められていました。
つまり、大量のゲームをプレイした後に、プログラマーが手動で調整し、上記各パラメータの最適と思われる値を見つけていました。
そんな中、Michael Buro によって作られた有名なプログラムである Logistello を始まりとし、評価関数の係数は、既知あるいは十分に推定された多数の局面に適用されるロジスティック回帰によって自動的に計算されました。
その手法は優れていることが証明され、Logistello や EDAX あるいは Zebra などの後続のプログラムは、その手法を採用して他のあらゆるプログラムを打ち負かし、1997 年には世界チャンピオンを打ち負かしました。
FOREST は version 5.0 までは、配置,着手,境界パラメータと、手動調整による端や対角線,隅のパターンテーブルとを組み合わせた、基本的な評価関数を使用していました。
その評価関数は、対人戦においてはかなり上手く機能しましたが、Zebra などの最高峰のプログラムには匹敵しませんでした。
Minimax
最も基本的なツリー探索手法のことです。
これは、再帰的に、各着手後のそれぞれの局面の評価に基づいて、プレイヤーの着手の評価値を最大化しながら、対戦相手の着手の評価値を最小化しようとします。
Minimax アルゴリズムは、最適な解を見つけることを保証しますが、ツリーの拡張係数(各ターンにおける平均合法手数)次第では、非常に長い時間がかかってしまいます。
αβ
[α β] ウィンドウの範囲外にある場合に、ツリーの branch を刈り取る、Minimax の改善版です。
これは、前ノードの走査で、ウィンドウ範囲外の branch が、既に走査済みの branch から得られた部分的な結果に影響を与えないことを記憶することで可能です。
αβ は、Minimax 探索の大きな改善版であり、同等の探索時間のまま、探索深度を劇的に改善することができます。
Negascout
αβ の改善版。
特定のノードで最良の branch が探索されると、後続の branch が null window で探索され、既に見つかった最良の branch よりも優れているかをチェックします。
null window を使用した探索は、αβ 探索よりもはるかに高速なので、branch が適切に順序づけられている場合、つまり最良な branch が最初に探索される時、Negascout は大幅に時間を節約できます。
これは、branch の事前並び替えを優れた精度で効率的に実行できることが前提になります。
そうでないと、Negascout はプレーンな αβ よりも時間がかかってしまう可能性があります。
Prob-cut
αβ の多少の改善として、中間の深さでの値と、その値で分岐する事前計算された確率に基づいて "弱い" branch を自動的に cut するアルゴリズムが考えられますが、探索を深くしても大して改善されないでしょう。
Prob-cut と Multi Prob-cut の変化版は、注意深く調整すると、探索ツリーの大幅な刈り込みに繋がり、より深い探索が可能になります。
Logistello, NTest, Zebra, Edax などの、深い探索(20手以上の先読み)を備えたプログラムは、どれも Prob-cut の手法を使用しています。
ただし、Prob-cut はリスキーです。なぜなら、最終的には深い深度で良好な結果が得られる branch を cut してしまう可能性を常に抱えているからです。
個人的には、Prob-cut はあまり好かないので、FOREST では使っていません。
私は、Neural networks の正確性と、深度に応じて着手の評価を適切に順序付ける機能により、探索深度が遥かに浅くても、Prob-cut と同様あるいはそれ以上の結果が得られると考えています。
Neural networks
Neural networks は、入力を受け取って線形結合を適用し、非線形活性化関数に従って次のニューロンに信号を発する "neurons" の結合です。
ニューラルネットのデジタルニューロンは、人間のそれを単純にモデル化したものです。
ニューロンの数とそのパラメータは、入力信号を適切に処理する方法を学習するニューロンの能力を大まかに調整します。
Neural networks は、推定や予測, 分類, パターン分類(画像認識), 意思決定およびその他多くの用途に使用できます。
オセロのようなボードゲームは、Neural networks と関連づけられるいくつかの要素を持っています。
パターン(盤面上の石の配置)が重要であり、スコアが常に有限の範囲 [0, 64] で予測可能です。
また、勝率を高めるために学習可能な戦術や戦略が存在します。
基本的に、盤面上の石の配置を考慮すると、両プレイヤーが全ての手番で最善手を打ち続けた場合、とりうる最終スコアは 1 つだけです。
オセロは、チェスや囲碁のような "完全情報ゲーム" なわけです。ポーカーとは違います。
ニューラルネットの仕様には 2 つのフェーズがあります。
- 訓練フェーズ。既知の入力と結果がセットになったデータを使い訓練します。各ニューロンとその活性化関数のパラメータを反復的に改良するアルゴリズムが用いられます。この手法は、ニューラルネットが模倣するための既知のデータセットが必要なので、"教師あり学習" として知られています。
- 予測フェーズ。ニューラルネットが 1 で得た知識を、1 では見たことない未知の入力に対して適用し、結果を予測します。
訓練フェーズでは、多くの "タグ付き" サンプル、つまり出力が分かっている入力サンプルが必要になります。
Neural networks のニューロン数が多いほど、訓練サンプルの量も多く必要になります。
オセロに関して言えば、私の経験上、スコアを適切に推定できるニューラルネットワークには、数百から数千ものパラメータがたやすく要求されます。
つまり、非常に多くのゲームデータ、それも全手番における全合法手の最終スコアが必要になります。
オセロには WTHOR データベースのようなライブラリが存在し、人間やコンピュータのプレイしたゲームが 10 万局以上含まれています。
しかしながら、そのようなライブラリは十分ではありません。主な理由は、全手番の局面に対する最終スコアが常に分かっているとは限らないためです。
WTHOR データベースでは、空マスが 24 以下の局面のみについて最終スコアが求められています。
しかし、各ゲームのプレイヤーの強さに依存して、盤面上で空きマスが多い場所は、多かれ少なかれ一定です。
そして何より、10 万というゲーム数は、本当に必要とされる "良い" ゲームの数よりも桁違いに少ないです。
これは実際には、EDAX, NTEST, ZEBRA などの既知の優れたプログラムを使用し、それらを互いに対局させるなどして、たくさんのゲーム数を追加する必要があることを意味します。
予測フェーズでは、ニューラルネットワークが盤面上の石の配置を "観察" し、多かれ少なかれ正確に最終スコアを予測します。
予測が正確であればあるほど、プログラムは上手くプレイします。
私の経験上、良い精度を得ること、すなわち配置から正確な最終スコアを予測することはとても難しいです。
なぜならオセロのゲームはとても "混沌" としているからです。
というのも、毎手番たくさんの石がひっくり返って配置パターンが大きく変わりうるからです。
そのオセロの特性はゲームが終盤になるにつれて増すため、終盤あるいは終局直近を除いて、配置を調べるだけで 1 石単位の精度で最終スコアを推定することはほぼ不可能です。
しかし、ニューラルネットワークが基本的に "評価関数" として機能することに気づいた場合は、少し異なる方法で使用することができます...
伝統的なオセロ(またはチェスや囲碁)のプログラムは、αβ ツリー探索と評価関数を組み合わせてゲームの着手を予測し、特定の局面あるいは着手のスコアを推定します。
その伝統的な αβ アプローチをニューラルネットワークと組み合わせて評価関数として使うのはどうでしょうか?
それこそが FOREST の行うことであり、上手く機能します。
実際私は、αβ が、ニューラルネットワークによって計算された推定を "平滑化" しており、深さが増すに連れて推定精度が高くなることを観測しました。
数学的な証明をしたわけではありませんが、私の推測では、葉の数がとても多い αβ は、ニューラルネットワークの精度を向上させる手法として知られている、"バギング" や結果の "アンサンブル" をしています。
その手法には一つ注意点があります。
ニューラルネットワークは従来の評価関数よりもはるかに膨大な計算を要するため、Negascout によって改善された αβ でもさほど深く掘り下げることができません。
ZEBRA や EDAX などの従来のプログラムは 24 手先のゲームを簡単に探索できますが、ニューラルネットワークでは 12 手先に到達することは既に挑戦的な課題となっています。
しかし...ニューラルネットワークは、従来の評価関数よりもはるかに正確に推定を行うので、先読みの深さが浅い点を補えます。
さて、ニューラルネットワークが比較的正確なのはなぜですか?
- 主な理由は、非線形関数を近似するニューラルネットワークの機能です。これまで、オセロプログラムで使用されている全ての評価関数は線形です。
すなわち、盤面上の配置や合法手,パリティ,特定の配置パターンに与えられた値など、いくつかの変数を線形に結合しているわけです。
これらの変数パラメータは、FOREST の初期バージョンなどの古いプログラムで経験的に決定されてきました。
そして、Michael Buro の有名な Logistello プログラムが登場して全ての既知のプログラムを凌駕し、ついに 1997 年に世界チャンピオンを打ち負かして以降、線形回帰あるいはロジスティック回帰によって決定され始めました。
しかし、Logistello によってプレイされたゲームと他の線形回帰を使用したプログラムのそれとを分析すると、バランスのとれたスコア(石差が0に近い)の配置ではとても正確に推定できますが、そうでない時に重大な間違いを犯しうることに、我々は気付きました。
これは、スコアが [-4, +4] の線形領域を外れる時に見られる、線形的な評価関数の限界に関するヒントです。
その点ではニューラルネットワークが明らかに優れています。
実際には、評価関数の非線形性の種類を知る必要はなく、十分な盤面配置サンプルを用意できれば、とにかく近似することができます。
- ニューラルネットワークが優位なもう1つの理由は "一般化" する機能、すなわち、未知のサンプルを適切に評価する機能です。
十分な数の既知のサンプル(通常は非常に多数)でニューラルネットワークを訓練したと仮定すると、未知のサンプルに対して適切な評価を求めることができます。
この一般化の機能は、オセロ,チェス,囲碁などのゲームにとって絶対的に重要なものです。
というのも、それらのゲームでは、盤面配置のパターン数が非常に多いため、それらを記憶したり、全てについてニューラルネットワークで訓練したりすることは事実上不可能だからです。
例えば、オセロのゲームパターン数は 10^58 と推定され、ありうる局面パターン数は 85 * 10^27 と推定されます。
Neural networks の種類
Neural networks は様々な構造を持つことができ、様々な種類のニューロンの組み合わせで構成できます: 完全に接続されたニューロンで構成される高密度層,CNN(畳み込みネットワーク),RNN(再帰型ネットワーク),ResNet(残差ネットワーク)などです。
オセロなどのボードゲームに関して言えば、基本的には 3 つのアプローチがあります。
- 盤面を、CNN がパターン認識して評価する画像と見なす
- 盤面上の各マスを、密に接続されたニューラルネットワークへの独立した入力と見なす
- 盤面をいくつかの領域に分割し、パターンにマッピングした後、密に接続されたニューラルネットワークに食わせる
最初のアプローチは、19×19 といった非常に大きい盤面サイズを持つ囲碁などで非常に上手く機能します。
なぜなら、畳み込みニューロンが盤面をスキャンし、盤面のエッジにあまり邪魔されることなくパターンを検出できるからです。
AlphaGo は、囲碁の石配置パターンを検出するのに CNN が非常に効率的であることを証明しました。
しかし、オセロ(そしておそらくチェスでも)の場合、私の経験から言うと上手く機能しません。
というのも、8×8 ボードでは、3×3 畳み込みニューロンはエッジに当たる前に各次元で6回しか移動できないこと、オセロにおいてエッジやコーナーはとても重要なことを考えると、畳み込みニューロンがその 3×3 パターンについて十分に一般的なことを学習できないことになるからです。
そしてさらに悪いことに、3×3 畳み込みニューロンの 2 番目の層は 4 回しか移動できません。
私はこのアプローチを諦めました。
2 番目のアプローチは、理論的には完璧ですが、大きな欠点があります。
各マスが (-1, 0, +1) の 3 値をとりうる入力と見なされる場合、N 個のニューロンの最初の密な隠れ層は N×64 の行列乗算を、次の M 個のニューロンの層では N×M の行列乗算を実行する必要があります。これはとても多いです。
結果として得られるニューラルネットワークは遅くなり、αβ の深さに深刻なペナルティを課すことになってしまうため、評価の全体的な精度が低下します。
このアプローチのもう一つの欠点は、訓練に必要な局面パターン数が非常に多いことです。
私はこのアプローチをすぐに諦めました。
3 番目のアプローチは、私が現在使用しているアプローチであり、かなり上手く機能します。
盤面をいくつかの領域に分割すると、オセロゲームの 8 軸の対称性を活用できます。
各領域を限られた数のパターンにマッピングすることで、次元削減を適用できるのです。
言語辞書の単語にシーケンス番号を付けるのと同じように、各パターンを番号で表すことができるという考え方です。
これを実行したら、自然言語処理のよく知られた手法である、単語/パターンの埋め込みを適用できます。
このアプローチの利点は、訓練時に、それぞれの離散的なパターンを浮動小数点値の適度なサイズのベクトルに自動変換することができ、直接高密度層に注入できることです。
埋め込み層の係数は数が非常に多いですが、それらは訓練時に計算されます。大幅に入力の次元数を削減することで、埋め込み層が、最初の密な隠れ層の乗算数を制限します。
これは、事前に計算された高密度層が最初の層にあると見なすことができますので、ニューロン 1 つの層とそこに紐づくコストのかかる行列乗算は基本的に節約可能です。
ニューラルネットワークのもう一つの側面は、深さ(隠れ層の数)と幅(各層のニューロン数)です。
最初は、解決する問題は複雑であるという信念に駆られて、ネットワークに多くの層と多くのニューロンを配置したくなりがちです。
そのアプローチは、過学習に繋がります。正しいアプローチは、最も単純なネットワークから始めて結果を確認し、レイヤーのニューロン数を増やして精度を向上させていくことです。
パーセプトロンとして知られる 1 層ニューラルネットワークは、既に普遍関数近似器であることに注意してください。
すなわち、任意の連続する関数について近似できるため、既に非常に強力です。
最終的に、ニューラルネットワークの各層には活性化関数があります。
Sigmoid, Tanh, Relu,および PRelu を試した後、当然のことながら、Relu 系が最もよく機能し、Leaky Relu は標準の Relu よりも僅かに優れていることが分かりました。
PRelu(Parametric Relu)も試しましたが、それ以上の精度は得られず、遥かに多くの訓練が必要でした。
ニューラルネットワークの最後の側面は、出力層です。
主に 2 つのオプションがあります。
- 線形活性化関数を持つ単一のニューロン。これは、ニューラルネットワーク全体を非線形回帰関数として使用することと同等であり、特定の局面のスコアを直接推定します。このアプローチの不便な点は、出力ニューロンの結果が無制限な浮動小数点の値であるのに対し、任意の実数値は [0, 64] または [-64, +64] の範囲の有界整数であることです。
- Softmax ニューロン。これは、ニューロンネットワークを分類関数として使用し、65 のスコアをそれぞれクラスとして使用することに同じです。このアプローチには 2 つの利点があります。適切な範囲で直接スコアを取得すること、さらに、その結果がどのくらいの確率で正しいかを取得できることです。これはとても興味深いことです。
何回もの試行を経て、私は最終的に...最初のアプローチを選択しました。
その理由は、Softmax 関数は実行時に計算するのに非常にコストがかかり、多くの乗算と指数関数が必要になるためです。
2 番目のアプローチは確かに比較的正確ですが、遅すぎるのです。時に我々は妥協することも必要です。
特徴エンジニアリング
続きはまた今度。
訓練データ
ニューラルネットワークには多くの訓練データが必要です。
ネットワークのパラメーターが多いほど、勾配降下法を使用してそれらのパラメーターを調整するためのデータが必要になります。
私が FOREST で使用しているニューラルネットワークには、それほど多くのニューロンがありません(70未満)が、その埋め込み層とゲームの複数のフェーズのために、それぞれが独自のパラメーターセットを持っているため、全体で 100 万を超えるパラメーターがあります。
この 100 万以上のパラメータを優れた精度で計算するには、数億のラベル付き局面、つまり、正確あるいは適切な近似値で最終スコアがわかっている局面が必要です。
しかし、どうやってそのような膨大な数のラベル付き局面を獲得しましょうか?
いくつかのオプションがありますが、とにかく、人間やコンピューターがプレイした、膨大な量のゲームが必要です。
ゲームの最初のセットは WTHORデータベース にあり、トーナメント中にさまざまな強さの人間とコンピューターとの間でプレイされた 10 万 を超えるゲームが含まれています。
しかし、これらのゲームは十分ではなく、スクリプトで簡単に使用できる EDAX などの参考プログラムと対峙させることによって、そのデータベースを補完する必要があります。
これらの自動生成されたゲームは、ランダムオープニングで開始することも、モンテカルロ木探索(MCTS)によって生成することもできます。
ゲームの数が多い場合は、それらのゲームの各局面の値を計算する必要があります。
EDAX や高速マルチコアコンピュータなどのプログラムを使用すると、空マスが 26 個以下の局面を解決するのはかなり高速ですが、空きマスがそれ以上に多い局面を解決するのは遅いか、不可能ですらあります。
残された唯一のオプションは、それらの局面の値を可能な限り正確に推定することです。
これは2つの方法で行うことができます:
独自の αβ 探索および評価関数でそれらの局面を評価するために参考プログラムを使用するか、ゲームのデータベースで統計を作成してゲームツリーの minimax 順序で各局面の値を推定するか です。
また、オセロゲームには 8 つの対称性があることを忘れないでください。これは、訓練データセットを 8 倍に増やす簡単な手段を提供してくれます。
オセロをプレイするための優れたニューラルネットワークを訓練するために必要なものが何かを示すものとして、FOREST は 100 万以上のゲームのデータベースを使用しています。
また、データベースに追加するゲームが多いほど、精度が向上します。ニューラルネットワークの訓練は終わりのないプロセスなのです。
多くの技術的な理由から、そしてニューラルネットワークの一般化を支援するために、入力データと出力スコアの両方を正則化、つまり[-1,+ 1] の範囲にスケーリングする必要がある点に注意してください。
理想的には、隠れ層の中間出力も正則化(Batch Normalization)する必要がありますが、これは予測時に困難を引き起こしますし、オセロの場合のように隠れ層の数が少ない場合は絶対に必要というわけではありません。
学習不足と過学習
ニューラルネットワークの定義と訓練の主な課題の 1 つは、未学習と過学習の間に存在する狭い領域にとどまることです。
- 未学習とは、ニューラルネットワークが小さすぎて訓練データから十分な情報を抽出できず、テストデータに対する予測精度すら低いことです。解決策は、ネットワークの隠れ層にニューロンを追加(より広いネットワーク)するか、より多くの層(より深いネットワーク)を追加するか です。
- 過学習とは、ニューラルネットワークが大きすぎてパラメーターが多すぎるために、全ての訓練データを期待される出力とともに保存できるメモリバンクになる一方で、未知のデータに対して適切な予測を行うことができない状態です。解決策は、ネットワークを単純化する(より狭い層やより少ない隠れ層)か、ネットワークが全てを記憶できないような訓練データを追加するか、または "ドロップアウト" や正則化などの手法を使用することです。
過学習はとても簡単に検出できます。というのも、ネットワークの精度が訓練データについては優れたスコアに達する一方で、検証データセットに対しては不十分なままになるからです。
簡単に検出できるとはいえ、解決するのは難しい問題です。
訓練データを入手することが高くつき、訓練データを追加するのが難しい場合があります。オセロはまさにこれに当てはまります。
ドロップアウトやバッチ正規化などの、効率的であることが知られている手法は、訓練時に簡単に適用できますが、ニューラルネットワークを評価関数として使用する場合は深刻な問題を引き起こします。
なぜなら、ニューラルネットワークは局面のバッチではなく個々の局面で使用されるため、個々の局面の評価に対するドロップアウトとバッチの正規化の影響を補正することは非常に困難です。
オセロにおける私の経験上、実用的には、過学習を防ぐ唯一の手法は、ネットワークのサイズと深さ、および L2 正則化を適切に調整することです。
正則化と一般化
ニューラルネットワークと深層学習の主な差別化要因の 1 つは、一般化する機能です。
つまり、訓練データセットを学習して獲得した知識を未知の入力に適用し、意味のある予測を提供します。
ただし、その一般化機能は、ニューラルネットワークが過学習していない場合、つまり、その係数が訓練データセットに正確に一致するようにカスタマイズされていない場合にのみ機能します。
これを達成するために私が見つけた最良の方法は、ニューラルネットワークの最大の係数(または重み)にペナルティを課す L2 正則化です。
これにより、これらの重みを妥当な範囲に保ち、入力を正確に一致させてしまう極値に至るのを回避します。
"ラムダ" として知られる正則化パラメーターの調整には注意が必要です。
小さくする以外にルールはありません。たとえば、10e-5 の範囲です。
小さすぎると効果がありませんし、大きすぎると予測精度が低下します。
正しい値を見つける適切な方法は、検証データ(not 訓練データではない)の予測が最適化されるまで、さまざまな値を試すことです。
私がオセロで観察したことは、ゲームが進むにつれてラムダが漸進的に減少しているということです。
これは、オセロゲームの序盤が比較的戦略的である(つまり、優れたプレーヤーが "一般的な" 戦略ルールを適用して堅実な着手をする)のに対し、ゲームの終盤はより戦術的である(つまり、プレーヤーがトラップを試し、最終スコアを最大化するために安定してカウンティングを行う）という直感と一致しています。
モンテカルロ木探索と UCB
モンテカルロ法は、ランダム性に基づく数学的手法の一種です。
その名前は、モンテカルロのカジノにあるゲームのランダム性に由来しています。
オセロ(およびチェスや囲碁)などのゲームに適用される特定のモンテカルロ法の 1 つは、従来の αβ ツリー探索の代わりに使用できる、モンテカルロツリー探索(MCTS)です。
最適なブランチのスコアについてツリー構造を探索する MCTS のアイデアは、ブランチのサブセットをランダムに探索し、探索されたブランチのスコアの平均が最適なスコアになると想定することです。
ランダムな分岐を取得するほど、推定値は理論上の結果(αβ で取得可能)に近づきます。
MCTSは非常に効率的です。
なぜなら、実用的には、結果の適切な見積もりを取得するために、非常に少数のブランチを探索、つまり、非常に少数のゲームをプレイまたはシミュレートするだけで良いからです。
シミュレートする必要のあるゲームはいくつでしょうか?
それは状況によって異なります...
数学的な証明はありませんが、私の直感では、ゲームの "静かさ" または "安定性" に依存します。囲碁やチェスなどのゲームは比較的静かです。
おそらくチェスゲームの最後のマットフェーズを除くと、盤面上のマスの強みや価値が荒々しく変わることがなく、ゲーム全体を通して比較的静かに変動するからです。
したがって、AlphaGo プログラムによって証明されているように、MCTS は囲碁で非常にうまく機能します。
しかし、オセロは囲碁やチェスとはかなり異なります。
オセロゲームの序盤は比較的静かですが、終盤に近づくにつれて混沌とし、最後 20 回の着手で、スコアは全ての着手で完全に変わる可能性があります。
完全にランダムなゲームをプレイすると、分散の大きい確率変数の平均スコアが得られるため、オセロは MCTS にとって課題となります。したがって、予測スコアは無意味になります。
MCTS をオセロに適応させるにはどうすればよいですか？
- 最初のアイデアは、純粋なモンテカルロ探索のランダム性を減らすことです。つまり、単にランダムなブランチを探索するのではなく、ツリーの各ノードで可能な限り最高の着手を選択します。これは、以下の 2 つの方法で実現できます。
- 探索されたことのないノード、または探索されていないブランチが存在するノードに到達した場合、既知の信頼できる評価関数を使用して、最良な着手を選択できます。
- 全てのブランチが少なくとも 1 回探索されたノードに到達したら、最良の結果が得られると予想されるブランチ、つまりこれまでで最高の平均スコアが得られたブランチを選択するか、"良好な可能性" がある別のブランチを探索します。
しかし、どのようにその選択をしますか?
これはとてもよく知られている問題であり、カジノで最高のスロットマシンを選択することから類推して、"K-Armed Bandit(多腕バンディット)" 問題として知られています。
これには、優れた解決策がいくつかあります。
実装するのが最も簡単な選択アルゴリズムは、いわゆる "Upper Confidence Bound"（UCB）アルゴリズムであり、特にそのUCB-1 または "UCB-1tuned" バリエーションが使われます。
よりはやく収束するもう 1 つの優れたアルゴリズムは、"Thomson Sampling" アルゴリズムですが、実装が比較的複雑です。
- 別のアイデアは、オセロゲーム終盤の混沌とした性質を克服することです。
私が観測したところによると、ゲームの最も難しいフェーズは、42 ~ 48 手目の間、つまり 12 ~ 18 個の空きマスが存在するフェーズです。
これは、最後の 18 マス空きに到達した時にゲームを正確に解決することで、MCTS によってテストされる各ゲームの品質が大幅に向上することを意味します。
実際には、さらに優れた方法で、20 個以上の空きマスのあるゲームを解決するのは簡単です。
これは、EDAX などの高速な終盤ソルバーを使用することで、ほんの一瞬で求められます。
にも関わらず、MCTS アルゴリズムに対するこれらの改善は、負の結果をもたらします。
パフォーマンス上の理由から、実行時、つまりライブゲームの間は、MCTS がほとんど使用できなくなります。
これは、全ての着手で適切な選択アルゴリズムを実行する必要があること、全ての 18 マス空きの終盤を完全に解く必要があること、また、短時間でテストできるゲームの数を減らす必要があること(個人の手が届かない巨大な並列システムを無料で利用できる場合を除く)が理由です。
αβ とその最適化された変形版は、依然としてライブゲームに最適なオプションです...
では、MCTS はそれでもなお有用になりうるのでしょうか? はい、2つの領域で有用になりえます:
- ニューラルネットワークを訓練するために、意味のある適切に分散された局面を生成します。
MCTS は、オセロのゲームツリー全体の最良のブランチを自動的に探索します。そして、生成されたツリーにはスコアの現実的な分布があるので、そこから得られるいくつかの統計値から、各ノードの適切な推定値を抽出します。
これは、ニューラルネットワークの教師あり学習に最適です。 - オープニングライブラリの構築。
オセロのゲームツリーを探索している間、MCTS は徐々に最良のブランチに焦点を合わせ、弱いブランチを棄てていきます。
これは、まさにオープニングライブラリを構築するために必要なことです。
理論的には、UCB-1 や Thomson Sampling などのアルゴリズムは、K-Armed Bandit 問題の最適解に向かって収束することが知られています。
オセロに関して言えば、MCTS に十分な時間が与えられると、最終的に 2 人のプレーヤーにとって最適なゲーム、つまり、どちらのプレーヤーもミスを犯していないゲームに収束することを意味します。
念のため言及しておきますが、8x8 のオセロが解決されたことはないものの、最適なスコアは引分であるという強い疑念があります。ただし、それは証明されていません。
オセロのゲームを解決するための MCTS の潜在的な使用法は非常にエキサイティングですが、残念ながら私の経験上、収束は非常に遅いです。
何万ものシミュレーションゲームの後、どのブランチでも 8 手目の着手で収束が見られませんでした。
したがって、オセロを解決するにはまだ長い道のりがあります。
しかし、AlphaGo で使用したのと同じ計算能力を使用すれば、Google Brain チームがそれを成し遂げるかもしれません。
ビットボード
バージョン 5.x までの FOREST を含め、初期のオセロプログラムのほとんどは、盤面をバイトのベクトルとして内部的に表現および操作していました。
たとえば、8×8 の盤面に加え、端を表現する 2 つの行/列を追加することで、盤面を横断ループする際にエッジの検出を用意にしていました。
結果として 10×10 = 100 バイトになります。
ボードの各マスには、3 つの状態値が含まれています。
たとえば、空きマスの場合は 0、白石の場合は 1、黒石の場合は 2、あるいは (-1, 0, +1) です。
その表現は単純で、ゲームの基本的なアルゴリズム(空きマスを見つける、合法手見つける、着手して相手の石を裏返す、ゲームをコピーする)を数行のコードで実装することができました。
ただし、この表現方法には大きな欠点が 3 つありました。
- ループの激しい使用は、CPU パイプラインを破壊し、プログラムの速度を大幅に低下させていました。
- 石を操作するたびに、メモリへのアクセスが必要でした。
- 多くの着手を試みるゲームツリーの探索は、メモリヒープ内に同数の盤面コピーを存在させたり、評価後に全ての着手がプレイされない原因となりました。どちらの操作も非常にコストがかかります。
もちろん、CPU は世代を重ねるごとに改善されますし、分岐予測が改善されるとループのコストが削減されます。内部キャッシュが大きくなると RAM にアクセスする必要性が減り、ブロックコピー操作が最適化されてゲームボードのコピーコストが削減されます。さらに、順序付けと並列実行により、石の反転と反転解除のコストが削減され、パイプラインが深くなりました。
また、FOREST 4.x などのプログラムは、主要なアルゴリズムを改善するためにループを展開する手法を広範囲に使用していました。
しかし、真のブレークスルーは、ゲームボード全体をレジスタのペアに格納できる新世代の 64 ビット CPU によって実現しました。
片方のレジスタに各マスに白石(0または1)の存在を格納し、もう一方のレジスタに黒石を格納するのです。
ボード表現を保持および操作するために 64 ビットレジスタのペアを使用する新しい手法は、"ビットボード操作" と呼ばれます。
ビットマスキング、シフト演算、および古典的な and/or/xor でのビット単位演算を使用すると、オセロ(およびチェス)をプレイするための非常に高速なルーチンの開発が可能になります。
RAM にアクセスせずに、いくつかの命令で特定局面の全合法手を一覧表示することもできます。
このアルゴリズムは Dumb7Fill として知られています。
FOREST では、バージョン 5.x でビットボードを使い始めました。
これにより、プログラムの速度が約 40 %向上しました。実際のところ、これは私が予想していたよりは少ないです。
おそらく、プログラムが既に非常に最適化されていて、最新の x86 CPU がデータのキャッシュ/フェッチとブランチの予測に非常に優れているため、ボードゲームのベクトル表現の欠点が大幅に軽減されたためです。
しかし、ともかく 40 %もの改善を得られるのですから、ビットボードを採用することに労力を費やすのは価値があることです。
マルチスレッド
最近の CPU はますます多くのコアを備えており、物理コアごとに複数の論理スレッドを実行することさえできます。
実際のところ、CPU 馬力の増加は、コア周波数または IPC (1サイクルあたりの命令数)の増加というよりも、主にコア数の増加(水平スケーリング)によるものです。
ただし、CPU 自体では全てのコアにワークロードを分散できないため、これら全てのコアの能力を活用することは依然として困難です。
アプリケーションのロジックは、全てのコアを活用するように変更する必要があり、OS には使用可能な全てのコアにワークロードのスレッドを分散できるスケジューラが必要になります。
オセロプログラムでマルチコアアーキテクチャをどのように使用できるでしょうか?
FOREST によって生成されるコンピューティングワークロードは、ゲーム中の αβ ツリー探索、評価関数として機能するニューラルネットワーク、ゲーム終盤の Win-Loss-Draw 探索、および正確なスコア決定といった 4 つの主要アルゴリズムで構成されます。
これらの各アルゴリズムは、並列処理を検討する良いポイントです。
- αβ アルゴリズムには分散バージョンがあります。その基本的な考え方は、新しいブランチを評価する必要がある場合に、そのブランチを評価するタスクを新しいスレッドで処理するというものです。このようなアルゴリズムは、いくつかの理由により、あまり拡張性がありません。
- αβ アルゴリズムは、役に立たないブランチをカットする際に、前ブランチの結果から得られる知識に大きく依存しています。つまり、各ブランチ評価の間には順序依存関係があります。
- 評価するブランチの数が多いと、それと同数のスレッドを起動する必要があるため、スレッドプールメカニズムを使用しない限り、大量のスレッドスイッチとオーバーヘッドが発生します
- 転置により、複数のブランチが同じ局面に到達する可能性があります。そこで、同じブランチが複数回評価されるのを避けるために、一般的に、クリティカルセクション(Mutex)で保護されたハッシュテーブルに基づいた、複雑な転置テーブルが必要になります。
要するに、分散ツリー探索は実装が難しい上に、その利点が利用可能なコア数に比例して増加することは無いということです。
EDAX のような非常に強力なプログラムはその方法を使用しますが、私はこの方法を選択していません。
- FOREST によって生成されるワークロードは、少なくともゲーム終盤以前においては、何千もの浮動小数点演算を必要とするニューラルネットワークの計算が支配的になります。
SIMD 命令(Intel / AMD CPU の AVX2)は間違いなく役立ちますが、ニューラルネットワークはワークロードの少なくとも 80 %を占め、残りは αβ ツリー探索中に着手して進行するためのビットボード操作です。
また、複数のニューラルネットワーク評価を並行して実行できる場所が 2 つあります。- ツリー探索中にノードを調べる場合、最良のブランチを最初に調べると、αβ のパフォーマンスが大幅に向上します。
最初に最適なブランチを選択する 1 つの方法は、対戦相手の合法手から生じる全ての局面について手番側のスコアを推定し、その値に従って調べるためにブランチを順位付けすることです。
これには、いくつかの局面を評価することが必要です。(合法手数の最大値は理論的には 32 ですが、実際の制限は約 26 です)。
これは並行して実行できます。
別のアプローチは、ニューラルネットワークに追加の出力層を追加して、その局面の値を提供することに加えて、特定の局面における合法手全てを順位付けすることであることに注意してください。
このアプローチは "ポリシーヘッド" として知られており、AlphaGo によって使用されて成功を収めています。
それは確かにオセロでも機能しますが、順位付けでどのような精度に到達できるかを確認するためにテストする必要があります。 - 探索ツリーの最も深いノードごとに、全てのリーフ、つまりすべての局面を評価して、最高のスコアを持つものを見つける必要があります。
実際、αβ 探索アルゴリズムでは、一部は通常カットされるため、全てのリーフを評価する必要はありません。
ただし、いずれにせよ、評価の一部が実際に使用されていない場合でも、最も深いノードの全てのリーフを並行して評価できます。
これは、CPU に十分なコアがあるかどうかは関係ありません。
- ツリー探索中にノードを調べる場合、最良のブランチを最初に調べると、αβ のパフォーマンスが大幅に向上します。
- ゲーム終了時の勝ち負けの探索については、空きマスが 24 個以下の場合は、通常単純化された minimax 探索が実行され、各プレーヤーの勝ちあるいは null の着手を探すだけで済むので、最高のスコアを探すよりも遥かに高速です。
この探索には、並列処理が可能なポイントが 3 つあります。- 探索ツリーのルートでの着手ごとに、勝ち -> 引き分け あるいは 引き分け -> 勝ち の順で探索する必要があります。
もちろん、引き分けが既に見つかっていない限り、勝ちと引き分けを並行して探索するのは興味深いことです。 - 探索ツリーのルートでの各着手は、勝ちあるいは少なくとも引き分けが見つかるまで、最終的に勝ちまたは引き分けを探索する必要があります。
したがって、全ての着手を並行して探索することができ、最初のブランチが勝ちまたは少なくとも引き分けを選択します。
もちろん、一部のブランチは、負けの場合に何も分析されないことがありますが、十分なコアが利用可能であれば、それは問題になりません。
理想的には、十分なコアがある場合、全ての着手が 1 つの着手を犠牲にして分析されます。
これは非常に大きな利点をもたらし、探索深度を 1 手分増やすことができます。これはゲームの終盤で非常に重要です。 - Win-Draw-Loss 探索は高速であり、オセロはゲーム終盤が最も不安定なフェーズであるため、ゲーム終盤で勝ちと引き分け、または引き分けと負けを区別することは簡単にできます。
また、ゲーム中盤に +/- 2 石差の精度の推定を達成することは非常に困難です。
したがって、可能性のある賢い手法は、通常の αβ による中盤探索と並行して、ゲームの序盤で、例えばゲーム中盤の終わり(30〜24マス空きの局面)の時点で Win-Draw-Loss 探索を開始することです。
Win-Draw-Loss 探索は、αβ が完了する前に勝ちを見つけるでしょうから、メリットだと言えます。もしかすると αβ が先に完了して Win-Draw-Loss 探索が中断されるかもしれませんが、それは特に問題になりません。時間が失われるわけではないため。
- 探索ツリーのルートでの着手ごとに、勝ち -> 引き分け あるいは 引き分け -> 勝ち の順で探索する必要があります。
- ゲーム終盤の正確なスコアの決定は、従来の αβ、またはその最適化された変化形の 1 つです。
ツリーのルートでの着手は並行して評価できますが、以前の兄弟ノードの評価を活用する Negascout などの αβ 最適化の利点が減少します。
ゲーム中の探索の場合と同様に、他の可能性は、最初に調べるブランチの決定に並列処理を使用することです。
これにより、αβ 探索の効率が常に向上します。
mult_threading を使用して何を並列化できるかが決まったら、次の質問は「どのようにやるか?」です。
C++ 言語と標準テンプレートライブラリ(STL)は、C++11 以降、優れた高レベルのマルチスレッドおよび同期プリミティブである Future オブジェクトと Promise オブジェクトを提供します。
これは、非同期ジョブを起動してその結果を待つのにとても便利です。
これらの高レベルなプリミティブが抱える問題は、オーバーヘッドです。それらは信じられないほど遅く、マクロタスクにしか適用できません。
それらを使用してニューラルネットワークの複数の計算などの小さなタスクを並列化することは、実際には計算を逐次実行するよりも遅くなります。
これには2つの理由があります。
- C++ ライブラリは、タスクごとに動的にスレッドを作成し、タスクの最後にスレッドを解放します。
ただし、Windows でスレッドを作成することは非常にコストがかかり、ワークロードが十分に大きくない場合、タスクによって実行されるワークロードよりも重くなってしまいます。
それは Linux でも同様ですが、Windows 程ではありません。 - 作成されるスレッド数は制御されないため、CPU で使用可能なコア数よりも多くなる可能性があります。その結果、不要なタスクスイッチが発生することがあります。
上記 2 つの問題の解決策は、"スレッドプーリング" と呼ばれ、プログラムの初期化時に固定数のスレッドを作成し、必要に応じてそれらのスレッドにワークロードを割り当てることで成り立ちます。
これにより、スレッドを動的に作成するコストが排除され、同時に実行されるスレッド数を正確に制御できます。
残念ながら、これまでのところ、C++ には標準のスレッドプールメカニズムがありません(一部の C++ スレッドプリミティブはWindows スレッドプールメカニズムを使用しますが、それは制御下にありません)。
したがって、唯一の解決策は、C++ STL の低レベルな条件変数(Condition Variables)と Mutex プリミティブを使用して、カスタムスレッドプールメカニズムを開発することです。
Mutex メカニズムは、それ自体がマルチスレッドのパフォーマンスに大きな影響を与えます。
スレッドプールの実装では、Mutex を使用すると、特定のスレッドがタスクの実行を待機したり、使用可能なタスクを選択して実行したりできます。
したがって、ニューラルネットワークの計算などの比較的小さなタスクの場合、Mutex のテスト、スレッドのブロック、およびスレッドの起動にかかる時間は重要になってきます。
問題は、コンパイラが異なれば std::mutex オブジェクトの実装も異なることです。
GCC/G++ は Pthread POSIX ライブラリに依存しますが、Visual Studio C++ は Windows Mutext メカニズムに依存します。
また、Pthread の実装は、標準の Windows Mutex よりも少なくとも 10 倍は高速です。
これは、Pthreads が Windows の "Critical Section" に依存しているためです。
これは実際には、OS の "user level" で実装されたスレッド間の排他メカニズムですが、Windows Mutex はカーネルレベルで実装されたプロセス間の排他メカニズムであり、OS のカーネル層にアクセスする必要があります。
したがって、Windows Mutex は、プロセス間の排他制御が可能であるため強力な一方、速度がはるかに遅くなります。
オセロの計算では、マルチプロセッシングではなくマルチスレッドのみが必要であることを考慮すると、Windows Critical Section を使用する方が、通常の Windows Mutex メカニズムを使用するよりもはるかに効率的です。
また、GCC ではなく Visual Studio C++ を使用し、プログラムで Pthread ライブラリをドラッグしないようにするための最適なオプションは、Windows の Critical Section(または Eventing および WaitForSingleObject プリミティブ)に依存するカスタム Mutex オブジェクトを開発することです。
実際には、これはほんの数行のコードであり、大したことではありません。
"メモリバリア" などの lock-free メカニズムを使用してさらに最適化することは可能です。
ただし、実際にそのようなメカニズムを使用して、タスクを起動したスレッドをブロックすることのないスレッドプールによって実行された、タスクの結果を取得する実装を私が行う場合でも、詳細には触れません。
ベクトル化
Intel Core、AMD Rizen、IBM Power、および一部の ARM プロセッサなどの最新の CPU は、SIMD(Single Instruction Multiple Data)機能を備えています。
つまり、単一の命令で複数のデータを処理できます。
このような命令は通常、+,-,x,/ の演算、2項演算(and,xor,not)、シフト演算、回転演算、整数および浮動小数点データで使用できます。
プロセッサおよびその世代や命令セットに応じて、SIMD 命令は128、256、512ビットを一度に処理できます。
たとえば、Intel プロセッサは、Haswell 世代(2013年のSandy Bridge シリーズ)以降、AVX2(Advanced Vector Extensions)命令をサポートしています。
これは、一度に 256 ビット、つまり 4 つの 64 ビット整数または 8 つの 32 ビット浮動小数点値を処理できます。
このような命令は、ビットボードの操作を大幅に高速化する可能性があります。
ただし、使用しているプログラミング言語と組み合わせてこれらの命令を適切に使用することは困難です。
これを行うには、実際には 2 つのオプションがあります。
- GCC、Clang、Visual C++、ICC などの一部の最新のコンパイラには、ベクトル化できるループを自動的に検出する自動ベクトル化機能が組み込まれています。
これは通常、ニューラルネットワークの行列演算では非常に効果的ですが、ビットボード操作では上手く機能しません。 - Intel と AMD は 、SSE と AVX の命令セットに、標準化された"組み込み関数"を多く持っています。
これらの組み込み関数は、C / C++ プログラムから呼び出すことができる関数ですが、コンパイラは、CPU SIMD 機能に一致するインライン命令(通常は関数呼び出しごとに 1 つの関数)を生成する特別な関数として認識します。
たとえば、__m256_mm256_add_ps(__m256 a,__m256 b)を呼び出すと、256 ビットレジスタ "a" の 8 つの浮動小数点値の合計を 256 ビットレジスタの 8 つの浮動小数点値 "b" に返す単一の SIMD 命令が生成されます。
これらの組み込み関数を使用して直接プログラミングすると、最適な命令を正確に使用できます。
しかし、特定のプロセッサの機能に関連付けられるため、C / C++ コードに移植性がなくなる部分が出てきます。
私が実際に行っているのは、C / C++ プリプロセッサを使用して、汎用コードと組み込み関数を含むコードの両方を配置する、条件付きセクションを作成することです。
そのため、どちらも構成スイッチに応じてコンパイルされます。
最新の Visual C++ 2019 コンパイラは優れた自動ベクトル化機能を備えており、通常の命令に適用できる全ての種類の最適化(算術単純化、部分表現の除去、融合乗算加算の検出、定数の畳み込み、パイプラインの最適化)を SIMD 命令に適用することができます。
これにより、コードが非常に高速になります。詳細については、こちらをご覧ください。
参考文献
Othello/Reversi のプログラミング、および様々な機械学習、深層学習手法、強化学習の使用に関する多くの技術論文や研究論文があります。
ここに、その内容と有用性に関する私のコメントとともに、最も注目すべきものを挙げます。
A world-championship-level Othello program
Paul S. Rosenbloom, 1981。
Logistello が登場する前の、最初期の強豪プログラムの 1 つである IAGO プログラムの開発に繋がった全てのテクニックとステップを詳細に説明した論文の1つ。
特に、オセロのゲームの戦略で役割を果たす "特徴"、すなわち重要な要素については良い議論があります。
An evaluation function for Othello based on statistics
Michael Buro, 2002。
有名な Logistello プログラムの作者である MichaelBuro による必読の論文です。
効率的な評価関数を数学的に決定する方法を初めて説明しました。
Michael はロジスティック回帰手法を使用しましたが、彼の教師あり学習方法論の原則は、今日でもニューラルネットワークに適用されています。
The evolution of Strong Othello programs
Michael Buro, 2003。
有名な Logiustello プログラム作者による論文。
IAGO 以降の強力なオセロプログラムの進捗状況と、手作りの評価関数を Logistello や数学的に調整された評価関数へと変えていった話が書かれています。
Experiments with Multi-ProbCut and a new High-Quality evaluation Function for Othello
Michael Buro, 2000。
Michael Buro による優れた論文。
αβ 探索木を刈り込みし、探索深度を劇的に増大させることができる Multi-ProbCut 手法について書かれています。
Toward Opening Book Learning
Michael Buro, 2000。
オープニング book の自動学習に関する Michael Buro による重要な論文。
これは、私がこれまでに見た中で最も洗練された効率的なテクニックです。
Knowledge-based feature discovery for evaluation functions
Tom E. Fawcet、1995。
オセロゲームの主要な特徴、つまり盤面配置の評価値(期待スコア)に重要な役割を果たす特性を発見するための、非常に興味深いアプローチの話です。
Linear versus Non-Linear Learning in the Context of Othello
Ali Alanjawi, 2000。
非線形評価関数が線形評価関数よりも優れていることを示す、いくつかの短い論文。
これは、私の知る限り、オセロに対して SVM を使用している唯一の論文でもあります。
Observing the Evolution of Neural Networks, Learning to Play the Game of Othello
Siang Y. Chong, 2005。
オセロをプレイするためのニューラルネットワーク利用の背後にある主要な考えを要約した論文。
この論文では、最新の AI フレームワークで現在可能な高度な手法については説明しされませんが、パターン検出ニューロン(畳み込みニューロン)とゲーム戦略機能の組み合わせの使用について言及した最初の論文です。
そういう意味ではなかなか面白いです。
On Bayesian Upper Confidence Bounds for Bandit Problems
Emilie Kaufmann, Olivier Cappe, Aurelien Garivier , 2012。
モンテカルロ木探索における UCB アルゴリズムを理解して使用するために不可欠な論文。
Tooling
プログラミング
FOREST は、C++ で開発され、MFC GUI クラスを使用する UI と、パフォーマンス上の理由からほとんど C であるゲームロジックの 2 層で設計されています。
マルチスレッドなどの C++ 標準ライブラリの特定の機能が必要なので、数個の C++ モジュールも使っています。
ビットボード操作やニューラルネットワークのロジックなど一部の C コードは、ループを展開したりニューラルネットワークのハイパラメータに対応するために Python スクリプトで自動生成されている点は注意が必要です。
私が使用している C++ / C コンパイラは、Visual Studio 2017 C++ です。
GCC と CLang を試しましたが、私のケースでは、VS C++ コンパイラの方が高速なコードを生成しました(約 10 %高速でした)。
特に、VS C++ の自動ベクトル化は、ニューラルネットワークのパフォーマンスにとって絶対的に重要で優れた仕事をします。
そうは言っても、VS C++ コンパイラが常に他のコンパイラよりも高速であることを意味するわけではありません。
実際にはコードに依存するため、最高のパフォーマンスを提供してくれるコンパイラを見つけるために、全てを試してみる必要があります。
しかし、FOREST のランタイムコードは、ゲームをプレイしてる時に実行されるものであり、氷山の一角に過ぎません。
実際には、訓練データを管理したり、ニューラルネットワークを訓練したり、FOREST をコンパイルして実行する前に訓練の出力を後処理したりするためのコードもあります。
そのコードは Python で書かれています。Python は、私の考えでは、データサイエンスにとって間違いなく最も柔軟なプログラミング言語です。
私が Python で最もよく使用する機能は、もちろんリストと辞書です。これらは、ゲームの局面を操作したり、ゲームツリーを構築したりするのに非常に便利です。
Python の唯一の欠点は、比較的遅い(セミインタープリターである)ことと RAM の消費量が多いこと(全ての変数が動的にリンクされているため、ポインターと動的メモリ割り当てがどこにでもある)であり、これは数千万のデータレコードを処理するときに問題になります。
これらの欠点を克服するための最良の方法は、大量の RAM を備えた強力なコンピューター(私のは 32 Gb RAM であり、もうすぐその量を 2 倍にするつもりです)を使うこと、そして、絶対に高速に実行する必要のある特定のルーチンに関しては Cython で記述された特定の拡張機能を使用すること です。
Cython は基本的に Python コンパイラであり、絶対的なパフォーマンスのために、純粋な C で記述された Python 拡張機能の開発を簡略化します。
Python だけでも非常に優れていますが、その能力のほとんどは、実際には、既知のデータ処理アルゴリズムのほとんどを統合する膨大な拡張機能群に由来します。
私が最もよく使用するものは次のとおりです。
- Numpy, 行列および N 次元配列の普遍的な操作を可能にする、高性能ライブラリ。
- Scipy,Scikit Learn, 機械学習ライブラリ。K-Best ランキングなどのデータ前処理や機能エンジニアリングに役立つあらゆる種類のアルゴリズムが含まれています。
- Sqlite3, ゲームと局面の膨大なデータを格納する SQL データベースを操作する簡単な方法を提供します。
- csv, "カンマ区切り値" ファイルを操作するため、中間結果を保存するのにとても便利です。
- othpy, オセロボードの操作を高速化するために Cython と C で作成した Python 拡張機能。
- Keras/Tensorflow, 次のセクションで説明します。
深層学習
続きはまた今度。
有益なリンク
- Computer Othello on Wikipedia, 有益なリンクとオセロプログラミング史の要約。
- Zebra, Gunnar Andersson による有名なオセロ(/リバーシ)プログラム。最も強力な古典的なプログラムの一つ。
- Edax, Richard Delorme 作。おそらく、これまでに作成された中で最強かつ最速の古典的なオセロ(/リバーシ)プログラム。ソースコードが入手可能であり、Windows, Linux, または OS X 向けにコンパイルできます。
- WTHOR database, 1997 年以降に人間あるいはプログラムによってプレイされたゲームを 10 万個以上含んでいます。全てのゲームは 24 マス空きで正確なスコアを保持しており、ニューラルネットワークを訓練したり序盤ライブラリを定義したりするのに有用です。
- Bitboards on the Chess Programming Wiki, オセロとチェスで高速なビットボードを実装するために知っておく必要のあること全てが書かれています。
法的な言及
- Othello(オセロ)は、株式会社メガハウスの登録商標です。
- Reversi は、Ravensburger AG の登録商標です。
- Windows は、Microsoft Corporation の登録商標です。
- TensorFlow は、Google Inc の商標です。
以上翻訳。
