KL情報量を利用した時間制御

先日の記事で、dlshogiの手数ごとのポリシーと訪問回数のKL情報量を調査した。

KL情報量が高い局面は、探索がより重要になる局面と考えられるため、KL情報量を時間制御に使用することを考えた。

現状の時間制御

現状のdlshogiは、以下の式で1手にかける時間を計算している。

$\displaystyle \frac{残り時間}{14 + max(30, 30 - ply)} + inc$

1手にかける残り時間で次善手が最善手を超えることがない場合、そこで探索を打ち切る。
ただし、21手以降で最善手の訪問回数が次善手の訪問回数の1.5倍以内の場合、もしくは、最善手と次善手の勝率が逆の場合は、探索時間を2倍に延長する。

1手にかける基本時間は、現状と同じ式で計算する。

探索中にKL情報量を計算し、基本時間にKL情報量をN倍した値を乗じる。
Nは、先日の調査で50手から100手でKL情報量が平均0.8くらいだったため、現状の探索延長した場合の2倍より少し大きいくらいになる値として4とした（要調整）。
また、基本時間から変化が大きくなりすぎないように、基本時間の0.5倍～4倍の範囲になるようにクリップする。

強さの測定

持ち時間5分1手2秒加算の条件で、強さを測定した。

   # PLAYER          :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 kld             :    48.9   29.1   153.0     256    60      96  132   42   82    16
   2 master          :     4.8   27.0   132.5     260    51      99  113   39  108    15
   3 suisho5-10th    :   -53.7   27.7   100.5     256    39     ---   84   33  139    13

※dlshogiは、V100×1、2スレッド
※水匠5は10スレッドで、強さ調整のため持ち時間を1.5倍にしている。

KLD情報量を利用したバージョンの方が、R+44.1だけ強くなっている。

ソフト間の勝率は以下の通り。

kld vs master: 60-46-24 (55.4%)
Black vs White: 69-37-24 (62.3%)
kld playing Black: 38-15-12 (67.7%)
kld playing White: 22-31-12 (43.1%)
master playing Black: 31-22-12 (56.9%)
master playing White: 15-38-12 (32.3%)

master vs suisho5-10th: 67-48-15 (57.3%)
Black vs White: 69-46-15 (58.8%)
master playing Black: 37-16-12 (66.2%)
master playing White: 30-32-3 (48.5%)
suisho5-10th playing Black: 32-30-3 (51.5%)
suisho5-10th playing White: 16-37-12 (33.8%)

kld vs suisho5-10th: 72-36-18 (64.3%)
Black vs White: 65-43-18 (58.7%)
kld playing Black: 41-12-10 (73.0%)
kld playing White: 31-24-8 (55.6%)
suisho5-10th playing Black: 24-31-8 (44.4%)
suisho5-10th playing White: 12-41-10 (27.0%)

現状のdlshogi(master)に対しても、水匠5に対しても勝率が上がっている。

消費時間の比較

現状

f:id:TadaoYamaoka:20220131231240p:plain

KL情報量を利用したバージョン

f:id:TadaoYamaoka:20220131231243p:plain

KL情報量を利用したバージョンは、序盤での消費時間が少なくなり、50手から100手の消費時間が多くなっており、100手から200手では消費時間が少なくなっている。
狙い通り、より中盤に時間を使うようになっている。

300手を超えたあたりで、KL情報量が大きくなり消費時間が急に多くなる局面があった。
局面を調べると、相入玉の局面で、KL情報量が大きくなる傾向があるようである。
クリップする範囲は、もう少し調整をした方が良さそうである。

なお、KL情報量は以下のようになっていた。
f:id:TadaoYamaoka:20220131232604p:plain

水匠5の消費時間

参考として、水匠5の消費時間は以下の通りであった。
前述した通り持ち時間は1.5倍にしている。
f:id:TadaoYamaoka:20220131231923p:plain

150手あたりまでは、比較的均等に時間を使っているようである。

まとめ

KL情報量を利用して時間制御を行う新しい手法を検討した。
KL情報量を利用することで、より中盤に時間を使うようになり、持ち時間5分1手2秒加算の条件で、現状よりも強くなることが確認できた。
KL情報量に乗じる値は勘で決めた値のため、まだ調整の余地があるため、もう少し調整したい。
基本時間の式も、50手くらいにピークがくるように調整した方が良さそうである。