自作リバーシAI Kalmiaの仕組み

目次

はじめに

Kalmiaはモンテカルロ木探索(MCTS)ベースのリバーシの思考エンジンです。思考エンジンと呼ぶと馴染みが無いかもしれませんが、誤解を恐れずに端的に述べればいわゆるAIです。KalmiaのMCTSではロールアウトの代わりにEdax*1で用いられているような静的評価関数を用いていることが特徴です。強さはトッププログラムの足元にも及びませんが、おそらく人間のトッププレイヤーやそれ以上の強さであると推測しています。
この記事ではまずKalmiaで用いている技術の基本的な説明から始め、その後にKalmiaの仕組みについて説明します。ですので既にMCTSやリバーシの評価関数に関する知識を持っている方は後半からいきなり読んでもらって構いません。 分かりにくい部分や不適切な部分があればコメント欄もしくはTwitter(以下リンク)で指摘をお願いします。

twitter.com

本記事の構成

前半: Kalmiaで用いている技術の基本的な説明
後半: Kalmiaの仕組み

モンテカルロ木探索

モンテカルロ木探索とは"選択"、"シミュレーション"、"バックアップ"、"展開"の4つのフェーズを繰り返しながら探索木を成長させていくアルゴリズムです。元々は囲碁プログラムで使われ始めたアルゴリズムであり、2006年にRémi Coulom氏がCrasy Stoneという囲碁プログラムに採用してブレイクスルーとなりました。Crasy Stoneで採用されたMCTSを簡単に説明すると、乱数による対局シミュレーション(モンテカルロ法)の勝敗で局面を評価する方法と木探索を組み合わせたものです。ただし、MiniMax探索のようにあらゆる局面をしらみつぶしに探索するのではなく、有望そうな手から優先的にシミュレーションを行って木を成長(先を読む)させます。MCTSで肝となるのは"有望そうな手"を選択する方法です。Crasy Stoneでは独自の手法で有望そうな手を選択しています*2。しかし、後に発表された論文“Bandit based Monte-Carlo Planning”*3で紹介された、UCB1方策(後述)によって手を選択する手法が後の囲碁プログラムでは一般的になります。この手法はUCB1方策を木探索に適用することからUCB applied to trees(UCT)と呼ばれます。現在では単にMCTSといった場合、このUCT(もしくはその亜種)のことを指すことが多いです。実際にKalmiaで用いているMCTSもUCTです。UCTについては後に詳しく述べます。

UCB1方策

UCB1(Upper Confidence Bound 1)方策とは、多腕バンディット問題を解くための方策のうちの1つです。多腕バンディット問題とは以下のような問題です。

"当たりの出る確率がそれぞれ異なるスロットマシーンがX台ある。任意のスロットマシーンに合計N回挑戦できるとき、報酬をできる限り最大化するにはどのような方策でスロットマシーンを回せばよいだろうか。ただし、スロットマシーンの当たりが出る確率は公開されておらず、同じマシーンに複数回挑戦しても良いものとする。"
※ここでいう報酬は"当たりが出た回数"という意味で用いています。以降は"当たりが出た回数"と書くと文が長くなるので"報酬"と記述します。

この問題に対する最も簡単な方策は、それぞれのスロットマシーンに一定の回数だけ挑戦して報酬の期待値を推測する方法です。そして残りの回数は報酬の期待値が高そうなスロットマシーンだけを回し続けます。具体例で説明すると、3台のスロットマシーンに計50回挑戦できるとき、それぞれのスロットマシーンを10回ずつ回して当たりが出た回数をカウントし、もっとも当たりが出たスロットマシーンを残りの20回だけ回すという方策です。しかしこの方策では、一定回数は全てのマシーンを回す必要があり非常に非効率です。そこで今まで回したスロットマシーンの結果を活用しつつ、まだ十分に回せていないマシーンも回すという方策が提案されます。それがUCB1方策です。UCB1方策では以下のUCB1式で求めたスコアが最も大きいスロットマシーンを選択して回していきます。

u_i = \frac{w_i}{n_i} + \sqrt{\frac{2\log{N}}{n_i}}\tag{1}
N = \sum_{i}^{}{n_i}

u_i: スロットマシーンiのUCBスコア
w_i: スロットマシーンiの累積報酬(今まで当たりが出た回数)
n_i: スロットマシーンiを回した回数
N: 各スロットマシーンを回した回数の総和

この式の第1項は今までの報酬の標本平均となっていることが分かります。 第2項を無視すれば、このスコアは報酬の標本平均が大きければ大きいほどそのスロットマシーンが選ばれやすくなるということを意味しています。今までの報酬の標本平均が高いのであれば、報酬の期待値も高いだろうと推測できるので、これは直感にも合うと思います。では第2項は一体何でしょう。対数や平方根を無視すれば、スロットマシーンiを回した回数の逆数になっています。これの意味することとはつまり、まだ十分に回していないスロットマシーンも選ばれるということです。第1項と第2項をまとめれば、UCB1方策とは「報酬の期待値が高そうなスロットマシーンを選びつつ、まだ十分に回せていないスロットマシーンも回す」という方策です。

UCB1式についてもう少し詳しい説明をすると、UCB1式と報酬の期待値E[X_i]との間には以下の関係が成り立ちます。

P(E[X_i] \leq \frac{w_i}{n_i} + \sqrt{\frac{2\log{N}}{n_i}}) = P(E[X_i] - \frac{w_i}{n_i} \leq \sqrt{\frac{2\log{N}}{n_i}}) \geq 1 - \frac{1}{N^4}\tag{2}

X_i: スロットマシーンiが当たりのときに1、そうではないときに0をとる確率変数

上式からUCB1式の第2項は、報酬の期待値と報酬の標本平均との差についての、信頼度(1-\frac{1}{N^4})以上における信頼区間の上限(Upper Confidence Bound)を表していることが分かります。つまりUCB1方策では、標本平均から推測される報酬の期待値と真の報酬の期待値との乖離が大きいと思われるスロットマシーンも選んでいるのです。また、信頼度にNが含まれていることから分かる通り、全体の試行回数が大きくなるにつれ、信頼度が1に近づくので、UCB1式の第2項の効果は薄れます。
より詳しい説明については、他の方が書いた以下の記事が詳しいです。

blog.monochromegane.com

UCT

UCTとはUCB applied to treesの略称であり、先ほどのUCB1方策を木探索に適用した手法です。MCTSでは有望な手を選択しながら探索木を成長させていくと述べましたが、この有望な手を選択するフェーズでUCB1方策を用います。UCTの具体的な流れを説明します。

選択フェーズ

各子ノードの訪問回数(ノードの選択回数)と対局シミュレーションの勝数、および兄弟ノードの訪問回数の総和からUCB1式に基づいてスコアを算出します。そしてそのスコアが最も高い手を選択します。この操作を末端ノード(葉ノード)に到達するまで続けます。なお、UCTで用いるUCB1式では、以下のように事前に決めた定数を第2項に作用させることが多いです。このようにすることで第2項の強さを変更することができます。c=\sqrt{2}とすれば、式(1)と同じです。

u(s,a) = \frac{w(s,a)}{n(s,a)} + c\sqrt{\frac{\log{\sum_{b}{n(s,b)}}}{n(s,a)}}\tag{3}

s: 現在の局面(状態)
a: 着手(行動)
u(s,a): 局面sにおける, 着手aのUCBスコア
w(s,a): 局面sで着手aを行って得られた累積報酬(末端ノードで行われた対局シミュレーションの勝敗のこと. 勝利: +1, 敗北: 0, 引き分け: +0.5)
n(s,a): 局面sで着手aを行うノードに訪問した回数
\sum_{b}{n(s,b)}: 兄弟ノードの訪問回数の総和
c: 第2項の強さを決める定数. 大きくすればするほど、探索が不十分なノードをより優先するようになるが,その代わり木の深さは浅くなる.

なお、KalmiaではAlphaZero*4で用いられている方法で定数部分が探索の進み具合に応じて変化するようにしています。詳しくは後に述べます。

(図1) 選択フェーズでUCBが最大の辺(緑)を選択していく様子
シミュレーションフェーズ

末端ノードに到達したら対局シミュレーションを1回行い、その勝敗を末端ノードに記録します(図2)。
Kalmiaのシミュレーションフェーズでは対局シミュレーションを行っていないのですが、それについては後に述べます。

(図2) シミュレーションフェーズで白の勝ちだった場合
バックアップフェーズ

末端ノードのシミュレーション結果をそのノードに至るまでに経由したノードに伝えます。例えば、末端ノードでのシミュレーション結果が白の勝ちであった場合(図3)、白の着手に関するノードでは累積報酬と訪問回数に1を加算し、黒の着手に関するノードでは訪問回数にのみ加算を行います。白の勝ちは黒にとっての負けだからです。また、末端ノードでのシミュレーション結果が引き分けであった場合は、どちらの着手のノードであるかに関わらず、訪問回数には1を加算、累積報酬には0.5を加算します。当たり前のことですが、相手が引き分けであれば自分も引き分けだからです。

(図3) 対局シミュレーションの結果が白の勝ちであった場合のバックアップ
展開フェーズ

末端ノードのシミュレーション回数があらかじめ決められた閾値に達した場合は、そこからさらにノードを展開します。もちろん、末端ノードの状態が終局であれば展開を行いません。

(図4) N(s2, a21)が展開閾値に達した場合の展開フェーズ

パターンの重み付き線形和を用いた評価関数

ゲームにおいて現在の局面の有利不利を判断することはとても重要なことです。リバーシほどの広い探索空間を持つゲームであれば、初期局面から終局まで完全に読み切ることは不可能だからです。そこで、ある程度の深さで探索を打ち切り、数手先の局面の有利不利を判断する必要があります。その役割を担うのが評価関数です。
リバーシAIの分野では1997年に当時のトッププレイヤーに6戦全勝したLogistello*5というプログラムが存在し、そのプログラムで用いられた石の並びのパターンの重み付き線形和による評価方法が現在の主流です。リバーシプログラムの中ではトップレベルの強さであるEdaxやZebra*6などのプログラムでもLogistelloの評価関数の亜種が用いられています。Logistelloの評価関数ではまず局面をいくつかの要素に分割し、それぞれの要素の石の並びのパターン(特徴)*7に点数を付け、最後にその点数を足し合わせます(式(4))。

v(s) = \boldsymbol{\phi}(s)\cdot\boldsymbol{w} = \sum_{i}^{}{\phi_i(s) w_i}\tag{4}

s: 局面
v(s): 局面sの価値(評価値)
\boldsymbol{\phi}(s): 局面sの特徴ベクトル(各要素は0か1をとる. 特徴iが出現した時はi番目の要素が1,そうでなければ0となる. )
\boldsymbol{w}: 重みベクトル(各要素はそれぞれの特徴の点数)

より詳しい実装については以下の記事が参考になります。

qiita.com

評価関数の最適化

以下、石の並びのパターンのことを"特徴"、特徴の点数のことを"重み"と呼びます。
リバーシの評価関数では、局面の各特徴に重みをつけて足し合わせると説明しました。では、それぞれの特徴の重みはどのように決めればよいのでしょうか。もしあなたがとても強いリバーシのプレイヤーあったとしても、全ての特徴の重みを手作業で決めることは不可能に近いです。なぜなら、リバーシで出現しうる特徴は20万以上に及ぶからです。さらにリバーシでは、ゲームの進行度によって評価関数を使い分けるので、実際は数百万個にも及ぶ重みを決める必要があります。そこで、それぞれの特徴の重みは、実際に打たれた棋譜から勾配降下法で最適化していきます。勾配降下法では評価関数によって予測されたゲームの結果(石差や勝敗など)と、実際の棋譜における結果との差が小さくなるように点数を調整していきます。ここでは評価関数を用いて最終的な石差を予測したい場合について説明します。まずは以下のような損失関数を考えます。

E(\boldsymbol{w};\boldsymbol{D})=\frac{1}{2}\sum_{s \in D}^{}{(v^*(s) - v(s))^2}\tag{5}

\boldsymbol{D}: 棋譜に含まれる局面の集合
v^*(s): 局面sの最終石差
v(s): 評価関数によって求めた局面sの最終石差の予測値
\boldsymbol{w}: 評価関数v(s)の重みベクトル

単純に、実際の最終石差と評価関数による予測値との差についての二乗和を取っているだけです。\frac{1}{2}を掛けている理由は、後に微分する時に定数が消えるからです。
最適な評価関数を得るには、損失関数 E(\boldsymbol{w};\boldsymbol{D})の値が最小となるような \boldsymbol{w}を求めればいいわけですから、まずは \boldsymbol{w}の各要素で損失関数を偏微分します。 \boldsymbol{w}の任意の要素w_jで損失関数 E(\boldsymbol{w};\boldsymbol{D})を偏微分すると、以下のようになります。

\frac{\partial E(\boldsymbol{w};\boldsymbol{D})}{\partial w_j}=\sum_{s \in D}^{}{(v^*(s) - v(s))(-\frac{\partial v(s)}{\partial w_j})}

ここでv(s) = \boldsymbol{\phi}(s)\cdot\boldsymbol{w} = \sum_{i}^{}{\phi_i(s) w_i}より、

\frac{\partial v(s)}{\partial w_j}=\phi_j(s)

\phi_j(s)は特徴jが出現していれば1、そうでなければ0であるから

\frac{\partial E(\boldsymbol{w};\boldsymbol{D})}{\partial w_j}= \begin{cases} \sum_{s \in D}^{}{(v(s) - v^*(s))} & (特徴jが局面sに含まれる)\\ 0 & (それ以外) \end{cases}\tag{6}

このように偏微分した結果はとてもシンプルになりました。重みベクトルの各要素で損失関数を偏微分した値は、その点における損失関数の勾配(傾き)を表しています。故に重みベクトルの各要素の値を、勾配を降下する方向に動かすことで、損失関数の値が小さくなることが期待できます。勾配降下法では、重みで偏微分 -> あらかじめ決めた学習率\etaの分だけ重みを変化 -> もう一度重みで偏微分 -> ・・・ という操作を繰り返しながら損失関数の値を小さくしていきます(式(7))

{w'}_j = w_j - \eta \frac{\partial E(\boldsymbol{w};\boldsymbol{D})}{\partial w_j}\tag{7}

Kalmiaの仕組みへ

以上、Kalmiaで用いている技術について概ね解説しました。ここからは実際のKalmiaの仕組みについて解説していきます。

KalmiaのMCTS

KalmiaのMCTSは選択フェーズにUCBを用いたUCTを用いています。ただし、シミュレーションフェーズと選択フェーズに若干の工夫があります。

シミュレーションフェーズ

通常のMCTSでは、このフェーズで対局シミュレーションを1回だけ行い、その勝敗を記録します。しかし、対局シミュレーションを行う必要があったのは、そもそも囲碁の評価関数を作るのが困難であったことが理由です。それならば、既にLogistelloの評価関数のような計算が高速かつ、それなりに精度の高いものが存在するリバーシでは不要です。そこでKalmiaでは、対局シミュレーションの代わりに、勝率を予測する価値関数(評価関数)v(s)を用いています。この価値関数v(s)は、ある局面sに対して決まった値を出力するので、通常のMCTSのように展開閾値を決める必要はありません。末端ノードの評価が1回終わったらすぐにノードを展開します。すなわち展開閾値は常に1です。

選択フェーズ

選択フェーズではUCBスコアがもっとも大きい子ノードを選択しますが、以下のような例外を設けています。

(1) 勝ちに至る子ノードが存在する場合
UCBスコアに関わらずそのノードを選ぶ。

(2) 負けに至る子ノードが存在する場合
UCBスコアに関わらずそのノードは選ばない。

(3) 引き分けに至る子ノードと負けに至る子ノードのみが存在する場合
引き分けを選ぶ(負けるよりはマシなので)。

また、選択フェーズにおいて、勝ちに至る子ノードを1つでも見つけた場合は、その親ノードも勝ちになるので、親ノードに"勝ち"とマークします。逆に子ノードが全て負けの時は親ノードも負けになるので、親ノードに"負け"とマークします。引き分けと負けの子ノードしか存在しない場合は、親ノードに"引き分け"とマークします。このように、確定したゲームの勝敗を親ノードへ伝播することで、終盤では木の末端でAND/OR木のような挙動をとります。この方法はチェスプログラムのLeela Chess Zero*8のMCTSを参考にしました。

KalmiaのUCB式

KalmiaではUCTの説明の際に紹介した式(4)を少し改変しています。その理由は、式(4)をそのまま用いた場合、特定の手を極端に深く読んでしまう現象が発生したからです。具体的には、他の候補手は12手程度先しか読んでいないのにもかかわらず、ある1手は50手ぐらい先を読んでしまうような現象が発生しました。定数cの値を何回か変更してもこの傾向は改善しなかったため、AlphaZeroで用いられていたPUCT式を参考に以下のような改変を加えました。

u(s,a) = \frac{w(s,a)}{n(s,a)} + c(s)\sqrt{\frac{\log{\sum_{b}{n(s,b)}}}{n(s,a)}}\tag{8}
c(s) = \log{\frac{1 + N(s) + C_{base}}{C_{base}} + C_{init}}
N(s) = \sum_{b}{n(s,b)}

C_{base}, C_{init}: 事前に決めるハイパーパラメータ

このようにすることで、親ノードの訪問回数によってc(s)が動的に変化します。具体的には、親ノードの訪問回数が少ないうちは価値の高い子ノードが比較的優先され、親ノードの訪問回数が多くなるにつれ、訪問回数が少ない(探索が十分でない)ノードも優先されます。KalmiaではC_{base} = 19652, C_{init} =0.35 と設定していますが、何回か動かして適当に決めた値なので最適な値とは言えません。いつかベイズ最適化などでより良い値にチューニングする予定です。

式(8)は\sum_{b}{n(s,b)} = 0(どの子ノードも未訪問)のときと、n(s,a)=0のときに未定義です。Kalmiaでは、ルート直下の未訪問ノードに関しては勝ちであると仮定し、それ以外の未訪問ノードは親ノードの価値で初期化します。未訪問ノードを親ノードの価値で初期化することで、親ノードよりも価値が高そうな子ノードが見つかれば、しばらくの間はそのノードが選ばれ続けるようになります。

MCTSの並列化

Kalmiaでは、MCTSの "選択"、"シミュレーション"、"バックアップ"、"展開" の一連の操作をCPUの論理コア数の分だけ並列に行います。ただし、単純に並列化してしまうと複数のスレッドが同じノードを選んでしまって効率が悪くなるので、あるスレッドが探索中のノードにはvirtual lossというペナルティをノードの訪問回数に加えます。こうすることで一時的にノードの価値が下がり、他のスレッドからは選ばれづらくなります。Kalmiaではvirtual lossを3に設定しています。

終盤探索

リバーシでは、空きマス数がある程度少なくなれば終局まで読み切ることが可能です。Kalmiaでは、終盤21手は必勝読み(最終的な勝敗を読む)、終盤20手は石差が最大となるような手を読みます*9。終盤探索では特に珍しいことは行っておらず、Alpha-Beta探索で読み切っています。ただし、局面の合流に関しては置換表で管理しています。Move orderingは単純な速さ優先なので非常に重い終盤ソルバーとなっています。終盤探索に関してはつい最近実装した機能なので今後改良していく予定です。

価値関数(評価関数)

KalmiaのMCTSの説明において対局シミュレーションの代わりに価値関数v(s)の値を利用すると述べました。ここではv(s)の構造について説明します。
価値関数v(s)は、局面からEdaxと同様の特徴を抽出し、それらの重み付き線形和で局面の価値を算出します。ただし、Kalmiaは最終石差を予測するEdaxとは異なり勝率を予測するので、重み付き線形和を標準シグモイド関数(式(9))に通して0.0~1.0の値に変換しています。

f(x) = \frac{1}{1 + e^{-x}}\tag{9}

v(s) = f(\boldsymbol{\phi}(s)\cdot\boldsymbol{w}) = f(\sum_{i}^{}{\phi_i(s) w_i})\tag{10}

s: 局面
v(s): 局面sの価値(予測勝率)
\boldsymbol{\phi}(s): 局面sの特徴ベクトル(各要素は0か1をとる. 特徴iが出現した時はi番目の要素が1,そうでなければ0となる. )
\boldsymbol{w}: 重みベクトル(各要素はそれぞれの特徴の点数)

1つの価値関数のみでは精度があまり良くないので、棋譜を4手ごとに分割した後、それぞれについて価値関数を最適化します。つまり価値関数は15個存在します。

価値関数の最適化

価値関数の最適化にはリバーシの棋譜用いており、勝ちを1、負けを0、引き分けを0.5として価値関数の予測値と棋譜の勝敗との誤差が小さくなるように最適化します。「評価関数の最適化」の項で紹介した損失関数E(\boldsymbol{w};\boldsymbol{D})では二乗和を用いましたが、Kalmiaの価値関数では勝率を予測するので、損失関数には2値クロスエントロピーを用います。クロスエントロピーとは2つの確率分布 p, qがどれくらい似ているかを表す指標です(式(11))。

E(\boldsymbol{w};\boldsymbol{D}) = -v^{*}(s)log(v(s)) - (1 - v^{*}(s))log(1- v(s)) \tag{11}

\boldsymbol{D}: 棋譜に含まれる局面の集合
v^{*}: 棋譜の勝敗(勝ち: 1, 負け: 0, 引き分け: 0.5)
v(s): 価値関数による予測勝率
\boldsymbol{w}: 評価関数v(s)の重みベクトル

この損失関数E(\boldsymbol{w};\boldsymbol{D})の値をできる限り小さくするような \boldsymbol{w}を求めればよいので、まずは \boldsymbol{w}の任意の要素w_jで損失関数 E(\boldsymbol{w};\boldsymbol{D})を偏微分します(式(12))。

\frac{\partial E(\boldsymbol{w};\boldsymbol{D})}{\partial w_j} = \sum_{s \in D}^{}{(- \frac{v^{*}(s)}{v(s)} \cdot \frac{\partial{v(s)}}{\partial{w_j}} + \frac{1 - v^{*}(s)}{1 - v(s)} \cdot \frac{\partial{v(s)}}{\partial{w_j}})} \tag{12}

標準シグモイド関数の導関数(式(13))より、\frac{\partial{v(s)}}{\partial{w_j}}は以下の通り(式(14))

f'(x) = (1 - f(x))f(x) \tag{13}

\frac{\partial v(s)}{\partial w_j} = (1- v(s))v(s) \frac{\partial (\sum_{i}^{}{\phi_i(s) w_i})}{\partial w_j} \tag{14}

よって損失関数 E(\boldsymbol{w};\boldsymbol{D})の w_jにおける勾配は式(14)を式(12)に代入することで得られます(式(15))。

\frac{\partial E(\boldsymbol{w};\boldsymbol{D})}{\partial w_j} = (v(s) - v^{*}(s))\frac{\partial (\sum_{i}^{}{\phi_i(s) w_i})}{\partial w_j} \tag{15}

ここで\phi_i(s)は特徴iが出現していれば1、そうでなければ0であるから、最終的に式(15)は以下の形になります(式(16))。

\frac{\partial E(\boldsymbol{w};\boldsymbol{D})}{\partial w_j}= \begin{cases} \sum_{s \in D}^{}{(v(s) - v^*(s))} & (特徴jが局面sに含まれる)\\ 0 & (それ以外) \end{cases}\tag{16}

結局のところ、「評価関数の最適化」で紹介した式(6)と全く同じ形になります。あとはこの勾配の式を利用して勾配降下法で最適化するだけです。

Kalmiaの欠点

ここではKalmiaの抱えている欠点について紹介します。

石差にこだわらない

Kalmiaでは勝率を予測しながら手を決めるので石差にこだわらない打ち方をします。それ故に、勝勢になるといきなり手が緩みます。具体的には、大差で自分が勝てるような局面でも2石差で勝つような手を選択することがあるのです。逆に劣勢になった際にはとにかく勝つために無理な手を選択し始めます。本当は僅差で負ける局面なのに、大差で負けてしまうこともしばしばあります。しかし、終盤完全読みを実装したお陰でこの傾向は従来よりはマシになりました。

メモリ使用量が多い

MCTSはアルゴリズムの特性上、一度訪問したノードは探索中ずっとメモリに残ります。それ故に長時間思考を行うとあっというまにメモリを食い潰します。

読み抜けを起こしやすい

MCTSでは探索が進むにつれ有望でないノードが選ばれづらくなります。これは前向き枝刈りのような効果を見せる反面、これが原因で有利な手を見逃してしまうことがあります。特にMCTSでは、ほとんどの手順では不利な手であるが、ある特定の手順では有利であるような手に弱いです。

Kalmiaの今後の改善点

速さを犠牲に評価関数の精度を上げる

Kalmiaの欠点で述べたように、現状ではメモリをすぐに食い潰してしまうので、敢えて価値関数の精度を上げて重くすることによりメモリの使用率を抑えようと考えています。新たな価値関数としては以下のようなものを考えています。

・末端ノードで浅いAlpha-Beta探索を行う
現状のKalmiaでは末端ノードに到達した際に、価値関数の出力をそのままノードに記録していますが、これを浅いAlpha-Beta探索によって求めた価値で記録するようにします。このようにすることで純粋な価値関数の出力よりも高い精度が期待できます。

・非線形モデルなどのより自由度の高いモデルを用いる
現在の価値関数では単純な線形モデルを用いていますが、これをニューラルネットワークのような非線形モデルに変更します。モデルの自由度が上がれば必然的に予測精度も向上するため大きく強さに影響することが期待できます。その反面、予測精度の向上によるメリットが低速化のデメリットよりも下回れば弱体化することになります。また、一般的に自由度の高いモデルは過適合を起こしやすく最適化が難しいです。

まとめと今後の予定

ここまでKalmiaで用いている技術の基本的な説明とKalmiaの仕組みについて説明しました。今後は「Kalmiaの今後の改善点」の項で挙げた改善を施す予定ですが、その前にKalmia用のGUIアプリ、もしくはWebアプリを開発しようかと考えています。というのも、現在のKalmiaはGoGuiというGUIアプリとGTP(Go Text Protocol)というプロトコルで通信することで人間との対局を実現しており、それらのソフトウェアの導入が少々面倒なのです。これでは多くの方に遊んでもらうことができないため、より遊びやすい形で配布したいと思っています。
Kalmiaのソースコードは以下のリポジトリで公開中です(開発言語はC#)。何か改善点やバグなどがあれば遠慮なく指摘してもらって構いません。ライセンスはGPL3です。

github.com

参考文献

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296
https://blog.monochromegane.com/blog/2020/05/16/bandit-algorithm-ucb1
https://deepmind.com/research/publications/2019/mastering-game-go-deep-neural-networks-tree-search
https://deepmind.com/research/publications/2019/mastering-game-go-without-human-knowledge
http://sealsoft.jp/thell/learning.pdf
https://sealsoft.jp/thell/algorithm.html

*1:https://github.com/abulmo/edax-reversi

*2:Rémi Coulom (2007). “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search”. Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006.

*3:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296

*4:https://www.science.org/doi/suppl/10.1126/science.aar6404/suppl_file/aar6404-silver-sm.pdf

*5:https://skatgame.net/mburo/log.html

*6:http://www.radagast.se/othello/zebra.html

*7:実際のLogistelloには石の並び以外にも着手可能数などの評価項目もあります。

*8:https://github.com/LeelaChessZero/lc0

*9:設定で変更は可能です