TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

dlshogiの序盤にランダム性を加える

dlshogi同士で、平手開始局面から対局すると毎回ほとんど同じ棋譜になる。
以前の調査では、先手勝率が65.7%と偏った結果になった。

また、最新のモデルでは先手で角換わりになるため、角換わりに偏った勝率になる。

そのため、平手開始局面からの計測した勝率はあまり信用できない。
そこで、コンピュータ将棋開発者の間では、互角局面集を使って勝率を測定するということが行われている。

序盤にランダム性を加える

互角局面集を使うと、同一棋譜になるのを回避して、様々な戦型での強さを計測できるというメリットがあるが、25手目から開始するため、24手目までの序盤の強さが見られなくなるというデメリットがある。
そこで、序盤にランダム性を加えて、平手開始局面から対局して勝率が落ちない範囲で、局面をばらけさせることを検討した。

また、自己対局時にも初期局面集を使用しているが、序盤の局面が学習データに含まれなくなるため、ランダム性を加えることで序盤局面の勝率を学習させたい。

実現方法

AlphaZeroでは、MCTSの探索結果の訪問回数に応じた確率で選択しているが、訪問回数は最善手に偏るため、最善手以外の手はあまり選択されない。
平手開始局面で、1万ノード探索した際の訪問回数と各手の価値は次のようになる。
f:id:TadaoYamaoka:20211204224256p:plain

価値がほとんど変わらない手でも訪問回数に大きな差がついているのが分かる。
序盤では価値が最善手から少ししか下がらない場合は、その手を選択しても勝率への影響は小さいため、同じくらいの確率で選択して欲しい。

分布に温度パラメータを適用することで、選択されやすくすることができる。
すなわち、訪問回数Nに温度\tauを適用して、N^{1/\tau}とする。

しかし、温度パラメータを適用すると、価値が低い手も選択されやすくなるため、勝率が低下してしまう問題がある。

折衷案として、温度パラメータを適用した上で、価値が最善手から一定以上下がる手を除外することにする。

温度パラメータを10として、価値の閾値を0.02とした場合、平手開始局面では、以下の3手が残り、分布は以下の通りになる。
f:id:TadaoYamaoka:20211204225721p:plain

勝率測定

温度、価値の閾値、何手までランダムムーブを行うかの条件を変えて、持ち時間5分、1手2秒加算で勝率を測定した。
dlshogiは、2GPU、3スレッド。水匠5は30スレッド。

温度10、価値閾値0.02、16手まで
   # PLAYER             :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 master             :    93.2   33.2   140.0     204    69     100  128   24   52    12
   2 random_cutoff20    :    -9.4   31.3    95.5     200    48     100   80   31   89    16
   3 suisho5-30th       :   -83.8   33.5    65.5     198    33     ---   56   19  123    10

White advantage = 33.01 +/- 20.40
Draw rate (equal opponents) = 13.26 % +/- 2.07

random_cutoff20がランダムムーブを行ったdlshogiで、masterがランダムを加えていないdlshogiである。

ランダムを加えた場合は、R-102.6になっている。

エンジン間の勝率は以下の通りである。

master vs random_cutoff20: 55-30-18 (62.1%)
Black vs White: 47-38-18 (54.4%)
master playing Black: 33-16-3 (66.3%)
master playing White: 22-14-15 (57.8%)
random_cutoff20 playing Black: 14-22-15 (42.2%)
random_cutoff20 playing White: 16-33-3 (33.7%)

master vs suisho5-30th: 74-22-6 (75.5%)
Black vs White: 46-50-6 (48.0%)
master playing Black: 36-12-3 (73.5%)
master playing White: 38-10-3 (77.5%)
suisho5-30th playing Black: 10-38-3 (22.5%)
suisho5-30th playing White: 12-36-3 (26.5%)

random_cutoff20 vs suisho5-30th: 50-34-13 (58.2%)
Black vs White: 52-32-13 (60.3%)
random_cutoff20 playing Black: 29-11-9 (68.4%)
random_cutoff20 playing White: 21-23-4 (47.9%)
suisho5-30th playing Black: 23-21-4 (52.1%)
suisho5-30th playing White: 11-29-9 (31.6%)

dlshogi間でも、水匠5に対しても、ランダムをムーブを行った方が勝率が下がっている。
ランダムの条件はもっと厳しくした方が良さそうである。

温度10、価値閾値0.015、16手まで
   # PLAYER             :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 master             :    51.1   13.2   588.5     978    60      80  493  191  294    20
   2 random_cutoff15    :    41.4   13.6   568.0     976    58     100  483  170  323    17
   3 suisho5-30th       :   -92.6   13.9   306.5     972    32     ---  224  165  583    17

White advantage = 54.09 +/- 8.93
Draw rate (equal opponents) = 19.37 % +/- 1.15

ランダムを加えた場合は、R-9.7と、誤差の範囲に収まっている。

エンジン間の勝率は以下の通りである。

master vs random_cutoff15: 196-197-98 (49.9%)
Black vs White: 212-181-98 (53.2%)
master playing Black: 121-106-19 (53.0%)
master playing White: 75-91-79 (46.7%)
random_cutoff15 playing Black: 91-75-79 (53.3%)
random_cutoff15 playing White: 106-121-19 (47.0%)

master vs suisho5-30th: 297-97-94 (70.5%)
Black vs White: 234-160-94 (57.6%)
master playing Black: 173-36-35 (78.1%)
master playing White: 124-61-59 (62.9%)
suisho5-30th playing Black: 61-124-59 (37.1%)
suisho5-30th playing White: 36-173-35 (21.9%)

random_cutoff15 vs suisho5-30th: 286-127-72 (66.4%)
Black vs White: 256-157-72 (60.2%)
random_cutoff15 playing Black: 167-38-38 (76.5%)
random_cutoff15 playing White: 119-89-34 (56.2%)
suisho5-30th playing Black: 89-119-34 (43.8%)
suisho5-30th playing White: 38-167-38 (23.5%)

dlshogi間はほぼ互角で、水匠5に対しては少しだけ勝率が落ちている。

16手までで重複した棋譜を調べると、
水匠5とランダムムーブなしの場合は、69.2%
水匠5とランダムムーブありの場合は、1.8%
dlshogi間では、38.1%
であった。

水匠5との対局では重複がほとんどなくなっている。

また、dlshogiのランダムムーブ同士で対局した場合、181局で重複は0だった。

温度10、価値閾値0.015、32手まで

32手までランダムムーブを行った場合の結果は以下の通り。

   # PLAYER                   :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 master                   :    59.6   18.4   356.0     573    62     100  310   92  171    16
   2 random_cutoff15_ply32    :    13.5   17.8   300.5     571    53     100  257   87  227    15
   3 suisho5-30th             :   -73.1   19.2   198.5     566    35     ---  157   83  326    15

White advantage = 39.69 +/- 11.37
Draw rate (equal opponents) = 16.10 % +/- 1.26

ランダムを加えた場合は、R-46.1となった。
手が進むほどランダムムーブの影響が大きくなると考えられる。

温度5、価値閾値0.015、16手まで

温度を5にした場合の結果は以下の通り。

   # PLAYER                   :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 random_cutoff15_temp5    :    46.1   31.1   119.5     203    59      51  103   33   67    16
   2 master                   :    45.2   30.4   120.5     205    59     100  103   35   67    17
   3 suisho5-30th             :   -91.3   32.4    64.0     200    32     ---   48   32  120    16

White advantage = 73.45 +/- 19.53
Draw rate (equal opponents) = 17.85 % +/- 2.27

ランダムを加えた場合は、R+0.9と、誤差の範囲になっている。

16手までで重複した棋譜を調べると、
水匠5とランダムムーブなしの場合は、44.6%
水匠5とランダムムーブありの場合は、0.0%
dlshogi間では、32.7%
であった。
温度10よりも重複が減っているのは、対局数が少ないことによる偶然と考えられる。

温度10から1度ずつ低下、価値閾値0.02、16手まで

温度10を徐々に低下させるパターンでも測定した。

   # PLAYER                          :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 master                          :    58.0   30.0   135.5     221    61      99  116   39   66    18
   2 random_cutoff20_temp10_drop1    :    -7.2   30.2   105.5     218    48      95   91   29   98    13
   3 suisho5-30th                    :   -50.8   29.0    86.0     215    40     ---   74   24  117    11

White advantage = 97.37 +/- 19.02
Draw rate (equal opponents) = 15.08 % +/- 2.01

ランダムを加えた場合は、R-65.2となった。
温度の影響より、価値の閾値の影響が大きいようだ。

まとめ

価値の閾値を0.015(1.5%)、温度10度として、16手までランダムムーブを行うことで、勝率を低下させることなく、相手が水匠5またはランダムムーブのdlshogiの場合、重複をほぼなくせることが分かった。

戦型は、角換わり以外も含まれるようになった。
ただし、振り飛車は含まれないため、様々な戦型での勝率の確認には互角局面集が有効だと思う。

ビルド済みバイナリ

https://gist.github.com/TadaoYamaoka/519f7b63c77cdb89f43fb81ab9641213/raw/71f5b8c9852c7c0ecdcc615e9341376778eece2d/dlshogi-ramdom_move.zip

USIオプションRandom_Plyにランダムムーブを行う手数を設定するとランダムムーブが有効になる(16が推奨値)。
Random_Cutoffには、価値の閾値を千分率で設定する(デフォルト15(1.5%))。
Random_Temperatureには、温度を千分率で設定する(デフォルト10000)。
Random_Temperature_Dropには、温度の一手ごとの低下量を千分率で設定する(デフォルト1000)。

2022/1/2 追記

Random_Temperature_Drop=1.0とRandom_Temperature_Drop=0.0で、勝率がどれくらい変わるか比較した。

A100x1GPU、3スレッドで測定。持ち時間5分、1手2秒加算。

   # PLAYER          :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 master          :    74.2   14.7   707.5    1090    65     100  596  223  271    20
   2 drop1           :    19.3   21.7   284.0     535    53      93  232  104  199    19
   3 drop0           :    -8.9   21.3   272.0     551    49     100  220  104  227    19
   4 suisho5-16th    :   -84.6   16.1   363.5    1078    34     ---  286  155  637    14

White advantage = 72.77 +/- 8.14
Draw rate (equal opponents) = 19.60 % +/- 1.04

上記の2GPUで測定した場合は、温度10、価値閾値0.015、16手まででR-9.7だったが、今回の測定(drop0)では、R-83.1(勝率38.26%)になった。
1手ずつ温度を1度下げた場合(drop1)は、R-54.9(勝率42.16%)になった。

前回測定よりもRが低下しているのは、今回は1GPUでの測定のため、探索ノード数が少なくなったことが関係していそうである。
短い持ち時間ではランダムの影響が大きくなるのではないかと考える。

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

drop0 vs master: 85-125-69 (42.8%)
Black vs White: 125-85-69 (57.2%)
drop0 playing Black: 47-47-45 (50.0%)
drop0 playing White: 38-78-24 (35.7%)
master playing Black: 78-38-24 (64.3%)
master playing White: 47-47-45 (50.0%)

master vs suisho5-16th: 172-56-45 (71.2%)
Black vs White: 131-97-45 (56.2%)
master playing Black: 97-22-18 (77.4%)
master playing White: 75-34-27 (65.1%)
suisho5-16th playing Black: 34-75-27 (34.9%)
suisho5-16th playing White: 22-97-18 (22.6%)

drop0 vs suisho5-16th: 135-102-35 (56.1%)
Black vs White: 155-82-35 (63.4%)
drop0 playing Black: 86-33-17 (69.5%)
drop0 playing White: 49-69-18 (42.6%)
suisho5-16th playing Black: 69-49-18 (57.4%)
suisho5-16th playing White: 33-86-17 (30.5%)
drop1 vs master: 74-127-69 (40.2%)
Black vs White: 125-76-69 (59.1%)
drop1 playing Black: 40-42-52 (49.3%)
drop1 playing White: 34-85-17 (31.2%)
master playing Black: 85-34-17 (68.8%)
master playing White: 42-40-52 (50.7%)

master vs suisho5-16th: 172-56-40 (71.6%)
Black vs White: 140-88-40 (59.7%)
master playing Black: 101-17-16 (81.3%)
master playing White: 71-39-24 (61.9%)
suisho5-16th playing Black: 39-71-24 (38.1%)
suisho5-16th playing White: 17-101-16 (18.7%)

drop1 vs suisho5-16th: 158-72-35 (66.2%)
Black vs White: 143-87-35 (60.6%)
drop1 playing Black: 93-22-18 (76.7%)
drop1 playing White: 65-50-17 (55.7%)
suisho5-16th playing Black: 50-65-17 (44.3%)
suisho5-16th playing White: 22-93-18 (23.3%)

16手目での棋譜の重複率は、

vs master vs suisho5
drop0 40.5% 18.9%
drop1 42.2% 7.9%

であった。
dlshogiのmasterに対しては、想定通り、温度低下あり(drop1)の方が、重複が多くなった。
温度低下あり(dop1)の方が、水匠5に対しては重複が少なくなるという想定と異なる結果になった。
たまたま水匠5の手がばらけやすい手を選択していたのかもしれない。

2021/1/4 追記

Random_Temperature=5.0とRandom_Temperature_Drop=0.5で測定した。

A100x1GPU、3スレッドで測定。持ち時間5分、1手2秒加算。

   # PLAYER                :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 master                :    57.0   17.3   372.0     611    61     100  314  116  181    19
   2 random_temp5drop05    :    -8.0   17.7   294.0     607    48     100  242  104  261    17
   3 suisho5-28th          :   -48.9   17.7   246.0     606    41     ---  199   94  313    16

White advantage = 111.20 +/- 11.09
Draw rate (equal opponents) = 18.73 % +/- 1.41

R-65となった。
Random_Temperature=10.0とRandom_Temperature_Drop=1.0よりも、レーティングが低下した。
よりランダム性は低くなっているのに、低下したのは測定結果のブレが大きいためと思われる。

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

master vs random_temp5drop05: 144-99-63 (57.4%)
Black vs White: 158-85-63 (61.9%)
master playing Black: 94-35-24 (69.3%)
master playing White: 50-64-39 (45.4%)
random_temp5drop05 playing Black: 64-50-39 (54.6%)
random_temp5drop05 playing White: 35-94-24 (30.7%)

master vs suisho5-28th: 170-82-53 (64.4%)
Black vs White: 174-78-53 (65.7%)
master playing Black: 112-20-21 (80.1%)
master playing White: 58-62-32 (48.7%)
suisho5-28th playing Black: 62-58-32 (51.3%)
suisho5-28th playing White: 20-112-21 (19.9%)

random_temp5drop05 vs suisho5-28th: 144-117-41 (54.5%)
Black vs White: 181-80-41 (66.7%)
random_temp5drop05 playing Black: 99-35-18 (71.1%)
random_temp5drop05 playing White: 45-82-23 (37.7%)
suisho5-28th playing Black: 82-45-23 (62.3%)
suisho5-28th playing White: 35-99-18 (28.9%)