探索部の実験メモ - 死ぬこと以外かすり傷

Lightweightの探索部は基本的にdlshogiに倣っており、下記式が最大となるノードを選んでいます。

$Q(s _ t, a) + U(s _ t, a)$

特に、 $U(s _ t, a)$ の部分については、以下のように求めています。（これもdlshogi通りです）

$\displaystyle{U(s, a) = c _ {puct} P(s, a) \frac{\sqrt{\sum_ b N(s, b)}}{1 + N(s, a)} }$

ここで、 $\displaystyle{\frac{\sqrt{\sum_ b N(s, b)}}{1 + N(s, a)}}$ の部分に注目してみると、
${\sqrt{\sum_ b N(s, b)}}$ は局面 $s$ において選択した全ての手の合計回数を示しており、また $N(s, a)$ は局面 $s$ において選択した手 $a$ の合計回数を示しています。
つまりこの部分は「選択回数の少ない手を優先する」という役割を担っていますが、「どのような場合に選択回数の少ない手をどれだけ優先させるか」という部分については改良の余地があるのではと考えます。

そこで現在、KLDを利用したPUCTアルゴリズムの改良案を試しており、floodgateや手元で自己対局を行って計測等を行っています。
KLDは直接的には「ある２つの確率分布の差異」を表す尺度ですが、これをコンピュータ将棋、特にdlshogi系のソフトに置き換えた場合は「局面の難しさ」を表す尺度になりうると考えています。
簡単な局面（≒探索があまり必要ではなく、Policyのみで最善手を判断できる場面を指す）であれば最善手が早々に定まりますが、
難しい局面となると、探索を進めるにしたがって最善手が変わることがよく起こります。これに従ってKLDも大きくなります。
（※もちろんモデルの精度が良いほど、この「難しい局面」のレベルが上がってくるわけですが....）

ここで１つ仮説を立てますが、
KLDが大きい、つまり探索がより重要な局面である場合は、
「選択回数が少ない手の優先度を引き上げてやることで、Policyが見落としている最善手をより発見しやすくする」
ことができるのではないかと考えました。

そこで2022/7/9に行われたTSEC3では、実験的にLightweightの探索部について、
$U(s _ t, a)$ の部分を以下のように変更していました。

$\displaystyle{U(s, a) = c _ {puct} P(s, a) \frac{KLD _ {adjustment} \sqrt{(\sum_ b N(s, b))}}{1 + N(s, a)}}$

$\displaystyle{KLD _ {adjustment} = \sqrt{kld(P _ s, Q _ s)+kld _ {base}}}$

（ただし、 $\displaystyle{1 ≤ KLD _ {adjustment} ≤ 3}$ ）

上記式の通りですが、 $\displaystyle{kld(P _ s, Q _ s)}$ に $\displaystyle{kld _ {base}}$ を足してルートを取ったものを $\sqrt{(\sum_ b N(s, b))}$ にかけることで、選択回数が少ない手の優先度をKLDに応じて動的に引き上げることが狙いです。
また、過度にKLDの値に引きずられて探索バランスが崩れないようにするため、 $\displaystyle{KLD _ {adjustment}}$ は１から３までの間に収まるように下限、上限を設けて調整しています。 $\displaystyle{kld _ {base}}$ はハイパーパラメータです。

このハイパーパラメータを決めるあたっては、以下の条件で連続対局を行い暫定的な値を決めています。
■計測条件
持ち時間：5秒（秒読み）
対局相手：S.Lightweight-EF（WCSC32出場時もの）
対局数　：1800対局（50games×36trials）
開始局面：互角局面集を使用
※差異は上記探索アルゴリズムの変更有無のみ
※その他のパラメータはWCSC32のもので統一

■計測結果

非線形で近似してみると、2.25付近が最大となっているように見えます。(※グラフ上は50〜350で表現されていますが、実際に内部で取り扱う際は他パラメータと同様に100で割っているので、225→2.25となります)
上記の計測結果をもとにして、TSEC3に出場したLIghtweight 2.0は $\displaystyle{kld _ {base}}$ =2.25で設定していました。
※ただし、そもそも1trialsあたりのgamesの回数が少なかったり、
$\displaystyle{kld _ {base}}$ が3.00以上の場合の計測回数が少ない、
また複数ソフトとの対戦を行っていないといった計測自体における不足点はあるので、
あくまで参考値としたほうがよさそうです。